De Morganの法則

同義語：ド・モルガンの法則de Morganの法則De Morgan's laws

概要

前提知識: 命題論理, 集合, 補集合, 全称記号

$1$ から $10$ までの整数を全体とし、偶数の集合を $A=\{2,4,6,8,10\}$、$3$ の倍数の集合を $B=\{3,6,9\}$ とする。「偶数または $3$ の倍数」である数は $A\cup B=\{2,3,4,6,8,9,10\}$ で、そうでない数は残りの $\{1,5,7\}$ である。一方、「偶数でない」数は $\{1,3,5,7,9\}$、「$3$ の倍数でない」数は $\{1,2,4,5,7,8,10\}$ で、この両方に入る数もやはり $\{1,5,7\}$ である。つまり「偶数または $3$ の倍数」を否定すると「偶数でなく、かつ $3$ の倍数でない」になる。同じように「偶数かつ $3$ の倍数」（$A\cap B=\{6\}$）を否定すると、$6$ 以外の $9$ 個の数、すなわち「偶数でない、または $3$ の倍数でない」数になる。否定をとると「または」と「かつ」が入れ替わる。これが De Morgan の法則 である。
De Morgan の法則は、命題（論理と命題）の否定、集合の補集合、「すべての」と「ある」という量化の否定の 3 つの場面に同じ形で現れる。証明の中で主張を否定するとき（背理法や対偶を使うとき）、閉集合の性質を開集合の性質から導くときなど、数学のいたるところで使われる。

定義

命題 $P,Q$ について、否定を $\lnot P$、論理積（「かつ」）を $P\land Q$、論理和（論理と命題。「または」）を $P\lor Q$ と書く。ここで $P\lor Q$ は「$P$ と $Q$ の少なくとも一方が真」の意味で、両方が真の場合を含む。2 つの論理式が、含まれる命題変数の真偽のどの組合せに対しても同じ真偽をとるとき、論理的に同値 であるといい、$\equiv$ で表す（Ham §2.6、p. 51）。

命題論理のDe Morganの法則

命題 $P,Q$ について、次の 2 つの論理的同値が成り立つ。
$$ \lnot(P\land Q)\equiv\lnot P\lor\lnot Q,\qquad \lnot(P\lor Q)\equiv\lnot P\land\lnot Q. $$

真理値表による

$P,Q$ の真偽の組合せは 4 通りである。T を真、F を偽として、両辺の値を真理値表（論理と命題）で比べる。
$$ \begin{array}{cc|cc|cc|cc} P & Q & \lnot P & \lnot Q & \lnot(P\land Q) & \lnot P\lor\lnot Q & \lnot(P\lor Q) & \lnot P\land\lnot Q\\ \hline \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{F} & \mathrm{F} & \mathrm{F} & \mathrm{F}\\ \mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{F}\\ \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{F}\\ \mathrm{F} & \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{T} \end{array} $$
第 5 列と第 6 列、第 7 列と第 8 列はそれぞれ 4 行すべてで一致する。よって 2 つの同値が成り立つ。$\square$

この 2 つの同値は Ham では Fact 2.1（§2.6、p. 51）、Lev では Theorem 1.3.7（§1.3、p. 49）として述べられている。論理と命題の記事の命題「基本的な恒真式」にも含まれる。
集合の場合は、全体集合 $X$ を 1 つ固定し、その部分集合 $A$ の補集合を $A^c:=X\setminus A$ と書く。

集合のDe Morganの法則

集合 $X$ の部分集合 $A,B$ について
$$ (A\cup B)^c=A^c\cap B^c,\qquad (A\cap B)^c=A^c\cup B^c $$
が成り立つ。

元の所属を命題に翻訳する

$x\in X$ を任意にとり、$P$ を「$x\in A$」、$Q$ を「$x\in B$」とする。和集合・共通部分・補集合の定義により、$x\in A\cup B$ は $P\lor Q$、$x\in A\cap B$ は $P\land Q$、$x\in A^c$ は $\lnot P$ と同じ意味である。したがって
$$ x\in(A\cup B)^c\iff\lnot(P\lor Q)\iff\lnot P\land\lnot Q\iff x\in A^c\cap B^c $$
であり、中央の同値は thm-de-morgan-propositional の 2 つ目である。$X$ のどの元についても両辺への所属が一致するので $(A\cup B)^c=A^c\cap B^c$ である。2 つ目の等式も、thm-de-morgan-propositional の 1 つ目を使って同じように示される。$\square$

