ブール代数

1. １．ブール代数の性質
2. ２．ブール関数

１．ブール代数の性質

　　代数系における束の節で述べたように，ブール代数とは，分配束であり，かつ，可補束である代数系です．再度，その定義を述べておけば以下のようになります．

［定義］　 2 種類の演算が定義された代数系 ( B ; ＋, ・, (　) ) が以下の条件を満たすとき，この代数系をブール代数という．なお，以下において，x，y，z ∈ B とする．

[束の条件]

1. (1) 結合律
   x ＋ ( y ＋ z ) = ( x ＋ y ) ＋ z
   x ・ ( y ・ z ) = ( x ・ y ) ・ z

2. (2) 交換律
   x ＋ y = y ＋ x
   x ・ y = y ・ x

3. (3) 吸収律
   x ・ ( x ＋ y ) = x
   x ＋ ( x ・ y ) = x

[分配束の条件]

1. (4) 分配律
   x ・ ( y ＋ z ) = ( x ・ y ) ＋ ( x ・ z )
   x ＋ ( y ・ z ) = ( x ＋ y ) ・ ( x ＋ z )

[零元 0 と 単位元 I ]

1. (5) 零元 0，単位元 I の存在
   x ＋ 0 = x，　x ・ 0 = 0
   x ＋ I = I，　x ・ I = x

[可補束の条件]

1. (6) 補元 x の存在
   x ＋ x = I
   x ・ x = 0

　　なお，ブール代数においては，零元，単位元，及び，補元は一意に決まります．また，上の定義からも明らかなように，ブール代数の任意の性質は，＋ と ・，及び，I と 0 を入れ替えても成立します．このことを，双対律といいます．ブール代数の例として，例えば，有限集合 A のベキ集合 P(A) において，

∪（和集合）　⇔　＋

∩（積集合）　⇔　・

( )^c （補集合）　⇔　(　)

A （全体集合）　⇔　I

φ（空集合）　⇔　0

のような対応関係を取ると，代数系 ( A ; ∪, ∩, ( )^c ) はブール代数となります．

　　上に述べた定義から，以下に示すようなブール代数の性質を導くことができます．例えば，ベキ等律は，以下のようにして導くとこができます．

x = x ＋ ( x ・ I )　　　吸収律において y = I

　　= x ＋ x　　　単位元 I の性質

1. 対合律（二重否定律）　　x = x

2. ベキ等律
   x ＋ x = x
   x ・ x = x

3. ド・モルガン律
   x ＋ y = x ・ y
   x ・ y = x ＋ y

4. モジュラー律
   x ・ ( y ＋ ( x ・ z )) = ( x ・ y ) ＋ ( x ・ z )
   x ＋ ( y ・ ( x ＋ z )) = ( x ＋ y ) ・ ( x ＋ z )

5. 補元の吸収
   x ＋ ( x ・ y ) = x ＋ y
   x ・ ( x ＋ y ) = x ・ y

　　元の数が有限なブール代数を有限ブール代数といいます．特に重要なのは，零元 0 と単位元 1 だけからなる集合 B₂ = { 0, 1 } の上に定義されたブール代数 ( B₂ ; ＋, ・, (　) ) です．ブール代数 ( B₂ ; ＋, ・, (　) ) は，ディジタル回路の設計や記号論理学の分野で重要な役割を果たします．以下に，ブール代数 ( B₂ ; ＋, ・, (　) ) における演算表を示します．なお，＋, ・ の代わりに ∨，∧ という記号もよく使用されます．

＋	0	1		・	0	1		x	x
0	0	1		0	0	1		0	1
1	1	1		1	0	1		1	0

２．ブール関数

　　ここでは，ブール代数として，B₂，及び，その直積である B₂ⁿ だけを考えます．n 変数ブール関数 f( x₁, x₂, ･･･, x_n ) とは，B₂ⁿ から B₂ への写像，

f ： B₂ⁿ → B₂

