命題論理 ①

具体的な命題をその都度書き下す代わりに、命題を表す記号として $P$ や $Q$ を用いることがある。
また、「真」「偽」をそれぞれ $T$（True）、$F$（False）と表すこともある。

例えば「$11$ は素数である」は真な命題であり、「$12$ は素数である」は偽な命題である。
$ $
一方、「$n$ は素数である」は $n$ の値が指定されていないため、
このままでは真偽が定まらず命題ではない。
$ $
ただし、$n$ に具体的な値を代入すれば命題になる。
例えば、$n = 11$ とすると「$11$ は素数である」は真な命題である。
$ $
また、「この映画は面白い」のように「面白い」が主観に依存して真偽が一意に定まりにくい文は、
命題とはみなさない。

ここで $\{T,F\}$ とは、$T$ と $F$ の$2$つの値をひとまとめにして表したもので、
今の段階では直感的に「$T$ と $F$ からなるもの」と読めばよい。

真理表より、命題$P,Q$に対して、命題$P$と命題$Q$のいずれか片方でも$T$(真)であるとき、$P \lor Q$は$T$(真)である(と覚えればよい)。

$2$つの命題$P,Q$に対して、上で定めた$P \lor Q$のような
「命題どうしをつないだり、命題の意味を反転したりして、新しい命題を作るための記号」を論理結合子(または論理演算子)という。
代表的な論理結合子(論理演算子)として
$$ \begin{align} \lnot &:\ \text{「〜でない」（否定）} \\ \land &:\ \text{「〜かつ〜」（連言）} \\ \lor &:\ \text{「〜または〜」（選言）※上で扱った} \\ \Rightarrow &:\ \text{「〜ならば〜」（含意）} \\ \Leftrightarrow &:\ \text{「〜であることと〜であることは同値」（同値）} \end{align} $$
-が挙げられる。

このような、各命題を、論理結合子を用いて組み合わせて作った記号列のことを論理式と言う。
たとえば、次のようなものが論理式の例である。
$$ \begin{align} & 1.\ P \\ & 2.\ Q \\ & 3.\ \lnot P \\ & 4.\ (P \land Q) \\ & 5.\ (P \lor Q) \\ & 6.\ (P \Rightarrow Q) \\ & 7.\ (P \Leftrightarrow Q) \\ & 8.\ \lnot (P \land Q) \\ & 9.\ (\lnot P \lor Q) \\ & 10.\ ((P \land Q) \Rightarrow R) \\ & 11.\ (P \Rightarrow (Q \lor R)) \\ & 12.\ ((P \Rightarrow Q) \land (Q \Rightarrow R)) \\ & 13.\ \lnot ((P \lor Q) \land R) \\ & 14.\ ((P \Leftrightarrow Q) \Rightarrow (\lnot R \lor P)) \\ & 15.\ (((P \Rightarrow Q) \land (Q \Rightarrow R)) \Rightarrow (P \Rightarrow R)) \end{align} $$

真理表とは、命題(やそれら命題同士を結合して得られる論理式)について、入力となる各命題(変数)の真偽値の組をすべて列挙し、
それぞれの場合にその論理式が真 $(T)$ になるか偽 $(F)$ になるかを表にまとめたものである。
たとえば命題変数が $n$ 個あるとき、入力の組は全部で $2^n$ 通りあるので、真理表は通常 $2^n$ 行（各行が$1$つの割当）からなる。

真理表より、命題$P,Q$に対して、命題$P$と命題$Q$のいずれか片方でも$F$(偽)であるとき、$P \land Q$は$F$(偽)である(と覚えればよい)。

すなわち、$\neg P$ は 命題$P$の真偽を反転させるものである(文字通りの『否定』である)。

特に $P$ が $F$ のときは、$Q$ の真偽に関わらず $P \Rightarrow Q$ は必ず $T$ である。
このように、$P$ が $F$ のとき、$Q$ の真偽に関わらず $P \Rightarrow Q$ が常に $T$ になることを『空虚に真』であると言う。

当然だが、命題 $P\Rightarrow Q$ は次のことを主張しない。
$$ \begin{align} (1)\quad & P \text{ が真であること。} \\ (2)\quad & Q \text{ が真であること。} \\ (3)\quad & P \text{ と } Q \text{ のどちらかが必ず真であること。} \\ (4)\quad & P \text{ と } Q \text{ に因果関係があること。} \end{align} $$
-真理表の定義より、$P\Rightarrow Q$ が偽となるのは
$$ P=T\ \text{かつ}\ Q=F $$
の$1$つの場合だけである。
そのため、$P\Rightarrow Q$ という形の命題を証明(命題が真であることを論理的に導く有限の記述を)するときは次の方針になる。

