MENU
カテゴリー
おすすめプログラミングスクール紹介中! 一覧はこちらから

ド・モルガンの法則とは?ベン図・真理値表(論理式)による証明をわかりやすく解説!【練習問題アリ】

こんにちは、ウチダです。

今日は、数学Ⅰ「集合と命題」で習う

「ド・モルガンの法則」

について、まずは前提知識から解説し、次にド・モルガンの法則を $3$ つの方法で証明し、最後にド・モルガンの法則を用いた練習問題にチャレンジしていきたいと思います。

スポンサーリンク
目次

ド・モルガンの法則の前に

まずは「集合とは何か」について理解しなければなりません。

集合の元である”要素”を理解し、いろいろな集合(共通部分・和集合・補集合)を考え、部分集合と「集合が等しいとはどういうことか」見ていきます。

これらの前提知識を理解している方は、この章は飛ばして目次2から読み進めていただいても構いません。

集合と要素

ここでは自然数を例に考えていきましょう。

↓↓↓

あまり多すぎても大変なので、今回は「 $1$ から $10$ までの自然数」の範囲で考えます。

このように、集合を考えるときは、まず全体のくくりを決めることが多いです。

その集合を“全体集合”と呼び、英語で「Universal set」と表すため、$U$ と表すことが多いです。

次に、集合 $A$ について考えましょう。(とりあえず集合 $B$ は無視。)

集合 $A$ の中には、自然数が $5$ つあります。

その一つ一つを、集合 $A$ の“元”もしくは”要素”と呼び、また集合 $A$ は$$A=\{1,2,4,5,9\}$$と表記します。
※集合には中括弧を用いて、多項式など一般的な式と区別します。

また、$$A=\{n|n=1,2,4,5,9\}$$のように、右側に条件式を書くことで集合を表すこともあります。

条件式を書く前には「|」を付けましょう。

この方法は、例えば全体集合が自然数で、偶数の集合などを表す際に$$\{2n|n=1,2,3,…\}$$のように表せて便利です。

(補足)
ちなみに、今回自然数が宙を舞っているように配置されていますが、ベン図を用いるときは大小関係などは気にせずに記します。ベン図というのはそもそも、視覚的にわかりやすいように図示化したものですので、あくまで一種のイメージだ
と捉えてください。

共通部分・和集合・補集合

さっきのベン図を用いて説明していきます。

集合 $A$ と集合 $B$ が重なっている部分があります。

このように、集合 $A$ と集合 $B$ のどちらにも属している要素全体の集合“共通部分”といい、$$A∩B=\{2,4\}$$と表します。

また、集合 $A$ と集合 $B$ の少なくとも一方に属している要素全体の集合“和集合”といい、$$A∪B=\{1,2,4,5,6,7,9\}$$と表します。

ここで用いた「∩」と「∪」はそれぞれ英語で”cap”と”cup”と呼びます。

ややこしいですが、帽子とマグカップの形とリンクさせましょう。

もう一つ。全体集合 $U$ から集合 $A$ の要素を除いた要素全体の集合“補集合”といい、$$\overline{A}=\{3,6,7,8,10\}$$と表します。

集合は、大体この $3$ つで表されることがほとんどです。この $3$ つを駆使して、いろいろな集合を表していきます。

また、補集合の性質として、以下も重要です。

【補集合の性質】
1. $A∩\overline{A}=φ$
2. $A∪\overline{A}=U$
3. $\overline{\overline{A}}=A$
4. $A⊂B$ ならば $\overline{A}⊃\overline{B}$

1~3 については、ベン図を見ていただければわかるかと思います。

ちなみに「$φ$(ファイ)」は“空集合”といい、要素が一つもない集合のことを指します。
※「要素が一つもないんだから集合じゃないじゃん」と感じますが、定義していた方が後々楽というか、これ以上小さい集合が存在しないという意味で基準にもなるので、まあそういうもんなのかと押さえておきましょう。僕的には $0^0=1$ と定義するのと同じ感覚です。

4の「⊂」や「⊃」について、次の章で解説していきます。

スポンサーリンク

部分集合

先ほどから用いている例に、少しだけ付け加えて説明していきます。

集合 $A$ の中にスッポリと収まるように、集合 $C$ を定義してみました。

たとえばこのように、「集合 $C$ が集合 $A$ にスッポリと収まっているとき、集合 $C$ は集合 $A$ の部分集合である」と言います。

スッポリという表現が数学的ではないので、しっかりと定義していきます。

今、集合 $C$ のすべての要素が集合 $A$ の要素でもあります。