を意味します．各変数 x_i （ブール変数）は，0 または 1 のいずれかの値を取りますので，その組み合わせは 2ⁿ 個になります．各変数の値に対する関数値を表にしたものを真理値表と呼びます．例えば，3 変数ブール関数 f( x, y, z ) = ( x ＋ y ) ・ z に対する真理値表は以下のようになります．

x	y	z	f( x, y, z )
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

　　ブール関数においても，通常の関数のように等式を変形したい場合があります．通常の関数に対しては，移項や約分などの操作を行うことができます．これは，体の節で述べたように，体には各演算に対する逆元が存在するためです．しかし，ブール代数には逆元が存在しないため，移項や約分による等式の変形を行うことができません．

　　ブール代数においては，等式の両辺に同じ演算を施しても等式は成立します．つまり，P，Q，R を任意のブール関数とした場合，

P = Q　⇒　P ＋ R = Q ＋ R，　P ・ R = Q ・ R

は成立しますが，その逆，つまり，

P ＋ R = Q ＋ R　⇒　P = Q

P ・ R = Q ・ R　⇒　P = Q

は成立しません．

　　通常の関数において，

f( x, y ) = x ( x + y)，　f( x, y ) = x² + xy，　・・・

などのように，同じ関数を複数の形で表現可能です．ブール代数においても，同じ結果を与える関数を複数の形で表現できます．そこで，ここでは，標準的な表現形式（標準形）について考えてみます．

　　ブール変数又はその否定の積からなる式を最小項，また，ブール変数又はその否定の和からなる式を最大項といいます．このとき，最小項の和の形をした表現形式を主加法標準形（加法標準形，積和標準形），最大項の積の形をした表現形式を主乗法標準形（乗法標準形，和積標準形）といいます．

　　具体的な例として，先に述べた 3 変数ブール関数 f( x, y, z ) = ( x ＋ y ) ・ z について考えてみます．この関数に対する真理値表，真理値が 1 になっている行に対する最小項，及び，真理値が 0 になっている行に対する最大項は以下のようになります．

x	y	z	f( x, y, z )	最小項	最大項
0	0	0	0		x ＋ y ＋ z
0	0	1	0		x ＋ y ＋ z
0	1	0	0		x ＋ y ＋ z
0	1	1	1	x ・ y ・ z
1	0	0	0		x ＋ y ＋ z
1	0	1	1	x ・ y ・ z
1	1	0	0		x ＋ y ＋ z
1	1	1	1	x ・ y ・ z

　　この例からも明らかなように，最小項は，変数の値が 1 の場合はそのまま，また，0 の場合はその否定を取った変数の積になっています．同様に，最大項は，変数の値が 0 の場合はそのまま，また，1 の場合はその否定を取った変数の和になっています．このとき，主加法標準形，及び，主乗法標準形は，以下に示すように，各々，真理値が 1 である行に対する最小項の和，及び，真理値が 0 である行に対する最大項の積になります．

f( x, y, z ) = x ・ y ・ z ＋ x ・ y ・ z ＋ x ・ y ・ z

f( x, y, z ) = ( x ＋ y ＋ z ) ・ ( x ＋ y ＋ z ) ・ ( x ＋ y ＋ z ) ・ ( x ＋ y ＋ z ) ・ ( x ＋ y ＋ z )

　　これらの関数を変形してみれば，元の関数に等しいことを容易に確認することができます．例えば，主加法標準形に対しては，以下のようにして変形可能です．

f( x, y, z ) = x ・ y ・ z ＋ x ・ y ・ z ＋ x ・ y ・ z

　　　= ( x ・ y ＋ x ・ y ＋ x ・ y ) ・ z　　　分配律

　　　= ( x ・ y ＋ x ・ ( y ＋ y ) ) ・ z　　　分配律

　　　= ( x ・ y ＋ x ・ 1 ) ・ z　　　補元

　　　= ( x ・ y ＋ x ) ・ z　　　単位元の性質

　　　= ( y ＋ x ) ・ z　　　補元の吸収