WIIS

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

述語論理におけるド・モルガンの法則

目次

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

ド・モルガンの法則

論理式\(A,B\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)でそれぞれ表記します。すると命題論理におけるド・モルガンの法則より、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \overline{A}\wedge \overline{B}\right)
\Leftrightarrow \lnot \overline{A}\vee \lnot \overline{B} \\
&&\left( b\right) \ \lnot \left( \overline{A}\vee \overline{B}\right)
\Leftrightarrow \lnot \overline{A}\wedge \lnot \overline{B}
\end{eqnarray*}がともに成り立ちます。任意の解釈において同様の議論が成立するため、\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*}がともに成り立つことが示されました。つまり、述語論理においてもド・モルガンの法則(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*}が成り立ちます。

例(ド・モルガンの法則)
「\(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\limits_{i=1}^{n}A_{i}\right) \Leftrightarrow
\bigvee\limits_{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\limits_{i=1}^{n}A_{i}\right) \Leftrightarrow
\bigwedge\limits_{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*}が成り立つ。

解答を見る

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

 

量化とド・モルガンの法則

ド・モルガンの法則を踏まえると、全称命題や存在命題に関して以下が成り立ちます。

命題(量化とド・モルガンの法則)
任意の論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\lnot \left( A\wedge B\right)
\Leftrightarrow \forall x\in X:\left( \lnot A\vee \lnot B\right) \\
&&\left( b\right) \ \forall x\in X:\lnot \left( A\vee B\right)
\Leftrightarrow \forall x\in X:\left( \lnot A\wedge \lnot B\right) \\
&&\left( c\right) \ \exists x\in X:\lnot \left( A\wedge B\right)
\Leftrightarrow \exists x\in X:\left( \lnot A\vee \lnot B\right) \\
&&\left( d\right) \ \exists x\in X:\lnot \left( A\vee B\right)
\Leftrightarrow \exists x\in X:\left( \lnot A\wedge \lnot B\right)
\end{eqnarray*}が成り立つ。

証明

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

例(量化とド・モルガンの法則)
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)について、上の命題より、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\lnot \left( P\left( x\right) \wedge
Q\left( x\right) \right) \Leftrightarrow \forall x\in X:\left( \lnot P\left(
x\right) \vee \lnot Q\left( x\right) \right) \\
&&\left( b\right) \ \forall x\in X:\lnot \left( P\left( x\right) \vee
Q\left( x\right) \right) \Leftrightarrow \forall x\in X:\left( \lnot P\left(
x\right) \wedge \lnot Q\left( x\right) \right) \\
&&\left( c\right) \ \exists x\in X:\lnot \left( P\left( x\right) \wedge
Q\left( x\right) \right) \Leftrightarrow \exists x\in X:\left( \lnot P\left(
x\right) \vee \lnot Q\left( x\right) \right) \\
&&\left( d\right) \ \exists x\in X:\lnot \left( P\left( x\right) \vee
Q\left( x\right) \right) \Leftrightarrow \exists x\in X:\left( \lnot P\left(
x\right) \wedge \lnot Q\left( x\right) \right)
\end{eqnarray*}などが成り立ちます。

全称命題は論理積を用いて、存在命題は論理和を用いてそれぞれ定義されますが、以上の事実とド・モルガンの法則を踏まえると、論理式\(A\)と変数\(x\in X\)がそれぞれ任意に与えられたとき、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \forall x\in X:A\right) \Leftrightarrow
\exists x\in X:\lnot A \\
&&\left( b\right) \ \lnot \left( \exists x\in X:A\right) \Leftrightarrow
\forall x\in X:\lnot A
\end{eqnarray*}が成り立つことが示されます。つまり、全称命題の否定は否定の存在命題と論理的に同値であり、存在命題の否定は否定の全称命題と論理的に同値です。

命題(量化とド・モルガンの法則)
任意の論理式\(A\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \forall x\in X:A\right) \Leftrightarrow
\exists x\in X:\lnot A \\
&&\left( b\right) \ \lnot \left( \exists x\in X:A\right) \Leftrightarrow
\forall x\in X:\lnot A
\end{eqnarray*}が成り立つ。

証明

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

例(量化とド・モルガンの法則)
命題関数\(P\left( x\right) \)は論理式であるため、先の命題より、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \forall x\in X:P\left( x\right) \right)
\Leftrightarrow \exists x\in X:\lnot P\left( x\right) \\
&&\left( b\right) \ \lnot \left( \exists x\in X:P\left( x\right) \right)
\Leftrightarrow \forall x\in X:\lnot P\left( x\right)
\end{eqnarray*}がともに成り立ちます。

