量化命題の脱カプセル化

全称命題 ∀x.A(x) はそのままでは量化子にカプセル化された命題 A(x) を利用できない。そのため、∀x.(A(x) -> B(x)), A(a) という仮定があってもそのままでは演繹ができない。A(x) -> B(x) を何らかの手段で取り出す必要がある。

全称命題 ∀x.A(x) の真理値が T のときは、領域 D の全ての x について A(x) が T であるから A(x) はトートロジーである。一階述語論理の完全性定理から同時に定理でもある。従って、∀x.A(x) が仮定あるいは定理のとき、カプセルの中身の A(x) も定理である。すなわち、次の証明が可能だ。

|- ∀x.A(x)
|- A(x)

A(x) が定理であれば対象変数 x にどのような対象をとっても、命題 A(a) は真である。これを利用すると、∀x.(A(x) -> B(x)) と A(a) という仮定からつぎのように B(a) を証明することができる。

|- ∀x.(A(x) -> B(x))
|- A(a)
|- A(x) -> B(x)
|- A(a) -> B(a)
|- B(a)

それでは存在命題 ∃x.A(x) の場合はどうだろうか。これは A(x) の真理値を T とするような領域 D の対象が少なくとも1つ存在していることを示している。つまり、∃x.A(x) が定理のとき A(a) も定理となる。この場合 a は領域 D の特定の要素である。

|- ∃x.A(x)
|- A(a)

このとき

|- ∀x.~A(x) (仮定)
|- ~A(x)
|- ~A(a)
|- A(a) と ~ A(a) が同時に証明可能なので矛盾する

ゆえに

|- ~∀x.~A(x)
|- ∃x.A(x) -> ~∀x.~A(x)

このように、全称命題と存在命題は一階述語論理の次の2つのルールで脱カプセル化できる。

∀x.A(x) -> A(x) ...... 全称特例化 ( universal instantiation )
∃x.A(x) -> A(a) ...... 存在特例化 ( existential instantiation )

逆もできる

A(x) (が定理ならば) -> ∀x.A(x) ...... 全称一般化 ( universal generalization )
A(a) -> ∃x.A(x) ...... 存在一般化 ( existential generalization )

量化命題の脱カプセル化という視点を持つことで、一階述語論理の議論を命題論理の問題として考えることができる。

[PR]
# by tnomura9 | 2017-09-19 00:27 | ラッセルのパラドックス | Comments(0)

全称命題はメタ命題

領域 D の対象が a, b, c, ... で命題が A, B, C, ... のとき命題は対象と述語のペア A(a) で表される。対象を変数 x で表した A(x) は命題関数だが x に置き換える対象が変われば真理値が変るので、命題論理の命題変数とみなす事ができる。A(x) が T になる対象を集めた集合 A* は述語 A の真理集合だ。

A(x) ∧ B(x) のような命題変数を論理結合子で結合した論理式の真理集合は A* ∩ B* のように真理集合の集合演算となる。また、真理集合の集合演算の値は領域 D の部分集合だ。つまり、領域 D の命題に関する論理的な操作は領域 D の冪集合の集合演算として全て表現することができる。命題 A(x) と真理集合 A* を同一視すれば、領域 D の論理的な操作は、領域 D の冪集合の集合演算として捉えることができる。

非常に分かりやすいモデルだが、全称命題 ∀x.A(x) はこの枠組にはいらない。∀x.A(x) は確かに真理値を持つので命題ではあるが、その真理値は A(x) がトートロジーのとき T となり、そうでないとき F となる、命題の性質を表すメタ命題であるからだ。

例えば A(x) -> B(x) の真理表は次のようになる。

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

この真理表では A(x) -> B(x) はトートロジーではないので ∀x.(A(x) -> B(x)) の真理値は F だ。一方 A(x) の真理集合 A* と B(x) の真理集合 B* の間に A* ⊂ B* という包含関係があるときは、x ∈ A* ならば x ∈ B* なので A(x) が T なら B(x) が F となることはないので真理表は次のようになる。

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

この場合 A(x) -> B(x) はトートロジーになるので ∀x.(A(x) -> B(x)) の真理値は T だ。もちろんこれも真理値をとる命題なので A(x) ∧ ∀x.(A(x) -> B(x)) のように論理結合子で結合することができる。しかし、この論理式から直接にB(x) を演繹することはできない。演繹は ∀x.(A(x) -> B(x)) が真のとき A(x) -> B(x) がトートロジーであることを利用するので真理表は次のようになる。

A(x) | ∀x.(A(x) -> B(x)) | A(x) -> B(x) | B(x)
T | T | T | T
T | F | * | *
F | T | T | *
F | F | * | *

つまり、A(x) と ∀x.(A(x) -> B(x)) が共に T のときは B(x) も T で、それ以外では B(x) の真理値は不定だ。従って「ソクラテスが哲学者ならソクラテスは人間であるという推論は次のようになる。

|- ∀x.(A(x) -> B(x))
|- A(x) -> B(x)
|- A(a) -> B(a)
|- A(a)
|- B(a)

∀x.P(x) ならば P(x) を推論規則とすると、A(x) -> B(x) は定理である。A(x) -> B(x) は定理なので A(a) -> B(a) も定理である。A(a) は仮定であるので、modus ponens の推論規則から B(a) は定理である。

全称命題の中の論理式を使う推論はそのままでは論理演算は利用できない。そのため、全称命題がメタ命題であることを意識して、中の論理式がトートロジーであることを利用して推論を行わないといけない。

