「エキサイト公式プラチナブロガー」スタート!

トートロジーの意義

1.トートロジーは何も語らない

複合命題は原子命題の関数と考えることができる。たとえば複合命題 A -> B は原子命題 A と B の真理値の値によってつぎの真理値表のように真か偽の値をとる。

A | B | A -> B
T | T | T
T | F | F
F | T | T
F | F | T

この真理値をもとにいろいろな推論ができる。たとえば、含意 A -> B が真のとき、A が真であれば B は必ず真である。これは前件肯定 (modus ponens) の推論が正当なものであることを示している。つまり、含意 A -> B が真であることは、原子命題の真偽値の取り方に制限をかける。論理的推論ではこのような複合命題の真偽値による単純命題の真偽値の制約を利用している。

ところが、複合命題がトートロジーの場合はこれが成り立たない。たとえば、A -> (B -> A) はトートロジーであるので真理値表は次のようになる。

A | B | B -> A | A -> (B -> A)
T | T | T | T
T | F | T | T
F | T | F | T
F | F | T | T

この真理値表から、原子命題 A と B が どのような値を取ったとしても複合命題 A -> (B -> A) の値は常に真である。また、A -> (B -> A) が真であり、A が真であっても B は真偽いずれの値もとることができる。つまり、A -> (B -> A) は何も語っていないのだ。なにも語らない恒真式に一体意味があるのだろうか。

2.トートロジーは大いに語る

たしかにトートロジーは原子命題には何の制約もかけることができない。しかし、トートロジーの部分論理式である複合命題には制約力をもっているのだ。次のトートロジーについて考えてみよう。

(¬B -> ¬A) -> (A -> B)

このトートロジーも原子命題 A や B には何の制約も及ぼさない。A が真であろうと、偽であろうと B が真偽の値を取るのに制約はない。しかし、トートロジーの部分論理式について考えると、一転このトートロジーは重要な情報を与えてくれる。すなわち、複合命題 ¬B -> ¬A が真であれば、複合命題 A -> B は真でなければならない。この対偶の推論は実際の論理的な推論にもよく使われている。

さらに、トートロジーは恒真命題である。トートロジーの論理式はそれが常に真であることが保証されているのだ。原子命題の内容によらず純粋に論理的な真値が保証されている。したがって、トートロジーの部分論理式を利用した推論は常に正当性が保証されている。原子命題の実際の真偽値によらず、純粋に論理的な真理による推論の法則をトートロジーは提供できるのだ。

つまり、トートロジーは原子命題についての推論には影響しないが、論理的推論の正当性を保証するのには絶大な力を発揮しているのである。

複合命題を原子命題の真理値の関数と考えると、2変数の原子命題のトートロジーは1つしかない。これは原子命題の数が増えても一緒で、n 変数の原子命題のトートロジーは1つしかないから、命題論理全体のトートロジーは可算個しかないことになる。

しかし、トートロジーが部分論理式の推論規則を導くと考えると、原子命題の関数として見たら一つしかないトートロジーには異なる推論規則を提供する無限の複合命題が含まれていると考えられる。これが非加算になるのかどうかはわからないが、非常にたくさんの意味のあるトートロジーが存在することを示唆している。

[PR]
# by tnomura9 | 2016-08-25 19:19 | 考えるということ | Trackback | Comments(0)

トートロジーとは何か

トートロジーとは原子命題の真偽によらず常に真となる複合命題のことだ。例えば、

A -> A

はトートロジーである。複合命題の真理値を単純命題の真理値の関数と考えると。上のトートロジーと、次のトートロジーを区別することはできない。

A ∨ ¬A

なぜなら、論理式は異なっていても、原子命題 A の真理値の値にかかわらず真になるからだ。複合命題を原子命題 A の関数と見た場合、この二つの論理式を区別することはできない。従って、トートロジーを原子命題の真理値の関数と考えた場合、その種類は、単にその論理式に含まれる原子命題の数による違いしかないと言える。

しかし、トートロジーである複合命題には違う働きがある。それは、その複合命題の部分命題の一つの真理値が決まると、他の部分命題の真理値が決まってしまうという面だ。論理的な演繹は、トートロジーのこのような性質を利用して行われる。例えば、トートロジーが A -> B という含意の形をしている時、A が偽であれば、B は常に真になる。

トートロジーをこのようにとらえる場合、トートロジーは原子命題の陰関数であるとみなすことができる。このような場合、原子命題の真理値の取り得る組み合わせが決まってくることになる。すなわち A -> B がトートロジーである時、V(x) を命題の真理値関数とすれば、(V(A), V(B)) のペアの取り得る組み合わせは V(A) = F の時、(F, T), (F, F) の二つの組み合わせに制限される。

このようなトートロジーの内部構造による原子命題どうしの真理値の関係は、同じトートロジーであっても異なる可能性がある。しかし、その場合でも、その種類は原子命題の数を n とすると 2^n を超えることはない。

複合命題は原子命題と論理記号の組み合わせで無限に作り出すことができるが、原子命題の数から眺めると。その多くは同値な命題になってしまう。このことは、公理系とトートロジーの同値関係をどうイメージするかにも関係してくるだろう。

[PR]
# by tnomura9 | 2016-08-22 07:21 | 考えるということ | Trackback | Comments(0)

定理の構造その2