つまり、$$x∈C ならば x∈A$$が成り立つとき、$C$ を $A$ の部分集合であると言い、$$C⊂A$$と表します。

ここでまたまた色々な記号が出てきましたね。

「∈」や「∋」というのは、集合の要素であることを示し、「⊂」や「⊃」というのは、集合の部分集合であることを示しています。

このあたりがややこしいので、しっかりと区別しましょう。

また、それを否定したいときは、たとえば「∉」のように、斜線を引くことで示します。

これは「≠」と同じ感覚ですね。

さて、補集合の性質4.について確認していきます。

今、$C⊂A$ が成り立っているので、$\overline{C}⊃\overline{A}$ が成り立てばOKです。

$$\overline{C}=\{2,3,4,6,7,8,10\}$$$$\overline{A}=\{3,6,7,8,10\}$$なので、しっかり性質を満たしていますね!

集合の等号

前提知識の最後として「集合が等しいとは何か」説明していきます。

この例で等しい集合の例を探してみると、$A$ と $C∪(A∩B)$ が等しいです。

つまり$$A=C∪(A∩B)$$が成り立つのですが、これを示すにはどうすればよいでしょうか。

ここで、先ほどの部分集合の知識が活きてきます。

「集合が等しい」ということは「どちらともスッポリ収まっている」と捉えることができるので、$$A⊂C∪(A∩B) かつ A⊃C∪(A∩B)$$

と考えることができます。

よって、部分集合であることを双方向から示せれば、集合として等しいことが証明できるわけです。

この方法は、ド・モルガンの法則の証明 $3$ つ目にて使いますので、ぜひ楽しみにしていてください♪

また、一般の「=」でも$$A≦B かつ A≧B ⇔ A=B$$が成り立つので、この事実と結び付けるといいかもしれませんね。

ド・モルガンの法則とは

ここまでで前提知識はすべて押さえることができました。

いよいよド・モルガンの法則について解説していきます。

【ド・モルガンの法則】
$$\overline{A∪B}=\overline{A}∩\overline{B} ……①$$$$\overline{A∩B}=\overline{A}∪\overline{B} ……②$$

この $2$ つを合わせて「ド・モルガンの法則」と呼びます。

イギリスの数学者「オーガスタス・ド・モルガン」さんにちなんで名づけられました。

さて、この法則の覚え方ですが、「補集合をとる」というものを一つの演算としてみると、$$\overline{∪} → ∩$$また$$\overline{∩} → ∪$$となってますよね。

つまり、この記号「ー(バー)」には、分配法則みたいなものが成り立って、

\begin{align}\overline{A∪B}&→\overline{A}\overline{∪}\overline{B}\\&→\overline{A}∩\overline{B}\end{align}

みたいな式変形が成り立つ、と覚えましょう。
※この式変形は実際やってはいけないので、矢印で表しました。あくまで一つの覚え方として参考程度に留めておいてください。(大学で論理演算を習うとこんな式変形が出てきますが、またそれは別の話。)

スポンサーリンク

集合が3つ以上の場合

大体、$2$ つで成り立つものは $3$ つ以上でも成り立ちます。

よって、ド・モルガンの法則も例にもれず、$$\overline{A\cup B\cup C}=\overline{A}\cap\overline{B}\cap\overline{C}$$また$$\overline{A\cap B\cap C}=\overline{A}\cup\overline{B}\cup\overline{C}$$が成り立ちます。

ド・モルガンの法則を一般化したものがこちらです。

【ド・モルガンの法則の一般化】
\begin{align}\overline{A_1\cup A_2\cup …\cup A_n}=\overline{A_1}\cap\overline{A_2}\cap…\cap\overline{A_n}\end{align}

※この数式は横にスクロールできます。(スマホでご覧の方対象。)

\begin{align}\overline{A_1\cap A_2\cap …\cap A_n}=\overline{A_1}\cup\overline{A_2}\cup…\cup\overline{A_n}\end{align}

※この数式は横にスクロールできます。(スマホでご覧の方対象。)

では次の章から、ド・モルガンの法則の証明を一緒に考えていきましょう。

ド・モルガンの法則の証明3つ

まず、今までも用いてきた「ベン図」による証明があります。

しかし、冒頭でもお伝えした通り、ベン図というのはあくまで視覚的にわかりやすいように図示化したイメージですので、証明というよりかは確認に近い作業です。

よって、最初にベン図で確認したのち、厳密な証明について考えていきましょう。

ベン図による証明(確認)

まず①の式$$\overline{A\cup B}=\overline{A}\cap\overline{B}$$から証明していきます。

