Document

0
0
1
0
1
0
1
1
電子回路学
講義＃7:　ブール代数、ブール代数の公理、
ブール代数の法則、ド・モルガンの定理、
シャノン展開
1
0
0
1
0
1
0
1
1
n 
n 
ブール(Boole）
Boole氏は、イギリスに生まれ、独学で数学者になり、
論理を記号で表す方法（symbolic logic）を研究した一
人
彼の記号法は、その後色々な学者により展開され、
ディジタル回路などの分野に応用されるようになりま
した
George Boole (1815〜1864)
2
0
0
1
0
1
0
1
1
n 
n 
ブル代数と論理回路
ブール氏の記号法から発展した代数を回路の記述に結
び付いた人は、情報の父と呼ぶShannon（シャノン）
氏でした
Shannon氏が当時勤めた電話会社（Bell）のリレー技術
を用いた電話交換機の回路の記述への適応を閃きまし
た
Claude Elwood Shannon (1916-2001)
3
0
0
1
0
1
0
1
1
n 
回路の論理式
回路の論理式の展開や簡単化、演算などをブール代数
で体系化されています
w
z
F
F=w・z
4
ブール代数の公理：I
0
0
1
0
1
0
1
1
n 
変数の値は1か0の何れか一つです
x=0
x=1
5
ブール代数の公理：II
0
0
1
0
1
0
1
1
n 
0の補数は1、1の補数は0です
0
1
補数
x
x
1
0
補数
y
y
6
ブール代数の公理：III
0
0
1
0
1
0
1
1
論理積：0・1 = 1・0 = 0・0 = 0
1・1 = 1　と成り立ちます
n 
1
0
0
1
1
1
0
等価
等価
0
0
1
7
ブール代数の公理：IV
0
0
1
0
1
0
1
1
論理和：1 + 0 = 0 + 1 = 1 + 1 = 1
0＋0 = 0　と成り立ちます
n 
1
0
0
0
0
1
等価
1
等価
1
1
0
8
ブール代数の基本演算：I
0
0
1
0
1
0
1
1
n 
直列のスイッチング回路の真理値表は、ブール代数で
はAND（論理積）という基本演算の真理値表に等しい
x
y
F
ANDのスイッチング回路
xy
00
01
10
11
F
0
0
0
1
ANDの真理値表
x
y
F
ANDの記号
9
ブール代数の基本演算：II
0
0
1
0
1
0
1
1
n 
一方、並列のスイッチング回路の真理値表は、ブール
代数ではOR（論理和）というもう一つの基本演算に
対応します
x
y
F
ORのスイッチング回路
xy
00
01
10
11
F
0
1
1
1
ORの真理値表
x
y
F
ORの記号
10
ブール代数の交換則
0
0
1
0
1
0
1
1
n 
AND、OR、若しくはNOTの演算を含む式では項の順
序は重要ではありません
交換則：
論理和の場合は：　論理積の場合は：
x + y = y + x　x・y = y・x
11
0
0
1
0
1
0
1
1
n 
ブール代数の結合則
式の変数は通常の代数の変数のように組み合わせるこ
とができます
結合則：
論理和の式の場合は：
(x + y) + z = x + (y + z)
論理積の式の場合は：
(x・y)・z = x・(y・z)
12
0
0
1
0
1
0
1
1
n 
ブール代数の分配則
混合演算の場合は、論理積および論理和が通常の代数
と同様に扱えます
分配則：
論理積を施して式を展開する例：
x・(y + z) = (x・y) + (x・ z)
論理和を施して式を展開する例：
x + (y・z) = (x + y)・(x + z)
13
0
0
1
0
1
0
1
1
n 
n 
n 
ブール代数の定理
公理や基本規則に基づいて数多くの有効な定理を導く
ことができます
その中から最も有名かつよく使用されるのはド・モル
ガン（DeMorgan）の定理（法則）とShannon展開の定
理です
ド・モルガンの定理は、ANDゲートで構成されている
回路をNORゲートに変換するとき、もしくはその逆、
すなわちORゲートで構成されている回路をNANDゲー
トの変換に使います
14
ド・モルガンの定理
0
0
1
0
1
0
1
1
n 
n 
論理和の否定は、否定した項の論理積に等しい
論理積の否定は、否定した項の論理和に等しい
x y x+y x+y
00 0
1
01 1
0
10 1
0
11 1
0
x + y = x・y
x・y = x + y
x y x・y
11 1
10 0
01 0
00 0
等しい
15
DeMorgan定理の応用例
0
0
1
x
y
F
↓
F
x
y
F
x
y
F
NOR
F
x
y
AND
x
y
AND
OR
F
NOR
NAND
↓
x
y
NAND
ゲート変換（置き換えの応用）
OR
0
n 
↓
1
1
↓
1
0
16
0
0
1
0
1
0
1
1
n 
DeMorgan定理の一般化
DeMorganの定理をn個（任意の数）の変数や項の式に
次のように一般化できます
(x1+x2+…+xn) = x1x2…xn
(x1・x2・…・xn) = x1 + x2+…+xn
17
論理関数の標準形
0
0
1
0
1
0
1
1
n 
論理関数の式の各項に全ての変数が出現すると、その
式を論理関数の標準形といいます
F(x,y) = x + xy
×
F(x,y) = xy + xy
◎
標準形
18
0
0
1
0
1
0
1
1
n 
n 
Shannonの展開定理
特定の変数を中心にして論理関数の式を展開するため
に使用される定理です
標準形ではない関数を標準形に変えるには使います
f(x1, x2,…,xi,…, xn) = xif(x1 ,…,1, … , xn ) + xif(x1 ,…,0, … , xn )
19
0
0
1
0
1
0
1
1
n 
Shannon展開の応用例
標準形への変換の例
F = x + xy
= y ⋅ F(y = 1) + y ⋅ F(y = 0)
= y ⋅ (x + x1) + y ⋅ (x + x 0)
= y ⋅ (x + x ) + y ⋅ (x + 0)
= (y ⋅ x + y ⋅ x ) + (y ⋅ x + y ⋅ 0)
= y ⋅ x + y ⋅ x + y ⋅ x + 0
= yx + yx + yx
20
0
0
1
0
1
0
1
1
n 
Shannonの定理の応用
式展開への応用
f(x1,x2,x3,x4,x5,x6) = x1x2x3 + x1x2x4 + x2x4x5 + x1x5x6
x2を着目して、論理関数ｆを展開してみると、
f = x2(x11x3+x11x4+1x4x5+x1x5x6)+x2(x10x3+x10x4+0x4x5+x1x5x6)
に展開でき、
f = x2(x10x3+x11x4+0x4x5+x1x5x6)+x2(x11x3+x10x4+1x4x5+x1x5x6)
f = x2(x1x4+x1x5x6)+x2(x1x3+x4x5+x1x5x6)
となります
21
0
0
1
0
1
0
1
1
n 
役立つ定理
次の定理は式（回路）の簡単化によく用いられます
xi + f(x1, x2,…,xi,…, xn) = xi + f(x1 ,…,0, … , xn )
22
応用例
0
0
1
0
1
0
1
1
n 
式の簡単化
x1+x2(x3x4 + x1x5 + x1x3)
のx1をxiにし、x2(x3x4 + x1x5 + x1x3)をf(x1,x2,x3,x4,x5) に対応
させ、前記の定理を用いてみると、
x1+x2(x3x4 + x1x5 + x1x3) = x1+x2(x3x4 + 0x5 + 0x3)
= x1+x2(x3x4 + 1x5 + 0x3)
= x1+x2(x3x4 + x5)
に簡単化できます
23
0
0
1
0
1
0
1
1
n 
ブル代数の双対性
等式関係にある式のそれぞれの定数1、0を0、1に、演
算記号+、・を・、+に置き換えても等式関係が保たれ
ます
つまり、
f1(x1, x2,…, xn,1,0,+,・) = f2(x1 ,x2, … , xn ,1,0,+,・)
が成り立っていれば、
f1(x1, x2,…, xn,0,1,・,+) = f2(x1 ,x2, … , xn ,0,1,・,+)
も成り立ちます
24
双対性の応用
0
0
1
0
1
0
1
1
n 
等式関係の式や定理に用いると、
一般等式も、
A + AB = A + B　→　A・(A+B) = A・B
前述の定理も、
xi + f(x1, x2,…,xi,…, xn) = xi + f(x1 ,…,0, … , xn )
次のように使用できます
xi・f(x1, x2,…,xi,…, xn) = xi・f(x1 ,…,1, … , xn )
25
その他の重要な性質
0
0
1
0
1
0
1
1
n 
同一則：
n 
n 
吸収則：
n 
n 
x+x+…+x=x（双対：x・x・…・x = x）
1 + y = 1　（双対：0・y = 0）
否定に関する性質
n 
n 
z + z = 1 （双対：z・z = 0）
w=w
26
0
0
1
0
1
0
1
1
n 
n 
標準形への変換
否定に関する性質を用いることができる
例：
= AB + A
= AB + A(1)
= AB + A(B + B)
= AB + AB + AB
27
0
0
1
0
1
0
1
1
n 
n 
標準形への変換
否定に関する性質を用いることができる
例：
= xz + y
= x(y + y )z + (x + x )y(z + z )
= xyz + xyz + (xy + xy)(z + z )
= xyz + xyz + (xy + xy)z + (xy + xy)z
= xyz + xyz + xyz + xyz + xyz + xyz
= xyz + xyz + xyz + xyz + xyz
28

Download Report