教材一覧
教材検索
PROPOSITIONAL LOGIC

命題論理におけるド・モルガンの法則

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

ド・モルガンの法則

論理式\(A,B\)をそれぞれ任意に選んだとき、以下の真理値表が得られます。

$$\begin{array}{ccccccc}\hline
A & B & A\wedge B & \lnot \left( A\wedge B\right) & \lnot A & \lnot B & \lnot A\vee \lnot B \\ \hline
1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline
1 & 0 & 0 & 1 & 0 & 1 & 1 \\ \hline
0 & 1 & 0 & 1 & 1 & 0 & 1 \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline
\end{array}$$

表:ド・モルガンの法則

つまり、任意の解釈のもとで\(\lnot \left( A\wedge B\right) \)の値は\(\lnot A\vee \lnot B\)の値と一致するため、\begin{equation*}\left( a\right) \ \lnot \left( A\wedge B\right) \Leftrightarrow \lnot A\vee
\lnot B
\end{equation*}が成り立ちます。論理積の否定は否定の論理和と論理的に同値であるということです。上の命題において\(\wedge \)と\(\vee \)をお互いに入れ替えると、\begin{equation*}\left( b\right) \ \lnot \left( A\vee B\right) \Leftrightarrow \lnot A\wedge
\lnot B
\end{equation*}を得ますが、これもまた成り立ちます。つまり、論理和の否定は否定の論理積と一致します。以上をド・モルガンの法則(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\)に関する論理式\(\lnot \left( A\vee B\right) \)が真であるものとします。このとき、ド・モルガンの法則より\(\lnot A\wedge \lnot B\)は真であるため、さらに論理積\(\wedge \)の定義より\(\lnot A\)と\(\lnot B\)はともに真です。言い換えると、\(A\)と\(B\)はともに偽です。
例(ド・モルガンの法則)
任意の論理式\(A,B,C\)について、\begin{equation*}\lnot \left( A\wedge \left( B\vee C\right) \right) \Leftrightarrow \lnot
\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{彼はコーヒーと紅茶の両方が好きである}
\end{equation*}日常的な文脈では、この主張の否定を、\begin{equation*}
\text{彼はコーヒーと紅茶が両方とも好きではない}
\end{equation*}としてしまいそうですが、これは誤りです。論理的には、「両方とも好きである」ことの否定は「両方とも好きではない」ではありません。実際、命題変数\(P,Q\)をそれぞれ、\begin{eqnarray*}P &:&\text{彼はコーヒーが好きである} \\
Q &:&\text{彼は紅茶が好きである}
\end{eqnarray*}とおくと、もとの主張は\(P\wedge Q\)と定式化できますが、ド・モルガンの法則より、その否定は\(\lnot P\vee \lnot Q\)、すなわち、\begin{equation*}\text{彼はコーヒーが好きではない、もしくは紅茶が好きではない}
\end{equation*}となります。このとき、可能性としては、(1) コーヒーは好きだが紅茶が好きではない、(2) コーヒーは好きではないが紅茶は好き、(3) コーヒーと紅茶の両方が好きではない、の3通りが起こり得ます。言い換えると、コーヒーと紅茶の少なくとも一方が好きではないということです。一般に、「両方とも〜である」の否定は「両方とも〜ではない」ではなく、「少なくとも一方は〜ではない」であるということです。

例(ド・モルガンの法則)
Aさんによる「今日は晴れていて暑いですね」という発言に対し、Bさんが「いや、そうでもないですよ」と返したとき、Bさんの真意を考えてみましょう。命題変数\(P,Q\)をそれぞれ、\begin{eqnarray*}P &:&\text{今日は晴れている}
\\
Q &:&\text{今日は暑い}
\end{eqnarray*}とおくと、Aさんの発言は\(P\wedge Q\)と定式化されます。Bさんの主張はAさんの主張の否定に相当する\(\lnot \left( P\wedge Q\right) \)ですが、ド・モルガンの法則よりこれは\(\lnot P\vee\lnot Q\)と言い換え可能です。つまり、Bさんの真意は「今日は晴れていないか、暑くないかの少なくとも一方」ということになります。Bさんの考えとしては、「今日は晴れていない」「今日は暑くない」「今日は晴れてないし暑くもない」のいずれかであるということです(Bさんが論理的である場合には)。

 

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

論理式\(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_{i=1}^{n}A_{i}\right) \Leftrightarrow
\bigvee_{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_{i=1}^{n}A_{i}\right) \Leftrightarrow
\bigwedge_{i=1}^{n}\left( \lnot A_{i}\right)
\end{equation*}で表します。これは論理式の個数\(n\)に関する数学的帰納法により証明できます(演習問題にします)。

命題(ド・モルガンの法則)
任意の論理式\(A_{1},\cdots ,A_{n}\)について以下が成り立つ。\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*}
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(ド・モルガンの法則)
以下の主張\begin{equation}
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*}となります。

 

演習問題

問題(ド・モルガンの法則)
任意の論理式\(A,B,C\)について、\begin{equation*}\lnot \left( A\vee B\vee C\right) \Leftrightarrow \lnot A\wedge \lnot
B\wedge \lnot C
\end{equation*}が成り立つことを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(ド・モルガンの法則)
任意の論理式\(A,B,C\)について、\begin{equation*}\lnot \left( \left( A\wedge B\right) \vee C\right) \Leftrightarrow \lnot
\left( A\vee C\right) \vee \lnot \left( B\vee C\right)
\end{equation*}が成り立つことを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(ド・モルガンの法則)
「今日は買い物に行かないし、ジムにも行かない」の否定を明らかにしてください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次回は矛盾律について学びます。

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE
ド・モルガンの法則

集合演算におけるド・モルガンの法則

和集合の補集合は補集合の共通部分に等しく、共通部分の補集合は補集合の和集合に等しくなります。これをド・モルガンの法則と呼びます。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

命題論理