論理と集合の基本２｜ド・モルガンの法則

【論理と集合の基本1|集合の基礎知識】の続きです．

この記事では，前回の記事で説明した集合の共通部分，和集合，補集合などが合わさったときに，集合がどうなるかということを説明します．

そのなかでポイントとなるのが「ド・モルガンの法則(de Morgan’s law)」です．

「ド・モルガンの法則」は「共通部分の補集合や，和集合の補集合をとったときにどうなるのか」ということを述べた定理で，基本中の基本です．

「ド・モルガンの法則」空気を吸うように当たり前に使えるようになっておいてほしいところです．

【SPONSORED LINK】

1 準備
- 1.1 共通部分，和集合，補集合の復習
- 1.2 ベン図
2 ド・モルガンの法則
- 2.1 ベン図を使った説明
- 2.2 要素の分類による説明

準備

「ド・モルガンの法則」について書く前に，共通部分，和集合，補集合の復習をします．

そのあと，集合を視覚的に表すのに便利な「ベン図」を説明します．

共通部分，和集合，補集合の復習

前回の記事でも書きましたが，共通部分，和集合，補集合の定義を復習しておきます．

$A$ ， $B$ を集合とする．このとき，

$A$ と $B$ の両方に含まれる要素全部の集合を「 $A$ と $B$ の共通部分」といい， $A\cap B$ で表す．

$A$ と $B$ の少なくとも一方に含まれる要素全部の集合を「 $A$ と $B$ の和集合」といい， $A\cup B$ で表す．

また，集合 $C$ を集合 $U$ の部分集合とする( $U\subset C$ )．このとき， $C$ に属さない $U$ の要素全部の集合を「 $U$ における $C$ の補集合」といい， $\overline{C}$ と書く．ただし，補集合は全体集合を明示しないこともある．

たとえば，集合 $A$ ， $B$ を

$A=\{1,3,4\}$ ， $B=\{0,1,2,3\}$

とすると， $A$ ， $B$ の共通部分，和集合は

$A\cap B=\{1,3\}$ ， $A\cup B=\{0,1,2,3,4\}$

である．さらに，全体集合 $U$ を0以上5以下の整数からなる集合：

$U=\{1,2,3,4,5\}$

とすると， $U$ における $A$ ， $B$ の補集合は

$\overline{A}=\{0,2,5\}$ ， $\overline{B}=\{4,5\}$

となります．記号の上では全体集合 $U$ を明示しませんが，全体集合が何かは常に意識しておくことが必要です．

ベン図

集合を表すときは，集合を円で表す方法が視覚的に処理できて便利です．この集合を円で表した図のことを「ベン図」といいます．

「ベン図」は視覚的に理解できて非常に有用なので，必要なときには「ベン図」をぱっと描けるようにして下さい．

たとえば，上のベン図は全体集合が $U$ で， $A$ ， $B$ は $U$ の部分集合です．青丸の内部が $A$ で，黒丸の内部が $B$ となっています．

このベン図を用いると， $A$ ， $B$ の共通部分 $A\cap B$ ，和集合 $A\cup B$ ， $U$ における $A$ の補集合 $\overline{A}$ は以下のようになります．

$A\cap B$ ： $A$ にも $B$ にも属している要素なので，青丸と黒丸の両方の領域となっているところです．
$A\cup B$ ： $A$ と $B$ の少なくとも一方に属している要素なので，青丸と黒丸のどちらかの領域となっているところです．
$\overline{A}$ ： $A$ 以外の全部なので，青丸の外部です．

ド・モルガンの法則

さて，「ド．モルガンの法則」を紹介します．

[ド・モルガンの法則]　集合 $A$ ， $B$ に対し，次の等式が成り立つ．

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

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

文字面をみると， $\cap$ の”補集合”が $\cup$ となり， $\cup$ の”補集合”が $\cap$ となることが分かります．( $\cap$ は集合ではないので”補集合”を考えることはできないのですが，イメージのために敢えてそう書きました．)

ド・モルガンの法則は一度分かれば当たり前のことを言っているのですが，最初はよく分からないものです．以下の説明を読んだ後，一度自分の中で考えてみてください．

ベン図を使った説明

さて，これがどういう意味なのかということを説明します．全体集合は $U$ とします．

まず，1の左辺の $\overline{A\cap B}$ ですが，これは $A\cap B$ の補集合です．つまり， $\overline{A\cap B}$ をベン図で表すと， $A\cap B$ 以外の領域となります．

また， $\overline{A}\cup\overline{B}$ は $\overline{A}$ と $\overline{B}$ の和集合です．なので， $\overline{A}\cup\overline{B}$ は下図の緑線 $\overline{A}$ と赤線 $\overline{B}$ を併せた領域です．

こうみると， $\overline{A\cap B}$ と $\overline{A}\cup\overline{B}$ が同じ集合であることが分かります．すなわち，

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

と分かります．同様に，2の左辺と右辺をベン図にすることで，

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

が分かります．

要素の分類による説明

上では「ド・モルガンの法則」を図で直感的に説明しましたが，ここでは文章を使って少し論理的に説明します．

1つ目の等式

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

について説明します．

まず，全体集合 $U$ の要素には次の4種類があります．この1～4は「ベン図」で集合 $A$ ， $B$ を描いたときに分けられる4つの領域に対応していることを意識すると考えやすいと思います．

$A$ には属するけど， $B$ には属さない要素
$B$ には属するけど， $A$ には属さない要素
$A$ にも $B$ にも属さない要素
$A$ にも $B$ にも属する要素

$A\cap B$ は「 $A$ と $B$ に同時に属している要素の集合」ですから4そのものです．左辺の補集合 $\overline{A\cap B}$ は $A\cap B$ に属さない要素全部の集合でしたから，結局 $\overline{A\cap B}$ は1，2，3の和集合です．

一方， $\overline{A}$ は「 $A$ に属さない要素の集合」ですから2，3の和集合です．また， $\overline{B}$ は「 $B$ に属さない要素の集合」ですから1，3の和集合です．

結局，「 $\overline{A}$ と $\overline{B}$ の少なくとも一方に属する要素の集合」 $\overline{A}\cup\overline{B}$ は1，2，3の和集合です．

したがって， $\overline{A\cap B}$ も $\overline{A}\cup\overline{B}$ もどちらも1，2，3の和集合で一致しますから，同じ集合であることが分かります．

同様に，2の左辺と右辺が1～4のどれであるのかを考えることで，

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

が分かります．

【論理と集合の基本3|必要条件と十分条件】に続きます．