定理は公理から命題の置き換えと前件肯定 (modus monens) で演繹されるので、その構造には規則性があるはずだ。そこで、まずウカシェビッチの公理系を眺めてみる。これらの公理の特徴はそれが含意 A -> B の形をしているということだ。

P1. A -> (B -> A)
P2. (A -> (B -> C)) -> ((A -> B) -> (A -> C))
P3. (¬B -> ¬A) -> (A -> B)

公理は公理図式であるので、A, B, C などのプレースホルダーは原子命題を表しているわけではなくて、任意の複合命題を置き換えることができる。従って、任意の命題でプレースホルダーを置き換えてできる命題は、定理である。このように演繹された定理は当然含意の形をしている。

そのほかに、定理は前件肯定 (modus ponens) を用いて A が定理かつ A -> B が定理なら B は定理であると演繹する。前件肯定から演繹された定理は、まず公理を用いて推論されるので、公理の後件の構造を保存している。すなわち、

P1. の後件 B -> A
P2. の後件 ((A -> B) -> (A -> C))
P3. の後件 A -> B

さらに、P2. の後件が定理の場合、これは含意の形をしているから、その後件も定理として推論される場合がある。すなわち、

P2. の後件の後件 (A -> C)

このように、公理と前件肯定によって推論された定理の構造は必ず含意になることがわかる。

このように、公理は含意の後件であることに注意しておけば、定理の証明をある程度逆算していくことができる。それは、ある命題が定理であれば、それを導くための前提条件となる含意が公理であるということになる。そこで証明したい定理から、その定理の前提条件となる定理を推定することができる。例えば、証明したい定理が、

A -> A

であったとする。その時これを後件とする定理を考えてみる。例えば、

A -> (A -> A)

は公理なので定理であるが、前件は A になる、A には任意の命題を置き換えることはできないし、前件の命題は定理であるので含意 A -> B でなければならない。従って、A -> A を後件とする定理は A -> (A -> A) ではない。そこで、任意の命題 B を使って、

(A -> B) -> (A -> A)

という命題を考えてみる。これは公理 P2 の後件だ。これが定理になるためには、P2の前件である、(A -> (B -> A))が定理でなければならないが、これは明らかに公理 P1 であるので定理だ。従って上の (A -> B) -> (A -> A) は定理である。そうであれば、前件の (A -> B) が定理であれば、後件の A -> A が定理であることがわかる。

ここで A -> B の B に置き換える命題には何の制限もない。そこで、B を C -> A という命題で置き換えてみる。すると、

A -> (C -> A)

は公理 P1 である。そこで上の定理の B を C -> A に置き換えてみると、

(A -> (C -> A)) -> (A -> A)

前件 (A -> (C -> A)) は公理 P1 すなわち定理であるから、結局 A -> A は定理であることがわかる。

このように証明したい命題からそれを後件として含む定理を求めることを、仮に定理の拡張と呼ぶことにする。

次に難解な ¬¬A -> A について考えてみる。その前に、定理の拡張をおこなるときに便利な定理を一つ証明してみる。それば、

A が定理であれば、任意の命題 B について B -> A である。

というものである。証明は簡単だ。公理 P1 から、任意の B について、

A -> (B -> A)

は定理である。また仮定から A は定理であるから、前件肯定により任意の命題 B について、

B -> A

は定理である。

さて ¬¬A -> A の証明を考えてみよう。この命題には否定演算子が含まれるので、公理 P3 が証明に含まれなければならないことは明らかだ。すなわち、命題の拡張を次のように行う。すなわち次の命題は公理 P3 から定理である。

(¬A -> ¬¬¬A) -> (¬¬A -> A)

しかしこの定理の前件は定理であるかどうかはわからない。そこで上述の拡張定理を使って、任意の命題 B を利用し次のように拡張する。

B -> ((¬A -> ¬¬¬A) -> (¬¬A -> A))

これは後件が定理(公理P2)なので任意の命題 B について定理である。これを前件とする公理 P2 を作ると次のようになる。

