ド・モルガンの法則
論理式\(A,B\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)でそれぞれ表記します。すると命題論理におけるド・モルガンの法則より、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \overline{A}\wedge \overline{B}\right)
\Leftrightarrow \lnot \overline{A}\vee \lnot \overline{B} \\
&&\left( b\right) \ \lnot \left( \overline{A}\vee \overline{B}\right)
\Leftrightarrow \lnot \overline{A}\wedge \lnot \overline{B}
\end{eqnarray*}がともに成り立ちます。任意の解釈において同様の議論が成立するため、\begin{align*}
& \left( a\right) \ \lnot \left( A\wedge B\right) \Leftrightarrow \lnot
A\vee \lnot B \\
& \left( b\right) \ \lnot \left( A\vee B\right) \Leftrightarrow \lnot
A\wedge \lnot B
\end{align*}がともに成り立つことが示されました。つまり、述語論理においてもド・モルガンの法則(De Morgan’s law)が成り立つということです。
A\vee \lnot B \\
& \left( b\right) \ \lnot \left( A\vee B\right) \Leftrightarrow \lnot
A\wedge \lnot B
\end{align*}が成り立つ。
y\right) \right) \right) &\Leftrightarrow &\lnot P\left( x\right) \vee \lnot
\left( Q\left( x,y\right) \vee R\left( y\right) \right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot P\left( x\right) \vee \left( \lnot Q\left(
x,y\right) \wedge \lnot R\left( y\right) \right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \lnot P\left( x\right) \vee \lnot Q\left(
x,y\right) \right) \wedge \left( \lnot P\left( x\right) \vee \lnot R\left(
y\right) \right) \quad \because \text{分配律} \\
&\Leftrightarrow &\lnot \left( P\left( x\right) \wedge Q\left( x,y\right)
\right) \wedge \lnot \left( P\left( x\right) \wedge R\left( y\right) \right)
\quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot \left( \left( P\left( x\right) \wedge Q\left(
x,y\right) \right) \vee \left( P\left( x\right) \wedge R\left( y\right)
\right) \right) \quad \because \text{ド・モルガンの法則}
\end{eqnarray*}が成り立ちます。
Q\left( y\right) &:&y\text{は}3\text{で割り切れる}
\end{eqnarray*}を定義すると、「\(x\)は\(2 \)または\(3\)の少なくとも一方で割り切れる」という主張は、\begin{equation*}P\left( x\right) \vee Q\left( y\right)
\end{equation*}と定式化されます。したがって、その否定は、\begin{equation*}
\lnot \left( P\left( x\right) \vee Q\left( y\right) \right)
\end{equation*}となりますが、ド・モルガンの法則より、これは、\begin{equation*}
\lnot P\left( x\right) \wedge \lnot Q\left( y\right)
\end{equation*}と論理的に同値です。つまり、「\(x\)は\(2\)または\(3\)の少なくとも一方で割り切れる」という主張の否定は「\(x\)は\(2\)で割り切れず\(3\)でも割り切れない」となります。
ド・モルガンの法則の一般化
論理式\(A,B,C\)に対してド・モルガンの法則を繰り返し適用することにより、\begin{align*}\lnot \left( A\wedge B\wedge C\right) & \Leftrightarrow \lnot \left( \left(
A\wedge B\right) \wedge C\right) \quad \because \text{結合律} \\
& \Leftrightarrow \lnot \left( A\wedge B\right) \vee \lnot C\quad \because
\text{ド・モルガンの法則} \\
& \Leftrightarrow \left( \lnot A\vee \lnot B\right) \vee \lnot C\because
\text{ド・モルガンの法則} \\
& \Leftrightarrow \lnot A\vee \lnot B\vee \lnot C\quad \because \text{結合律}
\end{align*}すなわち、\begin{equation*}
\lnot \left( A\wedge B\wedge C\right) \Leftrightarrow \lnot A\vee \lnot
B\vee \lnot C
\end{equation*}が得られます。論理和についても同様に考えると、\begin{equation*}
\lnot \left( A\vee B\vee C\right) \Leftrightarrow \lnot A\wedge \lnot
B\wedge \lnot C
\end{equation*}が得られます。
有限かつ任意個の論理式についても同様の議論が成り立ちます。すなわち、有限\(n\)個の論理式\(A_{1},\cdots ,A_{n}\)について、\begin{equation*}\lnot \left( A_{1}\wedge \cdots \wedge A_{n}\right) \Leftrightarrow \lnot
A_{1}\vee \cdots \vee \lnot A_{n}
\end{equation*}という関係が成立するため、これを、\begin{equation*}
\lnot \left( \bigwedge\limits_{i=1}^{n}A_{i}\right) \Leftrightarrow
\bigvee\limits_{i=1}^{n}\left( \lnot A_{i}\right)
\end{equation*}で表します。論理和についても同様に考えると、\begin{equation*}
\lnot \left( A_{1}\vee \cdots \vee A_{n}\right) \Leftrightarrow \lnot
A_{1}\wedge \cdots \wedge \lnot A_{n}
\end{equation*}という関係が成立するため、これを、\begin{equation*}
\lnot \left( \bigvee\limits_{i=1}^{n}A_{i}\right) \Leftrightarrow
\bigwedge\limits_{i=1}^{n}\left( \lnot A_{i}\right)
\end{equation*}で表します。これは\(n\)に関する数学的帰納法により証明できます。
&\Leftrightarrow &\bigvee_{i=1}^{n}\left( \lnot A_{i}\right) \\
\left( b\right) \ \lnot \left( \bigvee_{i=1}^{n}A_{i}\right)
&\Leftrightarrow &\bigwedge_{i=1}^{n}\left( \lnot A_{i}\right)
\end{eqnarray*}が成り立つ。
量化とド・モルガンの法則
ド・モルガンの法則を踏まえると、全称命題や存在命題に関して以下が成り立ちます。
\Leftrightarrow \forall x\in X:\left( \lnot A\vee \lnot B\right) \\
&&\left( b\right) \ \forall x\in X:\lnot \left( A\vee B\right)
\Leftrightarrow \forall x\in X:\left( \lnot A\wedge \lnot B\right) \\
&&\left( c\right) \ \exists x\in X:\lnot \left( A\wedge B\right)
\Leftrightarrow \exists x\in X:\left( \lnot A\vee \lnot B\right) \\
&&\left( d\right) \ \exists x\in X:\lnot \left( A\vee B\right)
\Leftrightarrow \exists x\in X:\left( \lnot A\wedge \lnot B\right)
\end{eqnarray*}が成り立つ。
Q\left( x\right) \right) \Leftrightarrow \forall x\in X:\left( \lnot P\left(
x\right) \vee \lnot Q\left( x\right) \right) \\
&&\left( b\right) \ \forall x\in X:\lnot \left( P\left( x\right) \vee
Q\left( x\right) \right) \Leftrightarrow \forall x\in X:\left( \lnot P\left(
x\right) \wedge \lnot Q\left( x\right) \right) \\
&&\left( c\right) \ \exists x\in X:\lnot \left( P\left( x\right) \wedge
Q\left( x\right) \right) \Leftrightarrow \exists x\in X:\left( \lnot P\left(
x\right) \vee \lnot Q\left( x\right) \right) \\
&&\left( d\right) \ \exists x\in X:\lnot \left( P\left( x\right) \vee
Q\left( x\right) \right) \Leftrightarrow \exists x\in X:\left( \lnot P\left(
x\right) \wedge \lnot Q\left( x\right) \right)
\end{eqnarray*}などが成り立ちます。
全称命題は論理積を用いて、存在命題は論理和を用いてそれぞれ定義されますが、以上の事実とド・モルガンの法則を踏まえると、論理式\(A\)と変数\(x\in X\)がそれぞれ任意に与えられたとき、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \forall x\in X:A\right) \Leftrightarrow
\exists x\in X:\lnot A \\
&&\left( b\right) \ \lnot \left( \exists x\in X:A\right) \Leftrightarrow
\forall x\in X:\lnot A
\end{eqnarray*}が成り立つことが示されます。つまり、全称命題の否定は否定の存在命題と論理的に同値であり、存在命題の否定は否定の全称命題と論理的に同値です。
\exists x\in X:\lnot A \\
&&\left( b\right) \ \lnot \left( \exists x\in X:A\right) \Leftrightarrow
\forall x\in X:\lnot A
\end{eqnarray*}が成り立つ。
\Leftrightarrow \exists x\in X:\lnot P\left( x\right) \\
&&\left( b\right) \ \lnot \left( \exists x\in X:P\left( x\right) \right)
\Leftrightarrow \forall x\in X:\lnot P\left( x\right)
\end{eqnarray*}がともに成り立ちます。
\Leftrightarrow \exists y\in Y:\lnot P\left( x\right) \\
&&\left( b\right) \ \lnot \left( \exists y\in Y:P\left( x\right) \right)
\Leftrightarrow \forall y\in Y:\lnot P\left( x\right)
\end{eqnarray*}がともに成り立ちます。実際、\begin{eqnarray*}
\lnot \left( \forall y\in Y:P\left( x\right) \right) &\Leftrightarrow
&\lnot P\left( x\right) \quad \because \text{全称命題の定義} \\
&\Leftrightarrow &\exists y\in Y:\lnot P\left( x\right) \quad \because \text{存在命題の定義}
\end{eqnarray*}より\(\left( a\right) \)は成り立ちます。\(\left( b\right) \)についても同様です。
\Leftrightarrow \exists x\in X:\lnot P\left( x,y\right) \\
&&\left( b\right) \ \lnot \left( \exists x\in X:P\left( x,y\right) \right)
\Leftrightarrow \forall x\in X:\lnot P\left( x,y\right)
\end{eqnarray*}がともに成り立ちます。
\end{equation*}の否定をとると、先の命題より、\begin{eqnarray*}
\lnot \left( \forall x\in X,\ \exists y\in Y:P\left( x,y\right) \right)
&\Leftrightarrow &\exists x\in X:\lnot \left( \exists y\in Y:P\left(
x,y\right) \right) \\
&\Leftrightarrow &\exists x\in X,\ \forall y\in Y:\lnot P\left( x,y\right)
\end{eqnarray*}となります。また、以下の論理式\begin{equation*}
\exists x\in X,\ \forall y\in Y:P\left( x,y\right)
\end{equation*}の否定をとると、先の命題より、\begin{eqnarray*}
\lnot \left( \exists x\in X,\ \forall y\in Y:P\left( x,y\right) \right)
&\Leftrightarrow &\forall x\in X:\lnot \left( \forall y\in Y:P\left(
x,y\right) \right) \\
&\Leftrightarrow &\forall x\in X,\ \exists y\in Y:\lnot P\left( x,y\right)
\end{eqnarray*}となります。
\end{equation*}となりますが、先の命題より、この論理式は、\begin{equation*}
\forall x\in \mathbb{R} :x^{2}\not=1
\end{equation*}と論理的に同値です。したがって、もとの主張は「任意の実数\(x\)について\(x^{2}\not=1\)が成り立つ」と言い換え可能です。
\end{equation*}となります。先の命題より、この論理式の否定をとると、\begin{eqnarray*}
\lnot \left( \forall x\in \mathbb{R} :x^{2}\geq x\right) &\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \left( x^{2}\geq x\right) \\
&\Leftrightarrow &\exists x\in \mathbb{R} :x^{2}<x
\end{eqnarray*}となります。したがって、もとの主張の否定は「\(x^{2}<x\)を満たす実数\(x\)が存在する」です。
\end{equation*}となります。この論理式の否定をとると、先の命題より、\begin{eqnarray*}
\lnot \left( \forall x\in \mathbb{R} ,\ \exists y\in \mathbb{R} :y^{3}=x\right) &\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \left( \exists y\in \mathbb{R} :y^{3}=x\right) \\
&\Leftrightarrow &\exists x\in \mathbb{R} ,\ \forall y\in \mathbb{R} :\lnot \left( y^{3}=x\right) \\
&=&\exists x\in \mathbb{R} ,\ \forall y\in \mathbb{R} :y^{3}\not=x
\end{eqnarray*}となります。したがって、もとの主張の否定は「ある実数\(x\)が存在して、それと任意の実数\(y\)の間には\(y^{3}\not=x\)が成り立つ」となります。
\end{equation*}となります。ちなみにこれをアルキメデスの性質と呼びます。この論理式の否定をとると、先の命題より、\begin{eqnarray*}
\lnot \left( \forall x\in \mathbb{R} ,\ \exists n\in \mathbb{N} :x<n\right) &\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \left( \exists n\in \mathbb{N} :x<n\right) \\
&\Leftrightarrow &\exists x\in \mathbb{R} ,\ \forall n\in \mathbb{N} :\lnot \left( x<n\right) \\
&\Leftrightarrow &\exists x\in \mathbb{R} ,\ \forall n\in \mathbb{N} :x\geq n
\end{eqnarray*}となります。したがって、もとの主張の否定は「ある実数は任意の自然数以上である」もしくは「任意の自然数以上であるような実数が存在する」という主張に相当します。
含意の全称・存在の否定
論理式\(A,B\)と変数\(x\in X\)がそれぞれ任意に与えられたとき、先の命題と含意の定義を踏まえると、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \forall x\in X:\left( A\rightarrow B\right)
\right) \Leftrightarrow \exists x\in X:\left( A\wedge \lnot B\right) \\
&&\left( b\right) \ \lnot \left( \exists x\in X:\left( A\rightarrow B\right)
\right) \Leftrightarrow \forall x\in X:\left( A\wedge \lnot B\right)
\end{eqnarray*}を得ます。
\right) \Leftrightarrow \exists x\in X:\left( A\wedge \lnot B\right) \\
&&\left( b\right) \ \lnot \left( \exists x\in X:\left( A\rightarrow B\right)
\right) \Leftrightarrow \forall x\in X:\left( A\wedge \lnot B\right)
\end{eqnarray*}が成り立つ。
x\right) \right) \right) \Leftrightarrow \exists x\in X:\left( P\left(
x\right) \wedge \lnot Q\left( x\right) \right)
\end{equation*}が成り立ちます。つまり、「任意の\(x\)について\(P\left( x\right) \)ならば\(Q\left( x\right) \)が成り立つ」という主張の否定は「\(P\left( x\right) \)が成り立つが\(Q\left( x\right) \)は成り立たないような\(x\)が存在する」です。同様に、\begin{equation*}\lnot \left( \exists x\in X:\left( P\left( x\right) \rightarrow Q\left(
x\right) \right) \right) \Leftrightarrow \forall x\in X:\left( P\left(
x\right) \wedge \lnot Q\left( x\right) \right)
\end{equation*}が成り立ちます。つまり、「\(P\left( x\right) \)ならば\(Q\left( x\right) \)が成り立つような\(x\)が存在する」という主張の否定は「任意の\(x\)について\(P\left( x\right) \)は成り立つが\(Q\left( x\right) \)は成り立たない」です。
\end{equation*}として定式化されます。この論理式の否定は、\begin{eqnarray*}
\lnot \left( \forall x\in \mathbb{R} :\left( x>2\rightarrow x^{2}\geq 4\right) \right) &\Leftrightarrow &\exists
x\in \mathbb{R} :\lnot \left( x>2\rightarrow x^{2}\geq 4\right) \quad \because \text{量化記号と否定} \\
&\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \left( \lnot \left( x>2\right) \vee x^{2}\geq 4\right) \quad \because
\text{含意の言い換え} \\
&\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \lnot \left( x>2\right) \wedge \lnot \left( x^{2}\geq 4\right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\exists x\in \mathbb{R} :\left( x>2\wedge x^{2}<4\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。したがって、もとの主張の否定は「\(x>2\)かつ\(x^{2}<4\)を満たす実数\(x\)が存在する」です。
\end{equation*}を導入すると、もとの主張は、\begin{equation*}
\forall x\in X:\left( \lnot P\left( x,B\right) \rightarrow P\left(
A,x\right) \right)
\end{equation*}という論理式として定式化されます。この論理式の否定は、\begin{eqnarray*}
\lnot \left( \forall x\in X:\left( \lnot P\left( x,B\right) \rightarrow
P\left( A,x\right) \right) \right) &\Leftrightarrow &\exists x\in X:\lnot
\left( \lnot P\left( x,B\right) \rightarrow P\left( A,x\right) \right) \quad
\because \text{量化記号と否定} \\
&\Leftrightarrow &\exists x\in X:\lnot \left( \lnot \lnot P\left( x,B\right)
\vee P\left( A,x\right) \right) \quad \because \text{含意の言い換え} \\
&\Leftrightarrow &\exists x\in X:\lnot \left( P\left( x,B\right) \vee
P\left( A,x\right) \right) \quad \because \text{二重否定} \\
&\Leftrightarrow &\exists x\in X:\left( \lnot P\left( x,B\right) \wedge
\lnot P\left( A,x\right) \right) \quad \because \text{ド・モルガンの法則}
\end{eqnarray*}となります。したがって、もとの主張の否定は、「\(A\)さんが好きではない人の中に\(B\)さんを好きではない人が存在する」となります。
演習問題
Q\left( x,y\right) &:&xy=1
\end{eqnarray*}を導入します。以下の問いに答えてください。
- 「\(x\not=0\)を満たす任意の整数\(x\)について、\(xy=1\)を満たす整数\(y\)が存在する」という主張を論理式として定式化してください。
- 問1で得た論理式の否定をとってください。
- 問2で得た論理式を日常言語で表現してください。
- 問1で得た論理式と問2で得た論理式、どちらが真であるか理由とともに答えてください。
\end{equation}について考えます。以下の問いに答えてください。
- 論理式\(\left( 1\right) \)の否定をとってください。
- 変数\(x,y,z\)の定義域\(X,Y,Z\)がいずれもすべての整数からなる集合\(\left\{ \cdots,-2,-1,0,1,2,\cdots \right\} \)であるとき、論理式\(\left( 1\right) \)と問2で得た論理式、どちらが真であるか理由とともに答えてください。
- 変数\(x,y,z\)の定義域\(X,Y,Z\)がいずれも\(1\)以上\(100\)以下の整数からなる集合\(\left\{ 1,2,\cdots ,100\right\} \)であるとき、論理式\(\left( 1\right) \)と問2で得た論理式、どちらが真であるか理由とともに答えてください。
\end{equation*}と定義します。以下の問いに答えてください。
- 「誰しも知り合いがいる」という言明を論理式として定式化してください。
- 問1で得た論理式の否定をとってください。
- 問2で得た論理式を日常言語で表現してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】