2. 論理ゲート と ブール代数 五島 正裕

今日の内容 前回の復習 アナログとディジタル 本論 論理ゲート ブール代数 今日のまとめ

前回の復習

アナログ と ディジタル 情報処理の過程において， 媒体の持つ物理量 と それの表す値 との 写像の方式 アナログ：連続 連続的なデータ ⇔ 媒体の連続的な状態 ディジタル：離散 離散的なデータ ⇔ 媒体の離散的な状態

物理量 と 値 の 写像 閾値 値 値 3 2 1 O O 物理量 物理量 アナログ ディジタル

アナログ，ディジタル と 信号劣化 劣化がなければ（S/N 比∞）… アナログがよい アナログ： 情報量∞ ディジタル： 量子化誤差がある 8b（256階調）で 0.4%（≒ 人間の識別限界） ビット数を増やせば，誤差は減る

アナログ，ディジタル と 信号劣化 劣化があるので… ディジタルがよい アナログ： 決して元に戻らない ディジタル： 閾値未満のノイズなら，完全に元に戻る 2値なら，10～20％ くらいなら耐えられる ただし，それでも誤るとアナログより致命的になり得る

ディジタル の メリット（まとめ） 記録/伝送 ノイズによって誤りが発生しにくい コピーや経年によって情報が劣化しにくい 再現性が高い 処理 ディジタル式のコンピュータとの親和性が高い プログラミング可能 圧縮が容易 誤り訂正符号などによる誤り訂正が可能 …

ディジタル回路 と 論理回路 ディジタル回路 物理的 通常は，Low/High の2つの物理状態を扱う 通常は，電子回路で作る 論理回路 抽象的，モデル 真理値の 0/1，false/true を扱う ディジタル回路で作る

論理ゲート と ブール代数

今日の目標 すべての論理回路は，AND，OR，NOT の組み合わせでできる．

論理ゲート AND OR NOT （論理積） （論理和） （論理否定） z = a∙b z = a + b z = a z = ¬ a a MIL記号 MIL symbol a a z z a z b b 論理式 logic expression z = a∙b z = a + b z = a z = ¬ a a b z 1 a b z 1 a z 1 真理値表 truth table

論理ゲート NAND NOR buffer? z = a∙b z = a + b z = a a a z z a z b b MIL記号 MIL symbol a a z z a z b b 論理式 logic expression z = a∙b z = a + b z = a a b z 1 a b z 1 a z 1 真理値表 truth table

論理ゲート XOR (EOR) XNOR (EQ) （排他的論理和） z = a b z = a b a a z z b b MIL記号 MIL symbol a a z z b b 論理式 logic expression z = a b z = a b a b z 1 a b z 1 真理値表 truth table

余談 MIL 記号 MIL : 米国軍用規格（Military Standard） JIS の論理記号もある（が，誰も使わない） OR と XOR OR : （包含的）論理和 (inclusive-OR) XOR : 　排他的　論理和 (exclusive-OR) 日常の「または」は，どっち？ 1年以下の懲役 または 100万円以下の罰金 x = 0, 1

組み合わせ回路 (Combinational Circuit) z c d z = a∙b + c∙d

ブール代数

ブール代数 ブール代数 (Boolean Algebra) George Bool 論理計算のために考案 Claude Shannon 論理回路に応用

ブール代数の公理系 変数（ブール変数）の値 0 または 1 論理和 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 0, 1 + 1 = 1 論理積 0 ∙ 0 = 0, 0 ∙ 1 = 1, 1 ∙ 0 = 1, 1 ∙ 1 = 1

論理関数 f : (i1, i2, …, in) → o (i1, i2, …, in, o : ブール変数） 2入力論理関数：先ほどの AND，OR 等 1入力論理関数：NOT ，BUF 等 n入力の論理関数は 22n とおり 入力は 2n とおり そのそれぞれに，0 または 1 を指定できる i1 i2 … in o 0/1 1 2n

すべての1，2入力論理関数 すべての1入力論理関数 すべての2入力論理関数 21 = 2 221 = 4 22 = 4 222 = 16 i1 o0 o1 o2 o3 1 すべての1入力論理関数 21 = 2 221 = 4 すべての2入力論理関数 i2 i1 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15 1 22 = 4 222 = 16

ブール代数の定理 対合律 ¬(¬x) = x 補元律 x∙(¬x) = 0 x + (¬x) = 1 べき等律 x∙x = x, 交換律 x∙y = y∙x x + y = y + x 結合律 (x∙y)∙z = x∙(y∙z) (x + y) + z = x + (y + z) 分配律 x + y∙z = (x + y)∙(x + z) x∙(y + z) = x∙y + x∙z 吸収律 x∙(x + y) = x x + x∙y = x ド・モルガンの定理 ¬(x∙y) = ¬x + ¬y ¬(x + y) = (¬x)∙(¬y)

ド・モルガンの法則 ¬(x∙y) = ¬x + ¬y ¬(x + y) = (¬x)∙(¬y)

完全性（Completeness，完備性） 完全集合 (Complete Set) 論理関数の集合で， その要素の組み合わせによって，すべての論理関数を表現できる 完全集合の例 {AND, OR, NOT} {AND, NOT} {OR, NOT} {NAND} {NOR}

完全性の証明 {AND, OR, NOT} 数学的帰納法： 1入力の論理関数は {AND, OR, NOT} の組合せで表現できる n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して，(n + 1) 入力の関数が表現できることをいう

完全性の証明 {AND, OR, NOT} o0 = 0 o1 = i1 o2 = ¬i1 o3 = 1 1 1 o0 = 0 o1 = i1 o2 = ¬i1 o3 = 1 1

すべての1，2入力論理関数 すべての1入力論理関数 すべての2入力論理関数 21 = 2 221 = 4 22 = 4 222 = 16 i1 o0 o1 o2 o3 1 すべての1入力論理関数 21 = 2 221 = 4 すべての2入力論理関数 i2 i1 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15 1 22 = 4 222 = 16

完全性の証明 {AND, OR, NOT} f0 f1 i1 i1 1 i2 = 0 2 入力の関数が表現できることをいう f0 i1 f1 i1 1 i2 = 0

完全性の証明 {AND, OR, NOT} f0 f1 i1 i1 1 i2 = 1 2 入力の関数が表現できることをいう f0 i1 f1 i1 1 i2 = 1

完全性の証明 {AND, OR, NOT} f = ¬in+1∙f0 + in+1∙f1 f0 f1 n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して， (n + 1) 入力の関数が表現できることをいう in+1 in … i2 i1 o 1 f0 f = ¬in+1∙f0 + in+1∙f1 f1

完全性の証明 {AND, OR, NOT} f0 f1 i1 i2 in i1 i2 in in+1 n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して， (n + 1) 入力の関数が表現できることをいう i1 f0 i2 in i1 f1 i2 in in+1

完全性の証明 一般の場合 {AND, OR, NOT} が作れることを言う ex) {NAND} AND OR NOT

今日のまとめ

ブール代数 完全集合： すべての論理関数が作れる 完全集合の例： ｛AND，OR，NOT｝ ｛NAND} 完全集合をディジタル回路で作ればよい！ 普通は，｛NAND，NOR，NOT｝

来週以降の予定 11/ 3 文化の日 11/10 組み合わせ回路の最小化