(B -> ((¬A -> ¬¬¬A) -> (¬¬A -> A)) -> ((B -> (¬A -> ¬¬¬A)) -> (B -> (¬¬A -> A)))

これは公理だが、前件は定理なので、

(B -> (¬A -> ¬¬¬A)) -> (B -> (¬¬A -> A))

は定理だ。そこで B を ¬¬A に置き換えると、

(¬¬A -> (¬A -> ¬¬¬A)) -> (¬¬A -> (¬¬A -> A))

この定理の前件は定理である。なぜなら、

¬A -> ((¬B -> ¬A) -> (A -> B))

は後件が定理なので、前件の命題が何であっても定理である。また、これは定理であるから P2 を利用して、

(¬A -> (¬B -> ¬A)) -> (¬A -> (A -> B))

は定理である。この前件は公理 P1 であるから結局

¬A -> (A -> B)

は定理であるからだ。従って、次の命題(上の命題の後件)は定理である。

¬¬A -> (¬¬A -> A)

これは公理 P2 によって次のような定理に変形できる。

(¬¬A -> ¬¬A) -> (¬¬A -> A)

前件は定理なので、後件の

¬¬A -> A

が定理であることが証明できた。このように命題論理の定理は、定理の拡張を行うことによって、比較的機械的に証明を求めることができる。

[PR]
# by tnomura9 | 2016-08-21 23:06 | 考えるということ | Trackback | Comments(0)

命題論理の完全性定理の説明

わかりやすい命題論理の完全性定理の説明を思いついた。証明になるのかどうかはわからないので説明としておく。

完全性定理とは、任意の命題 A について、|- A ⇔ |= A ということを証明する定理だ。すなわち、任意の命題 A が証明可能であるということと、その命題がトートロジーであるということは同値であるということだ。

|- A -> |= A の証明は簡単だ。命題 A の証明が A0, A1, ... , An(=A) であるとする。この時、証明に現れる命題 Ak は全て定理である。そこで命題の真理値関数を V(x) とおくと、任意の命題 X について、

1. 命題 X が公理ならば、V(X) = T である。
2. V(x) = T ならば V(¬X) = F である。
3. V(X -> Y) = T かつ、V(x) = T ならば V(Y) = T である。

となる。命題の証明の命題は全て公理かまたは Aj = Ai -> Ak かつ Aj ならば Ak という前件肯定 (modus ponens) によって演繹されるので。命題の証明に現れる命題に出現順に上の3つの真理値関数を適用することによって、全ての証明の命題 Ak は V(Ak) = T であることがわかる。すなわち、V(A) = T である。

|= A -> |- A の説明は次のようになる。まず公理から演繹される全ての命題の集合を Σ とする。Σは無限集合であるが、Σの要素は公理から証明された命題であり、有限の記号列なので、その証明は必ず存在する。この時、Σは無矛盾である。なぜなら、Σが矛盾していると仮定すると、全ての命題が証明可能であるためその体系は無意味であるからだ。また、A ∈ Σならば ¬A /∈ Σ かつ、¬A ∈ Σならば A /∈Σである。なぜならば A と ¬A がともに Σ の要素であれば、それから矛盾 ¬(p0 -> p0) を演繹できるので ¬(p0 -> p0) ∈ Σ となって Σは矛盾するからである。ここで任意の命題について次のような関数 V' を定義する。

A ∈ Σ -> V'(A) = T または A /∈ Σ -> V'(A) = F

この時、

V'(A) = T ならば A ∈ Σ

である。なぜなら、A /∈ Σであると仮定すると、V'(A) = F となり仮定に反するからである。ただし、これは A ∈ Σ か A /∈ Σのどちらかが成り立つという排中律が暗黙のうちに仮定されている。また、Σ の性質から、V'(x) について次の性質がわかる。

V'(A) = T ⇔ V'(¬A) = F および
V'(A -> B) = T ⇔ V'(A) = F または V'(B) = T

A が公理の時 A ∈ Σ だからウカシェビッチの公理 P について V'(P) = T である。また A が定理かつ A -> B が定理の時 B は定理だから、V’(P) は前件肯定 (modes ponens) の推論について、V'(B) = T である。これは、A ∈ Σ ならば V'(A) が V(A) と同一視できることを示している。

なぜならば、V'(x) の値は x ∈ Σ の時は T でそれ以外の時は F である。一方 V(x) の値は複合命題 x に含まれる原子命題の真偽値によってその値が決まる。しかし、公理は全てトートロジーであり、Σ の要素である命題も全てトートロジーであるので、A ∈ Σ の場合、V'(A) = V(A) = T である。

これらの条件から、

任意の命題 A について、V(A) = T ならば A は定理である

すなわち、

|= A -> |- A

である。

要するに、定理となる命題ばかりを集めた集合 Σ を考えた時、任意の命題 A について、A ∈ Σ か A /∈ Σ のどちらか一方だけが成立する。また、A ∈ Σ であれば ¬A /∈ Σ であり、¬A ∈ Σ であれば A /∈ Σ である。

ここで、A ∈ Σ の時のみ V'(A) = T となる関数 V'(A) = T を考えることができて、定理の性質から、V'(x) には V'(A) = T ⇔ V(¬A) = F および、 V'(A -> B) = T かつ V'(A) = F ならば V'(B) = T という性質がある。これは A ∈ Σ の場合 V'(x) の振る舞いが真理値関数 V(x) と一致していることを示している。すなわち A ∈ Σ ならば V(A) = V'(A) = T である。

一方 A /∈ Σ の時、¬A ∈ Σ と仮定する。すなわち、V'(¬A) = V(¬A) = T。この時 V(x) の性質から V(¬A) = T ならば V(A) = F である。従って、A が定理でなければ、V(A) = F である。すなわち、V(A) = T ならば A は定理である。

しかし、A /∈ Σ かつ ¬A /∈ Σ の時に V(A) = T ではないと言い切れるのだろうか。これが言えないと命題論理の完全性定理は 命題 A が定理なら命題 ¬A は定理ではないという至極当たり前のことしか証明していないことになるのだが .... 。おそらく誤解だろうから、もう少し教科書の証明についてよく考えないといけない。

追記

上の説明で V' は定理以外の命題に対しては F となることに注意が必要だ。V' は A が定理である時にのみ T となる。A ∨ B のようにトートロジーでないものは真偽が定まらないが、これは F になる。その意味で V' は真理値表を作るための真理値関数とは動作が異なっている。V'(x) と V(x) はそれが公理系の要素すなわち定理に対して適用された時のみ同一視できる。

追記その2

命題 A が命題でない時は、¬A が定理の時と、A と ¬A が共に定理でない場合がある。完全性定理では 命題 A が定理ではない時に ¬A が定理であると仮定し、それを定理として含む命題の集合を作っているようだ。¬A が定理でなければもともとそのような集合はできないので Σ = Φ だから、この場合も V(A) = F である。したがって、問題は起こらないということではないだろうか。

[PR]
# by tnomura9 | 2016-08-17 07:14 | 考えるということ | Trackback | Comments(0)

定理の構造

定理は公理から演繹されるので、定理の命題の構造には公理の命題の構造が反映されているはずだ。

まずウカシェビッチの公理を再掲する。

P1. A -> (B -> A)
P2. (A -> (B -> C)) -> ((A -> B) -> (A -> C))
P3. (¬B -> ¬A) -> (A -> B)

まず注目するのは、これらが公理図式であるということだ。A, B, C などのプレースホルダーには任意の命題を置き換えることができる。これらのプレースホルダーを任意の命題で置き換えたものは定理だ。したがって、定理の多くは命題の入れ子構造の再外層が3つ公理のどれかの形をしている。これらの定理が証明可能であるということは一目でわかる。

また、前件肯定 (modes ponens) の推論を用いて演繹を行うときは後件のみがのこるので、このような定理は公理の形はしていない。しかしながら、前件肯定の場合の前提条件が公理の場合の後件はつぎの3つのパターンをとる。

1. (B -> A) ........... B は任意、Aは定理
2. (A -> B) -> (A -> C) .......... A -> (B ->C) が定理
3. (A -> B) .......... (¬B -> ¬A) が定理

これらは、しかし、定理のパターンだけで定理かどうかを判別することはできない。

たとえば B -> A が定理であるかどうかだが、B は任意だから、A が定理であるかどうかが問題になる。Aが公理のパターンであれば、直ちに B -> A が定理であることが言える。Aが公理でなければ、A は定理であるが上の後件の3つのパターンのどれかになる。そうして、この作業を公理にいたるまで続けることになる。

しかし、A -> A は上の方法では定理であるかどうかを確認できない。1. B -> A のパターンに一致しているように見えるが、A は定理ではない。3. のパターンでもなさそうである。そこで、2. のパターンにあてはめることができないかどうか考える。A -> A は常に後件でなければならないので。

(A -> B) -> (A -> A)

と置いてみる。これが定理になるためには、A -> (B -> A) が定理にならなければならないが、これは公理である。したがって上のパターンは定理であることが分かる。上の含意をよく見ると後件の A -> A が定理になるためには A -> B が定理でなくてはならない。さいわい B = (A -> A) と置くと A -> (A -> A) は定理となる。したがって、上の命題を、

(A -> (A -> A)) -> (A -> A)

と置くと、A -> A は定理であることが分かる。

この記事では、木構造による探索を機械的に行うまでには至らなかったが、A -> A のようなトートロジーから直接に証明を発見するアルゴリズムは存在するような気がする。

[PR]
# by tnomura9 | 2016-08-16 19:18 | 考えるということ | Trackback | Comments(0)

命題論理の完全性定理の焦点

命題論理の完全性の定理の仕組みがもう一つわかった感じがしなかったので考えてみた。これは、出典はなく、管理人の考えなので間違っているかもしれない。

命題論理の完全性とは、A -> A のような命題が証明可能の時はトートロジーであり、トートロジーの時は証明可能であるということだ。

A -> A がトートロジーかどうかは真理値表や真理値関数で直接に計算できる。また、証明可能な命題の証明に現れる命題は全て定理であり、定理はトートロジーなのは真理値関数の性質から証明できる。従って、A -> A が証明可能であればそれがトートロジーであるのは比較的簡単にわかる。

問題は、証明可能な命題(定理)が全てトートロジーであると証明することだ。上で述べたように A -> A のような命題がトートロジーであるのは機械的な計算でわかる。また、A -> A が定理であればその証明を求めることは可能だ。しかし A ∨ B のような任意の命題が定理かどうかをどうやって判断するかは難しい。

そうであれば、証明可能な定理のみを要素とする集合が定義できれば、その集合の要素の真理値を T とする真理値関数を定義するのは簡単だろう。従って命題論理の焦点は、証明可能な定理のみを集めた集合を作る方法は何かということになる。

それでは、任意の命題 A が定理であるかどうかを判別する方法はどうすればいいのだろうか。A -> A が定理であればその証明を発見することはいつでも可能であるとしよう。しかし、命題 A が定理ではない時にそれが定理でないことを証明する方法はどうすればいいのだろうか。定理であるというのは証明という命題の列を発見すればいいが、定理でないということを証明するためにはそのような命題の列が存在しないことを証明しなければならない。幸い命題 A が定理でない時に関連する命題論理の補題がある。それは次のようなものだ。

Σ∪ {¬A} が矛盾する ⇔ Σ|- A

これから、

命題 A が定理かどうかを、Σ∪ {¬A} が矛盾するという命題に置き換えることができる。つまり命題 A が定理かどうかは、

{¬A} |- ¬(p0 -> p0)

という問題に変えることができる。命題 A が定理でない時証明がないことを証明する場合は、あらゆる可能性を考えなければいけないので選択肢が膨大になり不可能であるが、¬(p0 -> p0) の証明なら求められる。従って、{¬A} が矛盾する場合、命題 A が証明可能なので、命題 A が証明可能ではないという命題は、

{¬A} は無矛盾である

という命題に置き換えることができる。(無矛盾であるというのも否定の証明だが、{¬A} |- ¬(p0 -> p0) で無矛盾性は否定できる。)同じような判別命題を使えば命題 A0 について、

{¬A, A0} が無矛盾であることも証明可能である。この場合は ¬A と A0 が証明可能な命題となる。この操作を繰り返すことによって、¬A を含み無矛盾な命題を含む無限集合 Σ を作ることができる。

Σ = {¬A, A0, A1, A2, ... }

Σの要素は全て証明可能だから、任意の n について

|- An

である。また、この時、証明は省略するが A ∈ Σ か ¬A ∈ Σ のどちらかのみが成立する。

証明可能な命題はトートロジーだから、An もトートロジーである。この時、真理値関数 V(x) を次のように定義すると、これは命題の真理値関数の条件を満たしている。

V(A) = T ⇔ A ∈ Σ

つまり、証明可能な命題だけからなる命題の集合を作ることができたため、それがトートロジーであることを証明できるのだ。それでは、この V(x) を使って定理ではない命題 A の真理値を求めると A /∈ Σなので、

V(A) = F

となる。すなわち証明可能な定理はトートロジーである。

.... とここまで書いてきて、どうしても違和感が拭えないのに気がついた。

この証明は「証明可能な命題」という表現を単に「無矛盾な命題」に置き換えただけではないかということだ。すなわち、証明可能な命題の全体を求める明確なアルゴリズムが提示されていない。公理が決まれば、証明可能な命題は決まってくるはずだから(それは有限個の原子命題と論理記号の配列になるから)、単に「証明可能な命題の集合」Σ を考えることができる。その中に矛盾した命題があれば、それらから矛盾が証明できるはずだから、Σ は無矛盾でなくてはならない。またΣの要素 A の否定 ¬A が Σ に含まれていれば Σ は矛盾するので A ∈ Σ ならば ¬A /∈ Σ である。要は、そのような無矛盾な集合 Σ に真理関数 V を定義できることを示せば済む。そのような真理関数が命題の直接計算から得られる真理値と一致すれば、トートロジーと証明可能性の同値が証明できる。

トートロジーと証明可能性は、 例えば、A -> A という論理式が同じものを共有している。トートロジーはこの論理式の構造から証明できるが、そうであれば、証明可能性についても A -> A という命題の構造から証明できないといけないのではないかということだ。A -> A はその構造からトートロジーである。また同時に A -> A はその構造から証明可能と言えなくてはならないないのではないだろうか。この場合は当然トートロジーと証明可能性は同値である。もちろん A -> A の証明は1通りではなく無数に存在するから、それらの同値関係を考えないといけないから大変だろうが。

おそらく何かを誤解しているのだろうが、何となく、納得できない。

追記

命題 A が定理ではない場合はふた通りの場合がある。一つは ¬A が定理である場合と、A も ¬A も定理ではない場合である。完全性定理の論証は ¬A が定理である場合について行われるようだ。¬A が定理でない時、これを含む無矛盾な命題の集合は作れないので Σ = φである。すなわち、命題 A が定理でない時 V(A) = F。結局のところ 命題 A が定理でない場合は常に V(A) = F である。

[PR]
# by tnomura9 | 2016-08-15 21:20 | 考えるということ | Trackback | Comments(0)

命題論理記事リスト

命題論理記事リスト

『数学基礎論講義 不完全性定理とその発展』田中一之、鹿島亨、角田法也、菊池誠共著 日本評論社の命題論理の部分の読書ノートです。命題論理の部分だけで力尽きたので、これだけ。


[PR]
# by tnomura9 | 2016-08-14 23:11 | 考えるということのリスト | Trackback | Comments(0)

命題論理(17)

17. 命題論理の完全性定理

命題論理の完全性定理は次のようになる。

定理(命題論理の完全性定理) |- A ⇔ |= A

これは命題論理の公理系とトートロジーが同値であるということを証明している。つまり、A -> A のような命題が公理系から証明できれば、それは、トートロジーでもあるということだ。

例えば、命題 A -> A がウカシェビッチの公理と前件肯定 (modes ponens) から演繹された定理であるということは、A -> A を統語論的観点から眺めているのである。統語論的に考えるということは A の真理値か真であるか偽であるかを問わず、この命題が演繹のルールに従って記号の配列が導き出されたかどうかのみを問題にする。

一方 A -> A がトートロジーであるかどうかは、この命題の真理値を問題にする。命題の真理値は真理表や真理値関数で計算される。これは命題の記号の配列の変形規則ではなく、その命題に現れる原子命題の真理値の値によって A -> A という複合命題がどのような真理値を取るかを問題にする。これは A -> A の意味論的な検討をしていることになる。

完全性定理では A -> A のような命題が公理系で証明可能ならそれはトートロジーであり、この命題がトートロジーであれば証明可能であることを証明しなければならない。

命題 A -> A が証明可能なら、これがトートロジーであるのは簡単にわかる。まず、ウカシェビッチの公理は全てトートロジー である。

P1. A -> (B -> A)
P2. (A -> (B -> C)) -> ((A -> B) -> (A -> C))
P3. (¬B -> ¬A) -> (A -> B)

また、プレースホルダーの A, B, C には任意の命題を置き換えることができるが。その場合でも公理はトートロジーになる。さらに、前件肯定 (modes ponens) では A かつ A -> B であれば B は定理になるが、この場合も真理値関数 V(x) で真理値を求めると、V(A) = T かつ V(A -> B) = T ならば V(B) = T になる。

すなわち、 A -> A のような命題の証明が A0, A1, ... , Ak であれば、証明に現れる命題の真理値は全て T であるから、V(A -> A) = T になる。

逆に A -> A のような命題がトートロジーであることが分かっている時、これが定理であるかどうかを言うのは簡単ではない。もちろん、A -> A の場合は証明できるのが、どのような命題に対しても証明できるかどうかを抽象的に証明しないと、トートロジーと定理の同等性は主張できない。

それではどうやったらいいのだろうか。例えば、任意の命題 A が証明できない時、その真理値が F であれば、対偶から、命題 A の真理値が T ならば、A は証明可能であることがわかる。

ただし、これが成立するためには命題 A の真理値が T ならば、¬A の真理値は F であるという排中律が成り立っている必要がある。ところが A ∨ B のような命題の場合は、A と B の真理値の組み合わせ次第では真になったり偽になったりする。しかし、命題論理の完全性定理で扱う命題は全てトートロジーかその否定である恒偽命題しか現れないので問題ない。

さて、実際の完全性定理の証明に挑戦してみる。

まず任意の証明不可能な命題 A について考えてみる。これは実際はトートロジーかまたは恒偽命題だ。つまり恒に V(A) = T か V(A) = F のどちらかである。しかし、ここでは A の真理値については不定であるとする。それでは A が証明不可能な命題であるという条件から何がわかるだろうか。それは、演繹定理から派生した定理から、

{¬A} は無矛盾である。

そこでこれを Σ0 とする。すなわち、

Σ0 = {¬A}

ここで、全ての命題を順に A0, A1, A2, ... と並べておく。そうして {¬A, A0} が無矛盾の時は、Σ1 = {¬A, A0} とする。{¬A, A0} が矛盾する時は Σ1 = {¬A} とする。次に A1 について同じような操作を繰り返し無矛盾な命題のみを要素とする集合 Σn を拡大していく。すなわち、

Σ0 ⊆ Σ1 ⊆ Σ2 ⊆ ....

と拡大していく、この拡大は無限に続いていくがそれを全て集めたものを Σ と考える。Σの要素である命題は全て無矛盾である。

また任意の論理式 An に対し An ∈ Σ か ¬An ∈ Σ が言える。なぜなら Σ は無矛盾なので Σ |- An なら Σ∪ {¬An} は矛盾するし、Σ |- ¬An なら Σ∪ {An} が矛盾するからだ。

この時次のように真理値関数 V を定義する。

V(An) = T ⇔ An ∈ Σn+1

この定義と、¬A ∈ Σn+1 ⇔ A /∈ Σn+1から、

V(¬An) = T ⇔ V(An) = F

また、Am -> An ∈ Σ ⇔ ¬Am ∈ Σ または An ∈ Σから

V(Am -> An) = T ⇔ V(Am) = F または V(An) = T

が言える。この真理値関数 V(x) は x が Σの要素の時には T を Σの要素ではない時は F の値をとる。この時、証明不可能な命題 A について、V(A) = F であるから A はトートロジーではない。すなわち、

A がトートロジーであれば A は証明可能である。

ということができる。

このように、命題のトートロジーと証明可能性を結びつける規則は、演繹定理から派生した、

Σ ∪ {¬A} が矛盾する ⇔ Σ |- A

であることがわかる。つまり矛盾しない命題ばかりを集めて無限集合 Σを作り、その命題が真であることをその命題が Σ の要素であると定義してやる。すると、Σの要素はすべて証明可能な命題になるから、命題がΣの要素であるということと、命題がトートロジーであるということが1対1対応の関係になる。

また、この時真理値関数 V を命題が Σ の要素である時に真を戻すという定義をすると、命題の論理式から真理値を計算する真理値関数の定義を満たすことがわかる。

ただし、この場合命題論理の完全性定理で扱う命題 A がトートロジーかその否定であるということに注意しておかないと、混乱しそうな気がする。

この記事は厳密な証明ではなく『数学基礎論講義』田中一幸他共著 へのコメントなので一部説明を省略している部分もある。従って、正しくは原著を参照してほしい。

[PR]
# by tnomura9 | 2016-08-14 19:06 | 考えるということ | Trackback | Comments(0)

命題論理(16)

16. 矛盾

矛盾の出典は『韓非子』の故事だ。昔、楚の国に矛と盾を売る商人が、「この矛はどのような盾でも突き通すといい、盾はどのような矛でも突き通せない」と言ったところ、客の一人がその矛でその盾を突いたらどうなるのかと尋ねられて返答に窮したというものだ。

この故事から矛盾を考えると、それは両立しえない二つの命題の関係のことだ。しかし、論理学では任意の命題 P について Pかつ¬P を矛盾というと説明されている(ウィキペディア)。また『数学基礎論講義』では ¬(p0 -> P0) になっている。何れにしても原子命題のどのような真理値についても常に偽となるので、恒偽命題だ。恒偽命題が矛盾なら、トートロージーの否定は全て矛盾になるはずだが、教科書にはそうとは書かれていない。

ウカシェビッチの3つの公理からはトートロジーしか証明できないのに、なんで矛盾が発生するのだろうと不思議に思った。つまり、V(A) = T かつ V(A -> B) = T からは V(B) = T なので、前件肯定の推論ではトートロジーしか演繹できない。

しかし、矛盾は公理 P. A -> (B -> A) から簡単に発生させることができる。なぜならプレースホルダー B にはどのような命題も置き換えていいからだ。¬(p0 -> p0) は原子命題と論理記号で文法通りに作られた命題なので B と置き換えることができる。つまり、

{A} |- A -> (¬(p0 -> p0)) -> A)
{A} |- A
{A} |- ¬(p0 -> p0) -> A

