ディジタル回路 2. ブール代数 と 論理ゲート 五島 正裕

今日の内容 本論 論理ゲート ブール代数 論理関数 論理関数の完全性 「すべての論理回路は，AND，OR，NOT の組み合わせでできる」 ディジタル回路 今日の内容 本論 論理ゲート ブール代数 論理関数 論理関数の完全性 「すべての論理回路は，AND，OR，NOT の組み合わせでできる」 今日のまとめ

ディジタル回路 論理ゲート

論理ゲート AND OR NOT （論理積） （論理和） （論理否定） z = a∙b z = a + b z = a’ z = a ディジタル回路 論理ゲート AND OR NOT （論理積） （論理和） （論理否定） 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 z = ¬ a 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 ディジタル回路

余談 1/2 MIL 記号 MIL : 米国軍用規格（Military Standard） JIS の論理記号もある（が，誰も使わない） ディジタル回路 余談 1/2 MIL 記号 MIL : 米国軍用規格（Military Standard） JIS の論理記号もある（が，誰も使わない）

余談 2/2 OR と XOR OR : （包含的）論理和 (inclusive-OR) ディジタル回路 余談 2/2 OR と XOR OR : （包含的）論理和 (inclusive-OR) XOR : 　排他的　論理和 (exclusive-OR) 日常の「または」は，どっち？ 1年以下の懲役 または 100万円以下の罰金 x = 0, 1 英語の A and/or B

組み合わせ回路 (Combinational Circuit) ディジタル回路 組み合わせ回路 (Combinational Circuit) a b z c d z = a∙b + c∙d

ディジタル回路 ブール代数

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

ブール代数の公理 交換則 単位元 1 が存在する x ∙ y = y ∙ x ∀x, x∙1 = x x + y = y + x ディジタル回路 ブール代数の公理 交換則 単位元 1 が存在する x ∙ y = y ∙ x ∀x, x∙1 = x x + y = y + x 零元 0 が存在する 結合則 ∀x, x + 0 = x (x ∙ y) ∙ z = x ∙ (y ∙ z) 補元 x’ が存在する (x + y) + z = x + (y + z) ∀x, x∙x’ = 0 分配則 ∀x, x + x’ = 1 x ∙ (y + z) = x ∙ y + x ∙ z x + y ∙ z = (x + y) ∙ (x + z)

ブール代数の例 ― 論理演算 論理演算 単位元 ： 1 零 元 ： 0 ディジタル回路 ブール代数の例 ― 論理演算 論理演算 単位元 ： 1 零　元 ： 0 論理積 ： 0・0 = 0, 0・1 = 0, 1・0 = 0, 1・1 = 1 論理和 ： 0＋0 = 0, 0＋1 = 1, 1＋0 = 1, 1＋1 = 1 補　元 ： 0’ = 1, 1’ = 0

ブール代数の定理 吸収則１ x ∙ (x + y) = x x + (x ∙ y) = x 対合則 吸収則２ (x’)’ = x べき等則 ディジタル回路 ブール代数の定理 対合則 (x’)’ = x べき等則 x ∙ x = x x + x = x 吸収則１ x ∙ (x + y) = x x + (x ∙ y) = x 吸収則２ x ∙ (x’ + y) = x ∙ y x + (x’ ∙ y) = x + y ド・モルガンの定理 (x∙y)’ = x’ + y’ (x + y)’ = (x’)∙(y’)

ド・モルガンの法則 (x∙y)’ = x’ + y’ (x + y)’ = (x’)∙(y’) ベン図 ディジタル回路

双対性 (Duality) ブール代数の公理は「ペア」 ディジタル回路 双対性 (Duality) ブール代数の公理は「ペア」 “∙” (AND) ⇔ “＋” (OR)， “0” ⇔ “1” を入れ替えると入れ替わる 分配則：“＋” も分配する x ∙ (y + z) = (x ∙ y) + (x ∙ z) x + (y ∙ z) = (x + y) ∙ (x + z) 双対とは，いわば，「対等」

ディジタル回路 論理関数

