离散数学

离散数学是研究离散量的结构及其相互关系的数学学科，是计算机科学的理论基础。

集合论

集合论是数学的一个基本的分支学科，研究对象是一般集合的性质、结构、关系、运算等

集合

定义：集合是指具有某种特定性质的对象组成的集体，构成集合的对象则称为该集合的元素。

元素和集合的关系

集合中的元素有三个性质：

• 确定性：集合中的元素必须是明确的，即对于任何一个对象，都能判断它是否属于该集合。例如，集合 {1, 2, 3} 中的元素是明确的，1 属于该集合，而 4 不属于。
• 互异性：集合中的元素是互不相同的，不允许出现重复的元素。例如，集合 {1, 2, 3} 和 {1, 1, 2, 3} 是相同的。
• 无序性：集合中的元素没有固定的顺序。例如，集合 {1, 2, 3} 和 {3, 2, 1} 是相同的。

元素与集合之间的关系用“属于”（$\in$）或“不属于”（$\notin$）表示。例如：

• 如果 $x$ 是集合 $A$ 的元素，则记作 $x\in A$。
• 如果 $x$ 不是集合 $A$ 的元素，则记作 $x\notin A$。

集合本身也可以作为元素，例如 { {1, 2}, {3, 4} } ，这两个集合是整个大集合的元素

空集

定义：不含任何元素的集合称作空集，记作 $\mathrm{\varnothing }$

• 空集是任何集合的子集：对于任意集合 $A$，都有 $\mathrm{\varnothing }\subseteq A$
• 空集与任何集合的交集仍为空集：$A\cap \mathrm{\varnothing }=\mathrm{\varnothing }$
• 空集与任何集合的并集为该集合本身：$A\cup \mathrm{\varnothing }=A$
• 空集的幂集（即由空集的所有子集构成的集合）为 $\mathrm{\varnothing }$，这是一个只包含空集的集合

集合的基本运算

运算规则	符号	说明	示例
并集	$\cup$	$A\cup B$ 表示 $A$ 和 $B$ 中的所有元素组成的集合	若 A = {1, 2, 3} 和 B = {2, 3, 4}，则 $A\cup B$ = {1, 2, 3, 4}
交集	$\cap$	$A\cap B$ 表示同时属于 $A$ 和 $B$ 的元素组成的集合	若 A = {1, 2, 3} 和 B = {2, 3, 4}，则 $A\cap B$ = {2, 3}
差集	$-$	$A-B$ 表示属于 $A$ 但不属于 $B$ 的元素组成的集合	若 A = {1, 2, 3} 和 B = {2, 3, 4}，则 $A-B$ = {1}
补集	$\sim$	$\sim A$ 表示属于全集 $E$ 但不属于 $A$ 的元素组成的集合	若 E = {1, 2, 3, 4, 5} 和 A = {1, 2, 3}，则 $\sim A$ = {4, 5}
对称差集	$\oplus$	$A\oplus B$ 表示所有属于 $A$ 和 $B$ 但不属于 $A$ 和 $B$ 交集的元素组成的集合	若 A = {1, 2, 3} 和 B = {2, 3, 4}，则 $A\oplus B$ = {1, 4}
笛卡尔积	$\times$	$A\times B$ 表示所有可能的有序对 $(a,b)$ 组成的集合，其中 $a\in A$ 且 $b\in B$	若 A = {1, 2} 和 B = {a, b}，则 $A\times B$ = {(1, a), (1, b), (2, a), (2, b)}

$A\oplus B=(A-B)\cup (B-A)=(A\cup B)-(A\cap B)$

$\sim A=E-A（E\mathrm{为}\mathrm{全}\mathrm{集}，A\in E）$

集合的运算性质

• 幂等律：$A\cup A=A$；$A\cap A=A$
• 交换律：$A\cup B=B\cup A$；$A\cap B=B\cap A$
• 结合律：$(A\cup B)\cup C=A\cup (B\cup C)$；$(A\cap B)\cap C=A\cap (B\cap C)$
• 零律：$A\cup E=E$；$A\cap \mathrm{\varnothing }=\mathrm{\varnothing }$
• 同一律：$A\cup \mathrm{\varnothing }=A$；$A\cap E=A$
• 分配律：$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$；$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
• 吸收律：$A\cup (A\cap B)=A$；$A\cap (A\cup B)=A$
• 对合率：$\sim (\sim A)=A$
• 排中率：$A\cup (\sim A)=E$
• 矛盾率：$A\cup (\sim A)=\mathrm{\varnothing }$
• 德摩根定律：$\sim (A\cup B)=(\sim A)\cap (\sim B)$；$\sim (A\cap B)=(\sim A)\cup (\sim B)$

关系及其性质