WIIS

教材一覧
教材一覧
教材検索
PREDICATE LOGIC

述語論理における恒真式・恒偽式・事実式

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

恒真式

論理式\(A\)が任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で表記します。任意の解釈のもとで命題\(\overline{A}\)が真になる場合、もとの論理式\(A\)を恒真式(tautology)やトートロジー(tautology)などと呼びます。恒真式を表す記号を\(\top \)と定めます。

例(恒真式)
命題関数\(P\left( x\right) \)に関する論理式\begin{equation}\left( \exists x\in X:\lnot P\left( x\right) \right) \leftrightarrow \lnot
\left( \forall x\in X:P\left( x\right) \right) \quad \cdots (1)
\end{equation}について考えます。量化記号\(\forall ,\exists \)の定義より、これは以下の論理式\begin{equation*}\bigvee\limits_{x\in X}\lnot P\left( x\right) \leftrightarrow \lnot \left(
\bigwedge\limits_{x\in X}P\left( x\right) \right)
\end{equation*}と同一視されます。これは閉論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right) \)の形状を指定する必要があります。そこで、定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left( x\right) \)をそれぞれ任意に選ぶと、以下の命題\begin{equation}\bigvee\limits_{x\in \overline{X}}\lnot \overline{P}\left( x\right)
\leftrightarrow \lnot \left( \bigwedge\limits_{x\in \overline{X}}\overline{P}\left( x\right) \right) \quad \cdots (2)
\end{equation}が得られます。\(\left( 2\right) \)は命題であるため、命題論理を用いて真偽を判定できます。具体的には、ド・モルガンの法則より、\begin{equation*}\bigvee\limits_{x\in \overline{X}}\lnot \overline{P}\left( x\right)
\Leftrightarrow \lnot \left( \bigwedge\limits_{x\in \overline{X}}\overline{P}\left( x\right) \right)
\end{equation*}が成り立つため、\(\left(1\right) \)は真です。任意の解釈において同様であるため、\(\left( 1\right) \)が恒真式であることが示されました。
例(恒真式)
命題関数\(P\left( x\right) ,Q\left( x\right) \)に関する以下の論理式\begin{equation}P\left( x\right) \wedge Q\left( x\right) \rightarrow P\left( x\right)
\quad \cdots (1)
\end{equation}について考えます。これは開論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right),Q\left( x\right) \)の形状および変数\(x\)に代入する値を指定する必要があります。そこで、定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left( x\right) ,\overline{Q}\left( x\right) \)および変数に代入する値\(\overline{x}\)をそれぞれ任意に選ぶと、以下の命題\begin{equation}\overline{P}\left( \overline{x}\right) \wedge \overline{Q}\left( \overline{x}\right) \rightarrow \overline{P}\left( \overline{x}\right) \quad \cdots (2)
\end{equation}を得ます。\(\left( 2\right) \)は命題であるため、命題論理を用いて真偽を判定できます。具体的には、\(\left( 2\right) \)を同値変形すると、\begin{eqnarray*}\overline{P}\left( \overline{x}\right) \wedge \overline{Q}\left( \overline{x}\right) \rightarrow \overline{P}\left( \overline{x}\right) &\Leftrightarrow
&\lnot \left( \overline{P}\left( \overline{x}\right) \wedge \overline{Q}\left( \overline{x}\right) \right) \vee \overline{P}\left( \overline{x}\right) \quad \because \text{含意の言い換え} \\
&\Leftrightarrow &\left( \lnot \overline{P}\left( \overline{x}\right) \vee
\lnot \overline{Q}\left( \overline{x}\right) \right) \vee \overline{P}\left(
\overline{x}\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \overline{P}\left( \overline{x}\right) \vee \lnot
\overline{P}\left( \overline{x}\right) \right) \vee \lnot \overline{Q}\left(
\overline{x}\right) \quad \because \text{交換律} \\
&\Leftrightarrow &\top \vee \lnot \overline{Q}\left( \overline{x}\right)
\quad \because \text{排中律} \\
&\Leftrightarrow &\top \quad \because \text{恒等律}
\end{eqnarray*}となるため\(\left( 2\right) \)は真です。任意の解釈において同様であるため、\(\left( 1\right) \)が恒真式であることが示されました。

 

恒偽式

