恒真式

関係式

$${\cal P}~or~　not {\cal P}$$

について考えてみます。 これは ${\cal P}$が$x = 1$ を表しているものとすれば

$$(x = 1 )~or~ not(x = 1 )$$

という関係式を表しています。前項の$or$と$not$の真理値の計算結果を用いると ${\cal P}$が$T,F$どちらの値をとっても

$$\begin{eqnarray*} &&T~or~ notT=T~or~F=T \\ &&F~or~ notF=F~or~T=T \end{eqnarray*}$$

で恒に$T$となります。 関係式

$${\cal P}~or~　not {\cal P}$$

は、${\cal P}$が$x = 1$ などどのような関係式を表していようと,また,真偽 $T,F$どちらであろうと,恒に真$T$となります。このように関係式には,恒に真$T$となるものがあり,これは恒真式と呼ばれます。恒真式は他にもあり例えば以下のものが知られています。

1. ${\cal A} \Rightarrow {\cal A}$
2. $\cal (A \Rightarrow B) \Rightarrow [(B \Rightarrow C) \Rightarrow (A \Rightarrow C)]$
3. $\cal A \Rightarrow (A \lor B)$
4. $\cal B \Rightarrow (A \lor B)$
5. $\cal (A \Rightarrow C) \Rightarrow \{ (B \Rightarrow C) \Rightarrow [(A \lor B) \Rightarrow C]\}$
6. $\cal (A \land B) \Rightarrow A$
7. $\cal (A \land B) \Rightarrow B$
8. $\cal (C \Rightarrow A) \Rightarrow \{ (C \Rightarrow B) \Rightarrow [C \Rightarrow (A \land B)]\}$
9. $\cal [A \land (A \Rightarrow B)] \Rightarrow B$
10. $\cal [(A \land C) \Rightarrow B] \Rightarrow [C \Rightarrow (A \Rightarrow B)]$
11. $\cal (A \land \neg A) \Rightarrow F$
12. $\cal [(A \land B) \Rightarrow F ] \Rightarrow (B \Rightarrow \neg A)$
13. $\cal A \Rightarrow T$
14. $\cal F \Rightarrow A$
15. $\cal A \lor \neg A$

これらは「命題論理」の公理と呼ばれているものですが,もし,関係式が

$$(\forall {\cal X})({\cal P}({\cal X}))$$

や

$$(\exists {\cal X})({\cal P}({\cal X}))$$

のようなものを含んでいなければ,前述の「代数的な演算」の規則

$$\begin{eqnarray*} &&not~ T=F \\ &&not~ F=T \end{eqnarray*}$$

$$\begin{eqnarray*} &&T~and~T=T \\ &&T~and~F=F \\ &&F~and~T=F \\ &&F~and~F=F \\ \end{eqnarray*}$$

$$\begin{eqnarray*} &&T~or~T=T \\ &&T~or~F=T \\ &&F~or~T=T \\ &&F~or~F=F \\ \end{eqnarray*}$$

に

$$\begin{eqnarray*} &&T~\Leftrightarrow~T=T \\ &&T~\Leftrightarrow~F=F \\ &&F~\Leftrightarrow~T=T \\ &&F~\Leftrightarrow~F=T \\ \end{eqnarray*}$$

を加えたもので,真理値$T,F$　が決定でき,その関係式が恒真式かどうかが判ります。

しかし,

$$(\forall x)(x=1)$$

のような関係式はこのような方法では真理値$T,F$を決めることができません。 $x$が動く範囲が

$$1,2,3,\cdots,10$$

のように 有限ならばこの式は

$$(1=1) ~and~ (2=1) ~and~ \cdots, ~and~ (10=1)$$

と同じなので,真理値は上の「代数的な演算」の規則で決定できますが,一般には, $x$が動く範囲は無限個です。従って,別の方法に拠らなければなりません。