命題論理の形式システムＬＰの公理の独立性

命題論理ＬＰの公理系は次の３つが立てられていた。

公理
１　Ａ→（Ｂ→Ａ）
２　（Ａ→（Ｂ→Ｃ））→（（Ａ→Ｂ）→（Ａ→Ｃ））
３　（～Ｂ→～Ａ）→（Ａ→Ｂ）

これに次の推論規則

ｍｐ　ＡとＡ→Ｂが成立しているとき、Ｂの成立をいうことが出来る。

を使って命題を生成するシステムがＬＰということになる。このＬＰにおいて３つの公理が独立しているというのは、それぞれが他の２つの公理から、公理のＡ，Ｂ，Ｃの命題の置き換えとｍｐという推論規則の両方を使っては、決して生成できないものになっているということを意味する。これは、この公理系の無矛盾性と完全性が証明されていることと合わせて考えれば、この３つの公理が必要最小限のものになっているということを意味する。

この独立性の証明は、きわめて構造というもののとらえ方にかかわっているもののように感じる。この生成システムは、どんなにがんばって生成をし続けても、２つの公理と推論規則からでは、もう一つの公理を生成することが出来ない。しかし、それが現実の計算において出来ていないからといって、システム全体として未来永劫にそれが出来ないと結論することが出来ない。今は出来ないけれど、あるとき偶然に出来るかもしれないという可能性は、ただ計算をしてみるだけ（文字列を生成し続けるだけ）では結論できないからだ。規則に従って文字列を生成するだけでは、現実にはそれが生成できないという否定が正しいという結論を導くことが出来ない。



ＬＰという形式システムでは公理の独立性を示すことが出来ないのではないかと思われる。この独立性を示すには、ＬＰという公理系がどのような構造を持っているのかという、構造を把握する必要がある。その構造の下では、２つの公理と推論規則だけでは、構造的に見て決してもう一つの公理が生成できないのだということを示すしかない。まさにそのような証明がこの本では紹介されている。

この証明においては論理記号をある種の関数と見て、公理系を解釈することの出来るような集合を設定し、その構造を考察することになる。これは真理関数という発想を広げたものになる。真理関数では、命題を真か偽に対応させてそれぞれの論理記号は、真偽に対応して、合成された命題にまた真偽を対応させる関数として解釈される。真偽は２つの値しかないので、真に１を、偽に０を対応させるのが普通で、通常の真理関数は次のように解釈される。

　　　　Ａ　　　～Ａ
　　　　１　　　　０
　　　　０　　　　１

　　　　Ａ　　Ｂ　　　Ａ→Ｂ
　　　　１　　１　　　　１
　　　　１　　０　　　　０
　　　　０　　１　　　　１
　　　　０　　１　　　　１

～は、真理値を逆転させ、→はＡが１でＢが０の時にのみ０になるという関数として解釈される。命題論理の公理系ＬＰはこのような構造を持つとき、トートロジーという個々の要素命題がどのような真理値を持とうとも、合成された命題が常に真理値が１になるという論理式と結びつけられるという構造を持つ。

この真理値の関数は１と０の２つの値を取るものだったが、これを０，１，２という３つの値をとる関数で解釈する構造を考える。これは真理値のように感性的に捉えることは出来ない。あえていえば、真とも偽とも決定できない曖昧な状態を２と解釈するという見方で現実との関連を感性的に捉えるような感じになるだろうか。しかしそれは厳密に決定できないので、関数としてみた場合の解釈としては不安定になる。この３つの値をとる関数は、あくまでも構造を考察する上での便宜的に設定されたものとして理解した方がいいだろう。

さて、この３つの値の関数は次のように定義される。

　　　Ａ　　　～Ａ
　　　１　　　２
　　　２　　　２
　　　０　　　１