例(量化とド・モルガンの法則)
命題関数\(P\left( x\right) \)は論理式であるため、先の命題より、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \forall y\in Y:P\left( x\right) \right)
\Leftrightarrow \exists y\in Y:\lnot P\left( x\right) \\
&&\left( b\right) \ \lnot \left( \exists y\in Y:P\left( x\right) \right)
\Leftrightarrow \forall y\in Y:\lnot P\left( x\right)
\end{eqnarray*}がともに成り立ちます。実際、\begin{eqnarray*}
\lnot \left( \forall y\in Y:P\left( x\right) \right) &\Leftrightarrow
&\lnot P\left( x\right) \quad \because \text{全称命題の定義} \\
&\Leftrightarrow &\exists y\in Y:\lnot P\left( x\right) \quad \because \text{存在命題の定義}
\end{eqnarray*}より\(\left( a\right) \)は成り立ちます。\(\left( b\right) \)についても同様です。
例(量化とド・モルガンの法則)
命題関数\(P\left( x,y\right) \)は論理式であるため、先の命題より、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \forall x\in X:P\left( x,y\right) \right)
\Leftrightarrow \exists x\in X:\lnot P\left( x,y\right) \\
&&\left( b\right) \ \lnot \left( \exists x\in X:P\left( x,y\right) \right)
\Leftrightarrow \forall x\in X:\lnot P\left( x,y\right)
\end{eqnarray*}がともに成り立ちます。

例(量化とド・モルガンの法則)
命題関数\(P\left( x,y\right) \)に関する以下の論理式\begin{equation*}\forall x\in X,\ \exists y\in Y:P\left( x,y\right)
\end{equation*}の否定をとると、先の命題より、\begin{eqnarray*}
\lnot \left( \forall x\in X,\ \exists y\in Y:P\left( x,y\right) \right)
&\Leftrightarrow &\exists x\in X:\lnot \left( \exists y\in Y:P\left(
x,y\right) \right) \\
&\Leftrightarrow &\exists x\in X,\ \forall y\in Y:\lnot P\left( x,y\right)
\end{eqnarray*}となります。また、以下の論理式\begin{equation*}
\exists x\in X,\ \forall y\in Y:P\left( x,y\right)
\end{equation*}の否定をとると、先の命題より、\begin{eqnarray*}
\lnot \left( \exists x\in X,\ \forall y\in Y:P\left( x,y\right) \right)
&\Leftrightarrow &\forall x\in X:\lnot \left( \forall y\in Y:P\left(
x,y\right) \right) \\
&\Leftrightarrow &\forall x\in X,\ \exists y\in Y:\lnot P\left( x,y\right)
\end{eqnarray*}となります。

例(量化とド・モルガンの法則)
「\(x^{2}=1\)を満たす実数\(x\)は存在しない」という主張について考えます。変数\(x\)の定義域はすべての実数からなる集合\(\mathbb{R} \)です。主張を定式化すると、\begin{equation*}\lnot \left( \exists x\in \mathbb{R} :x^{2}=1\right)
\end{equation*}となりますが、先の命題より、この論理式は、\begin{equation*}
\forall x\in \mathbb{R} :x^{2}\not=1
\end{equation*}と論理的に同値です。したがって、もとの主張は「任意の実数\(x\)について\(x^{2}\not=1\)が成り立つ」と言い換え可能です。
例(量化とド・モルガンの法則)
「任意の実数\(x\)について\(x^{2}\geq x\)が成り立つ」という主張の否定について考えます。変数\(x\)の定義域はすべての実数からなる集合\(\mathbb{R} \)です。主張を定式化すると、\begin{equation*}\forall x\in \mathbb{R} :x^{2}\geq x
\end{equation*}となります。先の命題より、この論理式の否定をとると、\begin{eqnarray*}
\lnot \left( \forall x\in \mathbb{R} :x^{2}\geq x\right) &\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \left( x^{2}\geq x\right) \\
&\Leftrightarrow &\exists x\in \mathbb{R} :x^{2}<x
\end{eqnarray*}となります。したがって、もとの主張の否定は「\(x^{2}<x\)を満たす実数\(x\)が存在する」です。
例(量化とド・モルガンの法則)
「実数\(x\)を任意に選んだとき、それに対して\(y^{3}=x\)を満たす実数\(y\)が存在する」という主張の否定について考えます。変数\(x,y\)の定義域はともにすべての実数からなる集合\(\mathbb{R} \)です。主張を定式化すると、\begin{equation*}\forall x\in \mathbb{R} ,\ \exists y\in \mathbb{R} :y^{3}=x
\end{equation*}となります。この論理式の否定をとると、先の命題より、\begin{eqnarray*}
\lnot \left( \forall x\in \mathbb{R} ,\ \exists y\in \mathbb{R} :y^{3}=x\right) &\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \left( \exists y\in \mathbb{R} :y^{3}=x\right) \\
&\Leftrightarrow &\exists x\in \mathbb{R} ,\ \forall y\in \mathbb{R} :\lnot \left( y^{3}=x\right) \\
&=&\exists x\in \mathbb{R} ,\ \forall y\in \mathbb{R} :y^{3}\not=x
\end{eqnarray*}となります。したがって、もとの主張の否定は「ある実数\(x\)が存在して、それと任意の実数\(y\)の間には\(y^{3}\not=x\)が成り立つ」となります。
例(量化とド・モルガンの法則)
「任意の実数に対して、それよりも大きい自然数が存在する」という主張の否定について考えます。変数\(x\)の定義域はすべての実数からなる集合\(\mathbb{R} \)であり、変数\(n\)の定義域はすべての自然数からなる集合\(\mathbb{N} \)であるものとします。主張を定式化すると、\begin{equation*}\forall x\in \mathbb{R} ,\ \exists n\in \mathbb{N} :x<n
\end{equation*}となります。ちなみにこれをアルキメデスの性質と呼びます。この論理式の否定をとると、先の命題より、\begin{eqnarray*}
\lnot \left( \forall x\in \mathbb{R} ,\ \exists n\in \mathbb{N} :x<n\right) &\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \left( \exists n\in \mathbb{N} :x<n\right) \\
&\Leftrightarrow &\exists x\in \mathbb{R} ,\ \forall n\in \mathbb{N} :\lnot \left( x<n\right) \\
&\Leftrightarrow &\exists x\in \mathbb{R} ,\ \forall n\in \mathbb{N} :x\geq n
\end{eqnarray*}となります。したがって、もとの主張の否定は「ある実数は任意の自然数以上である」もしくは「任意の自然数以上であるような実数が存在する」という主張に相当します。

 

