含意の言い換え
論理式\(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 \)へ変換可能であるため、否定と論理和さえ定義されていれば含意を独立した論理演算として定義する必要はありません。ただ、含意を独立した論理演算として定義しておくと便利であるため、引き続き含意を利用します。
x\right) \vee Q\left( x\right)
\end{equation*}が成り立ちます。
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*}が成り立ちます。
\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*}が成り立ちます。
先の命題を踏まえると、全称命題や存在命題に関して以下が成り立ちます。
\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*}が成り立つ。
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*}が成り立ちます。
\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\)の倍数ではないか偶数であるかの少なくとも一方である」と言い換え可能です。
\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}\leftrightarrow \overline{B}\Leftrightarrow \left( \overline{A}\rightarrow \overline{B}\right) \wedge \left( \overline{B}\rightarrow
\overline{A}\right)
\end{equation*}が成り立ちます。任意の解釈において同様の議論が成立するため、\begin{equation*}
A\leftrightarrow B\Leftrightarrow \left( A\rightarrow B\right) \wedge \left(
B\rightarrow A\right)
\end{equation*}が成り立つことが示されました。
任意の論理式\(A,B\)に対して、\begin{equation*}A\leftrightarrow 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) \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*}が成り立ちます。
先の命題を踏まえると、全称命題や存在命題に関して以下が成り立ちます。
\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\wedge B\right)
\end{equation*}が成り立つ。
上の命題より、論理式中の排他的論理和\(\veebar \)は否定\(\lnot \)と論理積\(\wedge \)および論理和\(\vee \)へ変換可能であるため、否定と論理積および論理和さえ定義されていれば排他的論理和を独立した論理演算として定義する必要はありません。ただ、排他的論理和を独立した論理演算として定義しておくと便利であるため、引き続き排他的論理和を利用します。
x\right) \wedge \lnot Q\left( x\right) \right) \vee \left( \lnot P\left(
x\right) \wedge Q\left( x\right) \right)
\end{equation*}が成り立ちます。
先の命題を踏まえると、全称命題や存在命題に関して以下が成り立ちます。
\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*}が成り立つ。
演習問題
\\
Q\left( x,y\right) &:&x\text{は}y\text{で割り切れる}
\end{eqnarray*}を定義します。以下の問いに答えてください。
- 「素数ではないそれぞれの\(x\)に対して、\(x \)を割り切れる素数\(y\)が存在する」という言明を論理式として定式化してください。
- 問1で得た論理式の否定をとってください。
- 問2で得た論理式を日常言語で表現してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】