論理式\(A\)が任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で表記します。任意の解釈のもとで命題\(\overline{A}\)が偽になる場合、もとの論理式\(A\)を恒偽式(contradictory)と呼びます。恒偽式を表す記号を\(\bot \)と定めます。

例(恒偽式)
命題関数\(P\left( x\right) \)に関する論理式\begin{equation}\left( \exists x\in X:\lnot P\left( x\right) \right) \leftrightarrow \left(
\forall x\in X:P\left( x\right) \right) \quad \cdots (1)
\end{equation}について考えます。量化記号\(\forall ,\exists \)の定義より、これは以下の論理式\begin{equation*}\bigvee\limits_{x\in X}\lnot P\left( x\right) \leftrightarrow
\bigwedge\limits_{x\in X}P\left( x\right)
\end{equation*}と同一視されます。これは閉論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right) \)の形状を指定する必要があります。そこで、定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left( x\right) \)をそれぞれ任意に選ぶと、以下の命題\begin{equation}\bigvee\limits_{x\in \overline{X}}\lnot \overline{P}\left( x\right)
\leftrightarrow \bigwedge\limits_{x\in \overline{X}}\overline{P}\left(
x\right) \quad \cdots (2)
\end{equation}が得られます。\(\left( 2\right) \)は命題であるため、命題論理を用いて真偽を判定できます。具体的には、ド・モルガンの法則より、\begin{equation*}\bigvee\limits_{x\in \overline{X}}\lnot \overline{P}\left( x\right)
\Leftrightarrow \lnot \left( \bigwedge\limits_{x\in \overline{X}}\overline{P}\left( x\right) \right)
\end{equation*}が成り立つため、\(\left(2\right) \)は偽です。任意の解釈において同様であるため、\(\left( 1\right) \)が恒偽式であることが示されました。
例(恒偽式)
命題関数\(P\left( x\right) ,Q\left( x\right) \)に関する以下の論理式\begin{equation}(P\left( x\right) \wedge \left( P\left( x\right) \rightarrow Q\left(
x\right) \right) )\wedge \lnot Q\left( x\right) \quad \cdots (1)
\end{equation}について考えます。これは開論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right),Q\left( x\right) \)の形状および変数\(x\)に代入する値を指定する必要があります。そこで、定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left( x\right) ,\overline{Q}\left( x\right) \)および変数に代入する値\(\overline{x}\)をそれぞれ任意に選ぶと、以下の命題\begin{equation}(\overline{P}\left( x\right) \wedge \left( \overline{P}\left( x\right)
\rightarrow \overline{Q}\left( x\right) \right) )\wedge \lnot \overline{Q}\left( x\right) \quad \cdots (2)
\end{equation}を得ます。\(\left( 2\right) \)は命題であるため、命題論理を用いて真偽を判定できます。具体的には、\(\left( 2\right) \)を同値変形すると、\begin{eqnarray*}(\overline{P}\left( \overline{x}\right) \wedge \left( \overline{P}\left(
\overline{x}\right) \rightarrow \overline{Q}\left( \overline{x}\right)
\right) )\wedge \lnot \overline{Q}\left( \overline{x}\right)
&\Leftrightarrow &(\overline{P}\left( \overline{x}\right) \wedge \left(
\lnot \overline{P}\left( \overline{x}\right) \vee \overline{Q}\left(
\overline{x}\right) \right) )\wedge \lnot \overline{Q}\left( \overline{x}\right) \quad \because \text{含意の言い換え} \\
&\Leftrightarrow &(\left( \overline{P}\left( \overline{x}\right) \wedge
\lnot \overline{P}\left( \overline{x}\right) \right) \vee \left( \overline{P}\left( \overline{x}\right) \wedge \overline{Q}\left( \overline{x}\right)
\right) )\wedge \lnot \overline{Q}\left( \overline{x}\right) \quad \because
\text{分配律} \\
&\Leftrightarrow &(\bot \vee \left( \overline{P}\left( \overline{x}\right)
\wedge \overline{Q}\left( \overline{x}\right) \right) )\wedge \lnot
\overline{Q}\left( \overline{x}\right) \quad \because \text{矛盾律} \\
&\Leftrightarrow &\left( \overline{P}\left( \overline{x}\right) \wedge
\overline{Q}\left( \overline{x}\right) \right) \wedge \lnot \overline{Q}\left( \overline{x}\right) \quad \because \text{恒等律} \\
&\Leftrightarrow &\overline{P}\left( \overline{x}\right) \wedge \left(
\overline{Q}\left( \overline{x}\right) \wedge \lnot \overline{Q}\left(
\overline{x}\right) \right) \quad \because \text{交換律} \\
&\Leftrightarrow &\overline{P}\left( \overline{x}\right) \wedge \bot \quad
\because \text{矛盾律} \\
&\Leftrightarrow &\bot \quad \because \text{恒等律}
\end{eqnarray*}となるため\(\left( 2\right) \)は偽です。任意の解釈において同様であるため、\(\left( 1\right) \)が恒偽式であることが示されました。

 