全称命題がメタ命題であることをはっきりと意識すると、命題論理の推論の見通しが良くなるのではないだろうか。


[PR]
# by tnomura9 | 2017-09-18 09:24 | ラッセルのパラドックス | Comments(0)

LQ 公理系の推論規則がなんか変

LQ 公理系の推論規則に C -> A ならば C -> ∀x.A というのがあるが、なんとなく納得できなかった。C -> A がトートロジーであっても C が F であれば A は T の値も F の値もとれるので、∀x.A すなわち A はいつも T とは言えない。そこで次のように真理表を作ってみた。

C | A | ∀x.A | C -> A | C -> ∀x.A | (C -> A) -> (C -> Ax.A)
T | T | F | T | F | F
T | F | F | F | F | T
F | T | F | T | T | T
F | F | F | T | T | T

この真理表は領域 D について A の真理値が T の場合も F の場合もある時のものだ。この場合当然 ∀x.A の真理値は F だ。しかし C -> A が定理だとすると、この場合 C -> A が F となることはありえないので、真理表は次のようにならないといけない。

C | A | ∀x.A | C -> A | C -> ∀x.A | (C -> A) -> (C -> ∀x.A)
T | T | F | T | F | F
F | T | F | T | T | T
F | F | F | T | T | T

しかし、この場合でも C と A が共に T の場合 (C -> A) -> (C -> ∀x.A) の真理値は F になってしまう。つまり、どう考えても (C -> A) -> (C -> ∀x.A) はトートロジーにはならないのだ。実際、対象 a について C(a) と A(a) の真理値が共に T であっても、領域 D 全体を見たとき、A(b) が F になるような対象 b があったときは ∀x.A の真理値は F である。もっとも、NQ の自然演繹では、

A ならば ∀x.A

であるがこれは納得できる。A が常に T であれば当然領域 D の全ての対象 x について A の真理値は T である。したがって A が常に真なら ∀x.A の真理値は T だ。しかし、これと (C -> A) -> (C -> ∀x.A) とでは話が違う。どうしてもこのような推論をしたいのなら、C, C -> A ならば C -> ∀x.A ではないのだろうか。しかし、それであれば推論規則は NQ のように、

A ならば ∀x.A

とすべきなのではないだろうか。

全称命題の真理表については以前の記事に書いたが、量化子のつく命題の真理値のパターンによって真理値を真理表上に決めることができる。ただ、その命題の真理値の現れ方にしたがって、T も F もあらわれる場合、T のみの場合、F のみの場合と3つの真理表をつくらなければならない。このように3つの真理表を作った場合でも、2つの命題の真理値がどの真理表の場合も一致すればそれらは同値ということができる。例として ∀x.A と ~∃x.~A が同値であることを次に示す。

A | ~A | ∀x.A | ~∃x.~A
T | F | F | F
F | T | F | F

A | ~A | ∀x.A | ~∃x.~A
T | F | T | T

A | ~A | ∀x.A | ~∃x.~A
F | T | F | F

C -> A ならば C -> ∀x.A という推論規則を適用した証明では C も定理の場合は問題ないのだろうが、やっぱりなんか変。


[PR]
# by tnomura9 | 2017-09-18 02:03 | ラッセルのパラドックス | Comments(0)

わかりやすい命題論理の完全性定理

A -> B のような論理式の真偽は要素命題 A, B に真理値を割り当てることによって真偽が判別できる。そのなかでも A -> (B -> A) のような論理式は、A, Bにどんな真理値を割り当てても常に真になり、トートロジーと呼ばれる。

ある論理式がトートロジーであるかどうかを見極めるには、要素命題に起こり得る真理値をすべて割り当てた時の論理式の真理値を確かめなければならない。その操作をシステム的に行うのが真理表だ。A -> (B -> C) のような命題がトートロジーであるかどうかは、真理表をつくることによってその意味を確認しなければならないから、これは論理式に対する意味論的なアプローチだ。

一方、論理式についての分析は要素命題に真理値をわりあてる方法とは別に、公理と推論規則によって演繹した論理式が定理になるという方法がある。これは要素命題や命題結合子を文法規則によって並べた論理式について、公理と推論規則によって演繹できるものを定理として特別視する。つまり、論理式は命題論理の文法規則に従っていれば自由に作ることができるが、それらの中でも定理と呼ばれるものは公理と演繹規則というルールをもとに演繹されたものでないといけない。

この方法では、要素命題 A, B の真偽は問わない。演繹規則によって演繹された論理式を次々に作っていき、それによって目的の論理式を作り出すことができれば、それは定理となる。論理式が定理であるかどうかを文法と演繹規則によってのみ判別するので、この方法は論理式に対する構文論的なアプローチだ。

命題論理の完全性定理では、これらの論理式の意味論的なトートロジーと構文論的な定理が同値であることを主張している。つまりある論理式がトートロジーであればそれは定理であり、それが定理であればトートロジーであると主張する。これは、トートロジーの定義と公理系の定理の定義が質的に異なっているため必ずしも自明ではない。

ところで、命題論理の完全性定理とプログラミングには関連性がある。コンピュータのプログラミングではアプリケーションのプログラムを作ったとしてもそれを実行ファイルにコンパイルしないと動かない。つまり、コンピュータのプログラムは命題論理の論理式にあたり、実行ファイルは命題論理の真理値表の真理値にあたる。コンピュータのプログラムについても、プログラムの統語論的なアプローチと、その実行ファイルとしての意味論的なアプローチが必要になる。

