离散数学第2章-关系.ppt

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

1、世间万物都存在着联系.利用集合刻划这种联系的数学模型—关系.“关系”的相关内容对今后学习数据结构、数据库等许多课程都是很重要的.1Chapter2关系例学生A={张三,李四,王五};课程B={英语,数学实验,离散数学,数据结构,汇编语言};成绩C={优,良,合格,不合格}.22.1关系的概念2.1.1n元关系的定义选课(A与B之间的关系):R={(张三,离散数学),(张三,数据结构),(张三,英语),(李四,数据结构),(王五,数学实验),(王五,汇编语言)}.课程得分(A,B与C之间的关系):R

2、'={(张三,离散数学,优),(张三,数据结构,良),(张三,英语,优),(李四,数据结构,优),(王五,数学实验,合格),(王五,汇编语言,良)}.定义特别地,若,则称R为A上的n元关系.n=2:2元关系.例设A={0,1,2,3,4},A上的关系R={(x,y)

3、x=y+1或y=x/2},试用列举法求出R.解R={(1,0),(2,1),(3,2),(4,3)(0,0),(2,1),(4,2)}3集合关系2元关系:两个集合A和B(可以相同)间的关系A到B的关系:A到A,即A上的关系:A到B的空

4、关系AB与全关系ABAB.例A={a,b},B={1,2,3},Theorem

5、A

6、=m,

7、B

8、=n,则A到B的关系有2mn个.提示

9、AB

10、=mn.若

11、A

12、=m,则A上的关系有2m2个.42.1.2二元关系√??关系符号:设RAB,若(x,y)R,则称元素x与y有关系R,可记为xRy:例实数集合R上的大于“>”关系:例整数集合Z上的模k同余关系k:定义：A上的恒等关系:例若A={a,b,c},则IA={(a,a),(b,b),(c,c)}.k

13、(x-y)x除以k的余数=y除

14、以k的余数.5定义域:设RAB,domR={x

15、xA,存在yB,使得(x,y)R}即R中所有有序对中第一位置元素组成的集合,它显然是A的子集.例R={(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)}domR={1,2,3,4}.值域:设RAB,ranR={y

16、yB,存在xA,使得(x,y)R}即R中所有有序对中第二位置元素组成的集合,它是B的子集.在上例中,ranR={1,2,3,4}.62.1.3关系的定义域与值域1、关系图情形

17、1R是A到B(包括A上)的关系例A={a,b,c,d},B={1,2,3},R={(a,2),(a,3),(c,2),(d,2)}.72.1.4关系的表示(除集合表示外)情形2R是A上的关系例A={a,b,c,d},R={(a,b),(a,c),(c,a),(d,c),(d,d)}.82、关系矩阵例A={a,b,c,d},B={1,2,3},R={(a,2),(a,3),(c,2),(d,2)}.9例A={a,b,c},B={1,2,3},f:AB,f(a)=2,f(b)=3,f(c)=3.备注

18、一般来说,A到B的关系不是A到B的函数.2.1.5函数的关系(集合)定义×10函数:A到B有关系f,并满足以下条件,(1)domf=A;(2)例判断自然数集合N上的下列关系能否构成函数.f={(x,y)

19、x,yN,x+y<5}f={(x,y)

20、x,yN,y为小于等于x的素数个数}作业习题2.1P44:2.13(4).15.11不能能集合运算:122.2关系的运算2.2.1关系的集合运算逆关系:例A={a,b,c,d},B={1,2,3},R={(a,3),(c,2),(a,2),(b,2)}.

21、逆关系的关系图与关系矩阵:逆运算的性质:Theorem(对合律)132.2.2关系的逆运算Theorem(逆运算与关系的集合运算并,交,补的关系)(1)(2)(3)Proof(2)(4)(5)141、关系R与关系S的复合R◦S例152.2.3关系的复合运算借助于关系图理解复合运算:16例A={1,2,3,4},R1={(2,4),(3,3),(4,2),(4,4)},R2={(2,1),(3,2),(4,3)}R1R2={(2,3),(3,2),(4,1),(4,3)}R2R1={(3,4),

22、(4,3)}17借助于关系矩阵进行复合运算:abab0，1之间的逻辑加,逻辑乘abab18设A=[aij]为mp布尔矩阵，B=[bij]为pn布尔矩阵,A和B的逻辑乘运算为mn布尔矩阵C=[cij]定义如下矩阵的逻辑乘运算19矩阵的逻辑乘运算2332221011R1={(1,b),(2,b),(2,c)},R2={(a,1),(a,2),(b,1),(c,1),(c,2)}R1R2={(1,1),(2,1),(2,2)}A={1,2},B={a,b,c},20