集合の基礎
これらは離散数学の基礎概念であり、論理学・計算機科学・情報理論など多くの分野の基盤となる。
集合
- 集合 (set) とは、対象の集まりをひとつのものとして扱う数学的概念。
- 通常、波括弧 \(\{\}\) を用いて表す。
- 例：
- 自然数の最初の3つ：\(A = \{1, 2, 3\}\)
- アルファベットの母音：\(V = \{a, e, i, o, u\}\)
部分集合
集合$A$ が集合 $B$ の 部分集合 (subset) であるとは、$A$ のすべての要素が $B$ に含まれることをいう。
記号：\(A \subseteq B\)- 例：
- \(A = \{1, 2\}\), \(B = \{1, 2, 3\}\) のとき \(A \subseteq B\)
- 任意の集合 $A$ について、\(\emptyset\subseteq A\) および \(A \subseteq A\) が成り立つ。
- 真部分集合 (Proper subset):
\(A \subseteq B\) かつ \(A\neq B\) のとき、$A$ を $B$ の真部分集合といい、\(A \subset B\) と書く。
冪集合
集合 $A$ の冪集合 (power set) とは、$A$ の すべての部分集合の集合。
記号：$\mathcal{P}(A)$- 例：
- \(A = \{1, 2\}\) のとき、\(\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}\)
- 一般に、集合 $A$ の要素数が $n$ ならば、冪集合 $\mathcal{P}(A)$ の要素数は $2^n$ となる。
集合演算
和集合 (union)
集合 $A, B$ に対し、$A$ または $B$ に属する要素全体の集合。
記号：$A \cup B$
例：\(A = \{1, 2\}, B = \{2, 3\}\) のとき \(A \cup B = \{1, 2, 3\}\)積集合 (intersection)
集合 $A, B$ に共通して含まれる要素全体の集合。
記号：$A \cap B$
例：\(A = \{1, 2\}, B = \{2, 3\}$ のとき $A \cap B = \{2\}\)差集合 (difference)
集合 $A$ に属し、$B$ に属さない要素全体の集合。
記号：$A \setminus B$
例：\(A = \{1, 2, 3\}, B = \{2, 4\}\) のとき \(A \setminus B = \{1, 3\}\)補集合 (complement)
全体集合 $U$ に対して、$A$ に含まれない要素全体の集合。
記号：$\overline{A}$
例：\(U = \{1, 2, 3, 4, 5\}, A = \{1, 3\}\) のとき \(\overline{A} = \{2, 4, 5\}\)
ド・モルガンの法則
補集合と集合演算に関する基本的な関係式：
- $\overline{A \cup B} = \overline{A} \cap \overline{B}$
- $\overline{A \cap B} = \overline{A} \cup \overline{B}$
- 言い換えると：
- 「和集合の否定」＝「否定の積集合」
- 「積集合の否定」＝「否定の和集合」
これらは論理学におけるド・モルガン法則 (De Morgan’s law) とも対応しており、コンピュータ科学や回路設計などに広く応用される。
ベン図
ベン図 (Venn diagram) を用いると、集合の関係や演算を直感的に理解できる。
- $A \cup B$ : 2つの円全体
- $A \cap B$ : 2つの円の重なり部分
- $A \setminus B$ : $A$ のうち $B$ と重ならない部分
- $\overline{A}$ : 全体集合の中で $A$ 以外の部分
- ド・モルガンの法則は、ベン図で図示すると視覚的に確認できる。
まとめ
- 集合は「ものの集まり」。
- 部分集合は「含まれるかどうか」の関係。
- 冪集合は「すべての部分集合を集めた集合」。
- 集合演算は「和」「積」「差」「補」で構成される。
- ド・モルガンの法則は、補集合と集合演算の関係を示す重要法則。
- ベン図は集合の関係を可視化する便利な手法である。