2 ブール代数

2.1 教科書について

皆さんが使っている教科書のブール代数の説明は、あまりにも分かりにくいで す。ここでは、この教科書から離れて、通常の教科書のとおり順序だてて説明 します。方法は、

• ブール代数の公理を示します。ブール代数はこの公理から全て導くこ とが出来ます。
• 公理から導く諸定理を示します。
• 練習問題

です。

2.2 公理と定理

ブール代数を学習する前に公理と定理について説明しておきます。ところで、 公理とは、あるいは定理とはなんでしょうか?。皆さんが、中学生のときに学 習したユークリッド幾何学には、以下のような公理があります。

1. 勝手な点と、これと異なる他の勝手な点とを結ぶ直線は、一つ、そし てただ一つ引くことができる。
2. 勝手な線分は、これを両方への望むだけ延長することができる。
3. 勝手な点を中心として、勝手な半径で円をかくことができる。
4. 直角はすべて相等しい。
5. 一直線が二直線に交わるとき、もしその同じ側にある内角を加えたも のが二直角より小さかったならば、二直線はこの方向へ延長してゆけ ば、必ず交わる。

これは、日常生活の経験からして正しそうなものです。この正しそうな5つの 命題から、論理を展開したものがユークリッド幾何学です。ところで、これは 正しそうに思えますが、証明は可能なのでしょうか?。証明するとなると、そ れに必要な正しいと認められている事柄(命題)が必要になります。そうすると その命題を証明する必要が生じ、証明すべきことが果てしなく続きます。証明 するために新たに証明が必要となる矛盾から抜け出すために、ある仮定を作り ます。この仮定を公理といい、これに従い論理を組み立ます。要するに、公理 はひとつの理論体系を作るときの出発点となる根本命題のことです。

この命題の元に証明されたものが定理です。例えば、「三角形の内角の和は2 直角である」という有名な定理も、これらの公理から証明出来ます。1、2、5 番目の公理を使えば証明できます。

物理で学習したニュートンの力学の3法則も公理と考えてよいです。

1. 慣性の法則
2. 運動方程式
3. 作用・反作用の法則

これが、仮定と成り立っている場合を考えるのがニュートン力学です。実際に この公理は、日常経験と一致しているので非常に有用なものとなったのです。 また、アインシュタインは、以下の公理のもと特殊相対性理論を構築しました。

1. 相対性原理(全ての慣性系は同等である)
2. 光速度不変の原理(光の速度は光源や観測者の運動とは無関係に決まる)

最後に公理の性質を述べておきます [3]。

• それらは、無矛盾でなくてはならない。
• それらは、単純な事項であって、2つあるいはそれ以上に分解されては ならない。
• それらは、互いに独立でなくてはならない。1つの公理が他の公理群か ら導き出せてはならない。

皆さんも、公理という考え方を理解して、論理的な思考・議論ができるように なってください。

2.3 ブール代数の公理

2.3.1 公理

話がだいぶ横道にそれましたが、公理というもが理解できたと思います。ここ では、ブール代数の公理を示します。ブール代数は、

• 2項演算子$+$,$\cdot$と単項演算子$\bar{ }$が定義されています。それ ぞれ加法と乗法、および補元の演算子です。
• 使われる変数は、0と1です。

の特徴をもっています。0と1だけからなる代数系であり，これはコンピューター 内部で行われている演算そのものです。演算子もコンピューター内部の回路と 一致しています。それでは、ブール代数の公理を以下に示します。

公理 2.1 (ブール代数)  

$$\hspace{3mm} A+B=B+A, \hspace{10mm} A \cdot B = B \cdot A$$ 交換法則 (1)

$$A \cdot(B + C)=(A \cdot B)+(A \cdot C), A+(B \cdot C) = (A+B) \cdot (A+C)$$ 分配法則 (2)

$$A+0=A, A \cdot 1 = A$$ 単位元 (3)

$$A + \bar{A}=1, A \cdot \bar{A}= 0$$ 補元 (4)

これで、ブール代数が定義できました。それにしても、通常の数の演算と似て いますね。しかし、良く見ると少し異なります。