補集合を $X$ に関してとる代わりに差をとった形 $C\setminus(A\cup B)=(C\setminus A)\cap(C\setminus B)$、$C\setminus(A\cap B)=(C\setminus A)\cup(C\setminus B)$ も、$C\cap(\cdot)$ を付けて同じ議論で成り立つ（差集合の記事を参照）。無限個の集合からなる族 $(A_i)_{i\in I}$ についても
$$ \Bigl(\bigcup_{i\in I}A_i\Bigr)^c=\bigcap_{i\in I}A_i^c,\qquad\Bigl(\bigcap_{i\in I}A_i\Bigr)^c=\bigcup_{i\in I}A_i^c $$
が成り立つ。証明は集合族の記事の命題「集合族に対する De Morgan の法則」と補集合の記事の命題「和集合と共通部分の補集合」にある。証明の要点は、「どの $i$ についても $x\in A_i$ でない」が「ある $i$ について $x\in A_i$」の否定であることで、これは次の量化子の形そのものである。
集合 $X$ の元 $x$ について真偽の定まる主張 $P(x)$ を考える。「すべての $x\in X$ について $P(x)$」を $\forall x\in X\ P(x)$、「ある $x\in X$ について $P(x)$」を $\exists x\in X\ P(x)$ と書く（全称記号・存在記号）。

量化子のDe Morganの法則

集合 $X$ と $X$ 上の主張 $P(x)$ について
$$ \lnot\bigl(\forall x\in X\ P(x)\bigr)\iff\exists x\in X\ \lnot P(x),\qquad \lnot\bigl(\exists x\in X\ P(x)\bigr)\iff\forall x\in X\ \lnot P(x) $$
が成り立つ。$X$ が空集合でもよい。

真理集合の補集合をとる

$T:=\{x\in X\mid P(x)\}$ とおく。$\forall x\in X\ P(x)$ は $T=X$、すなわち $T^c=\emptyset$ と同じ意味であり、$\exists x\in X\ \lnot P(x)$ は $T^c\ne\emptyset$ と同じ意味である。前者の否定は $T^c\ne\emptyset$ なので 1 つ目の同値が成り立つ。同様に $\exists x\in X\ P(x)$ は $T\ne\emptyset$、$\forall x\in X\ \lnot P(x)$ は $T=\emptyset$ と同じ意味なので、2 つ目の同値が成り立つ。$X=\emptyset$ のときは $T=T^c=\emptyset$ であり、$\forall$ の主張はともに真、$\exists$ の主張はともに偽なので、両辺の真偽は一致している。$\square$

この 2 つは Ham §2.10 の式 (2.8)・(2.9)（p. 60）、Lev §1.3.4 の "Quantifiers and Negation"（p. 52）である。$X=\{a,b\}$ の 2 元集合なら $\forall x\ P(x)$ は $P(a)\land P(b)$、$\exists x\ P(x)$ は $P(a)\lor P(b)$ であり、prop-de-morgan-quantifiers は thm-de-morgan-propositional そのものになる。全称は「すべての元についての論理積」、存在は「すべての元についての論理和」であり、量化子の De Morgan の法則はその無限版と見ることができる。

直感

「$P$ かつ $Q$」が成り立たないとは、「両方そろって成り立つ」ことが崩れていることであり、崩れ方は「$P$ が成り立たない」か「$Q$ が成り立たない」か（その両方）である。「$P$ または $Q$」が成り立たないとは、どちらの逃げ道もふさがれていることで、「$P$ も $Q$ も成り立たない」ことである。集合の図でいえば、2 つの円の和の外側は「$A$ の外」と「$B$ の外」の重なりであり、2 つの円の重なりの外側は「$A$ の外」と「$B$ の外」を合わせたものである。
De Morgan の法則を一言でいえば、「否定を内側に通すと、$\land$ と $\lor$、$\cap$ と $\cup$、$\forall$ と $\exists$ が入れ替わる」ということである。この入れ替えは prop-de-morgan-duality の双対性として整理される。

例と反例

収束しないことの言い換え

