ブール代数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命題めいだいと集合しゅうごうの対応たいおう

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

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

この対応たいおうにより、論理式ろんりしきの変形へんけいを集合演算しゅうごうえんざんとして読よむことができる。

1Correspondence between propositions and sets

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

Then logical operations and set operations correspond as follows.

This correspondence lets us read transformations of logical formulas as set operations集合演算しゅうごうえんざん.

2冪集合べきしゅうごう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に対応たいおうする。

2A 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 corresponds to join結むすび, and $$\wedge$$\wedge corresponds to meet交まじわり.

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

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

論理ろんりでは

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

である。

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

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

In logic,

and for sets,

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

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

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

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

4What 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.

5証明しょうめい補足ほそく：補元ほげん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 である。

5Proof 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.

6証明しょうめい補足ほそく：ド・モルガンの法則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' も得えられる。

6Proof 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'.

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

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

7Exercise link and summary

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