• 式(2)の2つある分配法則のうちの一つが、数の計算の分配法 則にはありません。
• 補元は逆元に似ていますが、ちょっと違います。

これらの違いによーく気をつけてください。さらに、演算について重要なこと を付け加えておきます。それは、加法と乗法、補元の演算の結果は、必ず元の 変数の集合$\{0,1\}$に含まれることです。このことをこれらの演算について 閉じていると言います。閉じていることの確認は、節を見てください。

ブール代数には、この公理から直ちにに分かる重要な性質があります。この公 理の加法の$+$と乗法の$\cdot$、0と$1$をそれぞれ入れ替えても、同じ公理 になります。このことから次に示す双対の原理が成り立ちます。これは便利な もので、上手に使うと計算が楽になります。あるいは定理を憶えるのも半分で すみます。

定理 2.1 (双対の原理)   ブール代数では、元の式の$+$と$\cdot$、0と$1$ を交換してできる式を元 の式の「双対」(dual)と呼びます。ブール代数において、ある定理が成 り立つならば、その定理の双対もまた成り立たちます。

ブール代数においては加法と乗法は対等です。しかし、普通には、数の演算同 様に乗法は加法に先立って計算されます。さらに、括弧を用いて、演算順序の 変更も可能です。要するに、計算順序は普通の数の演算と同じと考えてよいで す。そのため乗法の記号$\cdot$が省略されたり、加法よりも乗法を演算順序 を優先することを暗黙の了解事項として書かれている場合があります。このよ うなことは可能で、試験でも正解とします。しかし、双対の原理を考慮すると、 加法と乗法の演算順序は対等とし、括弧で演算順序を決めて、さらに乗法の記 号もちゃんと書いたほうが考えやすいと思います。

2.3.2 真理値表

先に述べたように、ブール代数の変数の集合は${0,1}$です。そして、演算子 は$+$と$\cdot$、$\bar{}$です。変数も演算子も少ないので、すべての組み合 わせを表にすることは簡単です。それを表1から 3に示します。このように、変数の全ての組み合 わせを示して、その演算結果を示すものを真理値表と言います。

これらの表で示した演算は、全て公理から導くことができます。直接公理から 導けないものは、後で示す定理を使えば簡単に導くことが出来ます。定理も公 理から導いたので、この表の演算の根拠は公理にあります。

1. $A+B$の真理値表

2. $A \cdot B$の真理値表

. $\bar{A}$の真理値表

表 1: $A+B$の真理値表

$A$	$B$	$A+B$
0	0	0
0	1	1
1	0	1
1	1	1

表 2: $A \cdot B$の真理値表

$A$	$B$	$A \cdot B$
0	0	0
0	1	0
1	0	0
1	1	1

表: $\bar{A}$の真理値表

$A$	$\bar{A}$
0	1
1	0

2.3.3 ブール代数と現実の世界

ブール代数が定義されたので、それが実際の回路に適用可能であることを確認 します。公理とスイッチの動作の関係を調べます。結論から言うとブール代数 とスイッチの対応は、図2のようにすれば、それら は同一になります。この図が言っていることは、

• ブール代数の値0はスイッチが開を、1は閉をあらわします。
• ブール代数の加算は、スイッチが並列に接続されたことを表します。乗 算は直列接続です。
• $A$と書かれるスイッチは、$A$の値が0のとき開で、1のとき閉です。一方、 補元を表す$\bar{A}$の場合は、$A$の値が0のとき閉で、1のとき開です。

です。

このスイッチの動作がブール代数の公理と同じであることを確認します。先ほ どのブール代数とスイッチの関係を公理に当てはめると、図 2のようになります。公理が実際のスイッチの回路 と完全に矛盾無く対応していることが分かるでしょう。このことから、スイッ チの動作を記述するのにブール代数が使えることが分かります。

ではなぜ、公理で示された4つのことが成り立てば、全て成り立つのでしょう か?。それは、この4つが完全な公理になっているからです。この証明は大変で す。ここでの学習の範囲を超えますので、これ以上深入りしないことにします。