ただし、普通の論理体系では矛盾が定理になることはない。つまり、

Σ |- ¬(p0 -> p0)

となることはない。もしこういうことが起きたとすると、任意の命題 A について、

Σ |- (¬A -> ¬(p0 -> p0)) -> ((p0 -> p0) -> A) .......... : P3
Σ |- (¬A -> ¬(p0 -> p0)) .......... : 後件が定理なのでこの含意も定理
Σ |- (p0 -> p0) -> A .......... : 対偶
Σ |- A

となって任意の命題が定理となる。有名な「矛盾のある論理体系では全ての命題が証明可能である」ということだ。論理体系が何かの意味を持つためには矛盾のない体系である必要がある。

¬(p0 -> p0) を演繹できる論理体系は矛盾しているが、{A, ¬A} のように命題とその否定を公理として含む体系も矛盾する。

{A, ¬A} |- ¬¬(p0 -> p0) -> ¬A .......... : ¬A は定理
{A, ¬A} |- A -> ¬(p0 -> p0) .......... : 対偶
{A, ¬A} |- ¬(p0 -> p0) .......... : Aも定理

この場合も任意の命題 B は定理となる。

{A, ¬A} |- ¬B -> ¬A ........... : ¬A は定理なので任意の前件を付け加えた含意は定理
{A, ¬A} |- A -> B .......... : 対偶
{A, ¬A} |- B

