ド・モルガンの法則の確認

方針

解答

⓪ 発想 — どう考え始めるか。 ド・モルガンの法則 $\overline{A\cup B}=\overline{A}\cap \overline{B}$ を、両辺を実際に計算して確かめる問題だ。

左辺は「$A$ にも $B$ にも入らない」もの。右辺は「$A$ に入らず、かつ $B$ に入らない」もの。

日本語にすると同じことを言っている — その直感を、要素を書き出して数で確認する。法則を暗記するのではなく、成り立つ理由を目で見るのがこの問題の目的である。

$U$ は1〜12、$A$ は偶数 $\{2,4,6,8,10,12\}$、$B$ は3の倍数 $\{3,6,9,12\}$。

(1) まず $A\cup B$(どちらか一方でも)を求める。

$$A\cup B=\{2,3,4,6,8,9,10,12\}$$

その補集合(以外)は

$$\overline{A\cup B}=\{1,5,7,11\}$$

(2) 今度は $\overline{A}$ と $\overline{B}$ を別々に出す。

$$\overline{A}=\{1,3,5,7,9,11\},\overline{B}=\{1,2,4,5,7,8,10,11\}$$

その共通部分(両方に入る)は

$$\overline{A}\cap \overline{B}=\{1,5,7,11\}$$

(3) (1)と(2)を比べると、どちらも $\{1,5,7,11\}$。つまり

$$\overline{A\cup B}=\overline{A}\cap \overline{B}$$

まとめ:が確かに成り立つ。これがド・モルガンの法則だ。『どちらにも入らない = 一方にも入らず、もう一方にも入らない』と、言葉でも納得できる。

発展 — 一歩先へ。 この問題の $A$(偶数)と $B$($3$ の倍数)で $\overline{A\cup B}=\{1,5,7,11\}$ — 「$2$ でも $3$ でも割れない数」だ。$12$ 以下ならこれらは(1 を除いて)素数になる。「ふるいにかけて残った数」という発想は、素数を探すエラトステネスのふるい(数A)そのもの。集合の演算が、数論の道具として働いている。

ド・モルガンの法則は、命題の否定(「かつ」の否定は「または」)、条件の否定、そしてコンピュータの論理回路(NAND / NOR)まで、まったく同じ形で現れる。否定は $\cap$ と $\cup$ をひっくり返す — 論理の世界の基本法則である。

別解

この法則、日常の言葉に翻訳すると、当たり前すぎて笑ってしまう。

$A$ を「コーヒーが好きな人」、$B$ を「紅茶が好きな人」としよう。

$$\overline{A\cup B}\text{は「コーヒーか紅茶が好き、ではない人」}$$

これはどんな人か — コーヒーも好きじゃないし、紅茶も好きじゃない人だ。それがまさに $\overline{A}\cap \overline{B}$($A$ でなくかつ $B$ でない)。

$$\overline{A\cup B}=\overline{A}\cap \overline{B}$$

「または」を否定すると「かつ」になる — これがド・モルガンの本体だ。

もう $1$ つの法則も同じ調子で読める。

$$\overline{A\cap B}\text{は「コーヒーも紅茶も両方好き、ではない人」}$$

これは「コーヒーが嫌いまたは紅茶が嫌い」— どちらか一方でも嫌いなら「両方好き」ではない。$\overline{A\cap B}=\overline{A}\cup \overline{B}$ ✓。

記号を暗記すると $\cap$ と $\cup$ を取り違えるが、言葉に直せば間違えようがない。「否定すると、かつ ↔ または が入れ替わる」— この $1$ 行が、集合でも命題でも(次の単元でも)ずっと効く。