离散数学(集合论基础)

通常情况下用带或不带下标的大写英文字母表示集合:A,B,C,···,A1,B1,C1,···用带或不带下标的小写英文字母表示元素:a,b,c,···,a1,b1,c1,···

若a是集合A中的元素，则称a属于A，记为a∈A若a不是集合A中的元素，则称a不属于A，记为a∈/A

列出集合中的全部元素或者仅列出一部分元素，其余用省略号(···)表示。

通过刻画集合中元素所具备的某种性质或特性来表示一个集合。P={x|P(x)}

文氏图是利用平面上的点来做成对集合的图解方法。一般使用平面上的方形或圆形表示一个集合，而使用平面上的一个小圆点来表示集合的元素。

集合A中的元素个数称为集合的基数(basenumber)，记为|A|若一个集合的基数是有限的，称该集合为有限集(finiteset)若一个集合的基数是无限的，称该集合为无限集(infiniteset)

不含任何元素的集合叫做空集(emptyset)，记作∅.空集可以符号化为∅={x|x̸=x}.空集是绝对唯一的。

针对一个具体范围，我们考虑的所有对象的集合叫做全集(universalset)，记作U或E.在文氏图一般使用方形表示全集。全集是相对唯一的

集合中的元素是无序的。{1,2,3,4}与{2,3,1,4}相同。集合中的元素是不同的。{1,2,2,3,4,3,4,2}与{1,2,3,4}相同。

外延性原理两个集合A和B相等，当且仅当它们的元素完全相同，记为A=B,否则A和B不相等，记为A̸=B.

设A,B是任意两个集合，

由子集定义可有∅⊆AA⊆A

设A,B为任意两个集合，则A=B⇔A⊆B并且B⊆A

子集个数真子集个数

设A为任意集合，把A的所有不同子集构成的集合叫做A的幂集(powerset),记作P(A)，即，P(A)={x|x⊆A}

设A,B是两个集合，则集合A与B的并集定义为：A∪B={x|x∈A或x∈B}

设A,B是两个集合，则集合A与B的交集定义为：A∩B={x|x∈A并且x∈B}

设U是全集，则集合A的补集定义为：A={x|x∈/A}

设A,B是两个集合，则集合A与B的差集定义为：A−B={x|x∈A并且x∈/B}

设A,B是两个集合，则集合A与B的对称差集定义为：A⊕B={x|(x∈A并且x∈/B)或者(x∈/A并且x∈B)}

对于两个有限集合而言，比较二者的大小只需要看集合的基数，但对于无限集合却没有这么简单。如何比较无限集合的“大小”呢？这里需要采用一种通过判断两个无限集合之间是否存在一种一一对应的关系来解决这个问题。

从有限到无限，不仅仅是简单数量上的变化(量变)，而引起了本质的改变(质变)。