WIIS

述語論理

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

目次

Mailで保存
Xで共有

恒真式

論理式\(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) \)は事実式であることが示されました。

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

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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