一般的に、プログラミングで作成したプログラムがきちんと動作するかどうかはそれを実行してデバッグしなくては分からない。プログラムでは動くと思っていたのに、実際にはそのプログラムが実は無限ループであったり、不正なメモリのアクセスを行ってしまっていてエラーになってしまうということがよくあるからだ。デバッグの際には起こり得る様々な可能性を考えてテストしないと、プログラムを運用するために思っても見なかったエラーが発生してしまう事がある。これはプログラムに対する意味論的なアプローチである。

他方でプログラムは実行ファイルを作成する前にプログラム言語の文法に従ってテキストファイルとして作成される。プログラムが完成しても、それはコンパイルされない限り実行できないのでただの文字列である。この意味でプログラムのソースの作成はプログラムについての統語論的なアプローチだ。

コンピュータのプログラムではこのようにプログラムのソースが適正であっても、コンパイルした実行ファイルがきちんと動くとは限らない。きちんと動くかどうかは実行ファイルをテストしてバグがないかどうかを調べなくてはならない。コンピュータのプログラムではプログラムの統語論的な意味と、実行ファイルの意味論的な意味が厳密は対応していない場合があるからだ。また、実行ファイルのデバッグは、ソースファイルの作成以上に労力がかかる事が多い。起こりえる全ての可能性についてテストしないとエラーが起きないと断定できないからだ。ソースファイルを作成した時点で、そのソースが意味論的にもエラーを含まなければ、プログラムの作成の労力の殆どがソースファイルの作成で住んでしまうので効率的だ。

命題論理では論理式についての意味論的なアプローチと統語論的なアプローチが同値であることを証明している。コンピュータのプログラムで言えば、ソースプログラムが適正なら、それは必ず実行時にエラーを起こさないことを意味している。

それでは命題論理において、意味論的なアプローチと統語論的なアプローチが同値であることはどのようにしてわかるのだろうか。それを証明するのが命題論理の完全性定理だ。

先ず、論理式への統語論的なアプローチで定理とされた論理式が全てトートロジーであるのは理解しやすい。公理系の公理は全てトートロジーであるので、公理の命題の要素命題をどのような論理式で置き換えても、定理がトートロジーであることに変わりはない。また、2つの定理に推論規則 modes ponens を適用して得られる論理式もトートロジーになる。たとえば、A -> B がトートロジーで A がトートロジーのとき、B の真理値は必ず真になるのでトートロジーになる。

反対にトートロジーであるとわかっている論理式が公理系で演繹された定理であるということは簡単には言えない。論理式がトートロジーであるということが分かっていても、それが公理と推論規則で演繹された定理であるということをいうのは難しいからだ。命題論理の証明で躓くのはこのトートロジーならば定理であるという部分の証明だ。

この記事の範囲でこの証明を全て紹介するのは難しい、詳細はやはり参考書を読んで理解する必要がある。しかし、この記事では、この意味論的なアプローチが統語論的なアプローチでも定理であるという証明のアイディアの概観を述べてみたい。何をやっているかという意図が分かって証明を読むのと、それがわからずに手探りで理解していくのは随分と効率が違うからだ。

まず、適当に選んだ論理式の真理表からそれに関連する命題論理の証明があることが保証されていることを示す。論理式の例としては A -> B を用いる。最初に A -> B の真理表を作る。

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

これを作るのは簡単だ。そこで、これを LP 系の証明に変換することを考えてみる。それは次のようになる。

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

この4つの証明の作り方は簡単だ、上の真理表で要素命題 A の真理値が T のときは仮定を A とし、偽のときは ~A を仮定にとる。要素命題 B についても同様だ。また、論理式 A -> B についてもそれが真のときは A -> B とし、偽のときは ~(A -> B) とする。要するに真理表を公理系の証明に置き換えただけだ。うれしいことに、こうして作った証明は全て LP 公理系で証明可能であることが証明されている。再帰的に証明された証明の詳細については参考書を参照して欲しい。要は論理式の真理表から逐語的に公理系の証明に置き換えることができるということだ。

この証明では要素命題 A, B の真理値については考慮されていない。公理系による証明では記号の配列のみが問題にされるので、たとえ A, B |- A -> B の仮定 A の真理値が偽であってもこの証明は正当なものである。

そこで、トートロジー A -> (B -> A) についてこのような証明を作成してみる。

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

A -> (B -> A) はトートロジーなので仮定が A, ~A, B, ~ B のどれであってもおなじ論理式 A -> (B -> A) の証明が存在する。

ここで、演繹定理を用いて仮定 B または ~B を |- の右に移してみる。

A |- B -> (A -> (B -> A))
A |- ~B -> (A -> (B -> A))
~A |- B -> (A -> (B -> A))
~A |- ~B -> (A -> (B -> A))

この4つの証明は全て正当な証明だから、命題論理の定理 (A -> B) -> ((~A -> B) -> B)) を適用すると、

A |- A -> (B -> A)
~A |- A -> (B -> A)

と仮定の B が抜けてしまう。これにさらに演繹定理と上の定理を適用すると、

|- A -> (B -> A)

となり A -> (B -> A) が仮定のない定理であることが証明される。すなわち、トートロジー A -> (B -> A) は LP 公理系で証明可能な定理である事がわかる。また、A -> (B -> A) 以外のどのようなトートロジーについても同様な証明で LP 公理系で証明可能な定理であることを証明することができる。

数学の証明は一般的に記述するため、アイディアの骨子が見えにくいことが多い。参考書の分かりにくい完全性定理についての証明も上のようなイメージで読み解いていくと理解しやすい。

