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

2018年12月2日:公開

ド・モルガンの法則

論理積の否定は否定の論理和と同値であり、論理和の否定は否定の論理積と同値です。これをド・モルガンの法則(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*}
証明を見る(プレミアム会員限定)
例(ド・モルガンの法則)
任意の論理式\(A,B,C\)について、\begin{equation*}
\lnot \left( A\wedge \left( B\vee C\right) \right) \Leftrightarrow \left( \lnot A\vee \lnot B\right) \wedge \left( \lnot A\vee \lnot 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{分配律}
\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\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\nolimits_{i=1}^{n}A_{i}\right) \Leftrightarrow \bigvee\nolimits_{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\nolimits_{i=1}^{n}A_{i}\right) \Leftrightarrow \bigwedge\nolimits_{i=1}^{n}\left( \lnot A_{i}\right)
\end{equation*}で表します。

次回は恒真式や恒偽式と関連のある同値変形法則について学びます。

次へ進む 演習問題(プレミアム会員限定)