命題と命題変数

命題論理の複合命題、たとえば A -> B のような命題を構成する要素的な原子命題 A, B には2つの意味がある。一つは 「空が真っ赤だ」というような特定の命題を指し示す記号としての役割だ。A = 「空が真っ赤だ」、B = 「明日は晴れだ」の場合 A -> B は「空が真っ赤だ、ならば、明日は晴れだ」という特定の命題を表す。

一方、A, B のもう一つの意味は命題変数としての意味だ。この場合 A, B は特定の命題を表すのではなく、任意の命題をそこに置くためのプレースホルダーのような役目をする。この場合 A -> B は命題 A と 命題 B の関係性を表しているだけで特定の意味を持っているわけではない。

この2つの意味を意識的に使いこなさないと、命題論理の証明が理解できない場合がある。たとえば、命題式 A -> B は LP 公理系で証明可能だろうかという問に対してはなんと答えたら良いだろうか。A, B を命題変数と考えたら明らかに証明不可能だ。なぜならば、A -> B は次の真理表のようにトートロジーではないからだ。命題論理の完全性定理から、公理から証明できる定理はトートロジーであるからだ。

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

ところが、命題 A と 命題 B が特定の命題でその真理値が T であるとき、次の証明のように、A -> B は A, B の仮定のもとで証明可能になる。

A, B |- B
A, B |- B -> (A -> B)
A, B |- A -> B

この場合 A -> B の真理値は T である。なぜなら A, B ともに T だからだ。また、同時に仮定 A, B のもとで証明可能でもある。

それでは A -> B の A, B が命題変数であるばあいはどのように考えたら良いだろうか。この場合抽象的な命題としての A -> B はトートロジーではないので証明可能ではない。しかし、A, B に真理値が T だったり F だったりする場合に特定の命題を当てはめると証明可能な場合がある。A -> B の真理表をこの立場から再掲してみる。A, B が特定の命題であることをはっきりさせるために a, b と小文字で表示することにする。

a | b | ~a | ~b | a -> b | ~(a -> b)
T | T | F | T | T | *
T | F | F | T | * | T
F | T | T | F | T | *
F | F | T | T | T | *

a, b が共に T のときはこれを仮定すると a -> b が次のように証明できる。

a, b |- b
a, b |- b -> (a -> b)
a, b |- a -> b

a が F で b が T のときは a の仮定を ~a に置き換えると ~a は T なので a -> b が証明できる。

~a, b |- b
~a, b |- b -> (a -> b)
~a, b |- a -> b

a が F で b が F のときは a の仮定を ~a, b の仮定を ~ b で置き換えると a -> b が証明できる。

~a, ~b |- ~a
~a, ~b |- ~b
~a, ~b |- ~b -> ~ a
~a, ~b |- a -> b

a が T で b が F のときは a -> b は F になるので b の仮定を ~b に置き換え a -> b の結論を ~(a -> b) に置き換えると ~(a -> b) が証明できる。

a, ~b |- a
a, ~b |- ~b
a, ~b |- a ∧ ~b
a, ~b |- ~(a -> b)

ここで次のような表記を導入する。a' は a が T のとき a' = a で a が F のとき a' = ~a、b' は b が T のとき b' = b で b が F のとき b' = ~b、A = a -> b として A が T のとき A' = A で A が F のとき A' = ~A。

そうすると上の4つの関係は a' b' |- A' とまとめることができる。普通の仮定と証明の関係に似た記述だが、単一の証明を表しているのではなく上の4つのような場合の証明をまとめて表現しているので注意が必要だ。しかし、このことは、どのような論理式でもそれを証明する仮定の組み合わせを見つけることができることを示している。まるで魔法のようだが、再帰的に証明ができる。

詳しい証明は参考書を見てほしいが、これを仮定すると命題論理の完全性の証明は簡単だ。トートロジー A の要素命題を q1, q2, q3, ... , qm とすると上の表記で次のようになる。

q1',q2',q3', ... , qm' |- A'

ここで、qm が T の場合と F の場合を取り出すと、A' はトートロジーなのでつねに A' = A だ。したがって、

q1', q2', q3', ... , qm |- A
q1', q2', q3', ... , ~qm |- A

なので演繹定理から、

q1', q2', q3', ... , qm-1' |- qm -> A
q1', q2', q3', ... , qm-1' |- ~qm -> A

が証明され、詳細は省くがこのことから

q1', q2', q3', ... , qm-1' |- A

が証明されて qm の仮説が抜けてしまう。これを繰り返すことで、結局 A がトートロジーならば、

|- A

となって A は証明可能であることが分かる。

こんな証明を思いつく人は頭の中が想像もつかないことになっているに違いない。

[PR]
by tnomura9 | 2017-09-12 03:23 | ラッセルのパラドックス | Comments(0)
<< 原子命題と論理式 二項関係の真理表 >>