【SPONSORED LINK】

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

前の記事「論理と集合の基本1|集合の基礎知識」の続きです.

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

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

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

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

【SPONSORED LINK】

準備

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

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

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

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

ABを集合とする.このとき,

  1. ABの両方に含まれる要素全部の集合をABの共通部分」といい,A\cap Bで表す.
  2. ABの少なくとも一方に含まれる要素全部の集合をABの和集合」といい,A\cup Bで表す.

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

たとえば,集合AB

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

とすると,ABの共通部分,和集合は

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

である.さらに,全体集合Uを0以上5以下の整数からなる集合:

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

とすると,UにおけるABの補集合は

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

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

ベン図

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

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

論理と集合の基本pic1
たとえば,上のベン図は全体集合がUで,ABUの部分集合です.青丸の内部がAで,黒丸の内部がBとなっています.

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

論理と集合の基本pic2 論理と集合の基本pic3 論理と集合の基本pic4

  1. A\cap BAにもBにも属している要素なので,青丸と黒丸の両方の領域となっているところです.
  2. A\cup BABの少なくとも一方に属している要素なので,青丸と黒丸のどちらかの領域となっているところです.
  3. \overline{A}A以外の全部なので,青丸の外部です.

ド・モルガンの法則

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

[ド・モルガンの法則] 集合ABに対し,次の等式が成り立つ.

  1. \overline{A\cap B}=\overline{A}\cup\overline{B}
  2. \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以外の領域となります.

論理と集合の基本pic5

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

論理と集合の基本pic6

こうみると,\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は「ベン図」で集合ABを描いたときに分けられる4つの領域に対応していることを意識すると考えやすいと思います.

  1. Aには属するけど,Bには属さない要素
  2. Bには属するけど,Aには属さない要素
  3. AにもBにも属さない要素
  4. AにもBにも属する要素

A\cap Bは「ABに同時に属している要素の集合」ですから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|必要条件と十分条件」に続きます.

関連記事

以下,関連記事です.

【良いと思ったらシェアを!】

SNSでもご購読できます。