Monthly posts: 2019/05

ブール代数

2019/05/29 09:00
math

ブール代数は古典論理における命題論理と密接に関連している. 結論からいえば, 両者の違いは歴史的な背景ぐらいであり, 殆どの場合は同等の理論であるということができる¹. ブール代数はその応用として論理回路の構築に直接役立つことから, 計算機科学, とくにハードウェアの分野において重宝される代数系の 1 つである.

ブール代数の公理とその定理

次に示すのはブール代数の公理系である. 公理系に関する詳細は証明理論 (TODO) の冒頭を参照のこと.

ブール代数

半順序集合 $(B,\lor,\land,',0,1)$ が可補分配束ならば, $(B,\lor,\land,',0,1)$ はブール代数である. すなわち, $x,y,z\in B$ に対して, 次のすべての公理を満たした $(B,\lor,\land,',0,1)$ はブール代数である.

$\htmlId{boolean_algebra1}{\rm 可換律}$ : $x\land y=y\land x,x\lor y=y\lor x$
$\htmlId{boolean_algebra2}{\rm 分配律}$ : $(x\lor y)\land z=(x\land z)\lor(y\land z),(x\land y)\lor z=(x\lor z)\land(y\lor z)$
$\htmlId{boolean_algebra3}{\rm 同一律}$ : $^\forall x\in L$ に対して $x\land 1=x,x\lor 0=x$ . ここで $1$ は最大限, 単位元である. $0$ は最小限, 零元である.
$\htmlId{boolean_algebra4}{\rm 補元律}$ : $^\exists x'\in L\ {\rm s.t.}\ ^\forall x\in L, x\lor x'=1, x\land x'=0$

また, この $1,0$ からのみ成る集合をブール領域, ブール代数の下に書かれた式をブール式, $n\in\mathbb{N}$ 個のブール領域の引数をとり, 1 個のブール領域の値となる関数 $f:B^n\to B$ をブール関数という. 例えば, 2 変数ブール関数 $f(x_1,x_2)$ では $x_1,x_2$ がそれぞれ $1,0$ のいずれかとなるので, $2^4=16$ 通りの 2 変数ブール式が存在することとなる. 以下, 演算の優先順序は左結合性で $',\land,\lor$ の順とする. ただし, 括弧内の演算はより優先される.

さてブール代数の公理における乗法 $\land$ と加法 $\lor$ , および $1, 0$ をそれぞれ入れ替えると, 再びブール代数の公理である. これは双対の原理という公理である.

双対の原理

ブール代数で成立する文/式は, そこに現れるすべての $\lor ,\land,0,1$ をそれぞれ $\land,\lor ,1,0$ で置き換えても成立する.

これらの公理から補元の一意性, べき等律, 有界律, 吸収律, 結合律, 対合律, ド・モルガンの法則, シャノンの展開定理が導出可能である. 以下 $x,y,z\in B$ とする.