命題論理では統語論的に作成された論理式はすべてトートロジーである。Haskell の場合も文法チェックをパスしたプログラムは原則的にはすべて実行可能だ。このように統語論と意味論が同値な言語はデバッグの時間を短縮し、プログラムの生産性を飛躍的に上げることができる。

[PR]
# by tnomura9 | 2017-09-17 10:00 | ラッセルのパラドックス | Comments(0)

公理系と真理表

公理系と真理表の関係が思ったより直接的だったので対照させてみた。含意 A -> B の真理表は次のようになる。

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

これに対応する LP 公理系の証明は次のようになる。個々の証明については前回の記事で紹介した。

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

仮定が A, ~B のときは結論が ~(A -> B) と否定形になっているところも、真理表に対応しているのが分かる。命題論理の完全性定理から当然なのだろうけれど、真理表が公理系で表現できるというのが不思議に思える。実はこの公理系の真理表で A が真値を持つかどうかは証明には関係ない。公理系の推論は命題の真偽ではなく、命題の記号の配列を推論の規則によって置き換えていくだけだからだ。したがって、A, B |- A -> B の証明で A の真理値が偽であったとしてもその証明は正当なものである。

ところで、この公理系の真理表について、仮定が ~A, B と ~A, ~B の場合を考えてみるが、演繹定理を使って次のように変形してみる。

~A |- B -> (A -> B)
~A |- ~B -> (A -> B)

これに命題論理の定理 (A -> B) -> ((~A -> B) -> B) を適用すると、

~A |- A -> B
~A |- A -> B

となって、仮定が ~A のときは仮定 B はなくても良くなり、抜け落ちることが分かる。A -> (B -> A) のように論理式がトートロジーの場合はどうなるだろうか。A -> (B -> A) の公理系での真理表はつぎのようになる。

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

A -> (B -> A) は公理だから別に証明をしなくても上の証明は成立する。このとき A -> B で述べた定理を使うと、

A |- B -> (A -> (B -> A))
~A |- ~B -> (A -> (B -> A))

から仮定 B が抜け落ちて、

A |- A -> (B -> A)
~A |- A -> (B -> A)

となり、さらに、

|- A -> (A -> (B -> A))
|- ~A -> (A -> (B -> A))

から、仮定 A も抜け落ちて、

|- A -> (B -> A)

となり結局のところトートロジーは仮定なしの公理系から証明可能である事が分かる。

この命題論理の完全性定理で重要な働きをするのが、

|- (A -> B) -> ((~A -> B) -> B)

という定理だが、つぎのように証明できる。

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

トートロジーは真理表で要素命題に真理値を割り当てた時の論理式の真理値だし、LP 公理系の証明は、公理と推論規則 modes ponens から演繹された論理式だが、両者は意外に対応関係がつけやすいことが分かる。

[PR]
# by tnomura9 | 2017-09-16 00:52 | ラッセルのパラドックス | Comments(0)

原子命題と論理式

命題論理ではそれ以上分解できない最も簡単な命題を原子命題といい A, B, C, ... で表す。一方 A -> B のように原子命題を命題結合子で結合した複合命題を論理式と呼ぶ。前回は任意の論理式、たとえば、A -> B のようなものが、原子命題に真理値を割り当ててそれを仮定すると、命題論理の公理系 LP で証明可能であることを示した。適当に作った A -> (B -> A) のような論理式がどれも LP 公理系で仮定 A, B から証明可能であるというのは不思議な感じがする。この不思議な現象の秘密の元は何なのだろうか。おそらく、それは LP 公理系そのものに潜んでいるのだろう。

LP では次のウカシェビッチの3つの公理と、A が定理で A -> B が定理なら B も定理であるという推論規則 modus ponens から次々に定理を紡ぎだしていく。次のウカシェビッチの公理はいずれも、真理表ではトートロジーになる。

A -> (B -> A)
A -> (B -> C) -> ((A -> B) -> (A -> C))
(~B -> ~A) -> (A -> B)

また modes ponens で推論する場合 A がトートロジーで A -> B がトートロジーであれば B もやはりトートロジーになる。

したがって、LP 公理系で紡ぎだされた定理はトートロジーになることは自明である。完全性定理では逆に任意の論理式がトートロジーであればそれは LP 公理系で証明可能であることを証明している。しかし、任意のトートロジーである論理式が証明可能であることをどうやって証明すればいいのだろうか。このあたりが命題論理の完全性定理の理解で苦戦するところだ。

それを解決するために A -> B のような論理式について考えてみる。論理式は論理式の文法規則によって原子命題と命題結合しを配列したものである。また、真理表は原子命題の真理値によって論理式の真理値を計算することができる。したがって、原子命題 A と原子命題 B の真理値が真である場合は、これを LP 公理系の仮定として採用することで、論理式を演繹することができる。この過程の下で任意の論理式を演繹できればよいのだ。例えば A と B が真であったとするとこれを仮定として採用して次のように様々な論理式が演繹できる。

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

しかし、A, B が真であるという仮定からは ~A は演繹できない。なぜなら ~A は偽であるので、LP 公理系では A が真であるという仮定からは演繹できないからだ。

幸いなことに A, B のとり得る真理値は真のみではない、A が偽で B が真の場合もある。この場合には ~A が真となるので仮定は ~A, B を採用することになる。この場合には次のように ~A が真である演繹が公理系でできる。

~A, B |- ~A

