述語論理において論理式が恒真式であるとは、任意の解釈においてその論理式の値が 1 であることを意味します。また、論理式が恒偽式であるとは、任意の解釈においてその論理式の値が 0 であることを意味します。恒真式や恒偽式ではない論理式を事実式と呼びます。

恒真式

論理式の値が任意の解釈において\(1\)であるならば、その論理式を恒真式(tautology)やトートロジー(tautology)などと呼びます。

論理式の解釈について復習する

恒真式を表す記号を\(\top \)と定めます。命題定数\(T\)は論理式ですから、これもまた恒真式です。

例(恒真な閉論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)を部分論理式として持つ閉論理式\begin{equation}
\exists x\in X\ \left( \lnot P\left( x\right) \right) \leftrightarrow \lnot \left( \exists x\in X\ P\left( x\right) \right) \tag{1}
\end{equation}について考えます。存在記号\(\exists \)の定義より、上の論理式は、\begin{equation}
\bigvee\nolimits_{x\in X}\lnot P\left( x\right) \leftrightarrow \lnot \left( \bigwedge\nolimits_{x\in X}P\left( x\right) \right) \tag{2}
\end{equation}と言い換えられます。さらに、\(\left( 2\right) \)中の\(\leftrightarrow \)の左側の部分論理式はド・モルガンの法則より、\begin{equation*}
\bigvee\nolimits_{x\in X}\lnot P\left( x\right) \Leftrightarrow \lnot \left( \bigwedge\nolimits_{x\in X}P\left( x\right) \right)
\end{equation*}と言い換え可能ですが、これは\(\left( 2\right) \)中の\(\leftrightarrow \)の右側の部分論理式に他なりません。任意の解釈において\(\left( 2\right) \)中の\(\leftrightarrow \)の左右の部分論理式の値は一致するため、任意の解釈において\(\left( 1\right) \)は真になります。したがって\(\left( 1\right) \)は恒真式です。
例(恒真な開論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)を要素として持つ開論理式\begin{equation}
P\left( x\right) \ \wedge Q\left( x\right) \ \rightarrow \ P\left( x\right) \tag{1}
\end{equation}について考えます。この論理式に解釈を与えるということは、定義域\(X\)を特定し、関数\(P,Q\)の形状を特定し、さらに定義域\(X\)の中から特定の値\(\bar{x}\)を選ぶことを意味します。したがって解釈は無限通り存在しますが、それらは以下の 4 通り\begin{eqnarray*}
&&\left( a\right) \ P\left( \bar{x}\right) \text{と}Q\left( \bar{x}\right) \text{がともに真の場合} \\
&&\left( b\right) \ P\left( \bar{x}\right) \text{が真で}Q\left( \bar{x}\right) \text{が偽の場合} \\
&&\left( c\right) \ P\left( \bar{x}\right) \text{が偽で}Q\left( \bar{x}\right) \text{が真の場合} \\
&&\left( d\right) \ P\left( \bar{x}\right) \text{と}Q\left( \bar{x}\right) \text{がともに偽の場合}
\end{eqnarray*}に分類可能です。それぞれの場合における\(\left( 1\right) \)の値を特定するために真理値表を描くと、
$$\begin{array}{cccc}
\hline
P\left( \bar{x}\right)  & Q\left( \bar{x}\right)  & P\left( \bar{x} \right) \wedge Q\left( \bar{x}\right)  & P\left( \bar{x}\right) \wedge Q\left( \bar{x}\right) \rightarrow P\left( \bar{x}\right)  \\ \hline
1 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 1 \\ \hline
0 & 1 & 0 & 1 \\ \hline
0 & 0 & 0 & 1 \\ \hline
\end{array}$$
表:論理式の値

を得ます。つまり、開論理式\(\left( 1\right) \)は任意の解釈のもとで値が\(1\)になることが示されたため、これは恒真式です。

逆に、論理式が恒真でないとは、少なくとも 1 つの解釈においてその論理式の値が\(0\)になることを意味します。以下が恒真ではない論理式の例です。

例(恒真ではない閉論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)を部分論理式として持つ閉論理式\begin{equation}
\left( \forall x\in X\ P\left( x\right) \right) \ \vee \ \left( \forall x\in X\ \lnot P\left( x\right) \right) \tag{1}
\end{equation}について考えます。変数\(x\)は有限個の値\(x_{1},\cdots ,x_{n}\in X\)をとるものとします。このとき、上の論理式は、\begin{equation}
\left( \bigwedge\nolimits_{i=1}^{n}\ P\left( x_{i}\right) \right) \ \vee \ \left( \bigwedge\nolimits_{i=1}^{n}\ \lnot P\left( x_{i}\right) \right) \tag{2}
\end{equation}と言い換えられます。さらに、\(P\left( x_{j}\right) \)が真で\(P\left( x_{k}\right) \)が偽になるような値\(x_{j},x_{k}\in X\)と命題関数\(P\left( x\right) \)に注目します。以上の解釈のもとでは\(\left( 2\right) \)中の\(\vee \)の左右の部分論理式はともに偽になるため\(\left( 2\right) \)も偽になります。したがって\(\left( 1\right) \)は恒真式ではありません。

 

恒偽式

論理式の値が任意の解釈において\(0\)であるならば、その論理式を恒偽式(contradictory)と呼びます。

恒偽式を表す記号を\(\bot \)と定めます。命題定数\(F\)は論理式ですから、これもまた恒偽式です。

 

事実式

恒真式や恒偽式ではない論理式を事実式(contingency)や整合式などと呼びます。つまり、ある論理式が事実式であるとは、その論理式の値が\(1\)になるような解釈と、値が\(0\)になるような解釈の双方が存在するということです。

次回は必要条件と十分条件について学びます。

次へ進む 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
Share on print

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するためにはログインが必要です
ログイン

述語論理
アカウント
ログイン