saitei.net

集合4つの包除原理と真偽値

集合4つの包除原理と真偽値

はじめに

今回は,集合4つの包除原理を解説する。(上の図は集合4つの場合のベン図)
ただし,注意しておくが大学入試では集合が2つとか3つの場合の包除原理は必須だが,集合4つの場合は不要だ。そこまで知らなければ解けない問題は出題されない。

包除原理を導くのには,真偽値という概念が重要であることを解説するのが今回の目的だ。このことを解説する記事はwebでは見当たらないので,ここに書くことは意味があると思う。

包除原理

包除原理とは,集合の和集合(\(A\cup B\)など)の要素の個数(\(n(A\cup B)\)などと表す)を求める公式だ。次のようになる。

包除原理
\(n(A\cup B)=n(A)+n(B)-n(A\cap B)\)
\(n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap
A)+n(A\cap B\cap C)\)

集合4つの場合

集合4つの場合は
\begin{align*}
&n(A\cup B \cup C\cup D)\\
=&n(A)+n(B)+n(C)+n(D)\\
& -n(A\cap B)-n(A\cap C) -n(A\cap D)\\
& -n(B\cap C)-n(B\cap D) -n(C\cap D)\\
& +n(A\cap B\cap C)+n(A\cap B\cap D)+n(A\cap C\cap D)+n(B\cap C\cap D)\\
&-n(A\cap B\cap C\cap D)
\end{align*}
となる。

このことは二項定理を用いた証明がよく知られているが(例えば広瀬和之著「合格る確率」 を見よ。よい本だよ),「命題の真偽値」を使った証明の方が公式の形(どこからこんな式を思いつくんだ?)が納得しやすいと思う。

真偽値

命題\(P\)の真偽値\(T(P)\)とは

  • \(P\)が真のとき,\(T(P)=1\)
  • \(P\)が偽のとき,\(T(P)=0\)

として定めるものだ。(簡単!)

真偽値の性質とその応用例

次の性質は簡単に確かめられる。

  • 命題\(P\)の否定を\(\overline P\)と表すと,\(T(\overline P)=1-T(P)\)
  • \(T(PかつQ)=T(P)T(Q)\)

このことから\(T(x\in A\cup B)\)を次のようにして,\(T(x\in A)\)と\(T(x\in B)\)の式に変形できる。
\begin{align*}
&T(x\in A\cup B) \\
=& T(x\in A または x\in B)\\
=& T\left(\overline{\overline{x\in A または x\in B\quad}} \quad \right)\\
=& 1-T(\overline{x\in A または x\in B\quad} )\\
=& 1-T(\overline{x\in A}かつ\overline{x\in B}) \quad (\overline{否定の記号}が二つに分かれ,「または」が「かつ」に変わったことに注意せよ)\\
=& 1-T(\overline{x\in A})T(\overline{x \in B})\\
=& 1-\{1-T(x\in A)\}\{1-T(x\in B)\}\quad \cdots (1) \quad (これが重要)\\
=& T(x\in A) +T(x\in B) -T(x\in A)T(x\in B)
\end{align*}

真偽値と包除原理

上の結果と,\(T(x\in A)T(x\in B)= T(x\in A かつ x \in B)=T(x\in A\cap B)\)より
\[
T(x\in A\cup B)=T(x\in A) +T(x\in B) -T(x\in A\cap B) \qquad \cdots (2)
\]
となるが,これと
\[
包除原理 \quad n(A\cup B)=n(A)+n(B)-n(A\cap B)
\]
同じ形をしている!
(1)から(2)が導かれることが包除原理の本質である。

集合2つの包除原理の証明

集合2つの場合の包除原理は誰にでも明らかだと思うが,真偽値の使い方を分かってもらうために,(2)から証明してみよう。
一般に,全体集合を\(U\)とし,その部分集合集合\(S\)が有限集合の場合,\(S\)の要素の個数\(n(S)\)は
\[\displaystyle n(S)=\sum_{x\in U} T(x\in S)\]
と表される。(右辺は,『全体集合\(U\)のすべての要素\(x\)について,\(x\)が\(S\)の要素なら1とカウントせよ』と言うことだから,\(n(S)\)に一致する。)
よって,(2)を用いて
\begin{align*}
&n(A\cup B)\\
=& \sum_{x\in U}T(x\in A\cup B)\\
=& \sum_{x\in U}\{T(x\in A) +T(x\in B) -T(x\in A\cap B) \}\\
=& \sum_{x\in U}T(x\in A) + \sum_{x\in U}T(x\in B)-\sum_{x\in U}T(x\in A\cap B)\\
=& n(A)+n(B)-n(A\cap B) \quad (証明終わり)
\end{align*}

まとめ

集合4つの包除原理も「(1)に相当する式から(2)に相当する式を導く」と言う方法で証明できる。しかし,ここに直接書くのは手間なので,私の授業プリントを手直ししたものを見て欲しい。

(旧受験数学BLOG 2015/02/17 より)

  • ピックアップ
  • Category

この記事は参考になりましたか?

0
コメント0件
URL :
TRACKBACK URL :

Leave a reply

*
*
* (公開されません)

CAPTCHA


Return Top