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

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

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

ブール代数（公理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)は双対の 関係にある

ブール代数（定理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・… 多変数のド・モルガンの定理

練習問題【定理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

練習問題【定理T3 (a)の証明】 A B C T3(a)の左辺 T3(a)の右辺 A + B A + C (A+B)(A+C) B・C 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 上記表より、すべてのA,B,Cの組み合わせにおいて、(A+B)(A+C)とA+BCが等しいことを確認した。よって、定理T3(a)は成り立つ。

ド・モルガンの定理 ( A ・ B ) = A + B

双対性 練習問題：次の論理関数の否定を計算せよ f( x, y, z ) = ( x + y )( x + z ) = ?

関数 f を否定すること ＝ 各変数 x, y, x, z を否定し， 双対性 練習問題：次の論理関数の否定を計算せよ f( x, y, z ) = ( x + y )( x + z ) = ( x + y ) + ( x + z ) = x ・ y + x ・ z ド・モルガン の定理 ド・モルガン の定理 関数 f を否定すること　＝　各変数 x, y, x, z を否定し， 論理積と論理和を入れ替える

双対性 T11 定数０，１を含む論理関数の恒等式は，０と１，＋と・を同時に入れ替えても成立する ０ ⇔ １ １ ⇔ ０ ＋ ⇔ ・ ０　⇔　１ １　⇔　０ ＋ ⇔　・ ・　⇔　＋

双対性 練習：次の恒等式に双対な恒等式を求めよ． （１）　( x + y ) y = x y （２）　x + y + x y = 1

標準形 以下の真理値表による論理関数 f を求める f ( A, B, C ) = ?? A B C f ( A, B, C ) 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 f ( A, B, C ) = ??

標準形（主加法標準形） 最小項（minimal term）： すべての変数が真または偽の形で含まれている論理積項（論理的な最小区分を表す） B ③ ABC ABC ① ⑦ ④ ⑧ ⑥ ⑤ ② A C

標準形（主加法標準形） fが１の行に着目 入力変数が0ならば否定，1ならばそのままにして最小項を取る すべての最小項の論理和を求める⇒ｆとなる A B C f ( A, B, C ) 最小項 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

標準形（主加法標準形） fが１の行に着目 入力変数が0ならば否定，1ならばそのままにして最小項を取る すべての最小項の論理和を求める⇒ｆとなる A B C f ( A, B, C ) 最小項 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 A = 0, B = 1, C = 1の時 ABC = 0・1・1 = 1

標準形（主加法標準形） f( A, B, C ) = ABC + ABC + ABC + ABC A B C f ( A, B, C ) 最小項 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 f( A, B, C ) = ABC + ABC + ABC + ABC

標準形（主乗法標準形） 最大項（maximal term）： すべての変数が真または偽の形で含まれている論理和項（論理的な最大区分を表す） B A+B+C A+B+C A C

標準形（主乗法標準形） fが0の行に着目 入力変数が0ならば否定，1ならばそのままにして最大項を取る すべての最大項の論理積を求める⇒ｆとなる A B C f ( A, B, C ) 最大項 0 0 0 1 0 0 1 A+B+C 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

標準形（主乗法標準形） fが0の行に着目 入力変数が0ならばそのまま，1ならば否定にして最小項を取る すべての最大項の論理積を求める⇒ｆとなる A B C f ( A, B, C ) 最大項 0 0 0 1 0 0 1 A+B+C 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 A=0, B=0, C=1の時 A+B+C = 0+0+1 = 0

標準形（主乗法標準形） f( A, B, C ) = ( A+B+C )( A+B+C )( A+B+C )( A+B+C ) A B C 最大項 0 0 0 1 0 0 1 A+B+C 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 f( A, B, C ) = ( A+B+C )( A+B+C )( A+B+C )( A+B+C )

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