Bool 代数と Spencer-Brown の原始代数の等価性

黒木 玄

2000年10月19日 Version 0.03 (2000年9月19日 Version 0.01)


NEW 2000.10.19 「スペンサー・ブラウンなんていらない」へのリンクを追加した。「ガードナーとクヌースとコンウェイによる最低の評価」などを含む。スペンサー・ブラウン批判の要約を「コンウェイのコメント」につけた私のコメントで読むことができます。おそらくそれを最初に読んでおくのが良いと思います。


目次


0. はじめに

以下のノートの目的は Bool 代数と Spencer-Brown の原始代数 (以下 SB 代数と呼ぶ) の概念の等価性を示すことである。

Bool 代数を知っている人であれば、 Spencer-Brown の [SB] の第6章と補遺2を見れば、すぐさまこの等価性に気付くはずである。証明は単なる計算であり、どこにも難しいところはない。

あとがきにおいて、 [SB] の第11章における「re-entry」と「時間」の概念の導入は、フィードバックを含まないデジタル回路(組み合わせ論理回路)を記述する Bool 代数の理論からフィードバックを含むデジタル回路(順序論理回路)の理論への拡張に対応していることを簡単に説明しておいた。「re-entry」のはデジタル回路における「フィードバック」に対応している。

なお、Bool 代数に関しては、

[T] 田中俊一、『位相と論理』、日評数学選書、日本評論社、2000年

の第1章を参考にし、 Spencer-Brown の原始代数に関しては、

[SB] G. スペンサー=ブラウン、『形式の法則』、山口昌哉監修、大澤真幸・宮台真司訳、朝日出版社

の第6章を参照した。デジタル回路に関する最も易しい入門書としては、

[MOWM] 宮井幸男、尾崎進、若林茂、三好誠司共著、『イラスト・図解 デジタル回路のしくみがわかる本』、技術評論社、 1999年(平成11年)7月5日初版第1刷、 2000年2月25日初版第2刷

がおすすめである。フィードバックを含むデジタル回路(順序論理回路)に関しては第2章の終わり(37頁)以降に説明が書いてある。


1. Bool 代数

Bool 代数の公理を以下に全て書き下しておく:

参考:(B1.1)から(B3.2)までが束 (lattice) の公理であり、 (B4.2)までが分配束 (distributive lattice) の公理である。 (B4.1), (B4.2) は分配法則と呼ばれている。

(a∨b)∨c = a∨(b∨c) を a∨b∨c と書くことがある(∧についても同様)。

Bool 代数の公理を仮定する。以下では(B1.1)から(B2.4)は断わり無しに用いる。

(1.1) a∨b = 1, a∧b = 0, a∨c = 1, a∧c = 0 ならば b = c (補元の一意性).

証明:

b = 1∧b = (a∨c)∧b  =  (a∧b)∨(c∧b) = 0∨(b∧c) = b∧c.
                    (B4.1)

同様に c = b∧c も出る。よって b = c. □

(1.2) ¬¬a = a.

証明:¬a∨¬¬a = 1, ¬a∧¬¬a = 0, ¬a∨a = 1, ¬a∧a = 0 に(1.1)を適用すれば ¬¬a = a. □

(1.3) ¬0 = 1, ¬1 = 0.

証明: 0∨¬0 = 1, 0∧¬0 = 0, 0∨1 = 1, 0∧1 = 0 に(1.1)を適用すれば ¬0 = 1.  よって、 ¬¬0 = ¬1.  これに(1.2)を適用すれば 0 = ¬1. □

(1.4) ¬(a∨b) = ¬a∧¬b, ¬(a∧b) = ¬a∨¬b (de Morgan).

証明:a∨b∨¬(a∨b) = 1, (a∨b)∧¬(a∨b) = 0 と

  a∨b∨(¬a∧¬b)
= a∨((b∨¬a)∧(b∨¬b))   by (B4.2)
= a∨((b∨¬a)∧1)          by (B5.1)
= a∨(b∨¬a)
= (a∨¬a)∨b
= 1∨b                      by (B5.1)
= 1