数列の極限の定義によれば、実数列 $(a_n)$ が実数 $a$ に収束するとは
$$ \forall\varepsilon>0\ \ \exists N\ \ \forall n\ge N\quad |a_n-a|<\varepsilon $$
が成り立つことである。この否定を、prop-de-morgan-quantifiers を外側から 1 つずつ使って書き直すと
$$ \exists\varepsilon>0\ \ \forall N\ \ \exists n\ge N\quad |a_n-a|\ge\varepsilon $$
となる。すなわち「$a$ に収束しない」とは、「ある正の数 $\varepsilon$ があって、どれほど先の番号 $N$ をとっても、それ以降に $a$ から $\varepsilon$ 以上離れた項がある」ことである。たとえば $a_n=(-1)^n$ と $a=1$ では、$\varepsilon=1$ とすれば、どの $N$ に対しても $N$ 以上の奇数 $n$ で $|a_n-1|=2\ge1$ となるので、$(a_n)$ は $1$ に収束しない。否定をとるたびに $\forall$ と $\exists$ が入れ替わり、最後の不等式 $<$ が $\ge$ に変わることに注意する。Ham §2.10 の Example 2.13（p. 61）も同じ手順で 2 重の量化の否定を作っている。

有限個の命題に対するDe Morganの法則

$n\ge1$ 個の命題 $P_1,\dots,P_n$ について
$$ \lnot(P_1\land\cdots\land P_n)\equiv\lnot P_1\lor\cdots\lor\lnot P_n,\qquad \lnot(P_1\lor\cdots\lor P_n)\equiv\lnot P_1\land\cdots\land\lnot P_n $$
が成り立つ。

個数についての帰納法

1 つ目を $n$ についての数学的帰納法で示す。$n=1$ では両辺とも $\lnot P_1$ である。$n$ で成り立つとすると、$R:=P_1\land\cdots\land P_n$ とおいて thm-de-morgan-propositional を $R$ と $P_{n+1}$ に使い、次に帰納法の仮定を使えば
$$ \lnot(R\land P_{n+1})\equiv\lnot R\lor\lnot P_{n+1}\equiv(\lnot P_1\lor\cdots\lor\lnot P_n)\lor\lnot P_{n+1} $$
となる。論理的に同値な式を式の一部に代入しても真偽は変わらないので、この変形は正当である。2 つ目も同様である。$\square$

集合についても同じ帰納法で $(A_1\cup\cdots\cup A_n)^c=A_1^c\cap\cdots\cap A_n^c$ などが得られる。これは集合族の記事の命題の $I=\{1,\dots,n\}$ の場合でもある。

反例：否定をそのまま配ってはいけない

「整数 $x$ と $y$ はともに奇数である」の否定を「$x$ と $y$ はともに偶数である」とするのは誤りである。$x=1$、$y=2$ は「ともに奇数」でも「ともに偶数」でもないので、元の主張とその「否定」が両方とも偽になってしまう。正しい否定は、thm-de-morgan-propositional の 1 つ目により「$x$ は偶数であるか、または $y$ は偶数である」、すなわち「$x,y$ の少なくとも一方は偶数」である（Ham §2.10 の Example 2.11、p. 60）。
論理式でいえば、$\lnot(P\land Q)$ と $\lnot P\land\lnot Q$ は論理的に同値ではない。$P$ が真で $Q$ が偽のとき、前者は真で後者は偽である。この例は「否定は $\land$ の各項にそのまま配ってよい」という含意を破っている。否定を内側に通すときは、$\land$ を $\lor$ に取り替えなければならない。

反例：直観主義論理では一方の向きが証明できない