しかし、この公理系では最初の公理系とは仮定が異なっているので同じラインで論じることはできない。たとえば、最初の仮定では A が証明可能だが、~A は証明可能ではない。また2番目の仮定からは ~A は証明可能だが A は証明可能ではない。しかし、仮定が A の場合でも ~~A は証明可能である。さらに、原子命題 A, B についてさらにつぎのような2つの異なる仮定の公理系を作ることができる。

A, ~B |- ~B
~A, ~B |- ~A -> ~B

このように原子命題 A, B の真理値によって4種類の異なる仮定の LP 公理系を作ることができる。この場合に注意しなくてはならないのはどの場合でも仮定の命題の真理値は真であるということだ。これは modes ponens の前提の命題はトートロジーでなくてはならないからだ。

原子命題 A, B の真理値によって仮定を変えることで様々な論理式を演繹できることが分かったが、問題は、この方法でどんな論理式でも証明できるような仮定を見つけることができるかということだ。幸いなことにそれは可能だ。論理式には文法があり、その文法に従わないものは論理式ではない。たとえば ~A は論理式だが A~ は論理式ではない。また A -> B は論理式だが、A B -> は論理式ではない。論理式とは、A の形のスキーマ、すなわち A を命題変数と考え、そこに任意の論理式を代入した肯定形のものか、~A の 形のスキーマ、すなわち、A を命題変数と考え、そこに任意の命題を代入した否定形か、A -> B の形のスキーマ、すなわち、A と B を命題変数と考えそこに任意の命題を代入した含意か3つのパターンをとるということだ。そうであれば、A、~A 、A -> B の3つのパータンを上の4つの仮定で演繹できれば任意の論理式の演繹が4つの仮定のもとで証明できることになる。

まず A だが、これは A が真であるという仮定を採用すると、

A |- A

で証明可能である。

また、~A は A が偽であるという仮定の下で、

~A |- ~A

で証明可能だ。ただし、~(~A) は ~A からは演繹できない。しかし、これは A から演繹可能である。

A |- ~(~A)

このことから、否定形の論理式は ~(~(~(...(~A)))) のどの形の論理式も A か ~A の仮定から演繹可能である。

A -> B の場合は B と ~A の二つの仮定のもとで証明可能である。

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

~A |-> ~A
~A |-> ~A -> (~B -> ~A)
~A |-> ~B -> ~A
~A |-> A -> B

ただし、A -> B は A, ~B からは演繹できない。なぜなら ~A はこの仮定では演繹不可能だからだ。しかし、次のように ~(A -> B) は演繹可能である。

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

したがって、原子命題 A, B の可能な組み合わせについて A -> B または ~(A -> B) は証明可能である。これと ~A についての結果を組み合わせると、任意の論理式 Q について、Q または ~Q はその要素命題の真理値に応じて選んだ仮定によって演繹可能であることが分かる。

任意の論理式を要素命題の仮定から演繹できる仕組みは、LP 公理系そのものに備わっていたのだ。


追記

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


[PR]
# by tnomura9 | 2017-09-14 02:03 | ラッセルのパラドックス | Comments(0)

命題と命題変数

命題論理の複合命題、たとえば 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)

二項関係の真理表

領域 D の対象が a, b, c, ... で述語が A, B, C, ... のとき、A(a) は命題を表し、命題関数 A(x) は命題論理で言う命題変数を表すと考えることができる。従って、A(x)、B(x) を命題変数と考えると、A(x) -> B(x) という含意の真理表を次のように作ることができる。

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

A が述語の場合、A(x) のアリティ(項数)が1であるので全称命題 ∀x.(A(x) -> B(x)) の真理表も次のように作ることができる。

A(x) | B(x) | A(x) -> B(x) | ∀x.(A(x) -> B(x))
T | T | T | F
T | F | F | F
F | T | T | F
F | T | T | F

全称命題 ∀x.(A(x) -> B(x)) については、その真理値は要素的な命題 A(x), B(x) の真理値によって決まるのではなく、量化子のつけられた A(x) -> B(x) の真理値のパターンが領域 D でどうなるかということで決まる。領域 D について、A(x) -> B(x) の真理値が T にも F にもなり得るときは ∀x.(A(x) -> B(x)) の真理値は F で、A(x) -> B(x) の真理値が常に T のときは ∀x.(A(x) -> B(x)) の真理値は T である。

ところで、全称命題の真理表の議論は述語 A が1変数関数(アリティが1)だったが、2項関係のように2変数関数の場合には真理表が作れるのだろうか。それが、作れるのだ。例えば、述語 A の命題関数が A(x) という1変数関数で、2項関係 B の命題関数が B(x, y) だったとする。すると A(x) -> B(x,y) の含意の真理表は次のようになる。

A(x) | B(x, y) | A(x) -> B(x, y) |
T | T | T
T | F | F
F | T | F
F | F | F

A(x) は述語で、B(x,y) は2項関係であるが、どちらも領域 D の対象を A(a) や B(c,d) のように割り当てることによって真理値を求めることができるから、上のような真理表をつくることが可能だ。

それではこの場合の全称命題はどのように表現できるだろうか。例として、∀x∀y.(A(x) -> B(x,y)) の真理表を作ってみる。

A(x) | B(x, y) | A(x) -> B(x, y) | ∀x∀y.(A(x) -> B(x, y))
T | T | T | F
T | F | F | F
F | T | T | F
F | F | T | F