矛盾した体系からは全ての命題が証明できることのイメージはこちらの方が簡単に作れる。

矛盾についての活用範囲の多い定理が『数学基礎論講義』の補題 2.5 に紹介されている。

Σ ∪ {¬A} が矛盾する ⇔ Σ |- A

これは,

Σ ∪ {¬A} |- ¬A -> ¬(p0 -> p0)
Σ |- (p0 -> p0) -> A .......... 演繹定理より
Σ |- A

また Σ|-A ならば、Σ ∪ {¬A} からは A と ¬A の両方が証明できるので矛盾する。

これは公理系 Σ に命題 ¬A を付け加えた拡張された公理系で A が証明されるときは、もともとの公理系 Σが矛盾していることを示している。これによって、公理系 Σ が矛盾しているかどうかをテストすることができる。「真犯人はこの中にいる」のである。

これから、完全性定理の要となる次の補題が証明できる。

補題 2.6 Σが無矛盾であれば、任意の A に対し、Σ ∪ {A} か Σ ∪ {¬A} の少なくとも一方は無矛盾である。

つまり、公理系 Σ に命題 A を加えたものから命題 ¬A が証明できれば、Σは矛盾しているし、Σに 命題 ¬A を加えたものから命題 A が証明できれば、やはり Σ は矛盾している。従って、Σが無矛盾であれば命題 A かその否定 ¬A を付け加えたものの少なくとも一つは無矛盾でないといけない。

