述語論理における論理演算の言い換え

含意の言い換え

論理式\(A,B\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)でそれぞれ表記します。すると命題論理における含意の同値変形より、\begin{equation*}\overline{A}\rightarrow \overline{B}\Leftrightarrow \lnot \overline{A}\vee
\overline{B}
\end{equation*}が成り立ちます。任意の解釈において同様の議論が成立するため、\begin{equation*}
A\rightarrow B\Leftrightarrow \lnot A\vee B
\end{equation*}が成り立つことが示されました。

命題（含意の言い換え）

任意の論理式\(A,B\)に対して、\begin{equation*}A\rightarrow B\Leftrightarrow \lnot A\vee B
\end{equation*}が成り立つ。

上の命題より、論理式中の含意\(\rightarrow \)は否定\(\lnot \)と論理和\(\vee \)へ変換可能であるため、否定と論理和さえ定義されていれば含意を独立した論理演算として定義する必要はありません。ただ、含意を独立した論理演算として定義しておくと便利であるため、引き続き含意を利用します。

例（含意の言い換え）

命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)をそれぞれ任意に選んだとき、先の命題より、\begin{equation*}P\left( x\right) \rightarrow Q\left( x\right) \Leftrightarrow \lnot P\left(
x\right) \vee Q\left( x\right)
\end{equation*}が成り立ちます。

例（含意の言い換え）

命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)および\(R\left( x\right) \)をそれぞれ任意に選んだとき、\begin{eqnarray*}\left( P\left( x\right) \wedge Q\left( x\right) \right) \rightarrow R\left(
x\right) &\Leftrightarrow &\lnot \left( P\left( x\right) \wedge Q\left(
x\right) \right) \vee R\left( x\right) \quad \because \text{含意の言い換え} \\
&\Leftrightarrow &\left( \lnot P\left( x\right) \vee \lnot Q\left( x\right)
\right) \vee R\left( x\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &P\left( x\right) \vee Q\left( x\right) \vee R\left(
x\right) \quad \because \text{結合律}
\end{eqnarray*}が成り立ちます。

例（含意の言い換え）

命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)および\(R\left( x\right) \)をそれぞれ任意に選んだとき、\begin{eqnarray*}\left( P\left( x\right) \wedge \lnot Q\left( x\right) \right) \rightarrow
\lnot R\left( x\right) &\Leftrightarrow &\lnot \left( P\left( x\right)
\wedge \lnot Q\left( x\right) \right) \vee \lnot R\left( x\right) \quad
\because \text{含意の言い換え} \\
&\Leftrightarrow &\left( \lnot P\left( x\right) \vee \lnot \lnot Q\left(
x\right) \right) \vee \lnot R\left( x\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot P\left( x\right) \vee Q\left( x\right) \vee \lnot
R\left( x\right) \quad \because \text{二重否定の法則}
\end{eqnarray*}が成り立ちます。

先の命題を踏まえると、全称命題や存在命題に関して以下が成り立ちます。

命題（量化と含意の言い換え）

任意の論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( A\rightarrow B\right)
\Leftrightarrow \forall x\in X:\left( \lnot A\vee B\right) \\
&&\left( b\right) \ \exists x\in X:\left( A\rightarrow B\right)
\Leftrightarrow \exists x\in X:\left( \lnot A\vee B\right)
\end{eqnarray*}が成り立つ。

証明

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

例（量化と含意の言い換え）

命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)をそれぞれ任意に選んだとき、先の命題より、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( P\left( x\right) \rightarrow
Q\left( x\right) \right) \Leftrightarrow \forall x\in X:\left( \lnot P\left(
x\right) \vee Q\left( x\right) \right) \\
&&\left( b\right) \ \exists x\in X:\left( P\left( x\right) \rightarrow
Q\left( x\right) \right) \Leftrightarrow \exists x\in X:\left( \lnot P\left(
x\right) \vee Q\left( x\right) \right)
\end{eqnarray*}が成り立ちます。

例（量化と含意の言い換え）

