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

命題論理LPの公理系は次の3つが立てられていた。

公理
1 A→(B→A)
2 (A→(B→C))→((A→B)→(A→C))
3 (~B→~A)→(A→B)

これに次の推論規則

mp AとA→Bが成立しているとき、Bの成立をいうことが出来る。

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

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



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

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

    A   ~A
    1    0
    0    1

    A  B   A→B
    1  1    1
    1  0    0
    0  1    1
    0  1    1

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

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

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

   A   ~A
   1   2
   2   2
   0   1

   A  B   A→B
   1  1    1
   1  2    0
   1  0    0
   2  1    0
   2  2    0
   2  0    1
   0  1    1
   0  2    1
   0  0    1

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

  A B C  (A→(B→C))→((A→B)→(A→C))
  1 1 1    1  1   1   1  1  1
  1 1 2    0  0   1   1  0  0
  1 1 0    0  0   1   1  0  0
  1 2 1    0  0   1   0  1  1
  1 2 2    0  0   1   0  1  0
  1 2 0    1  1   1   0  1  0
  1 0 1    1  1   1   0  1  1
  1 0 2    1  1   1   0  1  0
  1 0 0    1  1   1   0  1  0
  2 1 1    0  1   1   0  1  0
  2 1 2    1  0   1   0  1  0
  2 1 0    1  0   1   0  1  1
  2 2 1    1  0   1   0  1  0
  2 2 2    1  0   1   0  1  0
  2 2 0    0  1   1   0  1  1
  2 0 1    0  1   1   1  0  0
  2 0 2    0  1   1   1  0  0
  2 0 0    0  1   1   1  1  1
  0 1 1    1  1   1   1  1  1
  0 1 2    1  0   1   1  1  1
  0 1 0    1  0   1   1  1  1
  0 2 1    1  0   1   1  1  1
  0 2 2    1  0   1   1  1  1
  0 2 0    1  1   1   1  1  1
  0 0 1    1  1   1   1  1  1
  0 0 2    1  1   1   1  1  1
  0 0 0    1  1   1   1  1  1

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

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

  A  B   (~B→~A)→(A→B)
  1  1    2 0 2 1  1
  1  2    2 0 2 1  0
  1  0    1 0 2 1  0
  2  1    2 0 2 1  0
  2  2    2 0 2 1  0
  2  0    1 0 2 1  1
  0  1    2 0 1 1  1
  0  2    2 0 1 1  1
  0  0    1 1 1 1  1

これも、AとBにどのような数値を当てようとすべて1の計算になるような命題となる。この「1,2,0」という3つの値をとる関数として「~」と「→」を解釈すると、その解釈の下では公理2と公理3は常に1の値に対応する関数を表すことになる。

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

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

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

このことは、公理2と公理3から推論規則mpを使って生成される定理はすべて、上の解釈において常に値1を取るものであることを意味する。そこで、公理1がAとBの値の取り方にかかわらず、常に1という値を取るものであるかを調べてみる。

  A  B   A→(B→A)
  1  1    1  1
  1  2    0  0
  1  0    1  1
  2  1    1  0
  2  2    1  0
  2  0    0  1
  0  1    1  0
  0  2    1  1
  0  0    1  1

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

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

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


<< 構造主義における「構造」のイメージ 命題論理の公理系の構造 >>