最初に、「左辺の集合がどういう集合であるか」考えましょう。

黄色の部分が左辺の表す集合です。

こちらはわかりやすいですね。

この集合と右辺の集合が一致していることを確認します。

$\overline{A}$ と $\overline{B}$ をそれぞれ表し、その共通部分を求めます。

すると、確かに左辺の集合と一致しましたね!

もう一つ(②)の式$$\overline{A\cap B}=\overline{A}\cup\overline{B}$$についても、同様に確認することができます。

まず左辺の集合が、下の図の緑色の部分になります。

次に右辺の集合について、同様に考えていくと…

となり、確かに一致しました。

スポンサーリンク

さて、これでド・モルガンの法則が成り立つことが確認できました。

では厳密な証明というのは、一体どのように行えばいいのでしょうか。

集合の包含関係による証明(まあ厳密)

ここで目次1-4「集合の等号」と目次1-3「部分集合」で解説した内容が役に立ちます。

【ド・モルガンの法則の集合の包含関係による証明の流れ】
ⅰ) $\overline{A\cup B}\subset\overline{A}\cap\overline{B}$ を示す。
ⅱ) $\overline{A\cup B}\supset\overline{A}\cap\overline{B}$ を示す。
※ここで、$C\subset D ⇔ x\in C ならば x\in D$

難しいところではありますので、イマイチよくわからない…という方は、ぜひ第一章を再読していただきたく思います。

それでは、以上の流れを踏まえ、実際の証明に移ります。

【証明】

ⅰ) $x\in\overline{A\cup B}$ とすると、$x\notin A\cup B$ である。

よって、$x\notin A$ かつ $x\notin B$ であることがわかる。

つまり、$x\in\overline{A}$ かつ $x\in\overline{B}$ なので、$x\in\overline{A}\cap\overline{B}$ 

したがって、$\overline{A\cup B}\subset\overline{A}\cap\overline{B}$

ⅱ) $x\in\overline{A}\cap\overline{B}$ とすると、$x\in\overline{A}$ かつ $x\in\overline{B}$ である。

よって、$x\notin A$ かつ $x\notin B$ であることがわかる。

つまり、$x\notin A\cup B$ なので、$x\in\overline{A\cup B}$

したがって、$\overline{A\cup B}\supset\overline{A}\cap\overline{B}$

ⅰ)ⅱ)より、$\overline{A\cup B}=\overline{A}\cap\overline{B}$

(証明終了)

熟読された方でお気づきの方はいらっしゃるでしょうか。

このように、ⅰ)ⅱ)と分けるのが基本ですが、実はこの証明では同値な命題しか使っていません。

つまりⅱ)の証明は、単なるⅰ)の逆順になっています。

よって、この証明は以下のようにまとめることも可能です。

【より簡潔な証明】

\begin{align}x\in\overline{A\cup B}&⇔ x\notin A\cup B\\&⇔x\notin A かつ x\notin B\\&⇔x\in\overline{A} かつ x\in\overline{B}\\&⇔x\in\overline{A}\cap\overline{B}\end{align}

よって、$$\overline{A\cup B}=\overline{A}\cap\overline{B}$$

(証明終了)

スポンサーリンク

集合論は特に大学に入ってから重要になってくるので、今のうちに簡単な証明だけでも着手しておいた方が良いと思います。

集合の包含関係(⊂や⊃)による証明はまあまあ厳密です。

なぜ「まあまあ」なのかについては、がっつり大学内容なので解説が困難です。

簡単に説明するならば、集合を定義するのにもいろいろな決まりごとが存在するからです。

興味のある方は、ラッセルのパラドックスについて調べてみると面白いかもしれません。
⇒参考.Wikipedia

【大学数学】真理値表(論理式)による証明

集合論をかたどっているのが「数理論理学」と呼ばれるものです。

つまり、集合論より厳密性が高いと言えるでしょう。

この論理学において“真理値表”と呼ばれる表を用いて証明する方法があります。

さっそく見ていきましょう。

【証明】

図のような真理値表を作る。

この図は$$1…その集合の元である。$$$$0…その集合の元でない。$$を対応させたものである。

ここで、全4パターンにおいて、真理値が一致しているため、$$\overline{A\cup B}=\overline{A}\cap\overline{B}$$が示せた。

同様に、もう一つの式についても、

真理値が一致するので、$$\overline{A\cap B}=\overline{A}\cup\overline{B}$$が示せた。

(証明終了)

この記事では、集合の元であれば「 $1$ 」、集合の元でなければ「 $0$ 」と定義してます。

また、ベン図で考えれば、以下のような図になります。

