ブール代数Boolean algebraの基本きほん

ブール代数Boolean algebraは、論理ろんりlogicと集合演算しゅうごうえんざんset operationを同おなじ形かたちで扱あつかうための構造こうぞうである。命題めいだいpropositionの「かつ」「または」「でない」と、集合しゅうごうsetの共通部分きょうつうぶぶんintersection、和集合わしゅうごうunion、補集合ほしゅうごうcomplementは対応たいおうしている。

1用語ようごと定義ていぎ

束そくlattice $$(B,\vee ,\wedge )$$(B,\vee,\wedge) が最小元さいしょうげん $$0$$0 と最大元さいだいげん $$1$$1 を持もち、任意にんいの $$x,y,z\in B$$x,y,z\in B について

という 2 つの分配律ぶんぱいりつdistributive lawを満みたすとする。さらに各かく $$x\in B$$x\in B に、

を満みたす補元ほげんcomplement $$x^{\prime }$$x' を備そなえるとき、$$(B,\vee ,\wedge ,{}^{\prime },0,1)$$(B,\vee,\wedge,{}',0,1) をブール代数だいすうBoolean algebraという。つまり、ブール代数だいすうBoolean algebraは補元ほげんを持もつ有界分配束ゆうかいぶんぱいそくbounded distributive latticeである。この後あとで、これらの公理こうりから補元ほげんが一意いちいであることを証明しょうめいする。

2述語じゅつごの真理集合しんりしゅうごうとの対応たいおう

全体集合ぜんたいしゅうごうuniversal set $$U$$U を固定こていし、$$U$$U 上うえの述語じゅつご $$P\left(x\right),Q\left(x\right)$$P(x),Q(x) を考かんがえる。$$P$$P の真理集合しんりしゅうごうtruth setを

とし、同様どうように $$S_Q=\{x\in U\mid Q(x\left)\right\}$$S_Q=\{x\in U\mid Q(x)\} とする。

とする。このとき、論理演算ろんりえんざんと集合演算しゅうごうえんざんは次つぎのように対応たいおうする。

この対応たいおうにより、論理式ろんりしきの変形へんけいを集合演算しゅうごうえんざんとして読よむことができる。とくに $$P\Rightarrow Q$$P\Rightarrow Q がすべての $$x\in U$$x\in U で真しんであることは $$S_P\subseteq S_Q$$S_P\subseteq S_Q と同値どうちであり、$$P\iff Q$$P\Leftrightarrow Q がすべての $$x\in U$$x\in U で真しんであることは $$S_P=S_Q$$S_P=S_Q と同値どうちである。

3冪集合べきしゅうごうpower setはブール代数Boolean algebraになる

任意にんいの集合しゅうごう $$U$$U に対たいして、冪集合べきしゅうごうpower set $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(U\right)$$\mathcal P(U) は、包含順序ほうがんじゅんじょ、和集合わしゅうごう、共通部分きょうつうぶぶん、補集合ほしゅうごうによってブール代数Boolean algebraになる。

ここで $$\vee$$\vee は結むすびjoin、$$\wedge$$\wedge は交まじわりmeet、$$\text{'}$$' は補元ほげんを表あらわす。したがって、論理ろんりの $$\vee ,\wedge ,\neg$$\lor,\land,\lnot は、この例れいではそれぞれ $$\cup ,\cap ,U\setminus (-)$$\cup,\cap,U\setminus(-) に対応たいおうする。

この例れいでは $$0=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$0=\varnothing、$$1=U$$1=U である。和集合わしゅうごうと共通部分きょうつうぶぶんは 2 つの分配律ぶんぱいりつを満みたし、$$X^{\prime }=U\setminus X$$X'=U\setminus X は $$X\cap X^{\prime }=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$X\cap X'=\varnothing、$$X\cup X^{\prime }=U$$X\cup X'=U を満みたす。したがって、上うえのブール代数だいすうBoolean algebraの定義ていぎをすべて満みたす。

4ド・モルガンの法則De Morgan's laws

ド・モルガンの法則De Morgan's lawsは、否定ひていが「かつ」と「または」を入いれ替かえることを表あらわす。

論理ろんりでは

である。集合しゅうごうでは

である。

5何なにを抽象化ちゅうしょうかしているか

ブール代数Boolean algebraは、対象たいしょうが命題めいだいなのか集合しゅうごうなのかをいったん忘わすれて、演算えんざんの満みたす法則ほうそくだけを見みる。保存ほぞんされるのは、結むすび、交まじわり、補元ほげん、最大元さいだいげん、最小元さいしょうげんに関かんする構造こうぞうである。

この抽象化ちゅうしょうかにより、論理回路ろんりかいろ、集合族しゅうごうぞく、条件分岐じょうけんぶんき、検索条件けんさくじょうけんの組くみ合あわせを同おなじ形式けいしきで扱あつかえる。

具体的ぐたいてきな命題めいだいpropositionや集合しゅうごうsetを置おき換かえても、同おなじ結むすびjoin・交まじわりmeet・補元ほげんcomplementの法則ほうそくで計算けいさんできることが要点ようてんである。対象たいしょうそのものではなく、演算えんざんが保存ほぞんする構造こうぞうを見みている。

6証明しょうめい補足ほそく：補元ほげんcomplementの一意性いちいせい

ブール代数だいすうBoolean algebra で $$x$$x の補元ほげんcomplement が一意いちいであることを示しめす。$$y$$y と $$z$$z がどちらも $$x$$x の補元ほげんだとする。つまり

である。このとき

同おなじ議論ぎろんで $$z\text{[PARSE ERROR: Undefined("Command("le")")]}y$$z\le y も従したがうので、反対称性はんたいしょうせいantisymmetryより $$y=z$$y=z である。

7証明しょうめい補足ほそく：ド・モルガンの法則De Morgan's laws

補元ほげんcomplementの一意性いちいせいを使つかうと、ド・モルガンの法則ほうそくDe Morgan's laws も見通みとおしよく証明しょうめいできる。たとえば $$x\wedge y$$x\wedge y の補元ほげんが $$x^{\prime }\vee y^{\prime }$$x'\vee y' であることを示しめせばよい。

よって補元ほげんの一意性いちいせいから

である。同おなじ方法ほうほうで $$(x\vee y{)}^{\prime }=x^{\prime }\wedge y^{\prime }$$(x\vee y)'=x'\wedge y' も得えられる。

8演習えんしゅうリンクとまとめ

ブール代数Boolean algebraは、論理ろんりと集合演算しゅうごうえんざんをつなぐ構造こうぞうである。冪集合べきしゅうごうpower setは標準的ひょうじゅんてきなブール代数Boolean algebraの例れいであり、ド・モルガンの法則De Morgan's lawsはその中心ちゅうしん的てきな計算けいさん法則ほうそくである。