論理関数 f : (i1, i2, …, in) → o (i1, i2, …, in, o : ブール変数） ディジタル回路 論理関数 f : (i1, i2, …, in) → o (i1, i2, …, in, o : ブール変数） 2入力論理関数：先ほどの AND，OR 等 1入力論理関数：NOT ，BUF 等 真理値表 (truth table) 関数の定義 i1 i2 … in o 0/1 1

ディジタル回路 表による定義 式 表 普通の 関数 f(x) = x 定義 定義ではない x f(x) 1 … 論理

n入力論理関数の数 2n n入力の論理関数は 22n とおり 入力は 2n とおり そのそれぞれに，0 または 1 を指定できる i1 i2 ディジタル回路 n入力論理関数の数 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 ディジタル回路 すべての1，2入力論理関数 i1 o0 o1 o2 o3 1 すべての1入力論理関数 21 = 2 すべての2入力論理関数 221 = 4 i2 i1 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15 1 22 = 4 222 = 16

すべての1，2入力論理関数 すべての1入力論理関数 すべての2入力論理関数 21 = 2 221 = 4 XOR NOR 22 = 4 ディジタル回路 すべての1，2入力論理関数 i1 o0 o1 o2 o3 1 すべての1入力論理関数 21 = 2 すべての2入力論理関数 221 = 4 XOR NOR i2 i1 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15 1 22 = 4 AND OR XNOR NAND

ディジタル回路 完全性

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

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

完全性の証明 {AND, OR, NOT} o0 = 0 o1 = i1 o2 = i’1 o3 = 1 1 ディジタル回路 完全性の証明 {AND, OR, NOT} 1入力の論理関数はすべて，{AND, OR, NOT} の組合せで表現できる． i1 o0 o1 o2 o3 1 o0 = 0 o1 = i1 o2 = i’1 o3 = 1 1

すべての1，2入力論理関数 すべての1入力論理関数 すべての2入力論理関数 i1 o0 o1 o2 o3 1 i2 i1 o0 o1 o2 ディジタル回路 すべての1，2入力論理関数 i1 o0 o1 o2 o3 1 すべての1入力論理関数 すべての2入力論理関数 i2 i1 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15 1

完全性の証明 {AND, OR, NOT} f = i’2 ∙ f10 + i2 ∙ f11 f10 f11 ディジタル回路 完全性の証明 {AND, OR, NOT} 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので， 2 入力の関数が表現できることをいう f = i’2 ∙ f10 + i2 ∙ f11 f10 i1 f11 1 i2 = 0

完全性の証明 {AND, OR, NOT} f = i’2 ∙ f10 + i2 ∙ f11 f10 f11 ディジタル回路 完全性の証明 {AND, OR, NOT} 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので， 2 入力の関数が表現できることをいう f = i’2 ∙ f10 + i2 ∙ f11 f10 i1 f11 1 i2 = 1

たとえば AND すべての1入力論理関数 すべての2入力論理関数 AND i1 o0 o1 o2 o3 1 i2 i1 o0 o1 o2 ディジタル回路 たとえば AND i1 o0 o1 o2 o3 1 すべての1入力論理関数 すべての2入力論理関数 i2 i1 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15 1 AND

ディジタル回路 たとえば AND 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので， 2 入力の関数が表現できることをいう f = i’2 ∙ f10 + i2 ∙ f11 f10 i1 f11 1 i2 = 0

ディジタル回路 たとえば AND 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので， 2 入力の関数が表現できることをいう f = i’2 ∙ f10 + i2 ∙ f11 f10 i1 f11 1 i2 = 1

完全性の証明 {AND, OR, NOT} f = i’n+1∙ fn0 + in+1∙ fn1 fn0 fn1 ディジタル回路 完全性の証明 {AND, OR, NOT} n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して， (n + 1) 入力の関数が表現できることをいう f = i’n+1∙ fn0 + in+1∙ fn1 in+1 in … i2 i1 o 1 fn0 i1 … i2 … in fn1 … in+1

LUT による完全性の証明 1/3 LUT : Look-Up Table ハードウェアで，真理値表そのものを作る方法 ディジタル回路 LUT による完全性の証明 1/3 LUT : Look-Up Table ハードウェアで，真理値表そのものを作る方法 1-bit × 2n-word のメモリ FPGA (Field-Programmable Gate Array) で多用される

ディジタル回路 LUT による完全性の証明 2/3 i2i1i0 ： アドレス i2 i1 i0 o 1 o i0 i1 i2

ディジタル回路 LUT による完全性の証明 3/3 in in−1 … i0 o 1 … … o … … i1 … in in+1

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

ディジタル回路 今日のまとめ

ブール代数 完全集合： すべての論理関数が作れる 完全集合の例： {AND，OR，NOT} {NAND} ディジタル回路 ブール代数 完全集合： すべての論理関数が作れる 完全集合の例： {AND，OR，NOT} {NAND} 完全集合をディジタル回路で作ればよい！ 実際は，{NAND，NOR，NOT, XOR (XNOR)}