ブール代数

ディジタル回路
2. ブール代数と論理ゲート
五島正裕
DATE :
ディジタル回路
今日の内容
1. 本論
1. 論理ゲート
2. ブール代数
3. 論理関数
4. 論理関数の完全性
「すべての論理回路は，AND，OR，NOT の組み合わせでできる」
2. 今日のまとめ
2
ディジタル回路
論理ゲート
3
ディジタル回路
論理ゲート
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
ディジタル回路
ディジタル回路
余談 1/2
 MIL 記号
 MIL : 米国軍用規格（Military Standard）
 JIS の論理記号もある（が，誰も使わない）
7
ディジタル回路
余談 2/2
 OR と XOR
 OR :
 XOR :
（包含的）論理和 (inclusive-OR)
排他的論理和 (exclusive-OR)
 日常の「または」は，どっち？
 1年以下の懲役または 100万円以下の罰金
 x = 0, 1
 英語の A and/or B
8
ディジタル回路
組み合わせ回路 (Combinational Circuit)
a
b
c
d
z
z = a∙b + c∙d
9
ディジタル回路
ブール代数
10
ディジタル回路
ブール代数
 ブール代数 (Boolean Algebra)
 George Bool
 論理計算のために考案
 Claude Shannon
 論理回路に応用
11
ディジタル回路
ブール代数の公理
 交換則
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)
 単位元 1 が存在する
 ∀x, x∙1 = x
 零元 0 が存在する
 ∀x, x + 0 = x
 補元 x’ が存在する
 ∀x, x∙x’ = 0
 ∀x, x + x’ = 1
ディジタル回路
ブール代数の例 ― 論理演算
 論理演算
 単位元： 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
14
ディジタル回路
ブール代数の定理
 吸収則１
 x ∙ (x + y) = x
 対合則
 (x’)’ = x
 べき等則
x ∙ x = x
x + x = 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)
 ブール代数の公理は「ペア」
 “∙” (AND) ⇔ “＋” (OR)， “0” ⇔ “1” を入れ替えると入れ替わる
 分配則：“＋” も分配する
 x ∙ (y + z) = (x ∙ y) + (x ∙ z)
 x + (y ∙ z) = (x + y) ∙ (x + z)
 双対とは，いわば，「対等」
17
ディジタル回路
論理関数
18
ディジタル回路
論理関数
 f : (i1, i2, …, in) → o (i1, i2, …, in, o : ブール変数）
 2入力論理関数：先ほどの AND，OR 等
 1入力論理関数：NOT ，BUF 等
 真理値表 (truth table)
o
0 0 … 0
0/1
0 0 … 1
0/1
1 1 … 1
…
…
…
…
…
 関数の定義
i1 i2 … in
0/1
19
ディジタル回路
表による定義
式
普通の
関数
f(x) = x
表
定義
x
f(x)
0
0
1
1
f(x) = x
定義
…
…
論理
関数
定義ではない
x
f(x)
0
0
1
1
定義
20
ディジタル回路
n入力論理関数の数
n
 n入力の論理関数は 2 とおり
2
n
 入力は 2 とおり
 そのそれぞれに，0 または 1 を指定できる
o
0 0 … 0
0/1
0 0 … 1
0/1
1 1 … 1
…
…
…
…
…
2
n
i1 i2 … in
0/1
21
ディジタル回路
すべての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
ディジタル回路
完全性
24
ディジタル回路
完全性（Completeness，完備性）
 完全集合 (Complete Set)
 論理関数の集合で，
その要素の組み合わせによって，すべての論理関数を表現できる
 完全集合の例
 {AND, OR, NOT}
 {AND, NOT}
 {OR, NOT}
 {NAND}
 {NOR}
25
ディジタル回路
完全性の証明 {AND, OR, NOT}
 数学的帰納法：
1. 1入力の論理関数は {AND, OR, NOT} の組合せで表現できる
2.
n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して，
(n + 1) 入力の関数が表現できることをいう
26
ディジタル回路
完全性の証明 {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
27
ディジタル回路
すべての1，2入力論理関数
i1
o0 o1 o2 o3
0
0
0
1
1
1
0
1
0
1
すべての1入力論理関数
すべての2入力論理関数
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
1
ディジタル回路
完全性の証明 {AND, OR, NOT}
1. 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので，
2 入力の関数が表現できることをいう
f = i’2∙ f10 + i2 ∙ f11
0
f10
i1
f11
1
i2 = 0
29
ディジタル回路
完全性の証明 {AND, OR, NOT}
1. 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので，
2 入力の関数が表現できることをいう
f = i’2∙ f10 + i2 ∙ f11
0
f10
i1
f11
1
i2 = 1
30
ディジタル回路
たとえば AND
i1
o0 o1 o2 o3
0
0
0
1
1
1
0
1
0
1
すべての1入力論理関数
すべての2入力論理関数
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
1
AND
ディジタル回路
たとえば AND
1. 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので，
2 入力の関数が表現できることをいう
f = i’2∙ f10 + i2 ∙ f11
0
f10
i1
f11
1
i2 = 0
32
ディジタル回路
たとえば AND
1. 1 入力の関数が {AND, OR, NOT} の組合せで表現できたので，
2 入力の関数が表現できることをいう
f = i’2∙ f10 + i2 ∙ f11
0f10
i1
f11
1
i2 = 1
33
ディジタル回路
完全性の証明 {AND, OR, NOT}
1. n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して，
(n + 1) 入力の関数が表現できることをいう
in+1 in … i2
0
0
…
0
1
1
0
…
0
0
0
…
0
1
…
…
…
1
…
1
1
fn0
fn1
…
…
1
in
…
…
…
…
…
1
i1
i2
…
0
o
…
…
…
1
0
…
0
i1
f = i’n+1∙ fn0 + in+1∙ fn1
in+1
34
ディジタル回路
LUT による完全性の証明 1/3
 LUT : Look-Up Table
 ハードウェアで，真理値表そのものを作る方法
n
 1-bit × 2 -word のメモリ
 FPGA (Field-Programmable Gate Array) で多用される
35
ディジタル回路
LUT による完全性の証明 2/3
i2i1i0 ：アドレス
i2 i1 i0 o
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
o
i0
i1
i2
ディジタル回路
LUT による完全性の証明 3/3
in in−1
…
i0 o
0
0
…
0
0
0
…
1
…
…
…
0
1
1
…
1
1
0
…
0
1
0
…
1
…
…
…
0
1
1
…
1
…
…
…
1
o
…
…
1
…
…
1
…
…
1
…
i1
…
in
in+1
ディジタル回路
完全性の証明一般の場合
 {AND, OR, NOT} が作れることを言う
 ex) {NAND}
AND
OR
NOT
38
ディジタル回路
今日のまとめ
42
ディジタル回路
ブール代数
 完全集合：
 すべての論理関数が作れる
 完全集合の例：
 {AND，OR，NOT}
 {NAND}
 完全集合をディジタル回路で作ればよい！
 実際は，{NAND，NOR，NOT, XOR (XNOR)}
43

Download Report