意味論的帰結と同値
要約
この授業では、命題論理における意味論的帰結と同値を学びます。これは、これまでに学んだ内容の自然な続きです。真理値の割り当てから意味論的帰結の概念をどのように得るか、そしてこの考え方が推論定理とどのように関連するかを学びます。また、連言除去や選言導入のような有用な性質を得るために真理値表を使う実用的な例を見ていきます。さらに、意味論的同値の概念を探求し、それが既に知っている性質とどのように関連するかを確認します。最後に、モデルや推論技法を用いることで、意味論的帰結と同値の問題の研究を簡略化できることを示します。
学習目標：
この授業の終了時に学生は以下のことができるようになります。
- 意味論的帰結の概念を理解する。
- 記号 ⊨ のさまざまな解釈を理解する。
- 意味論的バージョンの推論定理の証明と、それが意味論的帰結および同値の研究においてどのように用いられるかを理解する。
- 意味論的同値の定義と、それが真理値とどのように関係しているかを理解する。
- 意味論的推論定理を応用して、帰結の問題を妥当性の問題に変換する。
- 真理値表の有用な性質を応用して、意味論的同値を証明する。
- 吸収律、分配律、ド・モルガンの法則を適用して複雑な式を簡略化する。
- 命題論理の研究におけるモデルと推論の関係を分析する。
目次
割り当てとモデル
推論定理（意味論的バージョン）
意味論的帰結と同値の研究における推論定理の使用
意味論的同値と性質
まとめ
意味論的帰結と同値の研究は、命題論理の意味論を確認したときの自然な続きです。今回は、真理値の割り当てから意味論的帰結の概念がどのように得られるか、そしてそこからどのようにして推論定理の意味論的バージョンが自然に生まれるかを見ていきます。ここから、真理値表を用いて有用な性質を得る実用的な例が示されます。これらの内容はYouTube チャンネルでも確認できます。
割り当てとモデル
まずは、この項目で展開される理論の基礎となる重要な定義である「意味論的帰結」から始めましょう。
| 定義： 式 G は、式 F の（意味論的）帰結であるとは、すべての割り当て \mathcal{A} に対して、 \mathcal{A}\models F \Rightarrow \mathcal{A}\models G が成り立つときである。これは F\models G と記述され、「式 F は式 G をモデル化する」または「G は F の（意味論的）帰結である」と読む。 |
この定義をもとに、記号 \models には文脈によっていくつかの異なる解釈があることに注意しましょう：
- \mathcal{A} \models F は、\mathcal{A}(F) = 1、すなわち「\mathcal{A} が F をモデル化する」ことを意味する。
- G \models F は、任意の割り当てが G をモデル化すれば F もモデル化されることを意味し、「F は G の帰結である」と読む。
- \models F は、すべての割り当てにおいて F が成り立つこと、すなわち F が恒真式（トートロジー）であることを意味する。
このように、記号 \models は複数の意味を持ちうるが、文脈によって解釈が曖昧になることはない。
（意味論的）帰結の概念は、以前に見た「含意」の概念と近いものであり、F\models G が成り立つならば \models (F\rightarrow G) が成り立つ。実際、この性質は、以前の授業で学んだ推論定理と非常に類似している。
推論定理（意味論的バージョン）
[視聴]
| 定理： F と G が任意の式であるとき、次が成り立つ： F\models G \Leftrightarrow \models (F\rightarrow G) | ||||||||||||||||||||||||||||||||||||||||
| 証明： この定理の証明は、真理値表を観察することで容易に得られる。
F\models G の意味に注目すると、これは \mathcal{A}\models F \Rightarrow \mathcal{A}\models G と言うのと同じであり、さらにそれは \mathcal{A}\not\models F \vee \mathcal{A}\models G と言い換えられる。そして \mathcal{A}\not\models F は \mathcal{A}\models \neg F と等価であることから、F\models G は \mathcal{A} \models \neg F \vee \mathcal{A}\models G を意味する。今、F \rightarrow G の真理値表を作成し、\mathcal{A} \models \neg F \vee \mathcal{A}\models G が成り立つ領域を 緑色で示すと、以下のようになる：
このことから、F\models G のとき、常に \models (F \rightarrow G) が成り立ち、その逆もまた成り立つ。これはまさに意味論的バージョンにおける推論定理およびその逆を表している。 |
ある式 G が別の式 F の帰結であるかを知りたいとしましょう。これを帰結問題と呼びます。前述の定理を用いれば、この問題は妥当性の問題に変換できます。すなわち、「G が F の帰結であるのは、(F\rightarrow G) が定理であるとき、かつそのときに限る」ということです。
意味論的帰結と同値の研究における推論定理の使用
真理値表に基づいて、過去に見た性質に類似したいくつかの性質を導くことができます。
| 例: 真理値表を使って次の性質が成り立つことを示す | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 連言除去： | (F\wedge G)\models F | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 選言導入： | F\models (F\vee G) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 矛盾： | (F\wedge\neg F)\models G | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 解答： 先ほど確認した推論定理を用いることで、帰結問題を妥当性の問題に変換できます。 連言除去を解くためには、次のような真理値表を作成します。
このことから、((F\wedge G)\rightarrow F) が恒真式（トートロジー）であることが分かり、推論定理の逆を用いて (F\wedge G) \models F を得ることができます。 選言導入も同様に、適切な真理値表を構築することで証明されます。
ここで、(F\rightarrow (F\vee G)) が恒真式（トートロジー）であることが確認できます。したがって、推論定理の逆を用いると、F\models (F\vee G) が導かれます。 最後に、矛盾の性質も同じ方法を用いて証明されます。
この真理値表によって、((F\wedge \neg F)\rightarrow G) が恒真式であることが証明され、したがって推論定理の逆により (F\wedge \neg F)\models G が得られます。 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
意味論的同値とその性質
[視聴]
| 定義： F\models G かつ G\models F が同時に成り立つとき、F と G は意味論的に同値であると言います。これは F\equiv G と表記されます。 |
この定義の帰結として、2つの式が意味論的に同値であるとは、それらが同じ真理値を持つことと同値であるといえます。
| 例： 真理値表を用いて、対称性に基づく意味論的同値が成り立つことを示すことができます。 |
| (F\downarrow G) \equiv (G\downarrow F) |
| (F\vee G) \equiv (G\vee F) |
| (F\wedge G) \equiv (G\wedge F) |
| (F\leftrightarrow G) \equiv (G\leftrightarrow F) |
| (F\underline{\vee} G) \equiv (G\underline{\vee} F) |
| 例： F が任意の式、\top がトートロジー（恒真式）、\bot が矛盾（恒偽式）であるとき、真理値表を用いて次の意味論的同値が証明できます。 |
| (F\wedge \top) \equiv F |
| (F\vee \top) \equiv \top |
| (F\wedge \bot) \equiv \bot |
| (F\vee \bot) \equiv F |
| これらの同値は、吸収律（Absorption Laws）として知られています。 |
| 例： 命題論理の意味論においては、連言と選言の分配律（Distributive Laws）も成り立ちます。 |
| (F\wedge (G\vee H)) \equiv ((F\wedge G) \vee (F\wedge H)) |
| (F\vee (G\wedge H)) \equiv ((F\vee G) \wedge (F\vee H)) |
| 例： 命題論理の意味論では、ド・モルガンの法則（DeMorgan Laws）も成り立ちます。 |
| \neg(F\wedge G) \equiv (\neg F \vee \neg G) |
| \neg(F\vee G) \equiv (\neg F \wedge \neg G) |
| 練習問題： 良い練習として、真理値表を使って吸収律、分配律、ド・モルガンの法則における意味論的同値が実際に成り立つことを証明してみましょう。 |
| 例： 次の同値が成り立つことを意味論的同値を使って証明する： ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E))\equiv ((A\wedge B)\vee(C\wedge D)) |
| 解答： この同値は真理値表を用いて証明することもできますが、この場合、5つの命題変数を含むため 2^5 = 32 行の真理値表を作成する必要があり、それは避けたいところです。そのため、これまでに確認した同値を活用します。 まず、(E\vee \neg E) がトートロジー（恒真式）であることに注目します。このトートロジーを \top と表記しましょう。すると、吸収律を用いて次のようになります： ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) 次に、分配律を用いると： ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) \equiv ((C\wedge D) \vee (A\wedge B)) 最後に、対称性より： ((C\wedge D) \vee (A\wedge B)) \equiv ((A\wedge B) \vee (C\wedge D)) したがって、これらの同値を順に適用すると： ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((A\wedge B) \vee (C\wedge D)) これが証明したかった命題です。 |
まとめ
この最後の例の展開を観察すると、変数の数が増えるにつれて、意味論的帰結や同値の問題を真理値表に依存して調べる場合、その複雑さが指数関数的に増加することが分かります。しかしながら、モデルという考え方を展開する中で、これまで詳細に学んできた推論技法と類似のものが現れることを確認しました。このモデルと推論の関係性こそが、今後取り上げる内容であり、両者の組み合わせが論理学の研究において多大な労力を軽減してくれることになるのです。