「任意の整数\(x\)について\(x\)が\(4\)の倍数ならば\(x\)は偶数である」という主張について考えます。変数\(x\)の定義域はすべての整数からなる集合\(\mathbb{Z} \)です。主張を定式化すると、\begin{equation*}\forall x\in \mathbb{Z} :\left( x\text{は}4\text{の倍数}\rightarrow x\text{は偶数}\right)
\end{equation*}となりますが、先の命題より、この論理式は、\begin{equation*}
\forall x\in \mathbb{Z} :\left( \lnot \left( x\text{は}4\text{の倍数}\right)
\vee x\text{は偶数}\right)
\end{equation*}と論理的に同値です。したがって、もとの主張は「任意の整数\(x\)について\(x\)は\(4\)の倍数ではないか偶数であるかの少なくとも一方である」と言い換え可能です。

例（量化と含意の言い換え）

「任意の実数\(x,y,z\)について\(x\geq y\)かつ\(y\geq z\)ならば\(x\geq z\)である」という主張について考えます。変数\(x,y,z\)の定義域はすべての実数からなる集合\(\mathbb{R} \)です。主張を定式化すると、\begin{equation*}\forall x\in \mathbb{R} ,\ \forall y\in \mathbb{R} ,\ \forall z\in \mathbb{R} :\left( \left( x\geq y\wedge y\geq y\right) \rightarrow x\geq z\right)
\end{equation*}となりますが、先の命題を用いてこれを同値変形すると、\begin{eqnarray*}
\forall x &\in &\mathbb{R} ,\ \forall y\in \mathbb{R} ,\ \forall z\in \mathbb{R} :\left( \left( x\geq y\wedge y\geq z\right) \rightarrow x\geq z\right) \\
&\Leftrightarrow &\forall x\in \mathbb{R} ,\ \forall y\in \mathbb{R} ,\ \forall z\in \mathbb{R} :\left( \lnot \left( x\geq y\wedge y\geq z\right) \vee x\geq z\right) \quad
\because \text{含意の言い換え} \\
&\Leftrightarrow &\forall x\in \mathbb{R} ,\ \forall y\in \mathbb{R} ,\ \forall z\in \mathbb{R} :\lnot \left( x\geq y\right) \vee \lnot \left( y\geq z\right) \vee x\geq
z\quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\forall x\in \mathbb{R} ,\ \forall y\in \mathbb{R} ,\ \forall z\in \mathbb{R} :\left( x<y\vee y<z\vee x\geq z\right)
\end{eqnarray*}となります。

同等の言い換え

論理式\(A,B\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)でそれぞれ表記します。すると命題論理における同等の同値変形より、\begin{equation*}\overline{A}\rightarrow \overline{B}\Leftrightarrow \left( \overline{A}\rightarrow \overline{B}\right) \wedge \left( \overline{B}\rightarrow
\overline{A}\right)
\end{equation*}が成り立ちます。任意の解釈において同様の議論が成立するため、\begin{equation*}
A\rightarrow B\Leftrightarrow \left( A\rightarrow B\right) \wedge \left(
B\rightarrow A\right)
\end{equation*}が成り立つことが示されました。

命題（同等の言い換え）

任意の論理式\(A,B\)に対して、\begin{equation*}A\rightarrow B\Leftrightarrow \left( A\rightarrow B\right) \wedge \left(
B\rightarrow A\right)
\end{equation*}が成り立つ。

上の命題より、論理式中の同等\(\leftrightarrow \)は含意\(\rightarrow \)と論理積\(\wedge \)へ変換可能です。加えて、先に明らかになったように、含意\(\rightarrow \)は否定\(\lnot \)と論理和\(\vee \)へ変換可能です。したがって、否定と論理積と論理和さえ定義されていれば同等を独立した論理演算として定義する必要はありません。ただ、同等を独立した論理演算として定義しておくと便利であるため、引き続き同等を利用します。

例（同等の言い換え）

