<   2016年 08月 ( 23 )   > この月の画像一覧

仮定に含まれる命題はトートロジーである。

この記事は出典を参考にしたわけではないので誤っている可能性があるが、推論に間違いがなければ、命題論理の完全性の証明になるかもしれないと思ったので書いてみた。

ウカシェビッチの公理に仮定 A を加えて命題論理の拡張を行うと、明らかに、

A |- A

である。この時、A はトートロジーでなくてはならない。なぜなら A がトートロジーでないとすると、A のプレースホルダーには任意の命題を当てはめることができるので、恒真命題図式 T と 恒偽命題図式 I を適当に当てはめて A の真理値を偽にすることができる。こうして作られた命題を B とすると、

A |- B

から B は定理であるが、同時に恒偽命題、すなわち矛盾である。矛盾を演繹する公理系は全ての命題を証明できるので、A を含む拡張された公理系は無意味になる。従って、A がトートロジーでない時は、A を仮定として、公理系を拡張することはできない。

ところで、

|- A

の時、明らかに、

A |- A

である。従って、公理から演繹された定理は、仮定として公理を拡張できる。そこで、公理から証明される全ての定理を要素とする集合 Σ を考える。定理は全てトートロジーなので、Σ の要素もトートロジーである。また、明らかに Σ は無矛盾である。ここで命題 A が証明不可能な命題(図式)であるとする。すなわち

|-/ A

そこで、これを Σ とともに仮定に加えると、

Σ, A |- A

この時 A はトートロジーでなければならない、そうでなければ、Σ, A から矛盾が証明されるからだ。しかし Σ, A が無矛盾であれば、Σ は公理から証明可能な定理全てを集めた集合なので Σ, A = Σ である。すなわち、

Σ |- A

これから、

|- A

でなければならないので仮定と矛盾する。従って A はトートロジーではない。

この証明の特徴は証明に否定記号 ¬ を用いていないことである。従って、A がトートロジーかそれ以外かというふうに議論することができる。A がトートロジーの時、¬A は矛盾であって、トートロジー以外の命題を表しているわけではないからだ。

[PR]
by tnomura9 | 2016-08-31 07:39 | 考えるということ | Comments(0)

演繹定理と矛盾

命題論理ではウカシェビッチの公理に加えて命題の集合 Σ を仮定として取り、仮定を含む新しい公理から B が証明される時、B はΣから証明可能であると言い、次のように表記する。

Σ |- B

教科書では特にΣに含まれる命題については特に制限を述べていないが、どんな命題でもΣの要素なれるわけではない気がする。例えば、次のように公理と {A} から B が証明されたとしよう。

{A} |- B

この時 A は公理として取りあつかうことができるから、

{A} |- A

である。ところで A は特定の命題ではなく、命題図式である。すなわち A には任意の命題を置き換えることができるから。命題 ¬(p0 -> p0) と置き換えることも可能である。従って、

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

となり、{A} は矛盾していることが証明される。それでは、{ (A -> B) } についてはどうだろうか。

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

と、これもまた矛盾してしまう。従って、このような矛盾を引き起こさないためには、Σ の要素として許される命題(図式)は公理から証明された定理だけということにはならないだろうか。定理は命題図式のプレースホルダーに何を持ってきてもトートロジーであるので、矛盾を演繹することはないからだ。

演繹定理の場合も同様のことが言える。任意の命題 A について

Σ, A |- B ならば
Σ | A -> B

であるとすると、A を A -> A で置き換えることができるので、任意の命題 B が証明できることになる。すなわち A は任意の命題ではなくて、任意の定理でなければならない。完全性定理の場合、証明に演繹定理を使うので、完全性定理で公理で証明できない命題を考える場合は、命題の否定が定理になる特殊な命題ではないのだろうか。

[PR]
by tnomura9 | 2016-08-30 07:15 | 考えるということ | Comments(0)

公理図式

1. 命題論理の公理図式

次のウカシェビッチの公理は、公理図式だ。

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

公理図式の A , B, C などのプレースホルダーは原子命題を表しているのではなくて、任意の命題を置き換えることができる。なので、例えば B = C -> A を置き換えて、

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

のようなものも公理(定理)になる。またこれらの公理から A と A -> B が定理であれば、B も定理であるという前件肯定 modus pnens によって、新しい定理を作ることができる。

