集合基本概念
集合的表示法
- 列举法
- 特征法
子集
定理1.1:集合A和集合B相等的充要条件是:$A \subseteq B \bigwedge B \subseteq A$
空集$ \emptyset $是任何集合的子集
全集和补集
补集:设集合A,属于全集E,对于任意元素x
- $x \in E$
- $x \notin A$
则有x促成的集合称为A的补集合,记为:~A或$\bar{A}$
幂集
幂集:设A是集合,有A的所有子集作为元素构成的集合称为A的幂集,记为P(A)
定理1.2:设A是具有n个元素的有限集,即|A| = n ,其幂集的基$|P(A)| = 2^n$
定理1.1.2 证明
$$
证明:
根据排列组合规律,幂集的基为:|P(A)| = C_n^0+C_n^1+C_n^2+…+C_n^n
$$
$$
由二项式定理得:(a+b)^n = C_n^0 \times a^n + C_n^1 \times a^{(n-1)} \times b^1 + … + C_n^{n-1} \times a^1 \times b^{n-1} + C_n^n \times b^n
$$
$$
令a=b=1,得:2^n = C_n^0+C_n^1+C_n^2+…+C_n^n
$$
$$
\therefore |P(A)| = 2^n
$$
由此我们可以知道,一个集合A的所有子集的个数,一定是2的幂次,那么如何遍历一个集合的所有子集呢?
子集的遍历(生成幂集)
遍历一个集合的子集,也就是要生成该集合对应的幂集,由于幂集的元素个数总为2的次方,而对于集合中的每一个元素,讨论他是否在某个子集中时,他只有两种状态,在于不在,于是可以用0,1两种表示,则我们可以用n位二进制来表示幂集中的所有元素,而由定理1.1.2的证明我们可以知道n位二进制数是足够的,下面我们来实现一下:
查看代码
1 | void BinarySearch(set<int> &mySet) |
集合基本运算
交和并
- $A \cap B = B \cap A$,$A \cup B = B \cup A$
- $(A \cap B) \cap C = A \cap (B \cap C)$,$(A \cup B) \cup C = A \cup (B \cup C)$——结合律
- $A \cap A = A$,$A \cup A = A$
- $A \cap \emptyset = \emptyset$,$A \cup \emptyset = A$
- $A \cap E = A$,$A \cup E = E$
分配律
定理1.3:$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
定理1.3:$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
德·摩根率
定理1.4:$\bar{ A \cup B } = \bar{A} \cap \bar{B}$
定理1.4:$\bar{ A \cap B } = \bar{A} \cup \bar{B}$
证明
点击查看证明
$$
证明:设\bar{ A \cup B } = P,\bar{A} \cap \bar{B} = Q, x \in P,
$$
$$
则 x \notin A \bigwedge x \notin B
$$
$$
即 x \in \bar{A} \bigwedge x \in \bar{B}
$$
$$
\therefore x \in \bar{A} \cap \bar{B}
$$
$$
\therefore P \subseteq Q
$$
$$
设y \in Q
$$
$$
则y \in \bar{A} \bigwedge y \in \bar{B}
$$
$$
\therefore y \notin A \bigwedge y \notin B
$$
$$
\therefore y \in P
$$
$$
\therefore Q \subseteq P
$$
$$
由定理1.1得P = Q
$$
定理1.3也可由类似方法证明
吸收律
定理1.5:$A \cup (A \cap B) = A$
定理1.5:$A \cap (A \cup B) = A$
不知名公式
定理1.6:$A \cup (\bar{A} \cap B) = A \cup B$
差和对称差(异或)
差:设A、B为集合,x为元素
- $x \in A$
- $x \notin B$
由x组成的集合称为A与B的差集,记为A-B
- $A-A = \emptyset$
- $ A - \emptyset = A$
- $A - E = \emptyset$
- $E - A = \bar{A}$
定理1.7:$A - B = A \cap \bar{B}$
定理1.7:$A - (B\cup C) = (A - B) \cap (A-C)$
定理1.7:$A - (B\cap C) = (A - B) \cup (A-C)$
对称差:设集合A、B,x为元素
- $x \in A \bigwedge x \notin B \bigvee$
- $x \in B \bigwedge x \notin A$
由x组成的集合称为A与B的对称差,记为$A \oplus B$
定理1.8:$A \oplus B = (A - B) \cup (B - A)$
定理1.8:$A \oplus B = (A \cup B) \cap (\bar{B} \cup \bar{A} ) = (A \cup B) - (A \cap B)$
定理1.8:$A \cap (B \oplus C) = (A \cap B) \oplus (A \cap C)$
集合运算总结
等幂率
- $A \cap A = A$
- $A \cup A = A$
交换率
- $A \cap B = B \cap A$
- $A \cup B = B \cup A$
- $A \oplus B = B \oplus A$
结合律
- $(A \cap B) \cap C = A \cap (B \cap C)$
- $(A \cup B) \cup C = A \cup (B \cup C)$
- $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
分配律
- $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
- $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
- $A \cap (B \oplus C) = (A \cap B) \oplus (A \cap C)$
摩根率
- $\bar{A \cap B} = \bar{A} \cup \bar{B}$
- $\bar{A \cup B} = \bar{A} \cap \bar{B}$
吸收率
- $A \cap (A \cup B) = A$
- $A \cup (A \cap B) = A$
补余率
- $A \cap \bar{A} = \emptyset$
- $A \cup \bar{A} = E$
同一率
- $A \cap E = A$
- $A \cup \emptyset = A$
零一率
- $A \cup E = E$
- $A \cap \emptyset =\emptyset$
其它
- $\bar{\bar{A}} = A$
- $A - B = A \cap \bar{B}$
- $A \oplus B = (A - B) \cup (B - A) = (A \cap \bar{B} \cup (\bar{A} \cap B) = (A \cup B) - (A \cap B) = (A \cup B) \cap (\bar{A} \cup \bar{B})$
- $A \oplus A = \emptyset$
- $\bar{\emptyset} = E$
- $ \bar{E} = \emptyset$