図 2: ブール代数の変数および演算子とスイッチとの対応

図 3: ブール代数の公理とスイッチ回路の対応

つぎにブール代数と日常の言葉、回路の対応を示します。それぞれは、表 4の対応があります。論理回路については、 今後学習しますので、いまはそのようなものがあると思ってください。

表 4: ブール代数と日常の言葉、回路

ブール代数	日本語	英語	スイッチ	論理回路
0	偽	false	開	Low, 0, 0[V]
1	真	true	閉	High, 1, 5[V]
$+$	または	or	並列接続
$\cdot$	かつ	and	直列接続
$\bar{}$	否定	not	開閉が逆

2.4 ブール代数の諸定理

公理から導かれる諸定理を以下に書き出します。これらは、全て公理を用いて 証明可能であることを念頭に入れておいてください。皆さんは、公理は言うに 及ばず、以下の定理も証明をしないで自由に使って計算しても良いです。

定理 2.2 (演算の諸定理)  

$$\hspace{3mm} A+(B+C)=(A+B)+C, \hspace{20mm} A \cdot(B \cdot C) = (A \cdot B) \cdot C$$ 結合則 (5)

$$A+(A \cdot B)=A, A \cdot (A+B)=A$$ 吸収則 (6)

$$A+A=A, A \cdot A=A$$ 巾等律 (7)

$$A+1=1, A \cdot 0 = 0$$ (8)

$$A+(\bar{A}+B)=1, A \cdot (\bar{A} \cdot B)=0$$ (9)

$$(A+\bar{B}) \cdot (\bar{A}+B)=(A \cdot B)+(\bar{A} \cdot \bar{B}), (A \cdot \bar{B}) + (\bar{A} \cdot B)=(A + B) \cdot (\bar{A} + \bar{B})$$ (10)

$$\overline{(A+B)}=\bar{A} \cdot \bar{B}, \overline{(A \cdot B)}=\bar{A} + \bar{B}$$ ド・モルガン (11)

定理 2.3 (二重否定)  

$$\bar{\bar{A}}=A$$ (12)

定理 2.4   $A+\bar{B}=1$かつ $A \cdot \bar{B}=0$ならば、$A=B$である。

ここで示した全ての定理を公理を用いて証明することは、紙の無駄なので、2 つだけ例を示します。式(8)と非常に有用なド・モルガンの法則で ある式(11)を証明します。

【証明】 1   $A+1=1$を証明します。

$$A+1 =(A+1)\cdot 1$$ [公理:式(3)]

$$=(A+1) \cdot (A+\bar{A})$$ [公理:式(4)]

$$=A+(1 \cdot \bar{A})$$ [公理:式(2)]

$$=A+(\bar{A} \cdot 1)$$ [公理:式(1)]

$$=A+\bar{A}$$ [公理:式(3)]

$$=1$$ [公理:式(4)]

これで証明できました。式(8)のもう一方は、双対の原理に より成り立つのは明らかです。

公理のみを使って、ド・モルガンの法則を証明するには、多くのページが必要 です。そこでこの法則については、真理値表で証明します。公理を用いての証 明に興味ある人は、図書館にあるフィスターの本 [3]でも読んでください。

【証明】 2 (ド・モルガンの法則)   $\overline{(A+B)}=\bar{A} \cdot \bar{B}$を証明します。左辺と 右辺の真理値表が等しいことを示します。この式の左辺と右辺の真理値表は表 5のようになります。この式が成り立つことがわかった でしょう。この式が証明できたので、双対の原理により、 $\overline{(A \cdot B)}=\bar{A} + \bar{B}$も成り立つといえます。

表 5: ド・モルガンの法則の真理値表。 これより、 $\overline{(A+B)}=\bar{A} \cdot \bar{B}$が確認できる。

$A$	$B$	$A+B$	$\overline{(A+B)}$	$\bar{A}$	$\bar{B}$	$(\bar{A} \cdot \bar{B})$
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

ホームページ: Yamamoto's laboratory
著者: 山本昌志