资源描述：
《离散数学课本定义和定理》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、实用文案第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或2A1.2集合的运算定义
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的元构成的集
3、合称为A的补集，记为A'.定义1.2.6（对称差）：A和B是两个集合，则定义A和B的对称差A⊕B为A⊕B=A-B∪B-A1.3包含排斥原理定理1.3.1设A1,A2为有限集，其元素个数分别为A1，A2则A1∪A1=A1+A2-A1∩A2定理1.3.2设A1,A2,A3为有限集，其元素个数分别为A1,A2,A3，则A1∪A2∪A3=A1+A2+A3-A1∩A2-A1∩A3-A2∩A3+A1∩A2∩A3标准文档实用文案定理1.3.3设A1,A2,…,An为有限集，则A1∪A2∪…An=i=1nAi-1≤i
4、5、B是两个集合，则所有序偶x,y的集合，称为和的直接积（或笛卡尔积），记为A×B.定义2.1.4（直接积）：设A1,A2,…,An是n个集合，xi∈Ai,i=1,2,…,n，则所有n元组x1,x2,…,xn的集合，称为A1,A2,…,An的笛卡尔积（或直接积），记为A1×A2×…×An.定义2.1.5（二元关系）若A和B是两个集合，则A×B的任何子集都定义了一个二元关系，称为A×B上的二元关系。如果A=B，则称为A上的二元关系。定义2.1.5（恒等关系）：设Ix是X上的二元关系，Ix=x,x
6、x∈X，则
7、称Ix是X上的恒等关系。定义2.1.7（定义域、值域）：若S是一个二元关系，则称DS=x
8、存在y,使x,y∈S为S的定义域。RS=y
9、存在x,使x,y∈S为S的值域。定义2.1.8（自反）：设R是集合上X的关系，若对于任何x∈X，都有xRx即x,x∈R标准文档实用文案则称R关系是自反的。定义2.1.9（反自反）：设R是集合上X的关系，若对于任何x∈X，都满足x,x∈R,即xRx对任何x∈X都不成立，则称关系R是反自反的。定义2.1.10（对称）：设R是集合上X的关系，若对于任何x,y∈X，只要xRy,
10、就有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=x,z
11、
12、存在y,使x,y∈R且y,z∈SR∘S称为关系R和S的连接或复合，有时也记为R∙S.定义2.3.2（逆关系）：设R为X×Y上的关系，则定义R的逆关系为R-1为Y×X上的关系：R-1=y,x
13、y,x∈R.定理2.3.1设R和S都是X×Y上的二元关系，则下列各式成立（1）R-1-1=R（2）R∪S-1=R-1∪S-1（3）R∩S-1=R-1∩S-1（4）R'-1=R-1'（5）R-S-1=R-1-S-1定理2.3.2设R为X×Y上的关系，S为Y×Z上的关系，
