离散数学课本定义和定理.docxVIP

离散数学课本知识点 PAGE \* MERGEFORMAT11 第1章 集合 1.1 集合的基本概念 1. 集合、元（元素）、有限集、无限集、空集 2. 表示集合的方法：列举法、描述法 3. 定义1.1.1（子集）：给定集合A和B，如果集合A的任何一个元都是集合B中的元，则称集合A包含于B或B包含A，记为A?B或B?A，并称A为B的一个子集。 如果集合A和B满足A?B，但B中有元不属于A，则称集合A真包含于B，记为A?B，并且称A为B的一个真子集。 4. 定义1.1.2（幂集）：给定集合A，以A的所有子集为元构成的一个集合，这个集合称为A的幂集，记为 ρA 1.2 集合的运算 定义1.2.1（并集）：设A和B是两个集合，则包含A和B的所有元，但不包含其他元的集合，称为A和B的并集，记为A∪B. 定义1.2.2（交集）：A和B是两个集合，包含A和B的所有公共元，但不包含其他元的集合，称为A和B的交集，记为A∩B. 定义1.2.3（不相交）：A和B是两个集合，如果它们满足A∩B=?，则称集合A和B是不相交的。 定义1.2.4（差集）：A和B是两个集合，属于A而不属于B的所有元构成集合，称为A和B的差集，记为A-B. 定义1.2.5（补集）：若A是空间E的集合，则E中所有不属于A的元构成的集合称为A的补集，记为A 定义1.2.6（对称差）：A和B是两个集合，则定义A和B的对称差A⊕B为 A⊕B= 1.3 包含排斥原理 定理1.3.1 设A1,A2为有限集，其元素个数分别为 定理1.3.2 设A1,A2,A 定理1.3.3 设A1,A i=1 重要例题 P11 例1.3.1 第2章 二元关系 2.1 关系 定义2.1.1（序偶）： 若 x 和 y 是两个元，将它们按前后顺序排列，记为x,y，则y,x成为一个序偶。 ※ 对于序偶x,y和a,b，当且仅当x=a并且y=b时，才称x,y和a,b相等，记为x,y 定义2.1.2（有序n元组）： 若x1,x2,…,xn是个元，将它们按前后顺序排列，记为x1, 定义2.1.3（直接积）： A和B是两个集合，则所有序偶x,y的集合，称为和的直接积（或笛卡尔积），记为A×B. 定义2.1.4（直接积）： 设A1,A2,…,An是n个集合，xi∈Ai,i=1,2,…,n ，则所有n元组 定义2.1.5（二元关系） 若A和B是两个集合，则A×B的任何子集都定义了一个二元关系，称为A×B上的二元关系。如果A=B，则称为A上的二元关系。 定义2.1.5（恒等关系）： 设Ix是X上的二元关系，Ix=x,x|x∈X， 定义2.1.7（定义域、值域）：若S是一个二元关系，则称 DS=x|存在y,使x,y∈S为S 定义2.1.8（自反）：设 R 是集合上 X 的关系，若对于任何 x∈X，都有 xRx 即x,x∈R则称 定义2.1.9（反自反）：设R 是集合上 X 的关系，若对于任何x∈X，都满足x,x∈R,即xRx对任何x∈X都不成立，则称关系R是反自反的 定义2.1.10（对称）：设R 是集合上 X 的关系，若对于任何x,y∈X，只要xRy,就有yRx,那么称关系R是对称的。 定义2.1.11（反对称）：设R 是集合上 X 的关系，若对于任何x,y∈X，只要xRy并且yRx时,就有x=y，那么称关系R是对称的。 定义2.1.11（传递） 设R 是集合上 X 的关系，若对于任何x,y∈X，只要xRy并且yRz时，就有xRz，则称关系R是传递的。 定理2.1.1 设R 是集合上 X 的关系，若R是反自反的和传递的，则R是反对称的。 2.2 关系矩阵和关系图 定义 无 定理 无 2.3 关系的运算 定义2.3.1（连接）：设 R 为X×Y上的关系，S为Y×Z上的关系，则定义关系 R°S= R°S称为关系R和S的连接或复合，有时也记为R?S. 定义2.3.2（逆关系）：设 R 为X×Y上的关系，则定义R的逆关系为R-1为Y×X上的关系：R 定理2.3.1 设R和S都是X×Y上的二元关系，则下列各式成立 （1）R-1-1=R （ （3）R∩S-1=R-1∩S （5）R-S 定理2.3.2 设R为X×Y上的关系，S为Y×Z上的关系，则R°S 2.4 闭包运算 定义2.4.1（自反闭包）： 设R是集合X上的二元关系，如果R1是包含R的最小自反关系，则称R1是关系R的自反闭包，记为 定义2.4.2（对称闭包）： 设R是集合X上的二元关系，如果R1是包含R的最小对称关系，则称R1是关系R的对称闭包，记为 定义2.4.3（传递闭包）： 设R是集合X上的二元关系，如果R1是包含R的最小传递关系，则称R1是关系R的传递闭包，记为tR 定理2.4.1 设R是集合X上的二元关系，则 R是自反的，当且仅当rR R是对称的，