1. $P$ が真である場合を仮定して、そのとき必ず $Q$ が真になることを示す。
2. $P$ が偽である事を示し、含意 $P\Rightarrow Q$ は $Q$ の真偽に関わらず常に真となる(空虚に真であることから $P\Rightarrow Q$ を結論する。)
   $ $

-その他の証明方法として、以下も重要である。
3. $\neg Q$ が真であると仮定し、そこから $\neg P$ が真になることを示す（$P \Rightarrow Q$ と $\neg Q \Rightarrow \neg P$ が同値であることを利用する方針）
4. $P$ が真であり、かつ $Q$ が偽である（すなわち $P \land \neg Q$）と仮定して、矛盾を導く(背理法)。

逆・裏・対偶の関係を図で表現すると、以下のようになる。
$$ \begin{array}{ccc} \text{元} & & \text{逆} \\ (P \Rightarrow Q) & \longleftrightarrow & (Q \Rightarrow P) \\ \Updownarrow & & \Updownarrow \\ (\lnot Q \Rightarrow \lnot P) & \longleftrightarrow & (\lnot P \Rightarrow \lnot Q) \\ \text{対偶} & & \text{裏} \end{array} $$

真理表より、命題$P,Q$に対して、$P \Leftrightarrow Q$ が$T$(真)となるのは命題$P,Q$の真偽が一致しているときに限られている(文字通りの『同値』である)。

以下は集合の直観的な理解を助けるための、日常生活に基づく例である。
果物の集合として
$$ A = \{\text{りんご}, \text{バナナ}, \text{みかん}\} $$
平日の集合として
$$ B = \{\text{月曜日}, \text{火曜日}, \text{水曜日}, \text{木曜日}, \text{金曜日}\} $$
信号に使われる色の集合として、
$$ C = \{\text{赤}, \text{青}, \text{黄}\} $$
サイコロの出目の集合として
$$ D = \{1, 2, 3, 4, 5, 6\} $$
集合$A$の元として$\text{バナナ} \in A$であり、$\text{赤} \notin A$である。

命題とは、それ単独で真($T$)か偽($F$)のいずれかが定まる文のことである。
そのため 命題 $P$ 自体は、それ単独では 真($T$) や 偽($F$) のどちらであるかは決まらない。
そこで、命題というものを真($T$)か偽($F$)の$2$つの値を取る変数と見なし、これを命題変数と呼んでいる。
$ $
命題 $P$ 自体に真偽を与えるものは、各々の命題に真か偽を割り当てる次で与える評価（真偽値割当）
$$ v:\mathcal{P}\to\{T,F\} $$
を与えることによって、はじめて $v(P)\in\{T,F\}$ が定まり、そのとき $P$ は真偽値をもつ。
(ここで$v:\mathcal{P}\to\{T,F\}$は$\mathcal{P}$の個々の命題変数に対して、真と偽の$2$つの値のいずれかに結びつける対応$v$を意味する。)

命題変数と同様に、命題定数 $\top,\bot$ も論理式と見なす。

命題とは、それ単独で真($T$)か偽($F$)のいずれかが定まる文のことである。
そのため一般の命題変数 $P$ 自体は、それ単独では 真($T$) や 偽($F$) のどちらであるかは決まらない。
$ $
これに対して命題定数とは、真偽値があらかじめ固定された記号であり、評価によらず一定の真理値を表すものである。
特に命題定数 $\top,\bot$ は、それぞれ常に 真($T$) と 偽($F$) を表す。

すなわち、上記の定義を嚙み砕いて言い換えると

1. 個々の命題変数$P_{i}$は論理式である。
2. 命題定数は論理式である。
3. $A$が論理式ならば、その否定$\neg A$も論理式である。
4. $A,B$が論理式ならば、$(A\lor B),(A\land B),(A\Rightarrow B)$もまた論理式である。
5. 上記(1.~4.)によって得られる論理式のみを論理式と見なす。

特に、命題変数 $P_i$ と命題定数 $\top,\bot$ は、他の論理式を含まない事から原子論理式と呼ばれる。

評価（真偽値割当）は、まず命題変数に対して
$$ v:\{P_1,\cdots,P_k\}\to\{T,F\} $$
として定める。
これを論理式全体へ再帰的に拡張した写像を $\hat v$ と書くとき、命題定数については
$$ \hat v(\top)=T,\qquad \hat v(\bot)=F $$
と定める。

真偽値割当（評価）は『付値』とも呼ばれる。