2. 公理図式とブール代数

この公理図式の命題は全てトートロジーであるが、上の公理では命題が提示されるのみで、それがトートロジーであることは明記されていない。しかし、命題をブール代数の式であると考えると、上の公理は次のようなブール代数の方程式に書き換えることができる。ただし、A, B, C が命題の変数であることを強調するために小文字で表している。

P1. a -> (b -> a) = 1
P2. (a -> (b -> c)) -> ((a -> b) -> (a -> c)) = 1
P3. (¬a -> ¬b) -> (a -> b) = 1

これだと公理はブール代数の方程式を表しているのと考えることができるのでずいぶん見通しが良くなってくる。ただウカシェビッチの公理では論理記号の ¬ や -> は無定義語だ。公理は、この論理記号がブール代数のような2項演算としての意味を持っているわけではない。公理の推論はあくまでも公理と前件肯定による命題の記号列変形によって行われる。しかし、その方法でも、結局ブール代数の演算規則を定理として導くことができる。

従って、厳密には上の方程式と公理図式とは意味が異なるが、ブール代数の方程式からは、式の変形で簡単に次のように新しい公式を導くことができる。

a -> (b -> a) = 1
a -> (1 -> a) = 1
a -> (a) = 1
a -> a = 1

上の式の変形で任意の命題 a について a -> a = 1 が成り立つから a -> a は定理である。

これを形式的方法で定理を求める次の方法と比べてみる。

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

この場合は前件肯定を使う時に必ず前件に定理を持ってこなくてはならない。従って、操作としては、制限されたブール代数計算と考えられないこともない。

3. 前件肯定 modus pnens とブール代数

それでは、定理の証明をブール代数の方程式の変形と捉えた時に前件肯定はどのような意味を持っているのだろうか。それは、次のような連立方程式を解くことを意味している。

(a -> (c -> a)) -> (a -> a) = 1..... (1)
a -> ((c -> a)) = 1.....(2)

(2) 式を (1) 式に代入して、

1 -> (a -> a) = 1

1 -> (a -> a) = 1 になるのは前件が 0 かまたは後件が 1 なので (a -> a) = 1。したがって、

a -> a = 1

方程式の a はどのような命題でも構わないので a -> a は定理である。

このように、公理をブール代数の方程式と捉えることで、定理の意味が見えてくる。つまり、定理とは

(a + b)^2 = a^2 + 2ab + b^2

のような数式の公式のようなものなのだ。従って、これに a = 1, b = 2 を代入したら

(1 + 2)^3 = 1 + 4 + 4 = 9

であることがわかるように、公理や定理のプレースホルダーに実際の命題 Ai を代入することで、

Ai -> (B -> Ai) から V(Ai) = T の時は V(B -> Ai) = T

を推論することができる。 このように公理から演繹される定理というトートロジーは、個々の原子命題の真理値を代入することで、推論の正当性を確かめるための道具になるのである。

4. 命題論理の意味論と統語論

完全性定理から定理とトートロジーは同値関係にあるから、論理学の定理を実際の推論に応用する場合はどちらを使っても構わない。また、トートロジー自身は実際の原子命題に対して何も語らないが、対偶の例のように推論の方法について正当性の保証された方法を提示してくれる。そのため、実際の原子命題についての論理的な推論はトートロジーによって保証された多彩な推論方法を駆使できるのである。

論理を実用的な問題に活用しようと思う場合ブール代数の考え方を使うのが便利だ。論理記号の意味付けが具体的になされており、真理値表によって機械的に確かめることができる。ブール代数や真理値表による論理の記述は論理の意味論を構築している。実際論理デバイスの設計にもブール代数は活用されている。

一方公理系によって定理を導く方法は、文法規則とウカシェビッチの公理と命題の置き換えの公理と前件肯定の公理をつかって、論理記号の意味を問うことなく、記号列の変形規則のみで定理を導く試みだ。これには命題論理をさらに抽象化してその構造のみを浮かびがらせようという意図がある。論理そのものではなく、論理の構造に焦点をあてる方法であるといえる。つまり論理への統語論的なアプローチが公理系だ。

幸いなことに、命題論理ではトートロジーと公理は同値である。つまり、論理の意味論はその記号の文法に対応しているということができる。文章でその文章の構造が厳密に意味に対応しているということは難しいが、命題論理の場合はそれが可能なのである。