および

  (a∨b)∧¬a∧¬b
= ((a∧¬a)∨(b∧¬a))∧¬b   by (B4.1)
= (0∨(b∧¬a))∧¬b          by (B5.2)
= (b∧¬a)∧¬b
= (b∧¬b)∧¬a
= 0∧¬a                      by (B5.2)
= 0

に(1.1)を適用すれば、 ¬(a∨b) = ¬a∧¬b. 後者の等式は同様の議論もしくは前者に(1.2)を適用することによって示される。□

(1.5) a∧b = ¬(¬a∨¬b).

証明:

a∧b  =  ¬¬(a∧b)  =  ¬(¬a∨¬b). □
    (1.2)          (1.4)

この結果は Bool 代数の演算∧を他の二つの演算∨、¬で表わせることを意味している。結論を先走って言えば、 Spencer-Brown の原始代数 (SB 代数) は Bool 代数の公理を∨と0と¬だけで書き下したものなのだ。このことを示すのがこのノートの目標である。

(1.6) a∨b = b と a∧b = a は同値である。

証明: a∨b = b ならば、 (B3.2)より、 a = a∧(a∨b) = a∧b. 逆向きは(B3.1)より同様に示される。□

(1.7) a∨1 = 1, a∧0 = 0.

証明: それぞれ(B2.4), (B1.4)と(1.6)から出る。□

例1.8: A = {0, 1} に演算∨、∧、¬を

0∨0 = 0, 0∨1 = 1, 1∨0 = 1, 1∨1 = 1, 
0∧0 = 0, 0∧1 = 1, 1∧0 = 1, 1∧1 = 1, 
¬0 = 1, ¬1 = 0

と定めると、 A は Bool 代数をなす。□

例1.9: B が集合 U の部分集合全体の集合であるとき、 a, b ∈ B に対して、 0 = φ (空集合)、 1 = U、 a∨b = a∪b、 a∧b = a∩b、¬a = U - a (a の U における補集合) と定めることによって、 B は自然に Bool 代数をなす。□


2. SB 代数

前節の記号と合わせるために、 Spencer-Brown とは異なる次の記法を用いる:

      ---+
SB の  a | を ¬a,  SB の ab を a∨b,  SB の空文字列を 0 と書く。

この約束のもとで、Spencer-Brown の原始代数 (以下 SB 代数と呼ぶ) の公理を以下に書き下しておく。陽に示されている公理は以下の2つである:

この他に以下の公理が陰に仮定されている:

以上が SB 代数の公理の全てである。


3. SB 代数の Bool 代数からの導出

この節では SB 代数の公理を Bool 代数の公理から導出する。 Bool 代数の公理を仮定する。 (J1), (J2) のみを示せば良い。

(J1)の証明:

¬(¬a∨a)   =  ¬1  =  0. □
          (B5.1)   (1.3)

(J2)の証明: (1.4), (1.2)を順次用いると、

¬(¬a∨¬b) = ¬¬a∧¬¬b = a∧b.

よって、(J2)は次のように書き直される:

