一、集合

1. 集合的概念

• 集合是不同对象的无序聚集。这些对象被称为元素 (element) 或成员 (member)。
  • 属于：$a \in A$ 表示 $a$ 是集合 $A$ 中的一个元素。否则是不属于即 $a \notin A$。
  • 描述集合的方式：列举法（或者显而易见时用省略号代替其余部分）、构造器方法。
  • 集合不能自指，不然引发罗素悖论：
    • 某孤岛上只有一些人家和一位理发师。此理发师给且只给自己不刮脸的人刮脸。问他刮不刮自己。
    • 即构造集合 $P = \{ A \, | \, A \notin A \}$，$P \in P$ 和 $P \notin P$ 都必须成立。
  • 全集 $U$（随着所关注的对象范围，会有所不同）、空集 $\emptyset$。

2. 集合的关系

• 相等：当 $\forall x ((x \in A) \leftrightarrow (x \in B))$，记 $A=B$，称 $A$ 与 $B$ 相等。

• 子集（超集）：当 $\forall x ((x \in A) \to (x \in B))$，记 $A \subseteq B$，称 $A$ 是 $B$ 的子集，$B$ 是 $A$ 的超集。

  • $\emptyset \sube S$ 为空子集；$S \sube S$ 为平凡子集。
  • 真子集：当 $(A \subseteq B) \wedge \exists x ((x \in B) \wedge (x \notin A))$ 记 $A \subsetneq B$，称 $A$ 为 $B$ 的真子集。

• 基数：集合 $S$ 的元素数目称为基数，记为 $|S|$。

• 幂集：集合所有子集构成的集合。${\mathscr P}(S) = \{ T \, | \, T \subseteq S \}$。

  • $|{\mathscr P}(S)| = 2^{|S|}$，这是因为二项式定理的展开公式：

    $$ 2^n = C_n^0 + C_n^1 + C_n^2 + \cdots + C_n^n $$

• 文氏图：略。

3. 集合的运算

• 集合的基本运算
  • 并集：$A \cup B = \{ x \, | \, x\in A \vee x \in B \}$。
  • 交集：$A \cap B = \{ x \, | \, x\in A \wedge x \in B \}$。
    • 集合 $A, B$ 而言，如果 $A \cap B = \emptyset$，称 $A, B$ 为不相交的。
    • 容斥原理：$|A \cup B| = |A| + |B| - |A \cap B|$。
    • Jaccard Similarity：$J(A, B) = \frac {A \cap B}{A \cup B}$。
  • 差（补）集。
    • 相对补集。$A - B = \{ x \, | \, x\in A \wedge x \notin B \}$。
    • 绝对补集。$\overline A = U - A$。
    • $A - B = A \cap\overline B$。
  • 对称差：$A \oplus B = \{ x \, | \, x\in A \veebar x \in B \}$。
• 集合恒等式
  • 由对应的逻辑等价式可以证明。还可以通过成员表（类似于真值表）来证明。具体的公式将略过。
  1. 补律（双重否定律）：$\overline {\overline A} = A$
  2. 等幂律：$A \cap A = A$，$A \cup A = A$
  3. 吸收律：$A \cap (A \cup B) = A$，$A \cup (A \cap B) = A$
  4. 零律（支配律，零元）：$A \cap \empty = \empty$，$A \cup U = U$
  5. 同一律（恒等律，幺元）：$A \cap U = A$，$A \cup \empty = A$
  6. 互补律（矛盾律、排中律）：$A \cap \overline A = 0$，$A \cup \overline A = U$
  7. 交换律：$A \cap B = B \cap A$，$A \cup B = B \cup A$
  8. 结合律：
     • $A \cap (B \cap C) = (A \cap B) \cap C$
     • $A \cup (B \cup C) = (A \cup B) \cup C$
  9. 分配律：
     • $A \cap (B \cup C) = (A \cap B ) \cup (A \cap C)$
     • $A \cup (B \cap C) = (A \cup B ) \cap (A \cup C)$
  10. 德·摩根律：
      • $\overline {A \cup B} = \overline A \cap\overline B$
      • $\overline {A \cap B} = \overline A \cup\overline B$
• 集合的比特串表示
  • 如果全集 $U$ 是有限的，那么可以用长度为 $|U|$ 的比特串表示它的任意子集 $A$，代表全集 $U$ 的每个元素是 (1) 不是 (0) 属于该集合 $A$。
  • 交集的比特串是两个集合比特串的按位与。并集的比特串是两个集合比特串的按位或。

多重集

• 虽然仍然是元素的无序集，但每个元素作为成员可以出现多于一次，即拥有一个非负重数。
• 并集元素的重数取最大值。交集元素的重数取最小值。
• 和集（$P + Q$）、差集都可进行定义（但作2差时重数如果小于零，需要调整为零）。

模糊集

• 每个元素都有一个隶属度。

二、集族

• 集合的集合：称为集族，记为 $\mathcal A$。

• 大交、大并：$\cap \mathcal A = \bigcap _{A \in {\mathcal A}} A$，$\cup \mathcal A = \bigcup _{A \in {\mathcal A}} A$。

  • 定义空集族的大交和大并 $\cap \emptyset = U$，$\cup \emptyset = \empty$。

• $n$ 元容斥原理：

  $$ \begin{align*}

  \left| \bigcup_{i=1}^{n} A_i \right| &= \sum_{i=1}^n \left| A_i \right| - \sum_{i<j} \left| A_i \cap A_j \right| \\ &+ \sum_{i<j<k} \left| A_i \cap A_j \cap A_k \right| - \cdots + (-1)^{n+1} \left| \bigcap_{i=1}^n A_i \right|

  \end{align*} $$