これは領域 D の任意の対象から A(a), B(c,d) という命題を作ったとき、A(a) -> B(c,d) が T になったり F になったりするときは ∀x∀y.(A(x) -> B(x,y)) の真理値は F になることを示している。例えば、領域 D が自然数の場合

A(x) : x = 2
B(x, y) : x * y = y

のときは、A(2) = T のとき、B(2, 0) = T であるから、A(2) -> B(2, 0) = T であるが A(2) のとき B(2, 1) = F であるから A(2) -> B(2,1) = F である。すなわち、命題 A(x) -> B(x, y) は領域 D について T にも F にもなるので ∀x∀y.(A(x) -> B(x,y)) の真理値は F である。

それでは、次のような場合はどうだろうか。

A(x) : x = 1
B(x, y) : x * y = y

この場合 A(x) = T のときは x = 1 しかありえない。このときは B(1, y) : 1 * y = y であるので、全ての y について B(x, y) = T である。従って、A(x) = T のときは B(x, y) = F はありえないので、真理表は次のようになる。

A(x) | B(x, y) | A(x) -> B(x, y) | ∀x∀y.(A(x) -> B(x, y))
T | T | T | T
F | T | T | T
F | F | T | T

どんな自然数 x, y を持ってきても A(x) = T すなわち x = 1 のときは必ず B(x, y) = T となるから、A(x) -> B(x, y) の真理値はどんな場合でも T である。したがって、∀x∀y.(A(x) -> B(x, y)) の真理値は T となる事がわかる。

このように、述語 A(x) だけでなく、2項関係についても真理表による分析が可能であることが分かる。

[PR]
# by tnomura9 | 2017-09-07 05:43 | ラッセルのパラドックス | Comments(0)

全称命題の真理表

命題論理では含意の真理表は次のようになる。

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

A や B は特定の命題を表しているのではないのでこれらは命題変数と呼ばれる。従って、真理表では含意 A -> B の真偽は原子命題 A と B の真理値の組み合わせで決まる。

ところで、領域 D についての命題は領域 D の対象 a, b, c, ... と述語 A, B, C, ... の組み合わせ、たとえば A(a) で表せる。また対象の部分を変数にした A(x) は命題関数とよばれ、領域 D の対象を引数にとり、命題を返す。命題関数 A(x) を別の見方からみると、これは領域 D の対象と述語 A で作られる全ての命題を表しているとも考えられる。これは、上の命題論理の命題変数と同じ意味であつかう事ができる。従って、一階述語論理の含意の真理表はつぎのように作ることができる。

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

この真理表の作り方は、命題論理の真理表と全く変ることはない。命題変数 A(x) は領域 D について真の場合も偽の場合もあり、命題変数 B(x) についても同様だ。

しかし、一階述語論理には量化子を使った命題がある。たとえば、∀x.(P(x) -> Q(x)) のような全称命題だ。このばあい全称命題 ∀x.(A(x) -> B(x)) の真理値は、領域 D の全ての対象についての命題変数 A(x) -> B(x) の真理値のパターンによって決まる。すなわち、A(x) -> B(x) の真理値が領域 D の中で T でも F でも取ることができるときは ∀x.(A(x) -> B(x)) の真理値は F である。したがって、全称命題 ∀x.(A(x) -> B(x)) の真理表は次のようになる。

A(x) | B(x) | A(x) -> B(x) | ∀x.(A(x) -> B(x))
T | T | T | F
T | F | F | F
F | T | T | F
F | F | T | F

この真理表における ∀x.(A(x) -> B(x)) の真理値は個々の A(x) と B(x) の真理値の組み合わせで決まるのではなく A(x) -> B(x) が領域 D 全体についてとり得る真理値のパターンによって決まる。すなわち、領域 D の全対象について A(x) -> B(x) の真理値のとり得るパターンが T, F, T, T であるとき、∀x.(A(x) -> B(x)) の真理値は F である。

しかし、領域 D の全ての対象について A(x) と B(x) の組み合わせの全てのパターンすなわち (T, T), (T, F), (F, T), (F, F) が現れるわけではない。たとえば、A(x) が真ならば B(x) は必ず真であるというような述語間の関係が存在するとき上の真理表は次のようになり、∀x.(A(x) -> B(x)) の真理値は上の真理表とは異なって T になってしまう。

A(x) | B(x) | A(x) -> B(x) | ∀x.(A(x) -> B(x))
T | T | T | T
F | T | T | T
F | F | T | T

このように全称命題の真理値は、個々の命題変数の真理値の組み合わせではなく、領域全体についての命題変数の真理値のパターンで決まる。

このため、全称命題の真理表については命題論理の真理表とは異なる注意が必要になる。命題論理の真理表では複合命題の真理値は要素的な原子命題の真理値で決定できるため、すべての場合に同じ真理表で対応できた。しかし、全称命題については、量化子のつけられた命題変数の、領域 D 全体における真理値のパターンで真理値が決まる。したがって、領域 D における命題変数の真理値のパターンいかんによっては、全称命題の真理値が異なってしまう。

たとえば全称命題 ∀x.A(x) の場合、領域 D において A(x) の真理値が T と F の両方をとり得るのか、T だけしか取らないのか、F だけしか取らないのかの3つのパターンがある。そうして、それぞれのパターンでこの全称命題の真理値はかわってくるので、それぞれの真理表を作らなければならない。しかし、領域 D における A(x) の真理値のパターンはこの3つだけなので、3つの真理表を作成することで、∀x.A(x) についての一般的な議論をすることができる。

