第3章ブール代数

第３章
ブール代数
論理式の表現を数学的に取り扱い
やすくするために代数学の助けを借
りる.
第３章の概要







公理
ブール代数としての論理関数
双対性
ブール代数の定理
集合論ーブール代数の例
簡単化の例
ｎ変数ブール代数と拡大ブール代数
ブール代数系

代数学
– 元の集合、演算子の組み、少数の公理系
– その上に定理を組み立てて行く。

ブール代数
– 有限集合 K
– 二つの演算＋、・を定義
– ６つの公理系
ブール代数の公理系






二つの演算
恒等元の存在
交換法則
分配法則
補元の存在
K の大きさ＞１
演算子の定義
(a) K は演算子＋に関して閉じている。
(b) K は演算子・に関して閉じている。
恒等元の存在
(a) K は演算子＋に関する恒等元をもつ。
(b) K は演算子・に関する恒等元をもつ。
交換法則
(a) 演算子＋は可換である.
(b) 演算子・は可換である.
分配法則
(a) 演算子＋は分配法則を満たす.
(b) 演算子･は分配法則を満たす.
補元の存在
にたいして
を満たす
が必ず存在する.
K の大きさ＞１
Ｋの中には相異なる元が存在する.
注意

Ｋの要素については不問

通常の整数の演算と異なる。
– ＋が分配する
–
の存在
– 逆演算が存在しない.
２元ブール代数
この系が公理１,２,３,６を満たすことは、定義から
明らかである.
２.恒等元、３.交換法則、６.相異なる元の存在
ブール代数としての論理関数
双対性

Huntington の公理系は(a), (b) の対に
なっている.
の変換をすれば、一方から他方が得られる
ブール代数の定理

補題3.4.１恒等元０,１はそれぞれひとつ
しかない.

証明
証明終り

補題3.4.2 冪等（単一化）

証明

補題3.4.3

証明

補題3.4.4

証明
また、
である.双対性により

補題3.4.5

証明
意味が明白であれば・を省略することができる.
表記法としては・は＋に優先する.


補題3.4.6
証明いま a の補元が
のように２つあ
るとすれば、補元の定義より、
となる。したがって、
から
をうる.よって補元は単一である.

補題3.4.7 すべての
である.

証明
について
とおく.
はの補元
であるから、公理５より、
は
の補元であるから、公理５より、
となり、交換法則から
も
である. よって補題3.4.6から
もともに
の補元
である.

補題3.4.8

証明

定理3.4.1 結合法則
省略

定理3.4.2

証明

定理3.4.3 (De Morgan’s law)
ドモルガンの定理

証明
分配
定理１補題３
恒等元
分配
定理１補題３
恒等元
したがって
A と
B
とは互いに単一の補元である.
集合論･･･ブール代数の例
全集合 SU 空集合
SZ  {}
K  {Ri | Ri  SU }
K
ただし SU , SZ  K とする.
の上にブール
代数を定義する.
0  SZ
1  SU
空集合
全集合
R  S  R  S  {x | ( x  R)  ( x  S )}
R  S  R  S  {x | ( x  R)  ( x  S )}
C(S )  {x | x  SU  ( x  S )}
union, 和集合
intersection, 積集合
complement, 補集合
二つの集合
R  S と R とが等しいとは、
S
x  S , x  R
S R
x  R, x  S

例題
この代数が下の対応をつけることによって，ブー
 
ル代数になることを示せ.

  
S ZS Z  0 0
  
SUSU  1 1
SZ  0
CC
( S()S )  S S
SU  1
（ブール代数公理の成立することを示す）
C (S ) 
S
Venn図
A
B
A
and
B
or
A
A
not
簡単化の例

例題
3人の古書のコレクターがいた．それぞれが集めて
いる書籍は，
Ａ氏日本の歴史物と外国小説
Ｂ氏日本の小説を除く歴史ものと小説以外の日本の作品
Ｃ氏ノンフィクションただし日本の作品か外国の歴史もの
であるという．競合の起きる書籍はどんなものか？
本の集合を記号で表す．
Ｊ日本の作品
ＡＡ氏の収集本
Ｎ
Ｈ
Ｂ
Ｃ
小説
歴史物
Ｂ氏の収集本
Ｃ氏の収集本
求めたい本の集合Z は
Z  ( A  B)  ( A  C)  ( B  C )  ( A  B  C)
一方 ABC は
A  (J  H )  (J  N )
B  ( H  ( J  N ))  ( J  N )
C  ( J  ( H  J ))  N
これを Z に代入すると複雑な式となるが，ブール代数を
用いることにより簡単化されて，（プリント参照）
Z  JN HJ
をうる．
Z  ((J  H )  ( J  N ))  ((H  ( J  N ))  ( J  N ))
 ((J  H )  ( J  N ))  ( J  ( J  H ))  N
 ((H  ( J  N ))  ( J  N ))  ( J  ( J  H ))  N
 ((J  H )  ( J  N ))  ((H  ( J  N ))  ( J  N ))
 ( J  ( J  H ))  N
