代数学

ブール演算

 

S={0,1} とする。S の演算 ∨ と ∧ を次のように定める。
1∨1=11∨0=10∨1=10∨0=01∧1=11∧0=00∧1=00∧0=0
このとき、∨ を論理和といい、∧ を論理積という。

(a) 論理和 ∨ は結合則と交換則を満たし、0 は論理和 ∨ に関する単位元であることを示せ。
(b) 論理積 ∧ は結合則と交換則を満たし、1 は論理積 ∧ に関する単位元であることを示せ。

(a)
x,y,z∈S とした時に
(x∨y)∨z=x∨(y∨z)x∨y=y∨x
を示せば良い。

第2式の交換則は明らかに成り立つことが分かる。
また、演算 ∨ の単位元が0であること、すなわち、任意の x∈S に対して
x∨0=0∨x=x
も確かに成り立っている。

第1式について、８種類の全ての場合について計算してみる。
(1∨1)∨1=1∨1=11∨(1∨1)=1∨1=1(1∨1)∨0=1∨0=11∨(1∨0)=1∨1=1(1∨0)∨1=1∨1=11∨(0∨1)=1∨1=1(1∨0)∨0=1∨0=11∨(0∨0)=1∨0=1(0∨1)∨1=1∨1=10∨(1∨1)=0∨1=1(0∨1)∨0=1∨0=10∨(1∨0)=0∨1=1(0∨0)∨1=0∨1=10∨(0∨1)=0∨1=1(0∨0)∨0=0∨0=00∨(0∨0)=0∨0=0
となり、確かに結合則を満たしていることが分かる。

(b) 同様に ∧ についても、交換則は明らかに成り立つことが分かる。
さらに、演算 ∧ の単位元が１であること、すなわち、任意の x∈S に対して
x∧1=1∧x=x
も成り立つことが分かる。

結合則について、すべての場合について確かめると
(1∧1)∧1=1∧1=11∧(1∧1)=1∧1=1(1∧1)∧0=1∧0=01∧(1∧0)=1∧0=0(1∧0)∧1=0∧1=01∧(0∧1)=1∧0=0(1∧0)∧0=0∧0=01∧(0∧0)=1∧0=0(0∧1)∧1=0∧1=00∧(1∧1)=0∧1=0(0∧1)∧0=0∧0=00∧(1∧0)=0∧0=0(0∧0)∧1=0∧1=00∧(0∧1)=0∧0=0(0∧0)∧0=0∧0=00∧(0∧0)=0∧0=0
となり、確かに交換速を満たしていることが分かる。

RELATED POST