ド・モルガンの法則

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

ド・モルガンの法則

論理式\(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 facebook
Share on twitter
Share on email
< 前のページ

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

有料のプレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

述語論理
アカウント
ログイン