命題論理 ①

命題とは、宣言文（平叙文）であって、その意味内容に対して
$$ \text{真} \quad \text{または} \quad \text{偽} $$
のどちらか一方が 定まる ものをいう。

真偽値とは
$$ \{T,F\} $$
の$2$つの値のことであり、$T$ は「真」，$F$ は「偽」を表す。

命題 $P$ と命題 $Q$ に対し、「$P$ または $Q$」を $P \lor Q$ と書く。
このとき $P \lor Q$ の真偽は次の真理表で定義する。
$$ \begin{array}{|c|c|c|} \hline P & Q & P \lor Q \\ \hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \\ \hline \end{array} $$

命題 $P$ と命題 $Q$ に対し、「$P$ かつ $Q$」を $P \land Q$ と書く。
このとき $P \land Q$ の真偽は次の真理表で定義する。
$$ \begin{array}{|c|c|c|} \hline P & Q & P \land Q \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \\ \hline \end{array} $$

命題 $P$ と命題 $Q$ に対し、「$P$ ならば $Q$」を $P \Rightarrow Q$ と書く。
このとき $P \Rightarrow Q$ の真偽は次の真理表で定義する。
$$ \begin{array}{|c|c|c|} \hline P & Q & P \Rightarrow Q \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \hline \end{array} $$

命題 $P$ に対し、「$P$ でない（$P$ の否定）」を $\neg P$ と書く。
このとき $\neg P$ の真偽は次の真理表で定義する。
$$ \begin{array}{|c|c|} \hline P & \neg P \\ \hline T & F \\ F & T \\ \hline \end{array} $$

命題 $P$ と命題 $Q$ に対し、$ (P \Rightarrow Q) \land (Q \Rightarrow P) $ を表す記号として $P \Leftrightarrow Q$ を定める。
これを同値（同値記号）という。
$ $
このとき $P \Leftrightarrow Q$ の真偽は、$P \Rightarrow Q$ と $Q \Rightarrow P$ および $\land$ の定義から決まる。
真理表で表すと次の通りである。
$$ \begin{array}{|c|c|c|c|c|} \hline P & Q & P \Rightarrow Q & Q \Rightarrow P & P \Leftrightarrow Q \\ \hline T & T & T & T & T \\ T & F & F & T & F \\ F & T & T & F & F \\ F & F & T & T & T \\ \hline \end{array} $$

命題変数とは、命題論理の形式言語における記号（文字）のことであり、真偽値を表すための変数である。
より厳密には、命題変数全体の集合 $\mathcal{P}$ を
$$ \mathcal{P}=\{P_1,P_2,P_3,\cdots\} $$
のような互いに異なる記号の集合として定め、その各要素 $P\in\mathcal{P}$ を命題変数という。

命題変数 $P_1, P_2, \cdots, P_k$ を固定する。次で定める集合 $\mathcal{F}(P_1,\cdots,P_k)$ の元を命題論理式（論理式）という。
$$ \begin{align} \text{(i)}\ & P_i \in \mathcal{F}(P_1,\cdots,P_k)\quad (i=1,2,\cdots,k).\\ \text{(ii)}\ & A\in \mathcal{F}(P_1,\cdots,P_k)\ \Rightarrow\ \neg A \in \mathcal{F}(P_1,\cdots,P_k).\\ \text{(iii)}\ & A,B\in \mathcal{F}(P_1,\cdots,P_k)\ \Rightarrow\ (A\lor B),(A\land B),(A\Rightarrow B)\in \mathcal{F}(P_1,\cdots,P_k).\\ \text{(iv)}\ & \mathcal{F}(P_1,\cdots,P_k)\text{ は (i)--(iii) を満たす最小の集合である。} \end{align} $$
ここで $A,B$ は任意の論理式を表す（メタ）記号とする。

命題変数 $P_1, P_2, \cdots, P_k$ を固定する。各 $i$ に対し真偽値を割り当てる関数
$$ v:\{P_1,P_2,\cdots,P_k\}\to\{T,F\} $$
を真偽値割当（評価）という。評価 $v$ は次の規則により（唯一つに）論理式全体へ拡張される。
この拡張も同じ記号 $v$ で表し、例えば論理式 $f$ の真偽値を $v(f)\in\{T,F\}$ と書く。
$$ \begin{align} \text{(0)}\ & v(P_i)\text{ は与えられた割当により定めた値 }v(P_i)\in\{T,F\}\text{ とする。}\\ \text{(1)}\ & v(\neg A)\text{ は }v(A)\text{ と反対の真偽値である。}\\ \text{(2)}\ & v(A\lor B)\text{ は }\lor\text{ の真理表に従う。}\\ \text{(3)}\ & v(A\land B)\text{ は }\land\text{ の真理表に従う。}\\ \text{(4)}\ & v(A\Rightarrow B)\text{ は }\Rightarrow\text{ の真理表に従う。} \end{align} $$
ここで $A,B$ は任意の論理式を表す（メタ）記号とする。

論理式 $f(P_1,P_2,\cdots,P_k)$ がトートロジー（恒真式）であるとは、全ての評価 $v$ について $v(f)=T$ が成り立つことをいう。

論理式 $f(P_1,P_2,\cdots,P_k)$ が矛盾式であるとは、全ての評価 $v:\{P_1,P_2,\cdots,P_k\}\to\{T,F\}$ に対して
$$ v(f)=F $$
が成り立つことをいう。

論理式 $f(P_1,P_2,\cdots,P_k)$ が充足可能であるとは、ある評価 $v:\{P_1,P_2,\cdots,P_k\}\to\{T,F\}$ が存在して
$$ v(f)=T $$
が成り立つことをいう。

$P_1,P_2,\cdots,P_k$ を命題変数とし、$f(P_1,P_2,\cdots,P_k)$，$g(P_1,P_2,\cdots,P_k)$ をそれらから作られた論理式とする。
評価（真偽値割当）$v:\{P_1,P_2,\cdots,P_k\}\to\{T,F\}$ に対し、$v(f),v(g)$ をそれぞれ $f,g$ の真偽値とする。
$ $
このとき $f$ と $g$ が同値であるとは、全ての評価 $v$ について
$$ v(f)=v(g) $$
が成り立つことをいう。このとき、
$$ f(P_1,P_2,\cdots,P_k)\equiv g(P_1,P_2,\cdots,P_k) $$
と表す。

「$P \Leftrightarrow Q$」が $T$ であることと、$P$ と $Q$ の真偽が一致することは同値である。すなわち、
$$ 『\ P \Leftrightarrow Q\ \text{は}\ T\ 』\Longleftrightarrow P\ \text{と}\ Q\ \text{の真偽が一致する。} $$

$P \lor (\neg P)$ はトートロジーである。

命題 $P$ とその二重否定 $\neg(\neg P)$ は同値である。すなわち
$$ P \equiv \neg(\neg P) $$
が成り立つ。

命題 $P$ について次が成り立つ。

1. $P\land(\neg P)$ の真偽は $P$ の真偽によらず常に $F$ である。従って $P\land(\neg P)$ は矛盾式である。
2. $\neg\bigl(P\land(\neg P)\bigr)$ はトートロジーである。

論理式 $f(P_1,P_2,\cdots,P_k)$ と $g(P_1,P_2,\cdots,P_k)$ について、次は同値である。

1. 全ての評価 $v:\{P_1,P_2,\cdots,P_k\}\to\{T,F\}$ に対し $v(f)=v(g)$ が成り立つ。
2. 論理式 $f(P_1,P_2,\cdots,P_k)\Leftrightarrow g(P_1,P_2,\cdots,P_k)$ はトートロジーである。