ド・モルガンの法則
論理式\(A,B\)を任意に選んだとき、以下の恒真式\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）と呼びます。
論理積の否定\(\lnot \left( A\wedge B\right) \)をとると否定の論理和\(\lnot A\vee \lnot B\)になるというのが\(\left( a\right) \)の主張であり、論理和の否定\(\lnot \left( A\vee B\right) \)をとると否定の論理積\(\lnot A\wedge \lnot B\)になるというのが\(\left( b\right) \)の主張です。
A\vee \lnot B \\
& \left( b\right) \ \lnot \left( A\vee B\right) \Leftrightarrow \lnot
A\wedge \lnot B
\end{align*}が成り立つ。
P\vee \lnot Q \\
& \left( b\right) \ \lnot \left( P\vee Q\right) \Leftrightarrow \lnot
P\wedge \lnot Q
\end{align*}がともに成り立ちます。
Q &\rightarrow &R
\end{eqnarray*}はともに論理式であるため、ド・モルガンの法則より、\begin{align*}
& \left( a\right) \ \lnot \left( \left( P\rightarrow Q\right) \wedge \left(
Q\rightarrow R\right) \right) \Leftrightarrow \lnot \left( P\rightarrow
Q\right) \vee \lnot \left( Q\rightarrow R\right) \\
& \left( b\right) \ \lnot \left( \left( P\rightarrow Q\right) \vee \left(
Q\rightarrow R\right) \right) \Leftrightarrow \lnot \left( P\rightarrow
Q\right) \wedge \lnot \left( Q\rightarrow R\right)
\end{align*}がともに成り立ちます。
\end{equation*}が真であるものとします。このとき、ド・モルガンの法則より、\begin{equation*}
\lnot A\wedge \lnot B
\end{equation*}もまた真です。すると論理積\(\wedge \)の定義より\(\lnot A\)と\(\lnot B\)はともに真であり、したがって否定の定義より\(A\)と\(B\)はともに偽です。
\left( A\wedge B\right) \wedge \lnot \left( A\wedge C\right)
\end{equation*}が成り立つことを証明します。実際、\begin{eqnarray*}
\lnot \left( A\wedge \left( B\vee C\right) \right) &\Leftrightarrow &\lnot
A\vee \lnot \left( B\vee C\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot A\vee \left( \lnot B\wedge \lnot C\right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \lnot A\vee \lnot B\right) \wedge \left( \lnot
A\vee \lnot C\right) \quad \because \text{分配律} \\
&\Leftrightarrow &\lnot \left( A\wedge B\right) \wedge \lnot \left( A\wedge
C\right) \quad \because \text{ド・モルガンの法則}
\end{eqnarray*}となるため証明が完了しました。
「両方とも〜である」の否定
以下の主張について考えます。\begin{equation}
\text{彼はコーヒーと紅茶の両方が好きである} \quad \cdots (1)
\end{equation}日常的な文脈では、この主張の否定を、\begin{equation*}
\text{彼はコーヒーと紅茶が両方とも好きではない}
\end{equation*}としてしまいそうですが、これは誤りです。
論理的には、「両方とも好きである」ことの否定は「両方とも好きではない」ではありません。実際、命題変数\(P,Q\)をそれぞれ、\begin{eqnarray*}P &:&\text{彼はコーヒーが好きである} \\
Q &:&\text{彼は紅茶が好きである}
\end{eqnarray*}とおくと、もとの主張\(\left( 1\right) \)を\(P\wedge Q\)と定式化できますが、ド・モルガンの法則より、その否定\(\lnot \left( P\wedge Q\right) \)は\(\lnot P\vee \lnot Q\)と必要十分です。つまり、もとの主張\(\left( 1\right) \)の否定は、\begin{equation}\text{彼はコーヒーが好きではない、もしくは紅茶が好きではない} \quad \cdots (2)
\end{equation}です。\(\left( 1\right) \)の否定である\(\left( 2\right) \)が成り立つ場合、可能性としては、(a) コーヒーは好きだが紅茶が好きではない、(b) コーヒーは好きではないが紅茶は好き、(c) コーヒーと紅茶の両方が好きではない、の3通りが起こり得ます。つまり、\(\left( 2\right) \)をより正確に表現すると、\begin{equation*}\text{彼はコーヒーと紅茶の少なくとも一方が好きではない}
\end{equation*}となります。
結論をまとめると、一般に、「両方とも〜である」の否定は「両方とも〜ではない」ではなく、「少なくとも一方は〜ではない」であるということです。
\\
Q &:&\text{今日は暑い}
\end{eqnarray*}とおくと、Aさんの発言は\(P\wedge Q\)と定式化されます。Bさんの主張はAさんの主張の否定に相当する\(\lnot \left( P\wedge Q\right) \)ですが、ド・モルガンの法則よりこれは\(\lnot P\vee\lnot Q\)と必要十分です。つまり、Bさんの真意は「今日は晴れていないか、暑くないかの少なくとも一方」ということになります。Bさんの考えとしては、「今日は晴れていない」「今日は暑くない」「今日は晴れてないし暑くもない」のいずれかであるということです（Bさんが論理的である場合には）。
ド・モルガンの法則の一般化
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{align*}
\lnot \left( A\vee B\vee C\right) & \Leftrightarrow \lnot \left( \left(
A\vee B\right) \vee C\right) \quad \because \text{結合律}
\\
& \Leftrightarrow \lnot \left( A\vee B\right) \wedge \lnot C\quad \because
\text{ド・モルガンの法則} \\
& \Leftrightarrow \left( \lnot A\wedge \lnot B\right) \wedge \lnot C\because
\text{ド・モルガンの法則} \\
& \Leftrightarrow \lnot A\wedge \lnot B\wedge \lnot C\quad \because \text{結合律}
\end{align*}すなわち、\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{eqnarray*}\left( a\right) \ \lnot \left( A_{1}\wedge \cdots \wedge A_{n}\right)
&\Leftrightarrow &\lnot A_{1}\vee \cdots \vee \lnot A_{n} \\
\left( b\right) \ \lnot \left( A_{1}\wedge \cdots \wedge A_{n}\right)
&\Leftrightarrow &\lnot A_{1}\vee \cdots \vee \lnot A_{n}
\end{eqnarray*}すなわち、\begin{eqnarray*}
\left( a\right) \ \lnot \left( \bigwedge_{i=1}^{n}A_{i}\right)
&\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*}がともに成り立つということです。これは論理式の個数\(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 &\bigvee_{i=1}^{n}\left( \lnot P_{i}\right) \\
\left( b\right) \ \lnot \left( \bigvee_{i=1}^{n}P_{i}\right)
&\Leftrightarrow &\bigwedge_{i=1}^{n}\left( \lnot P_{i}\right)
\end{eqnarray*}が成り立ちます。
1,3,5,7,9\text{はいずれも奇数である} \quad \cdots (1)
\end{equation}の否定について考えます。以下の命題変数\begin{equation*}
P_{i}:2i-1\text{は奇数である}
\end{equation*}を導入すると、\(\left( 1\right) \)を以下の論理式\begin{equation*}\bigwedge\limits_{i=1}^{5}P_{i}
\end{equation*}として定式化できます。したがって、その否定は、\begin{equation*}
\lnot \left( \bigwedge\limits_{i=1}^{5}P_{i}\right)
\end{equation*}ですが、ド・モルガンの法則より、これは、\begin{equation*}
\bigvee\limits_{i=1}^{5}\lnot P_{i}
\end{equation*}と必要十分です。以上より、もとの主張\(\left( 1\right) \)の否定は、\begin{equation*}1,3,5,7,9\text{の中の少なくとも1つが奇数ではない}
\end{equation*}であることが明らかになりました。
演習問題
B\wedge \lnot C
\end{equation*}が成り立つことを証明してください。
\left( A\vee C\right) \vee \lnot \left( B\vee C\right)
\end{equation*}が成り立つことを証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】