离散数学:集合

集合基本概念

集合的表示法

1. 列举法
2. 特征法

子集

空集$ \emptyset $是任何集合的子集

全集和补集

补集：设集合A，属于全集E，对于任意元素x

1. $x \in E$
2. $x \notin A$

则有x促成的集合称为A的补集合，记为：~A或$\bar{A}$

幂集

幂集：设A是集合，有A的所有子集作为元素构成的集合称为A的幂集，记为P(A)

定理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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void BinarySearch(set<int> &mySet)
{
    int length = mySet.size();
    int n = 1 << length;
    for (int i = 0; i < n; i++)//外层循环遍历序号
    {
        for (int j = 0; j < n; j++)//内层循环遍历该序号二进制表示的每一位
        {
            if (i & (1 << j))//判断当前位是否为1
            {
                cout << j << " ";
            }
        }
        cout << endl;
    }
}

集合基本运算

交和并

1. $A \cap B = B \cap A$，$A \cup B = B \cup A$
2. $(A \cap B) \cap C = A \cap (B \cap C)$，$(A \cup B) \cup C = A \cup (B \cup C)$——结合律
3. $A \cap A = A$，$A \cup A = A$
4. $A \cap \emptyset = \emptyset$，$A \cup \emptyset = A$
5. $A \cap E = A$，$A \cup E = E$

分配律

德·摩根率

证明

定理1.3也可由类似方法证明

吸收律

不知名公式

差和对称差(异或)

差：设A、B为集合，x为元素

1. $x \in A$
2. $x \notin B$

由x组成的集合称为A与B的差集，记为A-B

1. $A-A = \emptyset$
2. $ A - \emptyset = A$
3. $A - E = \emptyset$
4. $E - A = \bar{A}$

对称差：设集合A、B，x为元素

1. $x \in A \bigwedge x \notin B \bigvee$
2. $x \in B \bigwedge x \notin A$

由x组成的集合称为A与B的对称差，记为$A \oplus B$

集合运算总结

等幂率

1. $A \cap A = A$
2. $A \cup A = A$

交换率

1. $A \cap B = B \cap A$
2. $A \cup B = B \cup A$
3. $A \oplus B = B \oplus A$

结合律

1. $(A \cap B) \cap C = A \cap (B \cap C)$
2. $(A \cup B) \cup C = A \cup (B \cup C)$
3. $(A \oplus B) \oplus C = A \oplus (B \oplus C)$

分配律

1. $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
2. $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
3. $A \cap (B \oplus C) = (A \cap B) \oplus (A \cap C)$

摩根率

1. $\bar{A \cap B} = \bar{A} \cup \bar{B}$
2. $\bar{A \cup B} = \bar{A} \cap \bar{B}$

吸收率

1. $A \cap (A \cup B) = A$
2. $A \cup (A \cap B) = A$

补余率

1. $A \cap \bar{A} = \emptyset$
2. $A \cup \bar{A} = E$

同一率

1. $A \cap E = A$
2. $A \cup \emptyset = A$

零一率

1. $A \cup E = E$
2. $A \cap \emptyset =\emptyset$

其它

1. $\bar{\bar{A}} = A$
2. $A - B = A \cap \bar{B}$
3. $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})$
4. $A \oplus A = \emptyset$
5. $\bar{\emptyset} = E$
6. $ \bar{E} = \emptyset$