論理回路 第４回 http://www.fit.ac.jp/~matsuki/LCA.html

今日の内容 前回の課題の解説 ブール代数 公理(P1 – P5) 定理(T1 – T5) 定理(T6 – T10)

基本論理演算（論理積：AND） A f B f = A・B AかつB（A and B）と読む A B f 1 真理値表 回路図 1 A f B ブール代数（代数式） f = A・B AかつB（A and B）と読む

基本論理演算（論理和：OR） A f B f = A+B AまたはB（A or B）と読む 真理値表 A B f 1 真理値表 回路図 1 A f B ブール代数（代数式） f = A+B AまたはB（A or B）と読む

基本論理演算（否定：NOT） 真理値表 真理値表 回路図 A f 1 A f ブール代数（代数式） f = A Aでない（not A）と読む

ブール代数（Boolean algebra） 論理演算を表す代数式 f = A・B f = A + B f = A

ブール代数 公理： ２つの定数０と１に関する論理積，論理和，否定などの演算の基礎法則 公理： 　２つの定数０と１に関する論理積，論理和，否定などの演算の基礎法則 定理： 　公理をもとに導かれる法則（公理を使って証明する必要がある）

ブール代数（公理P1～P5） P1 (a): もしA≠0ならば，A=1 (b): もしA≠1ならば，A=0 P2 (a):　0・0=0 (b):　1+1=1 P3 (a):　1・1=1 (b):　0+0=0 P4 (a):　0・1=0・1=0 (b):　1+0=0+1=1 P5 (a):　1=0 (b):　0=1 (a)と(b)は双対の 関係にある

ブール代数（公理P2） P2の場合 (a) 0・0 = 0 (b) 1+1 = 1 1 1 1 AND OR

ブール代数（公理P3） P3の場合 (a) 1・1 = 1 (b) 0+0 = 0 1 1 1 AND OR

ブール代数（公理P4） P4の場合 (a) 0・1 = 0 (b) 1+0 = 1 1 1 1 AND OR

ブール代数（公理P5） P2の場合 (a) 1 = 0 (b) 0 = 1 1 1 NOT

ブール代数（定理T1～T5） T1 (a): A・B = B・A (b): A + B = B + A 交換律 T2 (a):　(AB)C = A(BC) (b):　(A + B) + C = A + (B + C) T3 (a):　(A + B)(A + C) = A + BC (b):　AB + AC = A(B + C) T4 (a):　A・0 = 0 (b):　A + 1 = 1 T5 (a):　A・1 = A (b):　A + 0 = A 交換律 結合律 分配律 (a)と(b)は双対の 関係にある

ブール代数（定理T6～T10） T6 (a): A・A = 0 (b): A + A = 1 補元律 T7 (a):　A・A = A (b):　A + A = A T8 (a):　A(A + B) = A (b):　A + AB = A T9 :　(A) = A T10 (a):　(A・B) = A + B (b):　(A + B) = A・B 補元律 べき等律 吸収律 二重否定 ド・モルガンの定理

ブール代数（定理T10’） T10’ (a):　(A・B・C・…) = A + B + C + … (b):　(A + B + C + …) = A・B・C・… 多変数のド・モルガンの定理

ブール代数（定理T1） T1 (a): A・B = B・A (b): A + B = B + A 交換律 A A A・B A + B B B

ブール代数（定理T2） T2 (a): (AB)C = A(BC) (b): (A + B) + C = A + (B + C) 結合律

ブール代数（定理T3） T3 (a): (A + B)(A + C) = A + BC (b): AB + AC = A(B + C) 分配律 B A (A + B)(A + C) C A + BC C A B

ブール代数（定理T4） T4 (a):　A・0 = 0 (b):　A + 1 = 1 A A 1 1

ブール代数（定理T5） T5 (a):　A・1 = A (b):　A + 0 = A A A A A 1

練習問題【定理T4 (a)の証明】 問) A・0 = 0が成り立つことを証明しなさい。 解）　公理P1により、Aが0のときと1のとき、T4(a)が成立することを証明すれば良い。 A = 0のとき A・0 = 0・0 = 0　[公理P2(a)] (2) A = 1のとき A・0 = 1・0 = 0 [公理P4(a)] よって、T4(a)は成立する。

問題【定理T5 (a)の証明】 問) A・1 = Aが成り立つことを証明しなさい。 解）　公理P1により、Aが0のときと1のとき、T4(a)が成立することを証明すれば良い。 A = 0のとき A・1 = 0・1 = 0 = A　[公理P4(a)] (2) A = 1のとき A・1 = 1・1 = 1 = A [公理P3(a)] よって、T5(a)は成立する。

練習問題【定理T3 (a)の証明】 問) 定理T3(a)が成り立つことを真理値表を用いて証明しなさい。 解） 変数A,B,Cによる真理値すべての組み合わせで、T3(a)の左辺と右辺が同じであることを示せば良い。 A B C T3(a)の左辺 T3(a)の右辺 A + B A + C (A+B)(A+C) B・C A + BC 0 0 0 0 0 1 1 … 1 1 1 上記表より、すべてのA,B,Cの組み合わせにおいて、(A+B)(A+C)とA+BCが等しいことを確認した。よって、定理T3(a)は成り立つ。

注意事項 講義に関する質問・課題提出など： メールについて 2009lcx@gmail.com 本文にも短いカバーレター（説明）をつける 件名は，学籍番号＋半角スペース＋氏名 （例）S09F2099 　松木裕二 本文にも短いカバーレター（説明）をつける 課題はWordなどで作り，添付ファイルとして送る