命題論理の意味論

要約
この講義では、命題論理の意味論を学びます。特に、命題の真理値の割り当てと、それが論理結合子を通じてどのように他の命題へ伝播するかを扱います。真理値表の概念が導入され、否定、選言、連言、含意、両含意、排他的選言などの派生的な結合子の真理値表が示されます。さらに、原子的な命題の集合に対する割り当ての定義が提示され、その割り当てがその集合から構築されるすべての命題に自然に拡張される方法が説明されます。最後に、妥当（常に真）、充足可能（ある割り当てで真）、充足不能（常に偽）といった命題の分類が定義され、トートロジーや矛盾の例が提示されます。しかし、複雑な命題の真理値表の計算は非効率的となる可能性があるため、妥当性や充足可能性の問題を解く代替手法が模索されていることにも言及されます。

学習目標:
この講義の終了時に学生は以下ができるようになります。

命題論理の意味論を説明する
真理値表を用いて命題論理における命題の真理値割り当てを表現する
命題論理において命題とその割り当てをモデル化する
意味論的規則を適用して、命題がトートロジー、矛盾、または偶然的真理かを判断する

目次
真理値の割り当てについて
 命題論理における結合子の意味論
 命題論理における割り当て
 命題論理におけるモデル
 命題論理の意味論に潜む効率性の問題

真理値の割り当てについて

以前の講義で命題論理の構文と演繹体系について学びました。これにより、ある命題から別の命題を導出する方法を理解しましたが、真理値の割り当てについては何も述べていませんでした。演繹技法についてすでに十分に学んだので、これからは命題論理の意味論、つまりある命題から別の命題へと真理値の割り当てがどのように伝播するかを学んでいきます。

命題論理における結合子の意味論

結合子の意味論は真理値表を通じて導入されます。真理値表は、命題に対するすべての可能な割り当てを簡潔かつ体系的に表現する手段です。

否定連言の真理値表

まず最初にもっとも基本的な結合子である否定連言から始めます。その真理値表は次の通りです。

$\alpha$	$\beta$	$(\alpha\downarrow\beta)$
0	0	1
0	1	0
1	0	0
1	1	0

「1」と「0」は、それぞれ「真（True）」と「偽（False）」に対応します。真理値表の各行は、調査対象の式（または複数の式）を構成する変数（または原子的命題）に対する可能な割り当てを表します。同様に、これらの変数から構成される式が記載された各列には、それぞれの割り当てに対する結果が示されます。したがって、この表の解釈によれば、 $\alpha\downarrow\beta$ は $\alpha$ と $\beta$ がともに偽であるときにのみ真となり、それ以外の場合は偽です。このことから、結合子 $\downarrow$ は否定連言（ノア結合子）と呼ばれます。

派生結合子の真理値表

否定連言の意味論に基づいて、他の結合子の意味論をそれぞれの定義に従って導くことができます。以下にそれらを示します：

否定:	$\neg \alpha$	$:=$	$(\alpha\downarrow\alpha)$
包含的選言（または）:	$(\alpha \vee \beta)$	$:=$	$\neg(\alpha\downarrow\beta)$
連言（かつ）:	$(\alpha \wedge \beta)$	$:=$	$\neg(\neg\alpha\vee \neg\beta)$
含意（ならば）:	$(\alpha \rightarrow \beta)$	$:=$	$(\neg\alpha\vee \beta)$
両含意（同値）:	$(\alpha \leftrightarrow \beta)$	$:=$	$((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha))$
排他的選言:	$(\alpha \underline{\vee} \beta)$	$:=$	$\neg(\alpha\leftrightarrow \beta)$

これらの定義を基に、他の結合子の真理値表を計算することができます。

否定

$\alpha$	$\neg \alpha$
0	1
1	0

このことから、否定結合子は適用された命題の真理値を反転させるという性質を持つことがわかります。

包含的選言（ディスユンクション）

$\alpha$	$\beta$	$(\alpha\vee\beta)$
0	0	0
0	1	1
1	0	1
1	1	1

したがって、包含的選言（単に「選言」とも呼ばれる）は、2つの命題の少なくとも一方が真であれば真となり、両方が同時に偽である場合にのみ偽となります。

連言（アンド）

$\alpha$	$\beta$	$(\alpha\wedge\beta)$
0	0	0
0	1	0
1	0	0
1	1	1

その結果として、 連言は2つの命題が同時に真であるときにのみ真となり、それ以外は偽となります。このため、この結合子に対して「共に肯定する（共同肯定）」という名称も適切といえるでしょう。

含意（インプリケーション）

$\alpha$	$\beta$	$(\alpha\rightarrow\beta)$
0	0	1
0	1	1
1	0	0
1	1	1

したがって、 含意の真理値表は、「真」の命題は「真」の命題にのみ含意できるが、「偽」の命題は何でも含意しうる、という概念を要約したものです。

両含意（同値）

$\alpha$	$\beta$	$(\alpha\leftrightarrow\beta)$
0	0	1
0	1	0
1	0	0
1	1	1

両含意（同値） は、2つの命題の真理値が一致する場合に「真」となり、それ以外の場合は「偽」となります。

排他的選言（エクスクルーシブ・オア）

$\alpha$	$\beta$	$(\alpha\underline{\vee}\beta)$
0	0	0
0	1	1
1	0	1
1	1	0

排他的選言は、2つの命題のうちどちらか一方が真であり、もう一方が偽である場合に真となり、それ以外の場合は偽となります。

命題論理における割り当て