ここでいう「写像」とは、ある記号や式を受け取って、それに対する値を決める対応の規則のことである。
この文脈では、「写像」は「関数」や「割り当ての規則」とほぼ同じ意味で使ってよい。
たとえば
$$ v:\{P_1,P_2,\dots,P_k\}\to\{T,F\} $$
とは、命題変数 $P_1,P_2,\dots,P_k$ のそれぞれに対して、真偽値 $T$ または $F$ をただ$1$つ対応させる規則を表す。
つまり、$v$ は各命題変数に「真か偽か」を割り当てる役割を果たす。
また
$$ \hat v:\mathcal F(P_1,\dots,P_k)\to\{T,F\} $$
とは、命題変数だけでなく、そこから作られる論理式全体に対しても、真偽値 $T$ または $F$ を返す規則である。
この $\hat v$ は、もとの割当 $v$ を論理式全体にまで広げた写像であり、これを（論理式の）評価という。

任意の論理式 $A,B$ に対し、
$$ A \Leftrightarrow B \ \text{は}\ (A \Rightarrow B)\land(B \Rightarrow A)\ \text{の略記とする。} $$
よって $\hat{v}(A \Leftrightarrow B)$ は評価規則 $(5),(6)$により定まる。

例えば、$k=3$ として命題変数 $P_1,P_2,P_3$ を考える。
真偽値割当（評価）とは
$$ v:\{P_1,P_2,P_3\}\to\{T,F\} $$
のことであり、各 $P_i$ に $T$ または $F$ を割り当てる。例えば、次のような割当は真偽値割当である。
$$ \begin{align} v(P_1)&=T\\ v(P_2)&=F\\ v(P_3)&=T \end{align} $$
この $v$ を論理式全体へ再帰的に拡張した評価を $\hat v$ とする。
このとき、例えば論理式
$$ (P_1\land \neg P_2)\Rightarrow P_3 $$
を考えると、上の真偽値割当 $v$ のもとで
$$ \hat v\bigl((P_1\land \neg P_2)\Rightarrow P_3\bigr)=T $$
となる。実際に計算すると
$$ \begin{align} \hat v(\neg P_2)&=T\\ \hat v(P_1\land \neg P_2)&=T\\ \hat v\bigl((P_1\land \neg P_2)\Rightarrow P_3\bigr)&=T \end{align} $$
である。

恒真式は、どのように真偽値を割り当てても常に真となる論理式である。例えば
$$ P\lor(\neg P) $$
は恒真式である(後に示す)。

矛盾式は、どのように真偽値を割り当てても常に偽となる論理式である。例えば
$$ P\land(\neg P) $$
は矛盾式である。

充足可能でない論理式は、矛盾式である。すなわち
$$ \text{$f$ が充足可能でない}\ \Longleftrightarrow\ \text{$f$ は矛盾式である} $$
が成り立つ。
実際、$f$ が充足可能でないとは、任意の真偽値割当 $v$ に対し、その拡張 $\hat v$ について$\hat{v}(f)=F$ が成り立つことであり、
これは矛盾式の定義そのものである。

論理式 $f$ がトートロジーであるとは、任意の真偽値割当 $v$ に対し、その拡張 $\hat v$ について $\hat{v}(f)=T$ が成り立つことであった。
従ってトートロジーは必ず充足可能である。
$$ \text{$f$ がトートロジー}\ \Rightarrow\ \text{$f$ は充足可能} $$

紛らわしいので整理すると、

1. $P\Leftrightarrow Q$ は論理式（オブジェクト言語）
2. $f\equiv g$ は「全ての評価で同じ真理値」を表すメタレベルの関係

-である。

逆・裏・対偶の関係を図で表現すると、以下のようになる。
$$ \begin{array}{ccc} \text{元} & & \text{逆} \\ (P \Rightarrow Q) & \longleftrightarrow & (Q \Rightarrow P) \\ \Updownarrow & & \Updownarrow \\ (\lnot Q \Rightarrow \lnot P) & \longleftrightarrow & (\lnot P \Rightarrow \lnot Q) \\ \text{対偶} & & \text{裏} \end{array} $$
特に命題の「対偶」は $P\Rightarrow Q$ と同値である。すなわち
$$ (P\Rightarrow Q)\equiv(\neg Q\Rightarrow \neg P) $$
が成り立つ。一方、「逆」や「裏」は一般には $P\Rightarrow Q$ と同値ではない。
ただし「逆」と「裏」は互いに同値である。すなわち
$$ (Q\Rightarrow P)\equiv(\neg P\Rightarrow \neg Q) $$
が成り立つ。