以上の議論については全称命題について述べたが、存在命題の場合も同じようなやり方ができる。いずれにせよ、一階述語論理であっても命題論理と同じように真理表による分析はできるのだ。真理表を作ることができるということは、一階述語論理の性質を真理表を具体的に作成することで議論することができることを意味する。一階述語論理につきまとう抽象的な印象を随分和らげることができる。

例として ¬(∀x.A(x)) と ∃x.(¬A(x)) が同値であることを証明してみる。まず、A(x) が領域 D の対象全体について真理値を T も F もとり得る場合の真理表は次のようになる。A(x) の真理値は T と F の両方が存在するので ∀x.A(x) の真理値は F である。従って ¬(∀x.A(x)) の真理値は T である。一方 A(x) の真理値のうち A(x) が F になるものが存在し、その時 ¬A(x) は T になるので、∃x.(¬A(x)) の値は T である。すなわち、¬(∀x.A(x)) と ∃x.(¬A(x)) は同値である。

A(x) | ¬A(x) | ∀x.A(x) | ¬(∀x.A(x)) | ∃x.(¬A(x))
T | F | F | T | T
F | T | F | T | T

上では、領域 D について A(x) が T と F の両方の値を取る場合について述べたが、一般的な議論のためには、領域 D について A(x) が T の値しか取らない場合と、A(x) が F の値しかとらない場合も考えなくてはならない。

先ず、A(x) の値が領域 D において T の値しか取らない場合は A(x) の値は常に T なので、¬(∀x.A(x)) は F になるが、このときは ¬A(x) の値は常に F なので∃x.(¬A(x)) の値も F になり両者の真理値は一致する。

A(x) | ¬A(x) | ∀x.A(x) | ¬(∀x.A(x)) | ∃x.(¬A(x))
T | F | T | F | F

次に、A(x) が常に F となる場合は次のように ¬(∀x.A(x)) と ∃x.(¬A(x)) の真理値は T となるが、この場合も両者の真理値の一致がみられる。

A(x) | ¬A(x) | ∀x.A(x) | ¬(∀x.A(x)) | ∃x.(¬A(x))
F | T | F | T | T

このように領域 D における A(x) の可能な真理値のパターンで3つの異なる真理表の作成が必要になるが、どの場合にも ¬(∀x.A(x)) と ∃x.(¬A(x)) の真理値は一致するので両者は同値であると結論づける事ができる。一階述語論理には、量化子を使った命題があるからといっても、これを真理表で議論するのは不可能ではないし、難しくもない事がわかる。


[PR]
# by tnomura9 | 2017-09-03 22:04 | ラッセルのパラドックス | Comments(0)

一階述語論理と真理表

命題論理には真理表がある。これを使うと複合命題の真理表が機械的に計算できる。たとえば含意の真理表は次のようになる。

P | Q | P -> Q
T | T | T
T | F | F
F | T | T
F | F | T

真理表の利点は命題の真理値の機械的な割り当てで複合命題の真理値が計算できることだ。同じような定理を公理と推論規則から証明するのはかなり骨が折れる。命題論理学が分かりやすいと感じるのは真理表が寄与するところが大きいのではないだろうか。

しかし、一階述語論理には真理表がない。∀x. (P(x) -> Q(x)), P(a) が真ならば、Q(a) が真であるというような推論も真理値表が使えず。公理からの推論規則による証明が必要になってくる。そこで、論理にも真理表があれば便利だろうと思ったので考えてみた。一回述語論理の真理表による推論は、領域 D のモデルを使って行う。

対象の有限集合である領域 D を考える。領域 D の要素である対象 a, b, c, ... には述語 A, B, ... で表される性質を考えることができる。対象 a と述語 A の対は命題を作る。命題 A(a) は対象 a が A という述語の性質を持っているときに真である。そうでないときは A(a) は偽となる。述語 A に領域 D のすべての対象を割り当てて命題 A(a) が真になる対象のみを集めると述語 A の真理集合 A* ができる。A* は D の部分集合である。したがって真理集合は領域 D のべき集合の要素である。このべき集合を真理集合族と呼ぶことにする。

命題 A(a) の真理値と a ∈ A* の真理値は一致する。したがって A(a) と a ∈ A* は同値であり後者を命題と考えることができる。対象を変数で表した命題 A(x) は述語が A である命題全般を表す。述語 A を領域 D のすべての対象に適用したとき、領域 D の要素の数だけの命題ができるが、A(x) はそれらの命題の一つを表していると考えられる。つまり A(x) は述語が A であるような命題の命題変数だ。

A(x) は命題変数なので真理表をつくることができる。原子命題変数 A(x) と B(x) から複合命題 A(x) -> B(x) を作ることができて、それについての真理表を作ることができる。この際に A(x) と B(x) は同じ対象を表していると考えることにする。命題変数 A(x) と B(x) から作られる A(x) -> B(x) の真理表は次のようになる。これは命題論理学で使われる真理表と意味は同じである。

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

ここで A(x) -> B(x) が常に真であるという仮定をする。A(x) と B(x) が互いに自由に真理値をとれる場合はこのようなことは起こらないが、A(x) が真の時は必ず B(x) も真であるというような、述語 A と B の間に関連性があるときは、そのようなことも起こりえる。その場合の真理表は次のようになる。

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

ここで、述語 A を充足する対象 a を取り出して命題 A(a) を考えてみる。この時命題 A(a) の真理値は真である。また、含意 A(x) -> B(x) が恒真命題であると仮定する。すると次のような真理表ができる。

