ブール代数とハンチントンの公理系(英語原論文)
ブールが1815年に生誕して、今年(2015年)で200周年。先日は Google
のホリデーロゴとしても使われていた。1と0を使った簡単で特殊なデジタル
計算である「ブール代数」は、今現在、コンピューター、電子回路、情報関連
の基礎として教えられることが多いようだ。
記号の書き方は色々あるが、ここでは、「´」(ダッシュ : 文字の上の横棒の代
わり)、「×」、「+」を使って、まず簡単に基本的な計算法則を示しとこう。ちな
みに、×や+は、普通の算数・数学における意味とは違う(ずれている)ので
念のため。「=」(等号)については、算数・数学と同様としておく。
(1項演算) 1´=0, 0´=1
(2項演算) 1+1=1, 1+0=1, 0+1=1, 0+0=0
1×1=1, 1×0=0, 0×1=0, 0×0=0
(計算例) ((1×1)+1)´=(1+1)´=1´=0
☆ ☆ ☆
こうした議論を最初に提示したのは、19世紀の英国の数学者、ジョージ・ブー
ル(George Boole)だとされているが、本当に彼が最初なのかどうかは、考
察し直す価値のある歴史的問題だと思う。一応ここでは慣例や通説に従い、
「ブール代数」(boolean algebra)と呼んでおく。
ブールの重要な論文2本(1847年、1854年)の内、先に公開されたのが
「The Mathema
tical Analysis
Of Logic」。左は
公開中の原論文か
らのコピペだ。
これを読むと、ブー
ルの主たる関心は
計算やその応用とい
うより、論理、あるい
は演繹的推論だと分かる。つまり、真と偽、2つのみを命題の性質と考える
「二値論理」に関する哲学を行ってるわけで、そのための新たな道具、分析
方法が、ブール代数という計算体系なのだ。
例えば、「真の命題の否定は、偽の命題」。つまり、「ノット・真は、偽」、「not
真=偽」。これを、「1´=0」などと表記する。
また、「真の命題と真の命題を『または』で結合すると、真の命題」。つまり、
「真オア真は、真」、「真∨真=真」。これを、「1+1=1」などと表記する。
さらに、「真の命題と真の命題を『かつ』で結合すると、真の命題」。つまり、
「真アンド真は、真」、「真∧真=真」。これを、「1×1=1」などと表記する。
そして、それらを基本法則として、人間の論理的思考をとらえていくわけだ。
☆ ☆ ☆
「ブール代数」という言葉が最初に示唆(suggest)されたのは、ハンチント
ンによると、1913年とされているらしい(英語版ウィキペディア)。
しかしそれ以前に、洗練された公理体系を提示したのは彼自身であって、そ
の事はあまり話題にならないし、英語の原論文の内容まで参照した日本語
サイトは、検索しても見当たらない。これは過去、ペアノ、フレーゲ、ベルトラン、
ナッシュなどの時にも見られた状況だ。
エドワード・ハンチントン(Edward Huntington)の1904年の論文、「Sets
Of Independent Postulates For The Algeblra Of Logic」(論理の
代数のための、独立した要請の集合)は、JSTORで公開されてる。
これを読むと、ブール自身とは多少異なり、ハンチントンの関心はむしろ数学
にあるようだ。彼は、ブール代数のためのいわゆる「公理系」(独立した要請
の集合)として、3種類を提示している。だからこそ、論文タイトルでは複数形
の英単語を用いて「Sets」(諸集合)としてるわけだ。
3種類の内、最初に挙げられてるものが最も分かりやすいので、ブール代数
の基本とされたり、「ハンチントンの公理系」などと呼ばれたりしている。以下、
原論文の内容を見てみよう。
☆ ☆ ☆
上のコピペが、10個の要請(基本的命題)の内の、最初の7個。記号の使い
方が特殊だが、現在の簡単な記号と用語を用いて、簡単に解説してみよう。
英文の直訳ではないので、念のため。
集合(class)Kに対して、2種類の2項演算+、×を考える。
Ⅰa、Ⅰb Kの任意の要素a、bに対して、a+bとa×bもKの要素。
(注. 以下すべてK内で考え、「任意の」は省略。)
Ⅱa 0という要素が存在して、 a+0=a。
Ⅱb 1という要素が存在して、 a×1=a。
Ⅲa a+b=b+a
Ⅲb a×b=b×a
Ⅳa a+(b×c)=(a+b)×(a+c)
☆ ☆ ☆
続いて、残りの3個の要請について。
Ⅳb a×(b+c)=(a×b)+(a×c)
Ⅴ 1と0が、それぞれただ一つ存在するなら、aに対してa´という要素が
存在して、 a+a´=1、 a×a´=0
Ⅵ 少なくとも2つの異なる要素が存在する。
上の全てに関して、+と×、1と0を同時に入れ替えた命題も正しいという、
「双対性」(そうついせい:duality)が成立している。
以上をいわゆる「公理系」としてまとめる時は、Ⅱ~Ⅴの4種類を挙げるのが
普通のようだ。
1 単位元(の法則)
2 +と×の交換法則
3 分配法則
4 補元(の法則)
ちなみに補元もただ一つだが、それは証明できること、つまり独立ではない事
なので、Vでは強調されてない。単に不定冠詞を付けて書いている。あと、元の
Ⅴ(現在の4)は、「排中律」(~であるか、~でないか、どちらかだ)と「矛盾律」
(~であり、かつ、~でない、ということはない)とも解釈できるものだ。
☆ ☆ ☆
最後に2問だけ、具体的問題を解いてみよう。要請(または公理)を用いた定
理の証明だ。
(1) a×0=0の証明
a×0=a×0+0 (∵ Ⅱa : 単位元)
=a×0+a×a´ (∵ Ⅴ : 補元)
=a×(0+a´) (∵ Ⅳb : 分配法則)
=a×(a´+0) (∵ Ⅲa : 交換法則)
=a×a´ (∵ Ⅱa : 単位元)
=0 (∵ Ⅴ : 補元)
(2) a×(a+b)=aの証明 (第一吸収法則の片方)
a×(a+b)=(a+0)×(a+b) (∵ Ⅱa : 単位元)
=a+(0×b) (∵ Ⅳa : 分配法則)
=a+(b×0) (∵ Ⅲb : 交換法則)
=a+0 (∵ (1) )
=a (∵ Ⅱa : 単位元)
☆ ☆ ☆
その他の吸収法則や、反復法則、二重否定法則、結合法則、ド・モルガンの
法則なども証明できる。そうした普通の計算については、既に様々な所で書
かれていることでもあり、ここでは省略しよう。
上の(2)のように、式を簡単化する操作は、工学的な実用性も合わせ持つテ
クニックであって、いずれ別記事を書くかも知れない。その前に、より基本的
な式変形として、連言(かつ)や選言(または)の「完全標準形」を説明するべき
だろう。
なお、今週は計17080字となった。それでは、また来週。。☆彡
(計 2678字)
| 固定リンク | 0
「数学」カテゴリの記事
- 日テレ『頭脳王2021』ストレンジ・オセロ、先手必勝ゲームの証明と戦略(7通りの場合分け)(2021.02.23)
- 『頭脳王2021』、純金のピラミッドの金額&シロナガスクジラを持ち上げる金剛力士像の身長、計算式と解説(2021.02.20)
- 1と0のカードゲーム、単純そうで複雑な連続操作の考察~開成中学2021年入試、算数・問題3の解き方(2021.02.14)
- 宝くじの当選番号を予言して当てる迷惑メールの仕組み、他~2021年・大学入学共通テスト・情報関係基礎(2021.01.24)
- 陸上100m走のタイム(時間)とストライド(歩幅)、ピッチ(歩数)の関係~2021年・大学入学共通テスト・数学ⅠA・第2問〔1〕(2021.01.19)
コメント