論理とブール代数

2. クラスの代数 — 結び・交わり・1と0

ブール代数では、+は結び（どちらか一方にでも入っているものすべて）、×は交わり（両方に入っているものだけ）を表す。1は議論の対象全体、0は空クラスを意味し、F×(1−F)=0 という式は「何かが自分自身であり、かつその反対であることはできない」という矛盾律を表す。さらにx²=xという、従来の代数とは異なる式にも触れながら、「すべての人間は死すべき定めにある。ソクラテスは人間である。ゆえに、ソクラテスは死すべき定めにある」という三段論法が、代入と結合律だけで代数的に証明できることを確かめる。

ブール代数には2つの基本演算がある。「+」はクラスの結び（現代の用語でいう和集合）を 作る演算で、2つのクラスのどちらか一方にでも入っているものすべての集まりを表す。たとえば 「黒い猫のクラス+白い猫のクラス」なら、黒であるか白であるか、そのどちらかに当てはまるすべての猫の クラスになる。

もう一方の「×」はクラスの交わり（現代の用語でいう共通部分）を作る演算で、2つの クラスの両方に入っているものだけの集まりを表す。「雌猫のクラス×褐色の猫のクラス」なら、雌であり、 かつ褐色でもある猫だけが残る。2つの形容詞をつなげたものだと考えればわかりやすい。

結びと交わりには、従来の代数と同じ交換律・結合律・分配律がそのまま成り立つ。それだけでなく、 従来の代数では成り立たない「+の×に対する分配律」もブール代数では成り立つ——これは 後で真偽の0/1の形式に置き換えたとき、複雑な式を機械的に整理するための足場になる。

記号の1と0にも独自の意味がある。1は議論の対象全体、たとえば猫の話をしているなら 「すべての猫のクラス」を表し、雄猫のクラスMと雌猫のクラスFについて M+F=1 が成り立つ。 0は空クラス、つまり何も含まないクラスを表す。1−M は「全体から雄猫を除いたもの」 であり、これはF、すなわち雌猫のクラスに一致する。

F×(1−F) を計算すると、Fに入っていて、かつFに入っていないものは存在しないから、答えは0になる。 これは「何かが自分自身であり、かつその反対であることはできない」という矛盾律を、 そのまま式にしたものである。同時に F+(1−F)=1 も成り立つ——どんなものも、Fであるか、Fでないかの どちらかには必ず入る。

ブール自身が、自分の代数を従来の代数から区別する代表的な言明として挙げたのが x²=x である。数の代数ではこの式が成り立つのは0と1のときだけだが、クラスの代数 では常に成り立つ——雌猫のクラスと雌猫のクラス自身の交わりは、やはり雌猫のクラスにしかならないからだ。 同様に x+x=x も常に成り立つ。

この代数の力を実際に試してみよう。人間のクラスをP、死すべきもののクラスをM、ソクラテスのクラスをSと する。「すべての人間は死すべき定めにある」は P×M=P、「ソクラテスは人間である」は S×P=S と書ける。 第1式に第2式を代入し、結合律を使って整理すると S×M=S が導かれる——「ソクラテスは 死すべき定めにある」という結論が、記号の計算だけで確かめられたことになる。2300年前の推論が、代入と 結合律という機械的な手続きに置き換わった瞬間である。

このセクション: 0 / 6 問正解

3. 0と1の真偽テスト — AND・OR・NOTの表

ブール代数には、文字にクラスではなく0か1だけを割り当てる別形式もある——1はイエス・真（条件を満たす）、0はノー・偽（条件を満たさない）を表す。ANDの表（両方が1のときだけ1）とORの表（0+0のときだけ0。1+1=1が普通の足し算との唯一の違い）を使えば、どんなに複雑な条件式も機械的に評価できる。この「機械的」という言葉が、次のセクションで文字どおり機械（回路）になっていく。

ここまで見てきたのは、文字がクラスを表す形のブール代数だった。ブール代数にはもう1つ、文字にクラス ではなく「0か1だけ」を割り当てる形式がある——真偽テストと呼ばれる 形である。この形式では、1はイエス・真（ある条件を満たしている）を、0はノー・偽（満たしていない）を 表す。何についての真偽かは取り決め次第で、点灯/消灯や雄/雌といった具体的な意味は、あくまでその文脈 における一例にすぎない——前章で見た「ビットの意味は文脈に依存する」という考え方が、ここでもそのまま効いている。

