命題論理ではそれ以上分解できない最も簡単な命題を原子命題といい 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)
by tnomura9
| 2017-09-14 02:03
| ラッセルのパラドックス
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||