A(a) | B(a) | A(a) -> B(a)
T | * | T

B(a) の真理値が分からないが、それは上の含意の真理値表から推論することができる。すなわち A(x) と A(x) -> B(x) がともに真になるのは B(a) の真理値が T の時だけだ。したがって、この真理表は次のようになる。

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

したがって A(x) -> B(x) が常に真、すなわち、全称命題 ∀x. (A(x) -> B(x)) が真の時は、A(a) が真ならば B(a) も真である。これを真理集合を使って表現すると、

a ∈ A* ならば a ∈ B*

である。この条件を満たすどのような対象を a として持ってきても上の関係は成立するから、述語 A の真理集合と述語 B の真理集合は包含関係にある。すなわち、

A* ⊂ B*

である。

もうひとつ例を考えてみよう。命題変数 P(x) について次のような真理表を作ってみる。

P(x) | ¬P(x) | ∀x. (¬P(x)) | ¬(∀x. (¬(P(x)))
T | F | F | T
F | T | F | T

この真理表は P(x) が真になったり偽になったりする条件下では ¬(∀x. (¬(P(x))) は常に真になることを示している。この真理表で ∀x. (¬P(x)) の真理値の求め方は特殊だ。この命題の真理値は ¬P(x) の真理値の列が全て T の時だけ真になる。この真理表では T と F が出現するので ∀x. (¬P(x)) の真理値は常に偽になる。

これは P(x) が真にも偽にもなる場合は成立するが、P(x) に制限があって次の真理表のように P(x) が偽の値しかとらないときは真になる。

P(x) | ¬P(x) | ∀x. (¬P(x)) | ¬(∀x. (¬(P(x)))
F | T | T | F

そこで存在命題 ∃x. P(x) について考えてみる。この命題は P(x) が真となる場合が少なくとも一つは存在すると真になる。したがって真理表は次のようになる。

P(x) | ¬P(x) | ∀x. (¬P(x)) | ¬(∀x. (¬(P(x))) | ∃x. P(x)
T | F | F | T | T
F | T | F | T | T

これ以外に P(x) が必ず真となるときも、Ex. P(x) は真になる。

P(x) | ¬P(x) | ∀x. (¬P(x)) | ¬(∀x. (¬(P(x))) | ∃x. P(x)
T | F | F | T | T

また、P(x) が必ず偽となる場合は、Ex. P(x) は偽になる。

P(x) | ¬P(x) | ∀x. (¬P(x)) | ¬(∀x. (¬(P(x))) | ∃x. P(x)
F | T | T | F | F

P(x) の真理値のとりえる可能性はこの3つの場合だけだ。しかし、どの場合にも ¬(∀x. (¬(P(x))) と ∃x. P(x) の真理表における真理値は一致する。したがって、この二つの複合命題は同値である。

ここに述べた議論は領域 D が有限集合の場合だったが、これらの推論は述語に排中律が成立していれば領域 D が無限集合であっても適用できる。一階述語論理は領域 D が無限集合の場合も適用できる。すなわち、無限集合の領域 D にも一階述語論理を適用するためには排中律が必須であることがわかる。

追記

真理表の議論では A(x) が真であることは x ∈ A* に、偽であることは x /∈ A* に置き換えることができる。また A(x) ∧ B(x) のような複合命題は A* ∩ B* のように論理結合子に対応する集合演算に置き換えできる。

真理集合 A* と真理集合 B* の集合演算 A* ∧ B* の値もまた領域 D の部分集合である。すなわち、全ての論理演算は対応する領域 D の真理集合族についての集合演算について閉じている。

量化子を使った ∀x. P(x) のような命題は述語を持たないが、仮想的な述語 Q(x) を持つと考えると x ∈ Q* で真偽を論じることができる。この場合 Q* は領域 D と等しいか、または空集合 {} である。

このように一階述語論理の議論は領域 D とその真理集合族の議論に置き換えることができる。命題の真理値の議論については、対象についての述語の意味によらず真理集合族の要素に置き換える事ができるので、論理の法則の抽象性が保たれることになる。

また、述語を真理集合に置き換える利点は、それによって、領域 D が無限集合であっても論理と集合の置き換えが行えるということだ。ただし、命題は排中律を満たし真理集合を定義できなくてはならない。命題が排中律を満たしていれば、任意の対象 x について x ∈ A* かどうかの議論ができるので、命題 A(x) に対応する真理集合 A* を求める事ができる。

このことは、量化子のある命題 ∀x. P(x) が無限集合の領域 D にあっても定義できることを意味している。対象と命題の対で全ての原子命題を作ろうとしても、領域 D が無限集合の場合は、∀x. P(x) = P(a1) ∧ P(a2) ∧ ... と原子命題の無限の論理積を考えないといけないが、命題を集合に変えてやれば、任意の x について x ∈ P* という議論をすることができるので全称命題 ∀x. P(x) を無限の x についても定義することができる。

これらの議論から領域 D に一階述語論理の法則を適用できるための条件が明らかになる。それは、一階述語論理を適用しようと思う領域 D という全体集合が定義されていることと、命題の排中律が満されていることだ。素朴集合論を対象間の帰属関係が定義されたネットワークの全体として定義した場合、排中律が満たされないので、これを領域 D とする一階述語論理を適用することはできない。一方、上の議論では集合の集合というような集合の階層構造はないので、ラッセルのパラドックスのような自己言及のパラドックスも発生しない。

[PR]
# by tnomura9 | 2017-09-01 19:20 | ラッセルのパラドックス | Comments(0)