×がANDを意味するとき、結果が1になるのは左右の両方が1のときだけである。0×0=0、0×1=0、 1×0=0、1×1=1——結果は普通の掛け算とまったく同じ表になる。

+がORを意味するときの表は、普通の足し算とはただ1点だけ違う。0+0=0、0+1=1、1+0=1までは 足し算と同じだが、両方が1のときは2ではなく1になる。

1 + 1 = 1（ORの表だけの特別ルール）

両方が真であっても、結果はやはり真——ここに「+」が「または」を意味していることがはっきりと表れている。 NOTは「1−」の形で書ける。Xに1を割り当てれば 1−X は0に、Xが0なら1になる——値を反転させるだけの 演算である。クラスの代数における「全体から除く」という考え方が、0/1の形式では単純な反転として姿を 変えている。

ANDの表とORの表さえ手元にあれば、どんなに複雑に見える式でも、内側のカッコから順番に当てはめて いくだけで機械的に真偽を計算できる。なお現代の教科書では、ANDに∧、ORに∨という記号を使うことも ある。

この「機械的に計算できる」という感覚は、下のシミュレータで自分の手で確かめられる。 タブでブール式を選び、A・Bのボタンで0と1を切り替えると、式へ代入した結果と、 表の中の「いまの入力に当たる行」のハイライトが連動して動く。両方を1にしたとき、 A×BとA+Bで結果がどう分かれるかを試してみてほしい。

この「機械的に計算できる」という性質こそが、次のセクションで文字どおりの機械——電気回路——へと 姿を変えていく。

このセクション: 0 / 5 問正解

4. スイッチは論理を語る — 直列=AND・並列=OR

電池・電球と2つのスイッチを直列（一本道の途中に連続して）につなぐと、両方閉じたときだけ点灯する回路になり、その表はANDの表と一致する。並列（枝分かれした2本の道）につなぐと、どちらか一方でも閉じれば点灯し、その表はORの表と一致する。頭の中の論理（ブール代数）と物理的な装置（電気回路）が同じ構造を持つ——この一体化こそが、2進数で動くコンピュータの設計と構築を可能にする、この章最大の発見である。

直列・並列という言葉は、第1講「コードで世界を伝える」で すでに一度登場している。あちらは電池の直列・並列接続で、電圧が足し合わされるか、寿命が延びるかという 電気の物理的な性質の話だった。ここで扱う直列・並列はスイッチの配置についてであり、 意味はまったく違う——スイッチの直列・並列接続は、論理そのものを実行しているのである。

電池と電球、そして2つのスイッチを一本道の途中に連続してつなぐ——これが直列接続で ある。電球が点灯するのは、2つのスイッチの両方を閉じたときだけ。どちらか片方でも開いていれば、電流の 通り道が断たれて電球はつかない。この「両方閉じたときだけ点灯する」という表は、先ほど見たANDの表と 寸分違わず一致する。

一方、2つのスイッチを枝分かれした2本の道のそれぞれに配置する——これが並列接続で ある。電球が点灯するのは、どちらか一方のスイッチでも閉じたとき。両方閉じても、もちろん点灯する。 この表はORの表とそのまま一致する。

開=0・閉=1、消灯=0・点灯=1——この読み替えを行うと、スイッチをつないだ回路が、ブール代数の論理 演算を物理的に実行できることがわかる。頭の中だけの記号操作だったはずの論理が、電気の通り道という 物理的な装置とぴったり同じ構造を持っていた——これが本章最大の発見である。

この対応がわかると、ブール式からスイッチ回路を機械的に組み立てられるようになる。式の×記号が現れる 箇所は直列接続に、+記号が現れる箇所は並列接続に、そのまま置き換えればよい。たとえば (A×B)+C という 式なら、AとBを直列につないだひとまとまりを、Cと並列につなげばよい——どれほど複雑な条件判定の回路も、 この機械的な置き換えだけで組み上がる。

ブール自身は、自分の代数が回路として動く様子を見ることはなかった。白熱電球が発明されたのは、彼の死 から15年も後のことだったからである。モールスの電信は『思考の法則』が出版される10年前の1844年に すでに実証されていたにもかかわらず、19世紀のうちにブール代数とスイッチの直列・並列配線を結びつけた 者は——ブールと文通していたバベッジでさえも——いなかった。「コンピュータにはギアやレバーよりも、 電信のリレーを使った方がいい」。第2講「遠くまで、確実に届ける」 で見たリレーが、次講でついに論理ゲートへと姿を変える。

このセクション: 0 / 5 問正解