　　　Ａ　　Ｂ　　　Ａ→Ｂ
　　　１　　１　　　　１
　　　１　　２　　　　０
　　　１　　０　　　　０
　　　２　　１　　　　０
　　　２　　２　　　　０
　　　２　　０　　　　１
　　　０　　１　　　　１
　　　０　　２　　　　１
　　　０　　０　　　　１

この対応を、現実的に解釈するのはかえって混乱するだろう。これは機械的にこのような数が対応しているというとらえ方をして、この対応が公理系ＬＰの構造を示してくれると見た方がいい。さて、この関数の対応で公理２がどのような値をとるかを見てみたい。これは面倒ではあるがＡ，Ｂ，Ｃの３つの命題の値の可能性をすべて網羅して２７通りの値の与え方を調べてみて判断する。

　　Ａ　Ｂ　Ｃ　　（Ａ→（Ｂ→Ｃ））→（（Ａ→Ｂ）→（Ａ→Ｃ））
　　１　１　１　　　　１　　１　　　１　　　１　　１　　１
　　１　１　２　　　　０　　０　　　１　　　１　　０　　０
　　１　１　０　　　　０　　０　　　１　　　１　　０　　０
　　１　２　１　　　　０　　０　　　１　　　０　　１　　１
　　１　２　２　　　　０　　０　　　１　　　０　　１　　０
　　１　２　０　　　　１　　１　　　１　　　０　　１　　０
　　１　０　１　　　　１　　１　　　１　　　０　　１　　１
　　１　０　２　　　　１　　１　　　１　　　０　　１　　０
　　１　０　０　　　　１　　１　　　１　　　０　　１　　０
　　２　１　１　　　　０　　１　　　１　　　０　　１　　０
　　２　１　２　　　　１　　０　　　１　　　０　　１　　０
　　２　１　０　　　　１　　０　　　１　　　０　　１　　１
　　２　２　１　　　　１　　０　　　１　　　０　　１　　０
　　２　２　２　　　　１　　０　　　１　　　０　　１　　０
　　２　２　０　　　　０　　１　　　１　　　０　　１　　１
　　２　０　１　　　　０　　１　　　１　　　１　　０　　０
　　２　０　２　　　　０　　１　　　１　　　１　　０　　０
　　２　０　０　　　　０　　１　　　１　　　１　　１　　１
　　０　１　１　　　　１　　１　　　１　　　１　　１　　１
　　０　１　２　　　　１　　０　　　１　　　１　　１　　１
　　０　１　０　　　　１　　０　　　１　　　１　　１　　１
　　０　２　１　　　　１　　０　　　１　　　１　　１　　１
　　０　２　２　　　　１　　０　　　１　　　１　　１　　１
　　０　２　０　　　　１　　１　　　１　　　１　　１　　１
　　０　０　１　　　　１　　１　　　１　　　１　　１　　１
　　０　０　２　　　　１　　１　　　１　　　１　　１　　１
　　０　０　０　　　　１　　１　　　１　　　１　　１　　１

上の表は、「Ａ→Ｂ」において、Ａが０の時はＢが何であろうと「Ａ→Ｂ」は１になることと、Ａ，Ｂともに１なら「Ａ→Ｂ」が１になり、Ａが２でＢが０なら「Ａ→Ｂ」が１になるという数値の与え方を、それぞれの部分に与えてから、最後に全体がどうなるかを計算して作っている。それはちょうど中央に現れる値で、すべてが１になることが見て取れるだろう。

同様にして公理３も計算してみると次のようになる。

　　Ａ　　Ｂ　　　（～Ｂ→～Ａ）→（Ａ→Ｂ）
　　１　　１　　　　２　０　２　１　　１
　　１　　２　　　　２　０　２　１　　０
　　１　　０　　　　１　０　２　１　　０
　　２　　１　　　　２　０　２　１　　０
　　２　　２　　　　２　０　２　１　　０
　　２　　０　　　　１　０　２　１　　１
　　０　　１　　　　２　０　１　１　　１
　　０　　２　　　　２　０　１　１　　１
　　０　　０　　　　１　１　１　１　　１