事実式

論理式\(A\)が任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で表記します。命題\(\overline{A}\)が真になる解釈と命題\(\overline{A}\)が偽になる解釈がともに存在する場合、もとの論理式\(A\)を事実式(contingency)や整合式などと呼びます。

例(事実式)
命題関数\(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) \quad \cdots (1)
\end{equation}について考えます。量化記号\(\forall ,\exists \)の定義より、これは以下の論理式\begin{equation*}\left( \bigwedge\limits_{x\in X}P\left( x\right) \right) \vee \left(
\bigwedge\limits_{x\in X}\lnot P\left( x\right) \right)
\end{equation*}と同一視されます。これは閉論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right) \)の形状を指定する必要があります。そこで、定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left( x\right) \)をそれぞれ任意に選ぶと、以下の命題\begin{equation}\left( \bigwedge\limits_{x\in \overline{X}}\overline{P}\left( x\right)
\right) \vee \left( \bigwedge\limits_{x\in \overline{X}}\lnot \overline{P}\left( x\right) \right) \quad \cdots (2)
\end{equation}が得られます。\(\left( 2\right) \)は命題であるため、命題論理を用いて真偽を判定できます。例えば、\begin{eqnarray*}\overline{X} &:&\text{すべての偶数からなる集合} \\
\overline{P}\left( x\right) &:&x\text{は}2\text{で割り切れる}
\end{eqnarray*}のもとでは、\(\overline{X}\)の任意の値\(x\)について命題\(\overline{P}\left( x\right) \)は真であるため\(\left( 2\right) \)は真です。一方、\begin{eqnarray*}\overline{X} &:&\text{すべての偶数からなる集合} \\
\overline{P}\left( x\right) &:&x\text{は}4\text{で割り切れる}
\end{eqnarray*}のもとでは、命題\(\overline{P}\left( x\right) \)が真になるような\(\overline{X}\)の値\(x\)と命題\(\overline{P}\left( x\right) \)が偽になるような\(\overline{X}\)の値\(x\)がともに存在するため\(\left( 2\right) \)は偽です。したがって\(\left( 1\right) \)は事実式であることが示されました。
例(事実式)
命題関数\begin{equation}
P\left( x\right) \quad \cdots (1)
\end{equation}について考えます。これは開論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right) \)の形状および変数\(x\)に代入する値を指定する必要があります。そこで、定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left( x\right) \)および変数に代入する値\(\overline{x}\)をそれぞれ任意に選ぶと、以下の命題\begin{equation}\overline{P}\left( \overline{x}\right) \quad \cdots (2)
\end{equation}を得ます。\(\left( 2\right) \)は命題であるため、命題論理を用いて真偽を判定できます。例えば、\begin{eqnarray*}\overline{X} &:&\text{すべての偶数からなる集合} \\
\overline{P}\left( x\right) &:&x\text{は}2\text{で割り切れる} \\
\overline{x} &:&2
\end{eqnarray*}のもとでは\(\left( 2\right) \)は真になります。一方、\begin{eqnarray*}\overline{X} &:&\text{すべての偶数からなる集合} \\
\overline{P}\left( x\right) &:&x\text{は}2\text{で割り切れる} \\
\overline{x} &:&3
\end{eqnarray*}のもとでは\(\left( 2\right) \)は偽になります。したがって\(\left( 1\right) \)は事実式であることが示されました。

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

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

必要十分条件
命題論理における恒真式・恒偽式・事実式

論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 1 であるならば、その論理式を恒真式やトートロジーなどと呼びます。また、論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 0 であるならば、その論理式を恒偽式や矛盾式などと呼びます。恒真式や恒偽式ではない論理式を事実式と呼びます。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

述語論理