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

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

1、二元关系和函数第四章2第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数34.1集合的笛卡儿积和二元关系有序对笛卡儿积及其性质二元关系的定义二元关系的表示4有序对的性质：1）有序性（当xy时）2）与相等的充分必要条件是=x=uy=v例4.1<2,x+5>=<3y4,y>，求x,y.解3y4=2,x+5=yy=2,x=3§4.1二元关系的概念1.有序对/序偶：由两个元素x和y

2、按一定顺序排成二元组，记作：。其中x称作第一个元素；y称作第二个元素。5实例：1.空间直角坐标系中的坐标<3，5，－6>是有序三元组2.图书馆记录<书类别，书号，书名，作者，出版社，年份>是一个有序六元组.2.有序n元组：一个有序n(n3)元组是一个有序对，其中第一个元素是一个有序n-1元组，即<,xn>=。我们将来的研究重点为有序二元组，即有序对/序偶6例4.2A={1,2,3},B={a,b,c},C=AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,

3、<2,c>,<3,a>,<3,b>,<3,c>}BA={,,,,,,,,}AA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}AC=CA=3.笛卡儿积：设A,B为集合，用A中元素为第一个元素，B中元素为第二个元素，构成有序对.所有这样的有序对组成的集合叫做A与B的笛卡儿积记作AB,即AB={

4、xAyB}。7笛卡儿积的性质：1.不适合交换律ABBA(AB,A,B)2.

5、若A或B中有一个为空集，则AB就是空集.A=B=3.若

6、A

7、=m,

8、B

9、=n,则

10、AB

11、=mn4.不适合结合律(AB)CA(BC)(A,B,C)例：A={1},B={2},C={3}AB={<1,2>},(AB)C={<<1,2>,3>}={<1,2,3>}BC={<2,3>},A(BC)={<1,<2,3>>}{<1,2,3>}8二元关系：集合中两个元素之间的某种关系例3甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。比赛结果可表示为：{<乙,甲>，<甲,丙>，<乙,丙>

12、}，其中表示x胜y，它表示了集合{甲,乙,丙}中元素之间的一种胜负关系.例4有A、B、C3个人和四项工作G1、G2、G3、G4，已知A可以从事工作G1和G4，B可以从事工作G3，C可以从事工作G1和G2.那么，人和工作之间的对应关系可以记作R＝{,,,,∈R,可记作xRy；如果R,则记作xRy实例：R1={<1,2>,},R2=,R3={<1,2>,3,4}，R4={

13、x∈N

14、∧y∈Z}R1,R2,R4是二元关系；R3不是二元关系。4.二元关系：如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对(以有序对为元素的集合)（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.105.从A到B的关系与A上的关系设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例5A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=,R4={<0,1>}.那么R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.计数：

15、A

16、=n,

17、

18、B

19、=m,

20、A×B

21、=n×m,A×B的子集有个.所以A到B上有个不同的二元关系.

22、A

23、=n,

24、A×A

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

26、A

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

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

29、x∈A}例如,A={1,2},则EA={<1,1>,<1,2>,<2,1>,<2,2>}IA={<1,1>,<2,2>}注：{<1,1>}≠IA;{<2,2>}≠IA12A上重要关系

30、的实例（续