含意の全称・存在の否定

論理式\(A,B\)と変数\(x\in X\)がそれぞれ任意に与えられたとき、先の命題と含意の定義を踏まえると、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \forall x\in X:\left( A\rightarrow B\right)
\right) \Leftrightarrow \exists x\in X:\left( A\wedge \lnot B\right) \\
&&\left( b\right) \ \lnot \left( \exists x\in X:\left( A\rightarrow B\right)
\right) \Leftrightarrow \forall x\in X:\left( A\wedge \lnot B\right)
\end{eqnarray*}を得ます。

命題(含意の全称・存在の否定)
任意の論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \lnot \left( \forall x\in X:\left( A\rightarrow B\right)
\right) \Leftrightarrow \exists x\in X:\left( A\wedge \lnot B\right) \\
&&\left( b\right) \ \lnot \left( \exists x\in X:\left( A\rightarrow B\right)
\right) \Leftrightarrow \forall x\in X:\left( A\wedge \lnot B\right)
\end{eqnarray*}が成り立つ。

証明

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

例(含意の全称・存在の否定)
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)に対して、先の命題より、\begin{equation*}\lnot \left( \forall x\in X:\left( P\left( x\right) \rightarrow Q\left(
x\right) \right) \right) \Leftrightarrow \exists x\in X:\left( P\left(
x\right) \wedge \lnot Q\left( x\right) \right)
\end{equation*}が成り立ちます。つまり、「任意の\(x\)について\(P\left( x\right) \)ならば\(Q\left( x\right) \)が成り立つ」という主張の否定は「\(P\left( x\right) \)が成り立つが\(Q\left( x\right) \)は成り立たないような\(x\)が存在する」です。同様に、\begin{equation*}\lnot \left( \exists x\in X:\left( P\left( x\right) \rightarrow Q\left(
x\right) \right) \right) \Leftrightarrow \forall x\in X:\left( P\left(
x\right) \wedge \lnot Q\left( x\right) \right)
\end{equation*}が成り立ちます。つまり、「\(P\left( x\right) \)ならば\(Q\left( x\right) \)が成り立つような\(x\)が存在する」という主張の否定は「任意の\(x\)について\(P\left( x\right) \)は成り立つが\(Q\left( x\right) \)は成り立たない」です。
例(含意の全称の否定)
「\(x>2\)を満たす任意の実数\(x\)は\(x^{2}\geq 4\)を満たす」という主張の否定を考えます。変数\(x\)の定義域はすべての実数からなる集合\(\mathbb{R} \)です。主張を定式化すると、\begin{equation*}\forall x\in \mathbb{R} :\left( x>2\rightarrow x^{2}\geq 4\right)
\end{equation*}として定式化されます。この論理式の否定は、\begin{eqnarray*}
\lnot \left( \forall x\in \mathbb{R} :\left( x>2\rightarrow x^{2}\geq 4\right) \right) &\Leftrightarrow &\exists
x\in \mathbb{R} :\lnot \left( x>2\rightarrow x^{2}\geq 4\right) \quad \because \text{量化記号と否定} \\
&\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \left( \lnot \left( x>2\right) \vee x^{2}\geq 4\right) \quad \because
\text{含意の言い換え} \\
&\Leftrightarrow &\exists x\in \mathbb{R} :\lnot \lnot \left( x>2\right) \wedge \lnot \left( x^{2}\geq 4\right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\exists x\in \mathbb{R} :\left( x>2\wedge x^{2}<4\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。したがって、もとの主張の否定は「\(x>2\)かつ\(x^{2}<4\)を満たす実数\(x\)が存在する」です。
例(含意の全称の否定)
「\(A\)さんは、\(B\)さんを好きではない人全員が好きだ」という主張の否定について考えます。変数\(x\)の定義域\(X\)と変数\(y\)の定義域\(Y\)はともにすべての人間からなる集合であるものとし、\(x,y\)を変数とする命題関数\begin{equation*}P\left( x,y\right) :x\text{は}y\text{を好きである}
\end{equation*}を導入すると、もとの主張は、\begin{equation*}
\forall x\in X:\left( \lnot P\left( x,B\right) \rightarrow P\left(
A,x\right) \right)
\end{equation*}という論理式として定式化されます。この論理式の否定は、\begin{eqnarray*}
\lnot \left( \forall x\in X:\left( \lnot P\left( x,B\right) \rightarrow
P\left( A,x\right) \right) \right) &\Leftrightarrow &\exists x\in X:\lnot
\left( \lnot P\left( x,B\right) \rightarrow P\left( A,x\right) \right) \quad
\because \text{量化記号と否定} \\
&\Leftrightarrow &\exists x\in X:\lnot \left( \lnot \lnot P\left( x,B\right)
\vee P\left( A,x\right) \right) \quad \because \text{含意の言い換え} \\
&\Leftrightarrow &\exists x\in X:\lnot \left( P\left( x,B\right) \vee
P\left( A,x\right) \right) \quad \because \text{二重否定} \\
&\Leftrightarrow &\exists x\in X:\left( \lnot P\left( x,B\right) \wedge
\lnot P\left( A,x\right) \right) \quad \because \text{ド・モルガンの法則}
\end{eqnarray*}となります。したがって、もとの主張の否定は、「\(A\)さんが好きではない人の中に\(B\)さんを好きではない人が存在する」となります。

 

演習問題

問題(量化記号と否定)
変数\(x,y\)の定義域\(X,Y\)はいずれもすべての整数からなる集合であるとともに、以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\not=0 \\
Q\left( x,y\right) &:&xy=1
\end{eqnarray*}を導入します。以下の問いに答えてください。

  1. 「\(x\not=0\)を満たす任意の整数\(x\)について、\(xy=1\)を満たす整数\(y\)が存在する」という主張を論理式として定式化してください。
  2. 問1で得た論理式の否定をとってください。
  3. 問2で得た論理式を日常言語で表現してください。
  4. 問1で得た論理式と問2で得た論理式、どちらが真であるか理由とともに答えてください。
解答を見る

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

問題(量化記号と否定)
変数\(x,y,z\)に関する以下の論理式\begin{equation}\forall x\in X,\ \forall y\in Y,\ \exists z\in Z:x+y=z \quad \cdots (1)
\end{equation}について考えます。以下の問いに答えてください。

  1. 論理式\(\left( 1\right) \)の否定をとってください。
  2. 変数\(x,y,z\)の定義域\(X,Y,Z\)がいずれもすべての整数からなる集合\(\left\{ \cdots,-2,-1,0,1,2,\cdots \right\} \)であるとき、論理式\(\left( 1\right) \)と問2で得た論理式、どちらが真であるか理由とともに答えてください。
  3. 変数\(x,y,z\)の定義域\(X,Y,Z\)がいずれも\(1\)以上\(100\)以下の整数からなる集合\(\left\{ 1,2,\cdots ,100\right\} \)であるとき、論理式\(\left( 1\right) \)と問2で得た論理式、どちらが真であるか理由とともに答えてください。
解答を見る

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

問題(量化記号と否定)
変数\(x,y\)の定義域\(X\)はすべての人からなる集合であるとともに、命題関数\(P\left( x,y\right) \)を、\begin{equation*}P\left( x,y\right) :x\text{は}y\text{の知り合いである}
\end{equation*}と定義します。以下の問いに答えてください。

  1. 「誰しも知り合いがいる」という言明を論理式として定式化してください。
  2. 問1で得た論理式の否定をとってください。
  3. 問2で得た論理式を日常言語で表現してください。
解答を見る

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

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

関連知識

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

論理積の否定は否定の論理和と論理的に同値であり、論理和の否定は否定の論理積と論理的に同値です。これをド・モルガンの法則と呼びます。ド・モルガンの法則は任意個の論理式の関係としても拡張可能です。

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

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

DISCUSSION

質問とコメント

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

述語論理