thm-de-morgan-propositional の証明は真理値表、すなわち各命題が真か偽のどちらかに決まるという古典論理の前提に基づいている。この前提は、論理式としては排中律 $P\lor\lnot P$ と同じ働きをする。排中律を一般の原理として認めない直観主義論理では、4 つの含意
$$ \lnot(P\lor Q)\to\lnot P\land\lnot Q,\quad \lnot P\land\lnot Q\to\lnot(P\lor Q),\quad \lnot P\lor\lnot Q\to\lnot(P\land Q),\quad \lnot(P\land Q)\to\lnot P\lor\lnot Q $$
のうち最後の 1 つだけが一般には証明できない。
はじめの 3 つは排中律を使わずに示せる。$\lnot R$ を「$R$ を仮定すると矛盾が出る」と読む。1 つ目：$\lnot(P\lor Q)$ のもとで $P$ を仮定すると $P\lor Q$ が出て矛盾するので $\lnot P$、同様に $\lnot Q$ である。2 つ目：$\lnot P\land\lnot Q$ のもとで $P\lor Q$ を仮定すると、$P$ の場合も $Q$ の場合も矛盾が出る。3 つ目：$\lnot P$ の場合、$P\land Q$ を仮定すると $P$ が出て矛盾する。$\lnot Q$ の場合も同様である（この向きは直観主義論理の記事の命題「直観主義論理で証明できる式」の 5 である）。
最後の $\lnot(P\land Q)\to\lnot P\lor\lnot Q$ が直観主義論理で証明できないことは、直観主義論理の記事の例「反例：開集合と De Morgan の法則」で示されている。実数直線の開集合を真理値とみなし、$P$ に $(-\infty,0)$、$Q$ に $(0,\infty)$ を割り当てると、この含意の値が $\mathbb{R}\setminus\{0\}$ となって「真」（$\mathbb{R}$ 全体）にならない。この例は「De Morgan の法則の 4 つの向きは、排中律なしでもすべて導ける」という含意を破っている。否定を内側に通して $\lor$ を作る向きだけが、排中律に依存している。
量化子についても事情は似ている。prf-de-morgan-quantifiers は「$T^c=\emptyset$ でない」ことから「$T^c$ に元が存在する」ことを導いており、そこで排中律を使っている。$\exists x\ \lnot P(x)\to\lnot\forall x\ P(x)$ と、$\lnot\exists x\ P(x)$ と $\forall x\ \lnot P(x)$ の同値とは、上と同じ形の議論で排中律なしに示せるが、$\lnot\forall x\ P(x)\to\exists x\ \lnot P(x)$ を示す通常の証明は、「どの $x$ でも $\lnot P(x)$ でないなら $P(x)$」と背理法を使う。

性質

論理積と論理和の相互表現

否定を使った論理和と論理積の書き換え

命題 $P,Q$ について
$$ P\lor Q\equiv\lnot(\lnot P\land\lnot Q),\qquad P\land Q\equiv\lnot(\lnot P\lor\lnot Q) $$
が成り立つ。集合 $X$ の部分集合 $A,B$ については $A\cup B=(A^c\cap B^c)^c$、$A\cap B=(A^c\cup B^c)^c$ である。

二重否定と組み合わせる

thm-de-morgan-propositional の 2 つ目を $\lnot P,\lnot Q$ に使うと $\lnot(\lnot P\lor\lnot Q)\equiv\lnot\lnot P\land\lnot\lnot Q$ であり、$\lnot\lnot P\equiv P$（真理値表で明らか）なので右辺は $P\land Q$ である。1 つ目を $\lnot P,\lnot Q$ に使って両辺の否定をとると、同様に $P\lor Q\equiv\lnot(\lnot P\land\lnot Q)$ を得る。集合の等式は prop-de-morgan-sets を $A^c,B^c$ に使い、$(A^c)^c=A$ を用いれば同じように得られる。$\square$

したがって、$\lnot,\land,\lor$ で作られる論理式から、意味を変えずに $\lor$ を消去して $\lnot$ と $\land$ だけの式にすることができる（$\land$ を消去して $\lnot$ と $\lor$ だけにすることもできる）。集合の演算でいえば、補集合と共通部分があれば和集合はそれらで表せる。位相空間の閉集合の性質（任意個の共通部分と有限個の和で閉じること）が開集合の性質から従うのも、集合族に対する De Morgan の法則による（閉集合の記事の命題「共通部分と有限和」）。

双対性

$\lnot,\land,\lor$ と命題変数 $p_1,\dots,p_n$ から作られる論理式 $\varphi$ に対し、$\varphi$ の中の $\land$ と $\lor$ をすべて入れ替えた式を $\varphi$ の双対といい、$\varphi^{d}$ と書く。たとえば $\varphi=p_1\land(\lnot p_2\lor p_3)$ なら $\varphi^{d}=p_1\lor(\lnot p_2\land p_3)$ である。$\varphi$ の各 $p_i$ を $\lnot p_i$ に置き換えた式を $\varphi(\lnot p_1,\dots,\lnot p_n)$ と書く。

否定と双対

