ド・モルガンの法則の問題の解法

ド・モルガンの法則を使うと解きやすくなる問題です。

見出し

1 基本問題
- 1.1 解き方
  - 1.1.1 解説
2 終わりに

基本問題

全体集合Uを $U=\{n|n$ は $1000$ 以下の自然数 $\}$ とする。
AがUの部分集合で、 $A=\{3n+1|n$ は自然数 $\}$ の集合とする。
BがUの部分集合で、 $B=\{3n+2|n$ は自然数 $\}$ の集合とする。
CがUの部分集合で、 $C=\{3^n|n$ は自然数 $\}$ の集合とする。
(1) $\overline{A \cup B}$ を求めなさい。
(2) $C \subset \overline{A} \cap \overline{B}$ であることを示しなさい。

解き方

補集合の和や積が出てきたときは、ド・モルガンの法則を使うと簡単になることがあります。

解説

(1) $\overline{A \cup B}$ を求めなさい。
まずはどのような集合になるのか確認しておきましょう。
$A=\{1,4,7,11,...\}$
$B=\{2,5,8,12,...\}$
$A\cup B = \{1,2,4,5,7,8,10,11,...\}$
$\overline{A \cup B} = \{3,6,9,...\}$
どうやら3の倍数でない数が $A\cup B$ で、という事は3の倍数が $\overline{A \cup B}$ になりそうですね。

$A\cup B \cup \{3n|n$ は自然数 $\}$ は $3n+1,3n+2,3n$ で表される数です。
自然数は3で割ると「割り切れる数」「1余る数」「2余る数」に分類できますから、これは自然数全体になりますね。
$\{3n|n$ は自然数 $\}$ は $A\cup B$ の補集合です。
$\overline{A \cup B}=\{3n|n$ は自然数 $\}$ になります。

(2) $C \subset \overline{A} \cap \overline{B}$ であることを示しなさい。
まず $\overline{A} \cap \overline{B}$ がどのような集合になるのか求めておきましょう。
ド・モルガンを使ってくださいと言わんばかりの問題ですね。
（それとなくド・モルガンを使うような、使うとすごく楽になるような、そんな良い問題が作れずすみません。）

$\overline{A} \cap \overline{B}$ の要素は $3n+1$ ではない数と $3n+2$ ではない数の共通部分です。
このままどのような集合になるか求めても良いのですが、ド・モルガンの法則を使いましょう。
$\overline{A} \cap \overline{B}=\overline{A\cup B}$ となります。
(1)の答えから
$\overline{A} \cap \overline{B}=\{3n|n$ は自然数 $\}$ となります。

後は部分集合になる証明ですね。
部分集合の証明については部分集合であることの証明の問題の解法もご参照ください。

$C=\{3^n|n$ は自然数 $\}$ でしたので、 $C\ni m=3^n$ (nは自然数)が $\overline{A} \cap \overline{B}$ に含まれている事を示すわけですが、前半部分で示した通り $\{3n|n$ は自然数 $\}$ に含まれることを示せばよいですね。
$3^n=3\cdot 3^{n-1}$ ですね。
$3^{n-1}$ は(nは自然数)でしたので、整数になります。
$3^n=3\cdot 3^{n-1} \in \{3n\}$ です。
従って $C \subset \overline{A} \cap \overline{B}$ になります。

終わりに

補集合の和や積を求めるのが難しそうなとき、ド・モルガンの法則が使えないか思い出しましょう。
ド・モルガンの法則は、「和や積の補集合は途中で切ると和積が反転する」ので覚えやすいですね。
$\overline{A\cup B}=\overline{A}\cap \overline{B}$
$\overline{A\cap B}=\overline{A}\cup \overline{B}$