ブール代数の表記法にしてみる．
Z  AB  BC  CA  ABC
 AB  BC  C (1  B) A
 AB  BC  CA
A  HJ  J N
B  H ( JN )  J N  H ( J  N )  J N  H J  H N  J N
C  (J  H J )N  J N  H J N
AB  ( HJ  J N )(H J  H N  J N )
 HJ N  HJ N  H J N  HJ N  H J N
BC  ( H J  H N  J N )(J N  H J N )
 H J N  HJ N  H J N  J N
 H J N  HJ N  J N
CA  ( J N  H J N )(HJ  J N )  HJ N
Z  HJ N  H J N  H J N  HJ N  J N  HJ N
 HJ N  H J N  H J N  J N  J N  H J

定理3.6.1
ab  ac  bc  ab  ac
(a  b)(a  c)(b  c)  (a  b)(a  c)

証明
（プリントを参照）
a b c ab
aababacbcabaab
cab
bcbab
cab
acaab
ccaab
ab
acab
acab
bc
ac
ab
cab

aab
ab
a
ccabc
acbc
acbc
aacbc
ab
cab
cbc

ab
bc
ab
bc
ab
aab
accaacacbc
bc
cabc
cbc
bcbc
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
1
0
0
1
1
例題下図の論理回路を簡単化せよ
y xzz yyzz( zxz zxz) xz yz ( z  xz )
y z z x z x z xy z xz xy zx xz zyzx xzz xz 
y z z x z x yzyzxz zz xxxzyz xxx zzz xyxzzzxxxz yzyxx zxzzyyzyzzxx(zzz zz
xzxxz)z yyzz((zzxxzz))
y z z x z x z x z x y x z yz xz z  xz yz ( z  xz )
z (xxz yz ()(zxy xz )xz )
y z z x z x z x xz x zyxxy zxzyzxyxzzx
y z z x z x z x z x y x z yz xz z  xz yz ( z  xz )
x  z xy xz xy  xz ( x  z )(xy  xz )
F
y z z x z x z x z x y x z yz xz z  xz yz ( z  xz )
x z x z x z x y x z yxzxzz xzyxxzzxyyz( zxz (xxz ) z )(xy  xz )
x  z xy xz xy  xz ( x  z )(xy  xz )
y z z x z x z x z x y x z yz xz z  xz yz ( z  xz )
x  z xy xz xy  xz ( x  z )(xy  xz )
F  yz ( z  xz )  ( x  z )(x y  x z )
 yz  ( x  z )(x y  x z )
 yz  ( x  z ) x ( y  z )
 yz  x y  x z
a ( a  b)  a
ab  ac  a(b  c)
( a  b) a  a
ab  a c  bc  ab  a c
 yz  x z
y
z
yz
yz  xz
z
x
xz

例題次の関数を簡単化せよ．
F  x  xyz  yzx  wx  w x  x y
 x  yz( x  x )  x( w  w )  x y
a(b  b )  a 1  a
 ( x  x y )  yz  x
 x  y  yz  x
 x  ( y  yz)
 x y
分配法則
ab  ac  a(b  c)
a  ab  a  b
aa a
a  ab  a

別解
F  x  xyz  yzx  wx  w x  x y
a  b  ab
 x ( xyz) ( yzx ) ( wx ) ( w x) ( x y )
ab  a  b
 x ( x  y  z )( y  z  x)(w  x )(w  x )(x  y )
 x ( y  z  x)(w  x )(w  x )(x  y )
 x ( w  x )(w  x )(x  y )( y  z  x)
 x ( x  y )( y  z  x) a(a  b)  a
 x(x  y)
xy
F  x y  x y
a(a  b)  ab
ab  a  b
a ( a  b)  a
aa  a
ｎ変数論理関数

3変数論理関数はいくつあるか？
23  8 通り

n 変数では
2 通り
2n

2n
関数の表現はさまざまでも種類は 2 だけ．
f1  x  xy  y  yz
f 2  x  x y  x( w  w )
f3  x  y
はいずれも同じ真理値表になる．
真理値表が等しければ
二つの関数は等価である．
拡大ブール代数
n 変数論理関数の集合Ｋ
K  {あらゆる n 変数論理関数}
 { f1 , f 2 ,, f N }
この上にブール代数を定義する．
Ｖｅｎｎ図を使うことができる．
論理関数の問題
2n
2 個あるn変数論理関数の一つが
与えられた時に、この関数と等価な、
無数にある式の表現のうちで，何か
ある基準のもとで最も簡単なものを
求めることにある．

Download Report