命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)をそれぞれ任意に選んだとき、\begin{eqnarray*}P\left( x\right) \leftrightarrow Q\left( x\right) &\Leftrightarrow &\left(
P\left( x\right) \rightarrow Q\left( x\right) \right) \wedge \left( Q\left(
x\right) \rightarrow P\left( x\right) \right) \quad \because \text{同等の言い換え} \\
&\Leftrightarrow &\left( \lnot P\left( x\right) \vee Q\left( x\right)
\right) \wedge \left( \lnot Q\left( x\right) \vee P\left( x\right) \right)
\quad \because \text{含意の言い換え}
\end{eqnarray*}が成り立ちます。

先の命題を踏まえると、全称命題や存在命題に関して以下が成り立ちます。

命題（量化と同等の言い換え）

任意の論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( A\leftrightarrow B\right)
\Leftrightarrow \forall x\in X:\left( \left( A\rightarrow B\right) \wedge
\left( B\rightarrow A\right) \right) \\
&&\left( b\right) \ \exists x\in X:\left( A\leftrightarrow B\right)
\Leftrightarrow \exists x\in X:\left( \left( A\rightarrow B\right) \wedge
\left( B\rightarrow A\right) \right)
\end{eqnarray*}が成り立つ。

証明

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

排他的論理和の言い換え

論理式\(A,B\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)でそれぞれ表記します。すると命題論理における排他的論理和の同値変形より、\begin{equation*}\overline{A}\veebar \overline{B}\Leftrightarrow \left( \overline{A}\wedge
\lnot \overline{B}\right) \vee \left( \lnot \overline{A}\wedge \overline{B}\right)
\end{equation*}が成り立ちます。任意の解釈において同様の議論が成立するため、\begin{equation*}
A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right) \vee \left( \lnot
A\wedge B\right)
\end{equation*}が成り立つことが示されました。

命題（排他的論理和の言い換え）

任意の論理式\(A,B\)に対して、\begin{equation*}A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right) \vee \left( \lnot
A\wedge B\right)
\end{equation*}が成り立つ。

上の命題より、論理式中の排他的論理和\(\veebar \)は否定\(\lnot \)と論理積\(\wedge \)および論理和\(\vee \)へ変換可能であるため、否定と論理積および論理和さえ定義されていれば排他的論理和を独立した論理演算として定義する必要はありません。ただ、排他的論理和を独立した論理演算として定義しておくと便利であるため、引き続き排他的論理和を利用します。

例（排他的論理和の言い換え）

命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)をそれぞれ任意に選んだとき、先の命題より、\begin{equation*}P\left( x\right) \veebar Q\left( x\right) \Leftrightarrow \left( P\left(
x\right) \wedge \lnot Q\left( x\right) \right) \vee \left( \lnot P\left(
x\right) \wedge Q\left( x\right) \right)
\end{equation*}が成り立ちます。

先の命題を踏まえると、全称命題や存在命題に関して以下が成り立ちます。

命題（量化と排他的論理和の言い換え）

任意の論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( A\veebar B\right) \Leftrightarrow
\forall x\in X:\left( \left( A\wedge \lnot B\right) \vee \left( \lnot
A\wedge B\right) \right) \\
&&\left( b\right) \ \exists x\in X:\left( A\veebar B\right) \Leftrightarrow
\exists x\in X:\left( \left( A\wedge \lnot B\right) \vee \left( \lnot
A\wedge B\right) \right)
\end{eqnarray*}が成り立つ。

証明

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

演習問題

問題（論理演算の言い換え）

変数\(x,y\)の定義域\(X\)はいずれも\(1\)以上のすべての整数からなる集合であるとともに、以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\text{は素数である}
\\
Q\left( x,y\right) &:&x\text{は}y\text{で割り切れる}
\end{eqnarray*}を定義します。以下の問いに答えてください。

「素数ではないそれぞれの\(x\)に対して、\(x \)を割り切れる素数\(y\)が存在する」という言明を論理式として定式化してください。
問1で得た論理式の否定をとってください。
問2で得た論理式を日常言語で表現してください。

解答を見る

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

WIIS

WIIS

WIIS

述語論理

述語論理における論理演算の言い換え

目次

含意の言い換え

同等の言い換え

排他的論理和の言い換え

演習問題