(J2') (a∨c)∧(a∨c) = (a∧b)∨c.

これは((B1.2)の前提のもとで)分配束(B3.1)と同値である。□


4. Bool 代数の SB 代数からの導出

この節では前節と逆に Bool 代数の公理を SB 代数の公理から導出する。

SB 代数の公理を仮定し、∧と1を次のように定める:

a∧b = ¬(¬a∨¬b),   1 = ¬0.

(4.1) ¬a∧a = 0.

証明:(J1) ¬(¬a∨a) = 0 の a に ¬a を代入し、∧の定義を用いれば良い。□

この(4.1)と(B1.2)より(B5.2) a∧¬a = 0 が成立することがわかる。

(4.2) (a∨c)∧(a∨c) = (a∧b)∨c.

証明: (J2) ¬(¬(a∨c)∨¬(b∨c)) =¬(¬a∨¬b)∨c は記号∧を用いれば (J2') (a∨c)∧(a∨c) = (a∧b)∨c に書き直される。□

この(4.2)と(B1.2)より分配法則の片方(B4.2) a∨(b∧c) = (a∨b)∧(a∨c) が成立することがわかる。

(4.3) (¬a∨a)∧b = ¬¬b.

証明:

左辺 = ¬(¬(¬a∨a)∨¬b)  =  ¬(0∨¬b) = 右辺. □
                          (J1)

(4.4) ¬¬a = a.

証明:

¬¬a = 0∨¬¬a
      = (¬a∧a)∨¬¬a              by (4.1)
      = (¬a∨¬¬a)∧(a∨¬¬a)     by (4.2)
      = ¬¬(a∨¬¬a)               by (4.3)
      = (a∨¬a)∧(a∨¬¬a)         by (4.3)
      = a∨(¬a∧¬¬a)              by (4.2)
      = a∨0                         by (4.1)
      = a.  □

(4.5) ¬(a∨b) = ¬a∧¬b, ¬(a∧b) = ¬a∨¬b (de Morgan).

証明:

¬(a∨b) = ¬(¬¬a∨¬¬b)   by (4.4)
         = ¬a∧¬b           by definition of ∧,

¬(a∧b) = ¬¬(¬a∨¬b)     by definition of ∧
         = ¬a∨¬b           by (4.4).              □

(4.6) ¬0 = 1, ¬1 = 0.

証明:前者は 1 の定義である。前者と(4.4)より ¬1 = ¬¬0 = 0. □

(B5.1) a∨¬a = 1 が成立する。

証明:すでに(B5.2)が証明されている。(B5.2)に(4.4)と(4.5)を適用すれば(B5.1)が出る:

 a∨¬a = ¬¬(a∨¬a)     by (4.4)
        = ¬(¬a∧¬¬a)   by (4.5)
        = ¬0              by (B5.2)
        = 1                by definition of 1. □

分配法則のもう片方(B4.1) a∧(b∨c) = (a∧b)∨(a∧c) も成立する。

証明:すでに分配法則の片方(B4.2)が証明されている。(B4.2)に(4.4)と(4.5)を適用すれば(B4.1)が出る:

a∧(b∨c) = ¬¬(a∧(b∨c))                 by (4.4)
          = ¬(¬a∨(¬b∧¬c))             by (4.5)
          = ¬((¬a∨¬b)∧(¬a∨¬c)       by (B4.2)
          = (¬¬a∧¬¬b)∨(¬¬a∧¬¬c)  by (4.5)
          = (a∧b)∨(a∧c)                  by (4.4).  □

(B2.4) a∧1 = a が成立する。

証明: SB 代数の公理のうちの一つである(B1.4)に(4.4), (4.5), (4.6)を適用すれば(B2.4)が出る:

a∧1 = ¬¬(a∧1)     by (4.4)
     = ¬(¬a∨¬1)   by (4.5)
     = ¬(¬a∨0)     by (4.6)
     = ¬¬a          by (B1.4)
     = a              by (4.4). □

実は(4.4), (4.5), (4.6)から、すでに成り立つことがわかっている等式の中の、∨と∧、0と1を交換してできる等式も成立することがわかる。 (このことがわからない人は上と同じ議論を繰り返せば良い。)

よって、SB 代数の公理の中の(B1.1), (B1.2)から、(B2.1), (B2.2) が出る。

そして、まだ証明されてない残りの (B1.3), (B2.3), (B3.1), (B3.2) を示すためには(B1.3)と(B3.1)のみを示せば十分である。

以下、(B1.1), (B1.2), (B1.4), (B2.1), (B2.2), (B2.4)は断り無しに用いる。

(4.7) a∨(¬a∧b) = a∨b, a∧(¬a∨b) = a∧b.

証明:前者は次のように示される:

a∨(¬a∧b) = (a∨¬a)∧(a∨b)   by (B4.2)
            = 1∧(a∨b)          by (B5.1)
            = a∨b.

後者も同様の計算もしくは前者の式の∨と∧入れ換えることによって得られる。□

(4.8) ¬(¬a∧b) = a∨¬b.

証明: (4.5), (4.4) を順次適用すれば出る。□

(B3.1) a∨(a∧b) = a が成立する。

証明:

a∨(a∧b) = a∨(¬a∧a∧b)           by (4.7)の前者
          = a∨(¬a∧b∧a)
          = a∨(¬a∧b∧(¬b∨a))    by (4.7)の後者
          = a∨(¬a∧b∧(a∨¬b))
          = a∨0                     by (4.8) and (B5.2)
          = a.                                           □

(B1.3) a∨a = a が成立する。

証明:

  a∨a = a∨(a∧1)  by (B5.1)
       = a          by (B3.1).  □

以上で SB 代数の公理から Bool 代数の公理が導出できることがわかった。

なお、『形式の法則』 [SB] の第6章における等式 C1, C2, C3, C4, C5 は、正確ではないが大雑把には、それぞれ等式 (4.4), (4.7), (1.7), (B3.1), (B1.3) に対応している。

実は、このことに注意しながら、 [SB] の第6章を補遺2を参考にしながら読めば、 Spencer-Brown の原始代数の公理から Bool 代数の公理が導出できることが第6章において実質的に証明されていることがわかる。 (逆向きの導出は第3節で示したように自明である。)


5. あとがき

このノートによって示された SB 代数と Bool 代数の概念の等価性は、 Spencer-Brown の原始代数の理論が実質的に (SB の当時でさえ) 数学的に何も新しいことを含んでなかったことを意味している。

実は、前節の最後で注意しておいたように、この SB 代数と Bool 代数の概念の等価性は 『形式の法則』 [SB] の第6章で実質的に証明されているのである。それにもかかわらず、 Spencer-Brown が自分自身が新しい数学を展開したかのように([SB] の序文などで)語っているのは非常に奇妙である。

ただし、 Spencer-Brown は [SB] の第11章で原始代数 (および原始算術) の範囲を超えた数学を展開していることには注意しなければいけない。 (しかし、その内容は数学的に曖昧でかつ不明瞭であり、議論の展開の仕方も不完全であり、自明なことしか書かれてない。)

そこで新たに導入されたのは「re-entry」と「時間」の概念である。

しかし、それらは、デジタル回路におけるフィードバックと時間に対応しているとみなせる。 Bool 代数 (= SB 代数)の理論は内部にフィードバックを持たない組み合わせ論理回路の理論だとみなせるので、 Spencer-Brown は [SB] の第10章までで展開した「原始代数の理論」=「Bool 代数の理論」=「組み合わせ論理回路の理論」をその第11章において「re-entry と時間の概念を含む理論」=「内部にフィードバックを持つデジタル回路の理論」に拡張したのである。 (フィードバックを含むデジタル回路(順序論理回路)に関しては [MOWM] の第2章の終わり(37頁)以降に説明が書いてある。)

実際、第11章の注釈に「それらは、 D. J. スペンサー=ブラウン氏と協力して、コンピューター回路という特殊な目的のために、開発されました」(115頁)と書いてあるように、[SB]の著者 G. スペンサー=ブラウンは第11章のアイデアをコンピューターのデジタル回路設計から得ていたのである。

通常のデジタル回路との対応は、 Spencer-Brown が第11章で用いた

  ***       ***
     ***    ***
        *** ***
           ****
***************************
           ****
        *** ***
     ***    ***
  ***       ***

という記号を通常のデジタル回路における NOR ゲートの記号

    ************
*******         ***
       *           **
********            *○*****
       *           **
*******         ***
    ************

で置き換えると見易い。

以上のように、『形式の法則』[SB]に現われる数学的概念は全て他のよく知られた概念で置換可能である。

なお、『形式の法則』[SB]の「補遺2」では、命題論理の範囲内で述語論理を扱うことに挑戦し、当然そうなるべき陳腐なパターンでおかしなことになっている。

Spencer-Brown なんていらない、と言ってしまうのは言い過ぎであろうか?

追記 (2000年10月19日) 「スペンサー・ブラウンなんていらない」も参照せよ。