本系列笔记仅为个人备忘记录
如有谬误、补充，还望不吝指正

集合论是离散数学的重要部分，也是后面许多知识的基础

1 集合的基本概念

1.1 集合与元素

1.1.1 集合

由确定的对象构成的集体，称作集合，用大写的英文字母表示，这里所谓确定指的是论域里的个体，要么属于这个集合，要么不属于这个集合，其状态是唯一确定的

1.1.2 元素

集合中的对象，称之为元素

$\in$：表示元素与集合的属于关系

例：$\mathbb{N}$表示自然数集合，$2\in \mathbb{N}$，$1.5$不属于自然数集合，$1.5\not\in \mathbb{N}$

1.2 集合的表示方法

• 列举法
• 描述法：用句子(谓词公式)描述元素属性

例：$B=\left\{ x|x是偶数 \right\},A=\left\{ x|P(x) \right\}$，其中$P(x)$是谓词公式，如果论域内对象$a$使得$P(a)$为真，则$a\in A$，反之$a\not\in A$

1.3 集合间的关系

1.4 特殊集合

1.4.1 全集$E$

包含所讨论的所有集合的集合，称之为全集，记作$E$

实际上全集就是论域

1.4.1.1 谓词公式表示

用一个永真式定义全集

$$
E=\left\{ x|P(x)\lor \neg P(x) \right\}
$$

1.4.1.2 性质

在全集下，对于任何集合$A$，都有$A\subseteq E$

1.4.2 空集$\varnothing$

没有元素的集合，称之为空集，记作$\varnothing$

1.4.2.1 谓词公式表示

用一个矛盾式定义空集

$$
\varnothing =\left\{ x|P(x)\land \neg P(x) \right\}
$$

1.4.2.2 性质

空集是任何一个集合的子集

空集是唯一的

1.5 集合的运算

1.5.1 集合的交运算

$A,B$两个集合，既属于$A$，又属于$B$的元素构成的集合就是$A$和$B$的交集，记作$A\cap B$

1.5.1.1 性质

交运算有幂等律，交换律，结合律，同一律：任何一个集合交全集为自己，零律：交空集为空集

1.5.2 集合的并运算

$A,B$两个集合，由或者属于$A$，或者属于$B$的元素构成的集合就是$A$和$B$的并，记作$A\cup B$

1.5.2.1 性质

同上，同一律：任何一个集合交空集为自己，零律：交全集为全集

1.5.3 集合的差运算

$A,B$两个集合，由属于$A$，不属于$B$的元素构成的集合就是$A$和$B$的差集，记作$A-B$

1.5.3.1 性质

1.6 有穷集的计数

1.6.1 文氏图法

1. 根据已知构建文氏图
2. 填充已知区域的元素数，未知区域用变量来表示
3. 列方程组求解

1.6.2 包含容斥定理

$n$个有限集合$A_{1},A_{2},\dots,A_{n}$,$|A_{1}|,|A_{2}|,\dots,|A_{n}|$分别是这$n$个集合的元素个数，则

$$
\begin{align}
&|A_{1}\cup A_{2}\cup \dots \cup A_{n}|=\sum_{i=1}^n|A_{i}|-\sum_{1\leq i<j\leq n}|A_{i}\cap A_{j}|
+\sum_{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\dots+ \\
&(-1)^{n-1}|A_{1}\cap A_{2}\cap \dots \cap A_{n}|
\end{align}
$$