[PR]
by tnomura9 | 2016-08-29 07:36 | 考えるということ | Comments(0)

含意の真理表はどうして決まるのか

1. 含意の真理値表

今、『論理学をつくる』戸田山和久著を読んでいる。分厚い本だが、教科書に書いてないことがたくさん説明してあって、なるほどそういうことだったのか目からウロコの内容が多い。その中で含意の真理値表がどうしてあのようになるのかの説明があってよくわかった。

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

前件 A が 真 の時は、B が 真 の時は A -> B が真であることは当然だし、B が 偽 の時は A -> B の含意が偽であることも納得できる。しかし A が偽の時 B が真でも偽でも A -> B が真である理由がわからない。

このように前件が偽の場合の含意 A -> B の真理値については、納得できない部分がある。しかし、前件が偽なら含意は常に真であるのは、「逆また真ならず」(つまり A -> B が真でも B -> A が真であるとは限らない)ということと、A -> B かつ B -> C が真であれば A -> C も真であるという含意の推移律が成立するためには必要な条件なのだ。

2. 含意の真理値表の自明な部分

最初に、A の真理値が T の時の含意 A -> B の真理表は次のようになる。

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

ここで、V(x) を命題 x の真理値を表す関数とすると、V(A) = T のとき V(B) = T ならば当然 V(A -> B) = T である。また V(A) = T の時 V(B) = F ならば当然 V(A -> B) = F だ。ここでは A -> B の真理値表と直感的な含意の性質とのずれはみられない。問題は次のように、前件 A について V(A) = F のときだ。

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

この時の A -> B の真理値は A -> B が満たすべき性質によって決まる。

3. 逆また真ならず

まず、A -> B の満たすべき性質として、「逆また真ならず」という推論の性質がある。つまり、A -> B が真であるからと言って必ずしも B -> A が真ではないということだ。「煙草を吸うと肺がんになる」という場合、「肺癌であるから煙草を吸う」とは言えない。肺癌であっても煙草を吸わない人がいるからだ。

そこで、V(A) = F で V(B) = T の時に「逆また真ならず」が成立するためには A -> B の真理値がどうなればよいのかを考えてみる。まず、V(A -> B) = F であると仮定すると、これは V(B) = F, V(A) = T のときの B -> A の真理値と一致する。この場合ほかのV(A), V(B) の組み合わせの場合も V(A -> B) = V(B -> A) となってしまうから、 A と B の真理値のどんな組み合わせについても A -> B と B -> A の真理値が一致してしまう。したがって、「逆また真ならず」が真理値表で表現されるためには、V(A) = F で V(B) = T の時は A -> B の真理値は T であって、B -> A の真理値とは異なっていなければならない。

4. 推移律

次に、推移律(A -> B かつ B -> C ならば A -> C) について考えてみる。つまり、

((A -> B) ∧ (B -> C)) -> (A ->C)

について、V(A) = T, V(B) = F, V(C) = F の場合を考えてみる。この時 V(A->B) = F, V(B -> C) = 不定, V(A -> C) = F である。V(B -> C) = 不定というのは B -> C の V(B) = F, V(C) = F の時の真理値が決まっていないからだ。仮にこの時 V(B -> C) = F であるとすると、上の推移律の含意の真理値は F になって、推移律が成立しないことになる。

したがって、V(B) = F, V(C) = F の時は V(B -> C) = T でなければならない。つまり、含意 A -> B について、V(A) = F, V(B) = F のときは V(A -> B) = T である。

含意で前件が偽なら後件の真偽にかかわらす含意の推論は真であるというのは、記号論理学以前から分かっていたということだが、命題論理の含意の「逆また真ならず」と「推移律」が成立するためにも必要なことだったのだ。

命題論理は教科書では数ページの解説で済んでしまうが、素人目線から「分からないことは分からない」と開き直ると色々とその豊かな内容が見えてくる。

[PR]
by tnomura9 | 2016-08-28 11:48 | 考えるということ | Comments(0)

トートロジーの意義

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 | 考えるということ | 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 | 考えるということ | 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 | 考えるということ | 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 | 考えるということ | 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 | 考えるということ | 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 | 考えるということ | Comments(0)