离散数学:集合

集合基本概念

集合的表示法

列举法
特征法

子集

定理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位二进制数是足够的，下面我们来实现一下：

查看代码

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;
    }
}

集合基本运算

交和并

$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$