ド・モルガン則の一般形 | 集合と論理

1 三つの場面に同じ形で現れる

論理演算、集合演算、量化子について、否定を内側へ移す規則を並べます。

場面	否定・補集合を外へ出した形	内側へ移した形
論理演算	$\lnot(P \land Q)$	$\lnot P \lor \lnot Q$
論理演算	$\lnot(P \lor Q)$	$\lnot P \land \lnot Q$
集合演算	$\overline{A \cap B}$	$\overline{A} \cup \overline{B}$
集合演算	$\overline{A \cup B}$	$\overline{A} \cap \overline{B}$
量化子	$\lnot\,\forall x\, P(x)$	$\exists x\, \lnot P(x)$
量化子	$\lnot\,\exists x\, P(x)$	$\forall x\, \lnot P(x)$

どの行でも、否定を内側へ移すと、 $\land$ と $\lor$ 、 $\cap$ と $\cup$ 、 $\forall$ と $\exists$ がそれぞれ入れ替わります。論理演算の二つの行は§A3.2 定理 2.1、集合演算の二つの行は§A3.3 公式 5.1、量化子の二つの行は§A3.8 定理 2.1で示した規則です。

集合演算の行は、条件と真理集合の対応によって論理演算の行から得られます。範囲が $n\geq 1$ 個の要素からなる有限集合 $\{a_1,\dots,a_n\}$ である場合、 $\forall x\,P(x)$ は $P(a_1)\land\cdots\land P(a_n)$ であり、 $\exists x\,P(x)$ は $P(a_1)\lor\cdots\lor P(a_n)$ です。このため、量化子の規則も論理演算の規則と同じ形になります。範囲が無限集合である場合には、量化された命題を有限個の論理演算へ展開することはできません。その場合にも、次に示す意味によって量化子の規則が成り立ちます。

なお、添字の集合で表される一般の族に対する集合演算（ $\bigcap_{i \in I} A_i$ など）には、本記事では立ち入りません。§E1 数学の基礎が扱います。

2 量化子についての規則

定理 2.1 (量化子のド・モルガン則). $X$ を対象の範囲とし、 $P(x)$ を $X$ 上の述語とする。このとき

\lnot\,\forall x\in X\,P(x)\equiv\exists x\in X\,\lnot P(x),\qquad \lnot\,\exists x\in X\,P(x)\equiv\forall x\in X\,\lnot P(x)

が成り立つ。

証明.§A3.8 定理 2.1による。▨

3 入れ子になった量化子の否定

量化子が入れ子になった命題では、最も外側の量化子から順に定理 2.1を適用します。否定記号が一つの量化子を通るたびに量化子の種類が替わり、最後に内側の述語が否定されます。

\lnot\,\forall x\,\exists y\,P(x,y) \equiv\exists x\,\lnot\,\exists y\,P(x,y) \equiv\exists x\,\forall y\,\lnot P(x,y).

第1の同値変形では最も外側の $\forall x$ だけが $\exists x$ に替わり、否定記号が $\exists y$ の直前へ移ります。第2の同値変形では $\exists y$ が $\forall y$ に替わり、否定記号が $P(x,y)$ の直前へ移ります。量化子の位置は交換しないため、変数の順序は $x,y$ のままです。 $\exists x\,\forall y$ を $\forall y\,\exists x$ と書き換えると、元の命題の否定とは異なる主張になります。

4 連続であることの否定

量化子と条件文の否定を、連続性の条件に適用します。

例 4.1. $f\colon\mathbb R\to\mathbb R$ と $a\in\mathbb R$ を取る。 $f$ が点 $a$ で連続であることは

\forall\varepsilon>0\ \exists\delta>0\ \forall x\in\mathbb R \bigl(|x-a|<\delta\Rightarrow |f(x)-f(a)|<\varepsilon\bigr)

と書き表される。三つの量化子に定理 2.1を外側から順に適用すると、否定は

\exists\varepsilon>0\ \forall\delta>0\ \exists x\in\mathbb R \lnot\bigl(|x-a|<\delta\Rightarrow |f(x)-f(a)|<\varepsilon\bigr)

となる。条件文の否定 $\lnot(A\Rightarrow B)\equiv A\land\lnot B$ と、 $|f(x)-f(a)|<\varepsilon$ の否定を用いると、これは

\exists\varepsilon>0\ \forall\delta>0\ \exists x\in\mathbb R \bigl(|x-a|<\delta\land |f(x)-f(a)|\geq\varepsilon\bigr)

と同値である。

この例では、 $\forall\exists\forall$ が $\exists\forall\exists$ に替わり、量化子の順序は保たれています。量化子をすべて処理したあとに、条件文と不等号の否定を計算しています。

5 共通の反例と別々の反例

全称量化した論理和と、全称命題どうしの論理和では、否定が要求する要素の選び方が異なります。

例 5.1. 全体集合を $U=\{1,2,3,4\}$ とし、 $A=\{1,2\}$ 、 $B=\{3,4\}$ とする。 $A\cup B=U$ であるから、命題 $\forall x\in U\,(x\in A\lor x\in B)$ は真である。その否定は

\begin{aligned} \lnot\bigl[\forall x\in U\,(x\in A\lor x\in B)\bigr] &\equiv\exists x\in U\,\lnot(x\in A\lor x\in B)\\ &\equiv\exists x\in U\,(x\notin A\land x\notin B) \end{aligned}

となる。 $\overline A\cap\overline B=\{3,4\}\cap\{1,2\}=\varnothing$ であり、 $A$ にも $B$ にも属さない要素は存在しないので、この否定は偽である。

一方、命題 $\bigl(\forall x\in U\,x\in A\bigr)\lor\bigl(\forall y\in U\,y\in B\bigr)$ は、 $3\notin A$ 、 $1\notin B$ であるから偽である。その否定は

\begin{aligned} &\lnot\bigl[\bigl(\forall x\in U\,x\in A\bigr)\lor\bigl(\forall y\in U\,y\in B\bigr)\bigr]\\ &\qquad\equiv\bigl(\exists x\in U\,x\notin A\bigr)\land\bigl(\exists y\in U\,y\notin B\bigr) \end{aligned}

となる。 $x=3$ と $y=1$ を別々に取ることができるので、この否定は真である。

最初の否定は、二つの集合のどちらにも属さない同じ要素を要求する。後の否定は、一方の集合に属さない要素と他方の集合に属さない要素を別々に選ぶ。したがって、二つの元の命題は一般には同値でない。

§A3.13ド・モルガン則の一般形

1 三つの場面に同じ形で現れる

2 量化子についての規則

3 入れ子になった量化子の否定

4 連続であることの否定

5 共通の反例と別々の反例

例題

演習

前提記事