离散数学第四章二元关系和函数.ppt

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

1、第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数14.1集合的笛卡儿积和二元关系有序对笛卡儿积及其性质二元关系的定义二元关系的表示2有序对定义由两个客体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、=2,x=33有序n元组定义一个有序n(n3)元组是一个有序对，其中第一个元素是一个有序n-1元组，即=<,xn>当n=1时,形式上可以看成有序1元组.实例n维向量是有序n元组.4笛卡儿积定义设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={,,,

4、,2>,,,,,}A={},P(A)A={<,>,<{},>}5笛卡儿积的性质不适合交换律A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、=mn6性质的证明证明A(BC)=(AB

11、)(AC)证任取∈A×(B∪C)x∈A∧y∈B∪Cx∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)∈A×B∨∈A×C∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).7例题解(1)任取ACxAyCxByDBD例3(1)证明A=BC=DAC=BD(2)AC=BD是否推出A=BC=D?为什么？(2)不一定.反例如下：A={1}，B={2},C=D=,则AC=BD但是AB.8二元关系的定

12、义定义如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如∈R,可记作xRy；如果R,则记作xy实例：R={<1,2>,},S={<1,2>,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.9从A到B的关系与A上的关系定义设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例4A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R

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

14、A

15、=n,

16、A×A

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

18、A

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

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

21、x∈A}例如,A={1,2},则EA={<1,1>,<1,2>,<2,1>,<2,2>}IA={<1,1>,<2,2>}11A上重要关系的实例

22、（续）小于等于关系LA,整除关系DA,包含关系R定义：LA={

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

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

25、x,y∈A∧xy},A是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.12实例例如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(B)={,{a},{b},{a,b}},则A