离散数学课本定义和定理

第1章集合

1.1 集合的基本概念

1. 集合、元（元素）、有限集、无限集、空集

2. 表示集合的方法：列举法、描述法

3. 定义，如果集合A的任何一个元都是集合B中的元，则称集合A包含于B或B包含A，记为或，并称A为B的一个子集。

如果集合A和B满足，但B中有元不属于A，则称集合A真包含于B，记为，并且称A为B的一个真子集。

4. 定义，以A的所有子集为元构成的一个集合，这个集合称为A的幂集，记为或

1.2 集合的运算

定义，则包含A和B的所有元，但不包含其他元的集合，称为A和B的并集，记为. 定义，包含A和B的所有公共元，但不包含其他元的集合，称为A和B的交集，记为. 定义，如果它们满足，则称集合A和B是不相交的。

定义，属于A而不属于B的所有元构成集合，称为A和B的差集，记为.

定义，则E中所有不属于A的元构成的集合称为A的补集，记为.

定义，则定义A和B的对称差为

1.3 包含排斥原理

定理1.3.1设为有限集，其元素个数分别为，则

定理 1.3.2设为有限集，其元素个数分别为，则

定理1.3.3设为有限集，则

重要例题P11 例1.3.1

第2章二元关系

2.1 关系

定义

若和是两个元，将它们按前后顺序排列，记为，则成为一个序偶。

※对于序偶和，当且仅当并且时，才称和相等，记为

定义

若是个元，将它们按前后顺序排列，记为，则成为一个有序元组

（简称元组）。

定义

和是两个集合，则所有序偶的集合，称为和的直接积（或笛卡尔积），记为. 定义

设是个集合，，则所有元组的集合，称为

的笛卡尔积（或直接积），记为.

定义

若和是两个集合，则的任何子集都定义了一个二元关系，称为上的二元关系。如果，则称为上的二元关系。

定义

设是上的二元关系，，则称是上的恒等关系。

定义，则称

为的定义域。为的值域。

定义是集合上的关系，若对于任何

．．，都有即则称关系是自反的。

定义是集合上的关系，若对于任何，都满足,即对任何都不成立，则称关系是反自反的。

定义是集合上的关系，若对于任何，只要,就有,那么称关系是对称的。

定义是集合上的关系，若对于任何，只要并且时,就有，那么称关系是对称的。

定义设是集合上的关系，若对于任何，只要并且时，就有，则称关系是传递的。

定理2.1.1设是集合上的关系，若是反自反的和传递的，则是反对称的。

2.2 关系矩阵和关系图

定义无定理无

2.3 关系的运算

定义为上的关系，为上的关系，则定义关系

称为关系和的连接或复合，有时也记为.

定义为上的关系，则定义的逆关系为为上的关系：. 定理2.3.1设和都是上的二元关系，则下列各式成立

（1）（2）

（3）（4）

（5）

定理2.3.2设为上的关系，为上的关系，则

2.4 闭包运算

定义设是集合上的二元关系，如果是包含的最小自反关系，则称是关系的自反闭包，记为.

定义设是集合上的二元关系，如果是包含的最小对称关系，则称是关系的对称闭包，记为.

定义设是集合上的二元关系，如果是包含的最小传递关系，则称是关系的传递闭包，记为或.

定理2.4.1设是集合上的二元关系，则