离散数学第四章二元关系和函数知识点总结.doc

《离散数学第四章二元关系和函数知识点总结.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、集合论部分第四章、二元关系和函数4.1集合的笛卡儿积与二元关系有序对定义由两个客体x和y，按照一定的顺序组成的二元组称为有序对，记作实例：点的直角坐标(3,-4)有序对性质有序性¹（当x¹y时）与相等的充分必要条件是=Ûx=uÙy=v例1<2,x+5>=<3y-4,y>，求x,y.解3y-4=2,x+5=yÞy=2,x=-3定义一个有序n(n³3)元组是一个有序对，其中第一个元素是一个有序n-1元组，即=<

2、xn-1>,xn>当n=1时,形式上可以看成有序1元组.实例n维向量是有序n元组.笛卡儿积及其性质定义设A,B为集合，A与B的笛卡儿积记作A´B，即A´B={

3、xÎAÙyÎB}例2A={1,2,3},B={a,b,c}A´B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}B´A={,,,,,,,,}A={Æ},P(A)´A={<Æ,Æ>,<{Æ},Æ>}性质：不适合交换律A

4、´B¹B´A(A¹B,A¹Æ,B¹Æ)不适合结合律(A´B)´C¹A´(B´C)(A¹Æ,B¹Æ)对于并或交运算满足分配律A´(BÈC)=(A´B)È(A´C)(BÈC)´A=(B´A)È(C´A)A´(BÇC)=(A´B)Ç(A´C)(BÇC)´A=(B´A)Ç(C´A)若A或B中有一个为空集，则A´B就是空集.A´Æ=Æ´B=Æ若

5、A

6、=m,

7、B

8、=n,则

9、A´B

10、=mn证明A´(BÈC)=(A´B)È(A´C)证任取∈A×(B∪C)Ûx∈A∧y∈B∪CÛx∈A∧(y∈B∨y∈C)Û(x∈A∧y∈B)∨(x∈A

11、∧y∈C)Û∈A×B∨∈A×CÛ∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).例3(1)证明A=BÙC=DÞA´C=B´D(2)A´C=B´D是否推出A=BÙC=D?为什么？解(1)任取ÎA´CÛxÎAÙyÎCÛxÎBÙyÎDÛÎB´D(2)不一定.反例如下：A={1}，B={2},C=D=Æ,则A´C=B´D但是A¹B.二元关系的定义定义设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例4A={0

12、,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=Æ,R4={<0,1>}.那么R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.计数

13、A

14、=n,

15、A×A

16、=n2,A×A的子集有个.所以A上有个不同的二元关系.例如

17、A

18、=3,则A上有=512个不同的二元关系.设A为任意集合，Æ是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系，定义如下：EA={

19、x∈A∧y∈A}=A×AIA={

20、x∈A}例如,A={1,2},则EA={<1,1>,<1,2>,<2,1>,<

21、2,2>}IA={<1,1>,<2,2>}小于等于关系LA,整除关系DA,包含关系RÍ定义：LA={

22、x,y∈A∧x≤y},AÍR，R为实数集合DB={

23、x,y∈B∧x整除y},BÍZ*,Z*为非0整数集RÍ={

24、x,y∈A∧xÍy},A是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.例如A={1,2,3},B={a,b},则LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}A=P

25、(B)={Æ,{a},{b},{a,b}},则A上的包含关系是RÍ={<Æ,Æ>,<Æ,{a}>,<Æ,{b}>,<Æ,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}二元关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若A={a1,a2,…,am}，B={b1,b2,…,bn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]m´n,其中rij=1ÛÎR.关系图：若A={x1,x2,…,xm}，R是从A上的关系，R的关

26、系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从xi到xj的有向边.注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的