命題論理における完全性と健全性
要約
この講義では、命題論理における完全性と健全性の関係について取り上げます。命題論理の推論技法や意味論は広く議論されてきましたが、それら二つの側面の関係にはあまり注意が払われてきませんでした。健全性とは、論理体系が式 G を表現集合 Γ から推論できるという性質を指します。一方、完全性とは、もし G が Γ の意味論的帰結であるならば、前提 Γ による形式的証明が存在して G を推論できるという論理体系の性質を指します。本講義では、命題論理が健全かつ完全であることを証明し、それぞれの性質について詳細な説明を行います。特に、健全性が命題論理の推論体系の構造からどのように導かれるか、また完全性がいかに簡潔に示されるかを説明します。この分析は、命題論理の機能を理解し、様々な知識分野に効果的に応用するために非常に重要です。
学習目標:
この講義を終えた後、学生は次のことができるようになります：
- 健全性と完全性を論理体系において区別できる。
- 命題論理の健全性を示すために、ルカシェヴィチの公理に対して真理値表を適用できる。
- 演繹定理の意味論的バージョンを用いて、モーダス・ポネンスの形式を説明できる。
- 健全性と完全性が相互に関連しており、どちらも一方から導出できることを理解できる。
- 恒真命題（トートロジー）の概念と、命題論理における定理との関係を分析できる。
目次
命題論理における完全性と健全性
命題論理は健全である
命題論理は完全である
命題論理における完全性と健全性
ここに至って、命題論理の完全性と健全性について語るべき時が来ました。これまで命題論理における推論技術や意味論については多く語られてきましたが、それらはあたかも互いに全く関係のない二つの側面であるかのように扱われてきました。しかし、実際には全く逆なのです。
健全性（SOLVENCIA）: 一方で、ある論理体系が健全であるとは、ある式 G が表現集合 \Gamma から推論できるならば、G は \Gamma の（意味論的な）帰結であることを常に意味します。 |
完全性（COMPLETITUD）: 他方で、ある論理体系が完全であるとは、もし G が表現集合 \Gamma の意味論的帰結であるならば、前提 \Gamma に基づく形式的証明が存在し、そこから G を推論できることを意味します。 |
これらの概念を見直してみると、命題論理においては完全性と健全性の両方が満たされていることがわかります。
命題論理は健全である
命題論理の健全性を得るのは簡単です。その推論体系の構成を観察するだけで分かります。ルカシェヴィチの公理に対して真理値表を作成すると、それらが常に真となる構造を持っていることがわかります。すなわち：
| \models (\alpha \rightarrow (\beta \rightarrow \alpha)) |
| \models ((\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma))) |
| \models ((\neg\beta \rightarrow \neg\alpha)\rightarrow(\alpha \rightarrow \beta)) |
同様に、モーダス・ポネンスは次のように書き換えることができます：\{\alpha,(\alpha\rightarrow \beta)\}\models \beta.これは演繹定理の意味論的バージョンを用いて導くことができます。実際、この方法により次のように得られます：\{(\alpha\rightarrow \beta)\}\models (\alpha\rightarrow \beta),さらに、\models ((\alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow \beta)),。これはもちろん、明らかな恒真命題（トートロジー）です。
命題論理は完全である
命題論理の完全性が意味するのは、もし B が A の意味論的帰結であるならば、A から B を推論できるということです。言い換えれば、すべての真なる表現には証明が存在するということです。これが完全性と呼ばれるものです。そしてこれは簡潔な方法で導出できます。
これは簡単に導き出せます。A から B を推論できないと仮定しましょう。つまり、\neg(A\vdash B) であるとします。演繹定理によれば、これは \neg (\vdash A\rightarrow B) ということと同値です。ここで、健全性を用いると、\neg(\models A \rightarrow B) となり、演繹定理の意味論バージョンの逆を使うと、\neg(A\models B) にも等しいことが分かります。つまり、要約すると次のようになります：
\neg(A\vdash B) \Rightarrow \neg(A\models B)
これは次のように言い換えることができます：
(A\models B) \Rightarrow (A\vdash B)
すなわち、もし A が B をモデル化する（意味論的に導く）ならば、A から B を推論できるということです。そして、対応する演繹定理を用いれば、次のように得られます：
(\models A\rightarrow B) \Rightarrow (\vdash A \rightarrow B)
つまり、ある表現が恒真命題（トートロジー）であるならば、それは定理でもあるということです。そして見てきたように、定理とは証明によって導かれた結果なのです。