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

Basics of Boolean algebraブール代数だいすう

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

Boolean algebraブール代数だいすう is a structure for treating logic論理ろんり and set operations集合演算しゅうごうえんざん in the same formal shape. The propositional operations “and,” “or,” and “not” correspond to intersection共通部分きょうつうぶぶん, union和集合わしゅうごう, and complement補集合ほしゅうごう of sets集合しゅうごう.

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である。この後あとで、これらの公理こうりから補元ほげんが一意いちいであることを証明しょうめいする。

1Terms and definition

Let the lattice束そく $$(B,\vee ,\wedge )$$(B,\vee,\wedge) have a least element $$0$$0 and a greatest element $$1$$1. Suppose that for every $$x,y,z\in B$$x,y,z\in B it satisfies both distributive laws分配律ぶんぱいりつ:

If every $$x\in B$$x\in B has a complement補元ほげん $$x^{\prime }$$x' satisfying

then $$(B,\vee ,\wedge ,{}^{\prime },0,1)$$(B,\vee,\wedge,{}',0,1) is a Boolean algebraブール代数だいすう. Thus a Boolean algebra is a bounded distributive lattice有界分配束ゆうかいぶんぱいそく equipped with a complement for every element. We will prove below that these axioms make the complement unique.

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 と同値どうちである。

2Correspondence with truth sets of predicates

Fix a universal set全体集合ぜんたいしゅうごう $$U$$U and predicates $$P\left(x\right),Q\left(x\right)$$P(x),Q(x) on $$U$$U. Let the truth set真理集合しんりしゅうごう of $$P$$P be

Similarly, let $$S_Q=\{x\in U\mid Q(x\left)\right\}$$S_Q=\{x\in U\mid Q(x)\}.

Then logical operations and set operations correspond as follows.

This correspondence lets us read transformations of logical formulas as set operations集合演算しゅうごうえんざん. In particular, $$P\Rightarrow Q$$P\Rightarrow Q is true for every $$x\in U$$x\in U exactly when $$S_P\subseteq S_Q$$S_P\subseteq S_Q, and $$P\iff Q$$P\Leftrightarrow Q is true for every $$x\in U$$x\in U exactly when $$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の定義ていぎをすべて満みたす。

3A power set冪集合べきしゅうごう is a Boolean algebraブール代数だいすう

For any set $$U$$U, the power set冪集合べきしゅうごう $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(U\right)$$\mathcal P(U) becomes a Boolean algebra using the inclusion order, union, intersection, and complement.

Here $$\vee$$\vee denotes join結むすび, $$\wedge$$\wedge denotes meet交まじわり, and $$\text{'}$$' denotes complementation. Thus the logical operations $$\vee ,\wedge ,\neg$$\lor,\land,\lnot correspond in this example to $$\cup ,\cap ,U\setminus (-)$$\cup,\cap,U\setminus(-), respectively.

Here $$0=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$0=\varnothing and $$1=U$$1=U. Union and intersection satisfy both distributive laws, and $$X^{\prime }=U\setminus X$$X'=U\setminus X satisfies $$X\cap X^{\prime }=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$X\cap X'=\varnothing and $$X\cup X^{\prime }=U$$X\cup X'=U. Thus every part of the definition of a Boolean algebra is satisfied.

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

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

論理ろんりでは

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

である。

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

De Morgan's lawsド・モルガンの法則 say that negation interchanges “and” and “or.”

In logic,

and for sets,

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

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

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

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

5What is being abstracted

Boolean algebraブール代数だいすう temporarily ignores whether the objects are propositions or sets, and focuses only on the laws satisfied by the operations. The preserved structure concerns joins結むすび, meets交まじわり, complements補元ほげん, greatest elements, and least elements.

This abstraction lets logical circuits, families of sets, conditional branches, and search conditions be handled by the same formal rules.

The point is that even after replacing concrete propositions命題めいだい or sets集合しゅうごう, calculations use the same laws for joins結むすび, meets交まじわり, and complements補元ほげん. We are looking at the structure preserved by the operations, not at the objects themselves.

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 である。

6Proof supplement: uniqueness of complements補元ほげん

In a Boolean algebraブール代数だいすう, the complement補元ほげん of $$x$$x is unique. Suppose $$y$$y and $$z$$z are both complements of $$x$$x, meaning

Then

The same argument gives $$z\text{[PARSE ERROR: Undefined("Command("le")")]}y$$z\le y, so antisymmetry反対称性はんたいしょうせい implies $$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' も得えられる。

7Proof supplement: De Morgan's lawsド・モルガンの法則

Using uniqueness of complements補元ほげん, De Morgan's lawsド・モルガンの法則 can be proved cleanly. For example, it is enough to show that $$x^{\prime }\vee y^{\prime }$$x'\vee y' is a complement of $$x\wedge y$$x\wedge y.

Therefore uniqueness of complements gives

The same method gives $$(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はその中心ちゅうしん的てきな計算けいさん法則ほうそくである。

8Exercise link and summary

Boolean algebraブール代数だいすう is a structure connecting logic論理ろんり and set operations集合演算しゅうごうえんざん. A power set冪集合べきしゅうごう is a standard example of a Boolean algebra, and De Morgan's lawsド・モルガンの法則 are central calculation laws in it.