これは公理系 Σ が無矛盾であるかどうかを確かめるためのテストを提供する。

また、Σ が無矛盾であれば、命題 A かまたはその否定 ¬A を加えて無矛盾な公理を拡張することができることを示している。

この証明を見ていると、命題 A と 命題 ¬A で全ての可能性は尽くされているのかという疑問が湧いてくる。命題 A か 命題 ¬A のどちらかが成り立つという排中律が表に出ていないからだ。しかし、これは A も ¬A も証明される論理体系は矛盾しているという定理によって示されているのだろう。

命題 A か命題 ¬A のどちらが成り立つという排中律は命題の真理値を問うので意味論の問題だ。しかし、命題の記号の配列の規則のみに注目する公理系は統語論で行われる。従って、排中律も意味論と統語論では異なった表現になる。

しかし上の補題は、命題の排中律を扱ったもののように見える。命題論理の完全性を成立させる根底は排中律ではないかと思えてくる。

[PR]
# by tnomura9 | 2016-08-14 09:05 | 考えるということ | Trackback | Comments(0)

命題論理(15)

15. 演繹定理

『数学基礎論講義』では演繹定理は次のように定義されている。

定義 (演繹定理) Σ∪ {A} |- B ならば Σ|- A -> B

抽象化された定理は簡潔で美しいが、それだけでは分かりにくいので、具体的に考えるためにその内容を細かく見ていく必要がある。