$\lnot,\land,\lor$ から作られる任意の論理式 $\varphi$ について
$$ \lnot\varphi\equiv\varphi^{d}(\lnot p_1,\dots,\lnot p_n) $$
が成り立つ。とくに、$\varphi\equiv\psi$ ならば $\varphi^{d}\equiv\psi^{d}$ である。

式の組み立てについての帰納法

論理式の組み立ての段数についての帰納法で示す。$\varphi=p_i$ なら $\varphi^{d}(\lnot p)=\lnot p_i=\lnot\varphi$ である。$\varphi=\lnot\alpha$ で $\alpha$ について成り立つとすると、$\varphi^{d}=\lnot\alpha^{d}$ なので $\varphi^{d}(\lnot p)=\lnot\alpha^{d}(\lnot p)\equiv\lnot\lnot\alpha=\lnot\varphi$ である。$\varphi=\alpha\land\beta$ で $\alpha,\beta$ について成り立つとすると、$\varphi^{d}=\alpha^{d}\lor\beta^{d}$ なので、thm-de-morgan-propositional により
$$ \varphi^{d}(\lnot p)=\alpha^{d}(\lnot p)\lor\beta^{d}(\lnot p)\equiv\lnot\alpha\lor\lnot\beta\equiv\lnot(\alpha\land\beta)=\lnot\varphi $$
である。$\varphi=\alpha\lor\beta$ の場合も、もう一方の De Morgan の法則で同様である。
後半を示す。$\varphi\equiv\psi$ なら $\lnot\varphi\equiv\lnot\psi$ なので、前半により $\varphi^{d}(\lnot p)$ と $\psi^{d}(\lnot p)$ は、真偽のどの割り当てでも同じ値をとる。真偽の割り当て $v$ に対し、各 $p_i$ の真偽を反転した割り当てを $\bar v$ とすると、$\varphi^{d}$ の $\bar v$ での値は $\varphi^{d}(\lnot p)$ の $v$ での値に等しい。$v\mapsto\bar v$ はすべての割り当ての上の全単射なので、$\varphi^{d}$ と $\psi^{d}$ もすべての割り当てで同じ値をとる。$\square$

たとえば分配法則 $P\land(Q\lor R)\equiv(P\land Q)\lor(P\land R)$ から、双対をとるだけで、もう一方の分配法則 $P\lor(Q\land R)\equiv(P\lor Q)\land(P\lor R)$ が得られる。このように、$\land$ と $\lor$ についての法則は必ず対になって現れる。prop-de-morgan-duality は De Morgan の法則を任意の式に広げたものである。

Boolean 代数での De Morgan の法則

束 $L$ が最小元 $0$ と最大元 $1$ をもち、2 つの分配法則 $x\land(y\lor z)=(x\land y)\lor(x\land z)$、$x\lor(y\land z)=(x\lor y)\land(x\lor z)$ を満たし、各元 $x$ に $x\lor x'=1$、$x\land x'=0$ となる元 $x'$（補元）があるとき、$L$ を Boolean代数という。$X$ の冪集合（$\lor=\cup$、$\land=\cap$、$x'=x^c$）と、命題を論理的同値で分類したもの（$\lor,\land,\lnot$）がその典型例である。

Boolean代数における補元の公式

Boolean 代数 $L$ で、各元の補元はただ 1 つに定まり、任意の $x,y\in L$ について
$$ (x\lor y)'=x'\land y',\qquad (x\land y)'=x'\lor y' $$
が成り立つ。

補元の条件を確かめて一意性を使う

一意性：$b,c$ がともに $a$ の補元なら、分配法則により
$$ b=b\land1=b\land(a\lor c)=(b\land a)\lor(b\land c)=0\lor(b\land c)=b\land c $$
であり、$b$ と $c$ を入れ替えて $c=c\land b$ も得られるので $b=c$ である。
公式：$x'\land y'$ が $x\lor y$ の補元の条件を満たすことを示せばよい。2 つの分配法則を使うと
$$ (x\lor y)\lor(x'\land y')=(x\lor y\lor x')\land(x\lor y\lor y')=1\land1=1, $$
$$ (x\lor y)\land(x'\land y')=(x\land x'\land y')\lor(y\land x'\land y')=0\lor0=0 $$
である。一意性により $(x\lor y)'=x'\land y'$ である。2 つ目の公式も、$\land$ と $\lor$、$0$ と $1$ を入れ替えた同じ計算で得られる。$\square$