恒真式

1.1.5節では命題変数を $\lnot ,\quad \land, \quad \lor,\quad \Rightarrow$ 結合した式を論理式と呼んだ。 ここではそれを拡張して命題変数を1.1.6節で定義した，真理関数のみで結合した式をも論理式と呼ぶことにする。後に論理式は1.1.5節で定義したもので 総て表せることを示す。 例えば

$$\neg\neg X \Leftrightarrow X, \quad X \lor (Y \land Z)$$

などである。それらの式のうち，、 命題変数の値の如何に関わらす恒に$T$(真)の値のみをとる式を恒真式という。

定理1.1

　以下は恒真式である。左辺と右辺が

$$\phi_{10}$$

の同値 $\Leftrightarrow$で結合されているので 同値恒真式と呼ぶことにする。

(i).

$\neg T \Leftrightarrow F$, $\neg F \Leftrightarrow T$

(ii).

$X \land T \Leftrightarrow X$, $X \lor F \Leftrightarrow X$

(iii).

$X \land F \Leftrightarrow F$, $X \lor T \Leftrightarrow T$

(iv).

$\neg\neg X \Leftrightarrow X$     （二重否定の法則）

(v).

$X \land X \Leftrightarrow X$, $X \lor X \Leftrightarrow X$     （巾等律）

(vi).

$X \land \neg X \Leftrightarrow F$     （矛盾律）,          $X \lor \neg X \Leftrightarrow T$     （排中律）

(vii).

$X \land Y \Leftrightarrow Y \land X$, $X \lor Y \Leftrightarrow Y \lor X$      （交換法則）

(viii).

$X \lor (Y \lor Z) \Leftrightarrow (X \lor Y) \lor Z$     （結合法則）

(ix).

$X \land (Y \land Z) \Leftrightarrow (X \land Y) \land Z$     （結合法則）

(x).

$X \land (X \lor Y) \Leftrightarrow X$     （吸収法則）

(xi).

$X \lor (X \land Y) \Leftrightarrow X$     （吸収法則）

(xii).

$X \land (Y \lor Z) \Leftrightarrow (X \land Y) \lor (X \land Z)$      （分配法則）

(xiii).

$X \lor (Y \land Z) \Leftrightarrow (X \lor Y) \land (X \lor Z)$      （分配法則）

(xiv).

$\neg (X \land Y) \Leftrightarrow \neg X \lor \neg Y$      （ド・モルガンの法則）

(xv).

$\neg (X \lor Y) \Leftrightarrow \neg X \land \neg Y$      （ド・モルガンの法則）

(xvi).

$X \Rightarrow Y \Leftrightarrow \neg X \lor Y$

証明

　上の論理式は何れも左辺と右辺が $\Leftrightarrow$で結合されている。

$X$	$Y$	$X \wedge Y$	$X \vee Y$	$X \Rightarrow Y$	$X \Leftrightarrow Y$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$F$	$T$	$T$	$F$
$F$	$F$	$F$	$F$	$T$	$T$

で $X \Leftrightarrow Y$が$X,Y$とも同じ値のときのみ$T$になることに 注目すれば右辺と左辺の真理表を作ってそれが一致することを確かめればよい。 ここでは、(xii) と (xv) と (xvi) についてのみ示し、他は課題とする。

目的の式の右辺と左辺の真理表とともに補助的に、$X \land Y$, $\neg (X \land Y)$, $\neg X$, $\neg Y$ の真理表も作れば次のようにな る。

$$\begin{array}{\vert cc\vert\vert c\vert c\vert c\vert c\vert ... ... & F & F & T & F & T & T & T & T & T \\ \hline \end{array}$$

上の表から、(10) の左辺 $X \lor (X \land Y)$ と右辺 $X$ の真理表、 (14) の左辺 $\neg (X \land Y)$ と右辺 $\neg X \lor \neg Y$ の真理表、 および、(16) の左辺 $X \Rightarrow Y$ と右辺 $\neg X \lor Y$ の真 理表は、確かにそれぞれ一致している。 $\Box$