まず、Σは命題の集合だ。これを具体的に {S1, S2, S3} と書くことにする。この場合Σ∪ {A} = {S1, S2, S3, A} である。また {S1, S2, S3, A} |- B というのは、公理と {S1, S2, S3, A} を合わせて一般化された公理としてこれらから前件肯定 (modus ponens) によって順番に定理 B0, B1, ..., Bk-1, B と最後に B が演繹されるための命題(定理)の列が存在するということだ。

B0, B1, ..., Bk-1, B という命題の列は、(1) 一般化された公理であるか、(2) それ以前に演繹された定理の中に、Bi 及び Bj = Bi -> Bm となる命題が存在しなければならない。このように B が証明可能ということは、k 個の定理の列 B0, B1, ..., Bk-1, B(=Bk) が存在するというとだ。つまり、上の演繹定理は任意の自然数 k について B0, B1, ..., Bk-1, Bk という証明(定理の列)に対して成立しなくてはならない。

一般にこのような任意の自然数について定理が成立することを証明するには数学的帰納法が使われる。数学的帰納法とは自然数を添え字とする命題 Ak が全ての自然数について成立することを証明する方法だ。それには次の2つの要件が成立することを証明すればよい。

(1) A0 が成立する (the base case)
(2) Ak が成立していると仮定すると Ak+1 も成立する (the recursive case)

