論理積の否定は否定の論理和と同値であり、論理和の否定は否定の論理積と同値です。これをド・モルガンの法則と呼びます。

2018年11月17日:公開

ド・モルガンの法則

論理積の否定は否定の論理和と同値であり、論理和の否定は否定の論理積と同値です。これをド・モルガンの法則(De Morgan’s law)と呼びます。

命題(ド・モルガンの法則)
任意の論理式\(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*}
証明を見る(プレミアム会員限定)

以下の主張について考えます。\begin{equation}
\text{彼はコーヒーと紅茶が両方とも好きだ。} \tag{1}
\end{equation}日常的な文脈では、この主張の否定を、\begin{equation}
\text{彼はコーヒーと紅茶が両方とも好きではない。} \tag{2}
\end{equation}としてしまいそうですが、これは誤りです。論理的には、「両方とも好き」であることの否定は「両方とも好きではない」ではありません。実際、命題変数\(P,Q\)をそれぞれ、\begin{eqnarray*}
P &:&\text{彼はコーヒーが好きだ} \\
Q &:&\text{彼は紅茶が好きだ}
\end{eqnarray*}とおくと、もとの主張\(\left( 1\right) \)は\(P\wedge Q\)と定式化できますが、ド・モルガンの法則より、\(\left( 1\right) \)の否定は\(\lnot P\vee \lnot Q\)、すなわち、\begin{equation}
\text{彼はコーヒーが好きではない、または紅茶が好きではない} \tag{2}
\end{equation}となります。論理的には、「両方とも好き」であることの否定は「少なくとも一方が好きではない」です。したがって、例えば、彼はコーヒーが好きで紅茶が好きではない場合などには、もとの主張\(\left( 1\right) \)は偽になります。

例(ド・モルガンの法則)
任意の命題変数\(P,Q,R\)について、\begin{equation*}
\lnot \left( P\wedge \left( Q\vee R\right) \right) \Leftrightarrow \left( \lnot P\vee \lnot Q\right) \wedge \left( \lnot P\vee \lnot R\right)
\end{equation*}が成り立つことを証明します。実際、\begin{eqnarray*}
\lnot \left( P\wedge \left( Q\vee R\right) \right) &\Leftrightarrow &\lnot P\vee \lnot \left( Q\vee R\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot P\vee \left( \lnot Q\wedge \lnot R\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \lnot P\vee \lnot Q\right) \wedge \left( \lnot P\vee \lnot R\right) \quad \because \text{分配律}
\end{eqnarray*}が成り立つため証明できました。

 

ド・モルガンの法則の一般化

論理式\(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\quad \because \text{ド・モルガンの法則} \\
& \Leftrightarrow \lnot A\vee \lnot B\vee \lnot C\quad \because \text{結合律}
\end{align*}すなわち、$$
\lnot \left( A\wedge B\wedge C\right) \Leftrightarrow \lnot A\vee \lnot B\vee \lnot C
$$が得られます。論理和についても同様に考えると、$$
\lnot \left( A\vee B\vee C\right) \Leftrightarrow \lnot A\wedge \lnot B\wedge \lnot C
$$が得られます。

任意の有限個の論理式についても同様に議論が成り立ちます。すなわち、有限\(n\)個の論理式\(A_{1},\cdots ,A_{n}\)について、$$
\lnot \left( A_{1}\wedge \cdots \wedge A_{n}\right) \Leftrightarrow \lnot A_{1}\vee \cdots \vee \lnot A_{n}
$$という関係が成立するため、これを、$$
\lnot \left( \bigwedge\nolimits_{i=1}^{n}A_{i}\right) \Leftrightarrow \bigvee\nolimits_{i=1}^{n}\left( \lnot A_{i}\right)
$$で表します。論理和についても同様に考えると、$$
\lnot \left( A_{1}\vee \cdots \vee A_{n}\right) \Leftrightarrow \lnot A_{1}\wedge \cdots \wedge \lnot A_{n}
$$という関係が成立するため、これを、$$
\lnot \left( \bigvee\nolimits_{i=1}^{n}A_{i}\right) \Leftrightarrow \bigwedge\nolimits_{i=1}^{n}\left( \lnot A_{i}\right)
$$で表します。

次回は命題定数に関係のある恒真式について学びます。
次へ進む 演習問題(プレミアム会員限定)