これも、ＡとＢにどのような数値を当てようとすべて１の計算になるような命題となる。この「１，２，０」という３つの値をとる関数として「～」と「→」を解釈すると、その解釈の下では公理２と公理３は常に１の値に対応する関数を表すことになる。

次に推論規則について考えてみる。推論規則は、公理系を出発点として、公理とは違う形の文字列を生成し、それを定理とするものだ。そして、定理として確定したものはまた新たな定理を生成するための前提として推論規則を当てはめることが出来る。ｍｐと呼ばれる推論規則では、ＡとＡ→Ｂという２つの論理式からＢという論理式を定理として導いてもいいというものだ。まだ定理が発見される以前は、これは両方とも公理の１つになる。公理におけるＡ，Ｂ，Ｃのどれかを書き換えた論理式となる。

そうすると、Ａは公理であるから、これは上の解釈の下で常に１という値をとる。またＡ→Ｂも、最初の段階では公理の１つであるから、これも常に１という値をとる関数として解釈される。このとき、ＢというＡ→Ｂから分離された論理式は、やはり常に１という値をとる関数として解釈される。なぜならＡは常に１なのだから、ある場合にＢが０になってしまえば、Ａ→Ｂという論理式は０という値になってしまい、これが公理であって常に１になるということと矛盾するからだ。

以上の考察で、公理から分離される新たな定理は、公理と同様にやはり常に１という値をとる。そうすると、その定理を付け加えて新たな証明を考えれば、常に１という値をとる論理式にｍｐという推論規則を適用するのだから、そこから導かれる新たな定理Ｂはやはり常に１という値をとる。

このことは、公理２と公理３から推論規則ｍｐを使って生成される定理はすべて、上の解釈において常に値１を取るものであることを意味する。そこで、公理１がＡとＢの値の取り方にかかわらず、常に１という値を取るものであるかを調べてみる。

　　Ａ　　Ｂ　　　Ａ→（Ｂ→Ａ）
　　１　　１　　　　１　　１
　　１　　２　　　　０　　０
　　１　　０　　　　１　　１
　　２　　１　　　　１　　０
　　２　　２　　　　１　　０
　　２　　０　　　　０　　１
　　０　　１　　　　１　　０
　　０　　２　　　　１　　１
　　０　　０　　　　１　　１

この表を見ると、公理１は常に値１をとるのではなく、２カ所で値０となってしまう。公理２，公理３と推論規則ｍｐを使った新たな定理は常に値１にならなければならないのだから、公理１は決して公理２，公理３と推論規則から導くことは出来ない。それは、この公理系の持っている構造から必然的に帰結されることになる。

形式システムは、新たな定理を計算して生み出すという行為のみをその働きとして示す。その定理がどのような意味を持っているかは形式システムにとっては全く考えることが出来ない。形式システムは、ＡとＡ→Ｂがあったときに、Ｂという式を分離するという計算結果を出力するだけなのである。

ある文字列が生成できないという不可能性を示そうとすれば、構造を把握できるメタ的な視点からの考察をするしかない。もし我々が形式システムのように、対象を経験主義的にアルゴリズムに従った計算でしか考察できなかったら、その計算によってその問題が解決するかどうかは、それが解決不可能な問題であった場合には、不可能であるという証明は出来ないのではないかと思う。不可能性の証明は構造を捉えることによってしか確実には出来ないだろう。構造を捉える視点は、そのアルゴリズム（形式システム）の限界を見せてくれるものになるのではないかという感じがする。なかなか解答できない問題に我々が遭遇したときは、その構造に注目するということは、発想法として役に立つのではないかと思う。構造主義が、様々な現実の限界にぶち当たったときに誕生したように見えるのは、そのような意味を持っているのではないだろうか。