离散数学

要学到的

离散数学基础: 集合、偏序集、良序、数学归纳法、级数、递归、递推

概念定义

集合基数: 集合 A 中元素的数目称为集合A的基数(base number), 记为|A|

• 如|A|是有限的, 则称A为有限集
• 如|A|是无限的, 则称A为无限集

m元子集: 如果一个集合A中含有n个元素, 则称集合A为n元集, 称A的含有m个( $0\le m\le n$ )元素的子集为A的m元子集.

子集总数: 一般来说, 对于n元集A, 它的m( $0\le m\le n$ )元子集 $C_n^m$ 个, 所以不同的子集总数有:
$C_n^0+C_n^1+C_n^2+...+C_n^n=2^n$ 所以, n元集共有 $2^n$ 个子集

幂集: 设A为任意集合, 把A的所有不同子集为元素构成的集合叫做A的幂集(power set), 记为 P(A) 或 $2^A$
符号化表示:
$P(A)=\{x|\mathrm{一}\mathrm{切}\subseteq A\}$
该集合又称为集族(family of set)
对集族的研究在数学方面、知识库和表处理语言及人工智能等方面都有十分重要的意义
显然, 若集合A有n个元素, 则集合A共有 $2^{|A|}$ 个子集, 即
$|P(A)|=2^{|A|}$

集合的运算:
设A、B为任意集合, U为全集

• 并集$A\bigcup B=\{X|X\in A\mathrm{或}X\in B\}$
• 交集$A\bigcap B=\{X|X\in A\mathrm{且}X\in B\}$
• 差集$A-B=\{X|X\in A\mathrm{且}X\notin B\}$
• 补集$\overline{A}=U-A=\{X|X\in U\mathrm{且}X\notin A\}(A^{\prime },\sim A,A^C)$
• 对称差集$A\oplus B=\{X|((X\in A)\mathrm{且}(X\notin B))\mathrm{或}((X\in B)\mathrm{且}(X\notin A))\}$

推广:

$$\bigcup _{i=1}^n{A}_i=\bigcup _{i\in \{1,2,...,n\}}^n{A}_i=A_1\bigcup A_2\bigcup A_3\bigcup ...\bigcup A_n=\{X|(X\in A_1)\mathrm{或}(X\in A_2)\mathrm{或}...\mathrm{或}(X\in A_n)\}$$$$\bigcap _{i=1}^n{A}_i=\bigcap _{i\in \{1,2,...,n\}}^n{A}_i=A_1\bigcap A_2\bigcap A_3\bigcap ...\bigcap A_n=\{X|(X\in A_1)\mathrm{且}(X\in A_2)\mathrm{且}...\mathrm{且}(X\in A_n)\}$$

当n无限增大时, 可以记为

$$\bigcup _{i=1}^{\mathrm{\infty }}{A}_i=\bigcup _{i\in Z^{+}}{A}_i=A_1\bigcup A_2\bigcup A_3\bigcup ...$$$$\bigcap _{i=1}^{\mathrm{\infty }}{A}_i=\bigcap _{i\in Z^{+}}{A}_i=A_1\bigcap A_2\bigcap A_3\bigcap ...$$

差和补运算的几个性质

• $A-A=\mathrm{\Phi }$
• $A-B=A-(A\bigcap B)$
• $A\bigcup (B-A)=A\bigcup B$
• $A-B=A\bigcap \overline{B}$
• $(A-B)-C=A-(B\bigcup C)$

定理
设A、B、C为任意集合, U为全集, $\mathrm{\Phi }$ 为空集

• 幂等律$A\bigcup A=A;A\bigcap A=A$
• 恒等律$A\bigcup \mathrm{\Phi }=A;A\bigcap U=A$
• 零律$A\bigcup U=U;A\bigcap \mathrm{\Phi }=\mathrm{\Phi }$
• 否定律$\overline{\overline{A}}=A$
• 矛盾律$A\bigcap \overline{A}=\mathrm{\Phi }$
• 排中律$A\bigcup \overline{A}=U$
• 交换律$A\bigcup B=B\bigcup A;A\bigcap B=B\bigcap A$
• 吸收率$A\bigcap (A\bigcup B)=A;A\bigcup (A\bigcap B)=A$
• DeMorgAn律$\overline{A\bigcup B}=\overline{A}\bigcap \overline{B};\overline{A\bigcap B}=\overline{A}\bigcup \overline{B}$
• 结合律$A\bigcup (B\bigcup C)=(A\bigcup B)\bigcup C;A\bigcap (B\bigcap C)=(A\bigcap B)\bigcap C$
• 分配律$A\bigcap (B\bigcup C)=(A\bigcap B)\bigcup (A\bigcap C);A\bigcup (B\bigcap C)=(A\bigcup B)\bigcap (A\bigcup C)$