a` z

ディジタル回路
2. ブール代数 と 論理ゲート
五島 正裕
ディジタル回路
今日の目標
 すべての論理回路は,AND,OR,NOT の組み合わせでできる.
ディジタル回路
今日の内容
1. 本論
1. 論理ゲート
2. ブール代数
3. 論理関数
4. 論理関数の完全性
「すべての論理回路は,AND,OR,NOT の組み合わせでできる」
2. 今日のまとめ
ディジタル回路
ブール代数と 論理ゲート
ディジタル回路
論理ゲート
AND
(論理積)
MIL記号
MIL symbol
a
b
a
z
b
論理式
logic expression
真理値表
truth table
z = a∙b
NOT
(論理否定)
OR
(論理和)
z a
z=a+b
a
b
z
a
b
z
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
1
z
z = a’
z=a
z=¬a
a
z
0
1
1
0
ディジタル回路
論理ゲート
NAND
MIL記号
MIL symbol
論理式
logic expression
真理値表
truth table
a
b
buffer?
NOR
a
z
b
z = (a∙b)’
z a
z = (a + b)’
z
z=a
a
b
z
a
b
z
0
0
1
0
0
1
a
z
0
1
1
0
1
0
0
0
1
0
1
1
0
0
1
1
1
1
0
1
1
0
ディジタル回路
論理ゲート
XOR (EOR)
(排他的論理和)
MIL記号
MIL symbol
論理式
logic expression
真理値表
truth table
a
b
XNOR (EQ)
a
z
b
b
z=a
z
b
z=a
a
b
z
a
b
z
0
0
0
0
0
1
0
1
1
0
1
0
1
0
1
1
0
0
1
1
0
1
1
1
ディジタル回路
余談
 MIL 記号
 MIL : 米国軍用規格(Military Standard)
 JIS の論理記号もある(が,誰も使わない)
 OR と XOR
 OR :
(包含的)論理和 (inclusive-OR)
 XOR :
排他的 論理和 (exclusive-OR)
 日常の「または」は,どっち?

1年以下の懲役 または 100万円以下の罰金

x = 0, 1
ディジタル回路
組み合わせ回路 (Combinational Circuit)
a
b
c
d
z
z = a∙b + c∙d
ディジタル回路
ブール代数
ディジタル回路
ブール代数
 ブール代数 (Boolean Algebra)
 George Bool

論理計算のために考案
 Claude Shannon

論理回路に応用
ディジタル回路
ブール代数の公理
 交換則
 x∙y = y∙x
x+y=y+x
 結合則
 (x∙y)∙z = x∙(y∙z)
 単位元 1 が存在する
 ∀x, x∙1 = x
 零元 0 が存在する
 ∀x, x + 0 = x
 (x + y) + z = x + (y + z)
 補元 x’ が存在する
 分配則
 x∙(y + z) = x∙y + x∙z
 x + y∙z = (x + y)∙(x + z)
 ∀x, x∙x’ = 0
 ∀x, x + x’ = 1
ディジタル回路
ブール代数の例 ― べき集合上の集合演算
 集合 U の べき集合上の集合演算
 U = { 1, 2, 3 } の べき集合は

{ {}, {1}, {2}, {3}, {1,2}, {2,3}, {3,1}, {1,2,3} }
 単位元:U = {1,2,3}
{1,2}∙{1, 2, 3} = {1, 2}
零
{1,2} + {} = {1,2}
元:空集合 {}
 集合積:{1,2} ∙ {2,3} = {2}
 集合和:{1,2} + {2,3} = {1,2,3}
 補集合:{1,2}’ = {3}
ディジタル回路
ブール代数の例 ― 論理演算
 論理演算
 単位元: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
ディジタル回路
ブール代数の定理
 吸収則1
 x∙(x + y) = x
 x + x∙y = x
 対合則
 (x’)’ = x
 吸収則2
 x∙(x’ + y) = x∙y
 べき等律
 x + (x’∙y) = x + y
 x∙x = x
x+x=x
 ド・モルガンの定理
 (x∙y)’ = x’ + y’
 (x + y)’ = (x’)∙(y’)
ディジタル回路
ド・モルガンの法則
 (x∙y)’ = x’ + y’
 (x + y)’ = (x’)∙(y’)
ベン図
ディジタル回路
双対性 (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 : ブール変数)
 2入力論理関数:先ほどの AND,OR 等
 1入力論理関数:NOT ,BUF 等
n
 n入力の論理関数は 2 とおり
2
 入力は 2 とおり
n
 そのそれぞれに,0 または 1 を指定できる
n
o
0 0 … 0
0/1
0 0 … 1
0/1
1 1 … 1
…
…
…
…
…
2
i1 i2 … in
0/1
ディジタル回路
すべての1,2入力論理関数
1
2 =2
i1
o0 o1 o2 o3
0
0
0
1
1
1
0
1
0
1
すべての1入力論理関数
すべての2入力論理関数
1
22 = 4
i2
i1
o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
2
2 =4
1
22
2 = 16
ディジタル回路
すべての1,2入力論理関数
1
2 =2
i1
o0 o1 o2 o3
0
0
0
1
1
1
0
1
0
1
すべての1入力論理関数
すべての2入力論理関数
1
22 = 4
i2
XOR NOR
i1
o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
2
2 =4
1
AND
OR XNOR
NAND
ディジタル回路
完全性
ディジタル回路
完全性(Completeness,完備性)
 完全集合 (Complete Set)
 論理関数の集合で,
 その要素の組み合わせによって,すべての論理関数を表現できる
 完全集合の例
 {AND, OR, NOT}
 {AND, NOT}
 {OR, NOT}
 {NAND}
 {NOR}
ディジタル回路
完全性の証明 {AND, OR, NOT}
 数学的帰納法:
1. 1入力の論理関数は {AND, OR, NOT} の組合せで表現できる
1.
n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して,
(n + 1) 入力の関数が表現できることをいう
ディジタル回路
完全性の証明 {AND, OR, NOT}
1. 1入力の論理関数はすべて,{AND, OR, NOT} の組合せで表現できる.
o0 = 0
0
i1
o0 o1 o2 o3
0
0
0
1
1
1
0
1
0
1
o1 = i1
o2 = i’1
o3 = 1
1
ディジタル回路
すべての1,2入力論理関数
1
2 =2
i1
o0 o1 o2 o3
0
0
0
1
1
1
0
1
0
1
すべての1入力論理関数
21
すべての2入力論理関数
2 =4
i2
i1
o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
2
2 =4
1
22
2 = 16
ディジタル回路
完全性の証明 {AND, OR, NOT}
1. 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので,
2 入力の関数が表現できることをいう
f = i’2∙ f10 + i2∙ f11
0
i1
f10
i1
f11
1
i2 = 0
ディジタル回路
完全性の証明 {AND, OR, NOT}
1. 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので,
2 入力の関数が表現できることをいう
f = i’2∙ f10 + i2∙ f11
0
i1
f10
i1
f11
1
i2 = 1
ディジタル回路
完全性の証明 {AND, OR, NOT}
1. n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して,
(n + 1) 入力の関数が表現できることをいう
in+1
i2
i1
0
…
0
0
0
…
0
1
…
1
1
0
…
0
0
0
…
0
1
…
…
…
1
…
1
1
…
…
…
f = i’n+1∙ fn0 + in+1∙ fn1
o
…
…
1
…
1
…
…
0
in
fn0
fn1
in+1
ディジタル回路
完全性の証明 一般の場合
 {AND, OR, NOT} が作れることを言う
 ex) {NAND}
AND
OR
NOT
ディジタル回路
ブール微分 の 例
f (a, b, c, d ) = a∙b + c∙d
= d’∙ f (a, b, c, 0)
+ d∙ f (a, b, c, 1)
= d’∙(a∙b + c∙0)
+ d∙(a∙b + c∙1)
= d’∙(a∙b + 0)
+ d∙(a∙b + c)
= d’∙(a∙b)
+ d∙(a∙b + c)
ディジタル回路
ブール微分
fn+1(i1, i2, … , in, in+1)
= i’n+1∙ fn0(i1, i2, … , in)
+ in+1∙ fn1(i1, i2, … , in)
= i’n+1∙ fn+1(i1, i2, … , in, 0)
+ in+1∙ fn+1(i1, i2, … , in, 1)
fn0(i1, i2, … , in) = fn+1(i1, i2, … , in, 0)
fn1(i1, i2, … , in) = fn+1(i1, i2, … , in, 1)
ディジタル回路
ブール微分の例
a
b
c
d
a∙b + c∙d
a
b
c
d
d’∙(a∙b) + d∙(a∙b + c)
ディジタル回路
今日のまとめ
ディジタル回路
ブール代数
 完全集合:
 すべての論理関数が作れる
 完全集合の例:
 {AND,OR,NOT}
 {NAND}
 完全集合をディジタル回路で作ればよい!
 普通は,{NAND,NOR,NOT}