教材一覧
教材一覧
教材検索
PREDICATE LOGIC

ド・モルガンの法則

目次

次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

ド・モルガンの法則

論理式\(A,B\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)でそれぞれ表記します。すると\(\wedge \)と\(\vee \)に関するド・モルガンの法則より、\begin{equation*}
\lnot \left( \overline{A}\wedge \overline{B}\right) \Leftrightarrow \lnot
\overline{A}\vee \lnot \overline{B}
\end{equation*}が成り立ちます。任意の解釈において同様の議論が成立するため、\begin{equation*}
\left( a\right) \ \lnot \left( A\wedge B\right) \Leftrightarrow \lnot A\vee
\lnot B
\end{equation*}であることが示されました。\(\left( a\right) \)において\(\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*}
証明を見る(プレミアム会員限定)
例(ド・モルガンの法則)
命題関数\(P\left( x\right) \)と\(Q\left( x,y\right) \)と\(R\left( y\right) \)について、\begin{eqnarray*}
\lnot \left( P\left( x\right) \wedge \left( Q\left( x,y\right) \vee R\left(
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*}が成り立ちます。
例(ド・モルガンの法則)
命題関数\(P\left( x\right) \)と\(Q\left( x\right)\)について、\begin{eqnarray*}
\exists x\ \lnot \left( \lnot P\left( x\right) \wedge Q\left( x\right)
\right) &\Leftrightarrow &\exists x\ \left( \lnot \lnot P\left( x\right)
\vee \lnot Q\left( x\right) \right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\exists x\ \left( P\left( x\right) \vee \lnot Q\left(
x\right) \right)
\end{eqnarray*}が成り立ちます。
例(ド・モルガンの法則)
「\(x\)は\(2\)または\(3\)の少なくとも一方で割り切れる」という主張の否定を定式化します。以下の命題関数\begin{eqnarray*}
P\left( x\right) &:&x\text{は}2\text{で割り切れる} \\
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\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*}で表します。これは\(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*}
証明を見る(プレミアム会員限定)

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

次へ進む 質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定)
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

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

RELATED KNOWLEDGE

関連知識

述語論理