スポンサーリンク

この方法が一番確実であり厳密です。

だって、元 $x$ がどこに存在してても成り立つことを確認するには、実際にすべてのパターンについて総当たりで考えるのが手っ取り早いですもんね。

場合の数で「樹形図」が重要な理由と似ている気がします。

≫参考記事:樹形図を使う?使わない?【問題によって使い分けるコツを解説】

今用いた真理値表ですが、「真と偽」に対して「1と0」を対応させる関数と捉えることができます。

つまり、真理値表は本来“命題”に対して定義する関数です。

そこで、論理演算なるものを導入し、例えば$A\cap B$を”論理積(AND)”と呼び、$A\cup B$を”論理和(OR)”と呼び、それらを真理値表で定義します。

また、論理式をしっかり理解することで、背理法の原理を厳密に知ることもできます。

もう少し突っ込んだ話は「背理法」の記事で解説したいと思います。

⇒⇒⇒背理法とは?√2が無理数である証明問題などの具体例をわかりやすく解説!【排中律】

ド・モルガンの法則を使おう!【練習問題】

みなさん、大学数学の世界に足を踏み入れそうでしたね。

お帰りなさいませ。

それでは最後に、ド・モルガンの法則の基本的な使い方を、練習問題を通して具体的に考えていきましょう!

問題. $$U=\{n|nは1から10までの自然数\}$$$$A=\{2n-1|n=1,2,3,4,5\}$$$$B=\{1,2,3,4,5,6\}$$のとき、次の集合を求めよ。
(1) $\overline{A}\cup\overline{B}$
(2) $\overline{A}\cap\overline{B}$

このように、「補集合と補集合の~」というのは、まずそれぞれの補集合を求めるところから始まるので、まじめにやると面倒くさいんですよね。

ではこの問題を、ド・モルガンの法則を用いて解いてみましょう。

【解答】

(1) ド・モルガンの法則より、$\overline{A}\cup\overline{B}=\overline{A\cap B}$ が成り立つ。

また、$A\cap B=\{1,3,5\}$ なので、$\overline{A\cap B}=\{2,4,6,7,8,9,10\}$

したがって、$\overline{A}\cup\overline{B}=\{2,,4,6,7,8,9,10\}$

(2) ド・モルガンの法則より、$\overline{A}\cap\overline{B}=\overline{A\cup B}$ が成り立つ。

また、$A\cup B=\{1,2,3,4,5,6,7,9\}$ なので、$\overline{A\cup B}=\{8,10\}$

したがって、$\overline{A}\cap\overline{B}=\{8,10\}$

(解答終了)

スポンサーリンク

共通部分や和集合などは割と簡単に求めることができるので、少し計算がラクになりましたね。

また、$\overline{A}\cap B$ などを求める問題もあります。

これについては補集合の性質3.を用いて、

\begin{align}\overline{A}\cap {B}&=\overline{A}\cap\overline{\overline{B}}\\&=\overline{A\cup\overline{B}}\end{align}

と無理やりド・モルガンの法則を用いることもできますが、これでは計算はラクになっていないので、ド・モルガンの法則を使う意味は薄いです。

こういう問題については、地道に解くのみですが、ド・モルガンの法則が使えそうな問題については、積極的に使いこなしていきましょう!!

ド・モルガンの法則に関するまとめ

集合論は奥が深いです。

高校で習う集合でさえ、中々理解に苦しみますが、大学で習う集合論は心構えがないと、本当に訳わからなくなると思います。
(実は僕もそうでした。。)

しかし、ここをおざなりにすると、次に習う”命題”の話、特に“必要十分条件”が全然理解できなくなってしまいます。

この記事では少し大学数学にも触れました。今のうちにそこまで勉強しておく必要はないですが、「ド・モルガンの法則がなぜ成り立つのか」この疑問を通して、少しでも集合論に関する知識を深めておくことをオススメします。

次に読んでほしい「必要十分条件」に関する記事はこちらから!!

↓↓↓

関連記事
必要十分条件とは?例題・証明・矢印の向きの覚え方をわかりやすく解説!

あわせて読みたい
必要十分条件とは?例題・証明・矢印の向きの覚え方をわかりやすく解説! こんにちは、ウチダです。 今日は数学Ⅰ「集合と命題」で習う 「必要十分条件(必要条件と十分条件)」 について、例題や証明の仕方、矢印の向きの覚え方などわかりやすく...

以上、ウチダでした。
それでは皆さん、よい数学Lifeを!!

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!
スポンサーリンク

コメントを残す

コメントする

CAPTCHA


目次