この2つの要件が成立していれば、A0 は成立する、A0 が成立しているので A1 が成立する。A1が成立するので A2 が成立する。.... とどのような自然数 n についても An が成立すると主張できる。

そこで演繹定理について証明という定理の列が1個だけの場合を考えてみる。すなわち {S1, S2, S3, A} |- B を証明する命題の列が、B 一個だけの場合だ。これは B が ウカシェビッチの3つの公理 P1, P2, P3 か S1, S2, S3, A のどれか1個と一致する場合である。例えば

{S1, S2, S3, A} |- P2 や,
{S1, S2, S3, A} |- S2

などである。ところで、B が公理または {S1, S2, S3} に一致する時は、次の証明に公理としての A は必要ない。

B0 = B ........... Bは公理またはS1, S2, S3 のどれか
B1 = B -> (A -> B) ......... P1
B3 = A -> B ........ B1 = B0 -> B3

従って、

{S1, S2, S3} |- A -> B

また B = A の時は、A を除外した公理と {S1, S2, S3} から次の証明ができる。

B0 = A -> A
B1 = A -> B ......... A = B なので。

結局のところ命題の数を1個しか含まない証明の場合は、演繹定理は成立することがわかる。これは数学的帰納法の the base case にあたる。

次に B の証明が B0, B1, B2, ..., Bk-1, Bk(=B)

の場合を考えてみる。これは数学的帰納法の the recursive case だ。

Bk が 公理か {S1, S2, S3} の要素か A に一致する場合は、上に述べた証明の定理が1個だけの場合と同じだから演繹定理が成立するのは明らかだ。

それ以外の場合は B0, B1, ..., Bk-1 までの定理の中に Bj = Bi -> Bk となる命題 Bj (j < k) がなければならない。B0, B1, ... , Bk-1 はそういう証明が存在したらと仮定しているだけで、まだ具体的な証明を表しているわけではないが、証明が存在すれば Bj = Bi -> Bk という定理が必ず存在する。

ところで、演繹定理が Bk-1 以下で成立しているとすると、A -> Bi, A -> Bj という命題は Σ で証明可能である。そこで、A0, A1, ... , Am を Σ における A -> Bi の証明とし、Am+1, Am+2, ... , An を A -> Bj の証明であるとすると A0, A, ... , Am, Am+1, ... , An は A -> Bj の証明である。そうして、次の証明をこれに追加して A0, A1, ... , An, An+1, An+2, An+3 とするとこれは A -> Bk の証明である。

An+1 = (A -> (Bi -> Bk)) -> ((A -> Bi) -> (A -> Bk)
An+2 = (A -> Bi) -> (A -> Bk)
An+3 = A -> Bk

An+1 は公理 P2 から生成される。(A -> (Bi -> Bk)) が定理であるかどうかは直接的には示されていないが、証明 B0, B1, ... , Bk が定理を演繹する場合 Bj = Bi -> Bk という Bj が定理として演繹されていなければならない。つまり A -> (Bi -> Bk) について Bj = Bi ->Bk は定理だから A -> (Bi -> Bk) は定理である。ゆえに An+2 は定理である。また、A -> Bi が定理であるのは明らかだから結局 A -> Bk は定理である。

これは演繹定理の the recursive case を証明している。すなわち、k-1個の定理からなる証明では演繹定理が成立すると仮定した場合に k 個の定理からなる証明は演繹定理を満たすことが言えるからだ。なぜこのようなことが言えるかというと、それは、証明は演繹可能な定理を次々に並べていった命題の列であるという証明の定義からだ。この証明に現れる定理の制限が最終的な定理のあり方を束縛しているからだ。

演繹定理は非常に強力な定理で、次の ¬A -> (A -> B) の証明を見るとその意味がわかる。

{¬A, A} |- ¬B -> ¬ A
{¬A, A} |- A -> B
{¬A, A} |- A
{¬A, A} |- B
{¬A} |- A -> B
|- ¬A -> (A -> B)

演繹定理は矛盾 ¬(p0 -> p0) の性質を調べるのに活躍する。また、矛盾の概念は命題論理の完全性定理の証明のキーポイントとなる。

[PR]
# by tnomura9 | 2016-08-13 09:25 | 考えるということ | Trackback | Comments(0)