これまでに述べた内容により、 割り当ての基本的な概念は理解できましたが、今後の展開のためには、より厳密な定義が必要です。 $S=\{A_1, A_2, \cdots, A_n\}$ を原子的命題の集合、 $\mathcal{F}(S)$ を $S$ の要素から構成可能なすべての命題の集合とすると、次のように定義されます：

定義： $S$ 上の割り当てとは、 $\mathcal{A}: S \longrightarrow \{0,1\}$ なる関数のことをいう。

つまり、 $S$ 上の割り当てとは、 $S$ に含まれるすべての原子的命題に真理値を割り当てる操作のことです。 $\mathcal{A}$ は $S$ の割り当てであり、自然に $\mathcal{F}(S)$ のすべての要素へと拡張されます。命題 $F\in \mathcal{F}(S)$ があるとき、割り当て $\mathcal{A}$ は $F$ の真理値表の一意な行と対応し、 $\mathcal{A}(F)$ はその行における $F$ の真理値を表します。

さらに、 $\mathcal{A}$ は $\mathcal{F}(S)$ に含まれない式に対しても拡張されることがあります。もし $F_0$ が $\mathcal{F}(S)$ に属さない式であり、 $S_0$ を $F_0$ に現れる原子的命題の集合とするならば、 $\mathcal{A}$ の $S\cup S_0$ へのすべての拡張が $F_0$ に対して同じ真理値を与えるとき、 $\mathcal{A}(F_0)$ はその共通の真理値として定義されます。

例： $A$ および $B$ を原子的命題とし、 $\mathcal{A}$ を $\{A,B\}$ 上の割り当てであって、 $\mathcal{A}(A)=1$ 、 $\mathcal{A}(B)=0$ と定められているとすると：

$\mathcal{A}(A\wedge B)=0$ および $\mathcal{A}(A\vee B)=1$

また、 $C$ に関しては割り当てが与えられていないにもかかわらず、次のように言えます：

$\mathcal{A}(A\wedge (C\vee \neg C))=1$ および $\mathcal{A}(B\vee (C\wedge \neg C))=0$

これは、 $C$ にどのような真理値を割り当てても：

$\mathcal{A}(C\vee\neg C)=1$ および $\mathcal{A}(C\wedge\neg C)=0$

となることによります。このことは、対応する真理値表を計算することで容易に確認できます。

$C$	$\neg C$	$(C\wedge \neg C)$	$(C \vee \neg C)$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$

■ 例の終わり

命題論理におけるモデル

ある割り当て $\mathcal{A}$ を命題の集合 $S$ 上に与えます。 $F\in S$ であり、 $\mathcal{A}(F)=1$ であるとき、割り当て $\mathcal{A}$ は $F$ をモデル化すると言い、または $F$ は $\mathcal{A}$ によって支持されていると言います。これは次のように記述されます：

$\mathcal{A}\models F$

この定義から、次の定義が導かれます：

定義： すべての割り当てに対して真となる式を妥当（valid）という。式 $F$ が妥当であるとき、 $\models F$ と記述する。妥当な式はトートロジー（恒真式）とも呼ばれる。

例：式 $(C\vee \neg C)$ は、すでに見たように、トートロジー である。

■ 例の終わり

定義： ある割り当てに対して真となる式を充足可能（satisfacible）という。トートロジーでない充足可能な式は偶然的真理（contingencia）と呼ばれる。

定義： いかなる割り当てにおいても真とならない式を充足不能（insatisfacible）または矛盾（contradicción）という。式 $F$ が矛盾であるとき、 $\not\models F$ と記述する。

例：式 $(C\wedge \neg C)$ は、すでに見たように、矛盾である。

■ 例の終わり

トートロジーと矛盾の例

ある式が妥当かどうかを調べたいと仮定しましょう。この問いは、命題論理の意味論における判定問題（problema de decisión）の一例です。判定問題とは、ある入力に対して「はい」または「いいえ」で答えられる問題のことです。式 $F$ が与えられ、それが妥当かどうかを問う場合、それは妥当性問題（problema de validez）と呼ばれます。同様に、充足可能かどうかを問う場合、それは充足可能性問題（problema de satisfacibilidad）となります。命題論理において、真理値表はこれらの判定問題を体系的に解決する手段を提供します。すべての真理値が「1」であれば、 $F$ は妥当；一部が「1」であれば、 $F$ は充足可能；すべてが「0」であれば、 $F$ は充足不能です。

例：式 $((A\wedge (A \rightarrow B)) \rightarrow B)$ を考えましょう。この式が妥当か、充足可能か、あるいは矛盾であるかを判断するには、真理値表を作成します。

$A$	$B$	$(A\rightarrow B)$	$(A\wedge(A\rightarrow B))$	$((A\wedge(A\rightarrow B))\rightarrow B)$
$0$	$0$	$1$	$0$	$1$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

この表から、 $((A\wedge(A\rightarrow B))\rightarrow B)$ はすべての割り当てに対して真理値「1」となることがわかります。したがって、この式はトートロジーです。

■ 例の終わり

例：次に、式 $(((A\rightarrow B)\rightarrow A)\wedge \neg A)$ を考えてみましょう。真理値表の計算によって以下のような結果が得られます：

$A$	$B$	$(A\rightarrow B)$	$((A\rightarrow B)\rightarrow A)$	$\neg A$	$(((A\rightarrow B)\rightarrow A)\wedge \neg A)$
$0$	$0$	$1$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$0$
$1$	$1$	$1$	$1$	$0$	$0$

したがって、この結果は矛盾（コントラディクション）であることがわかります。

■ 例の終わり