七章节关系.ppt
第七章 关系,7.1 集合的笛卡尔积集 7.2 二元关系的基本概念 7.3 二元关系的性质7.4 二元关系的闭包运算7.5 等价关系和集合的划分 7.6 偏序关系和格 7.7 链与反链,二元关系,定义1 A，B是两个集合，称 的一个子集为从集合A到集合B的一个二元关系，简称从到的一个二元关系。,例 A=1,2，B=a,b,c,AB(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)二元关系例子：=(1,a),(2,a)(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),例,A=1,2,3，A2=AA(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)二元关系例子：A2(1,1),(2,2),(3,3),空关系、全关系、恒等关系,设是从到的一个二元关系，则。若R=，称为空关系若，称为全关系当AB时，称二元关系A为A上的二元关系当AB时，记A=(x,x)xA为A 的恒等关系,二元关系,设是从到的一个二元关系，若(x,y)R,也记为xRy,并说元素x与y有关系R；若(x,y)R,记为xRy,说元素x与y没有关系R。,集合A中某些元素与集合B中某些元素的相关性,例 设 Aa,b,c,d是4个学生的集合，B=英语，高等数学，计算机原理，离散数学，数据结构 AB 给出了学生和课程之间的所有可能配对.关系R(a,英语),(a,高等数学),(b,计算机原理),(b,英语),(c,离散数学),(c,数据结构),(d,英语),(d,离散数据),“相关性”意义既可以是描述学生们所选取的课程,也可以是表示学生对某些课程有偏爱。,二元关系的四种表示方法,有序二元组表图矩阵,例 A=a,b,c,d,B=,R=(a,),(b,),(c,),(c,),(d,),二元关系的运算,令 R1和R2是从A到B的二元关系，那么 R1R2 R1R2 R1R2 R1R2 也是从A到B的二元关系，它们分别称为R1和R2的交、并、差和对称差。,例 设A，B分别表示学生的集合和课程的集合。令,R1=(x,y)xA,yB,学生x学习课程y R2=(x,y)xA,yB,学生x喜欢课程y 则 R1R2=(x,y)xA,yB,学生x学习课程y,或者学生x喜欢课程y R1R2=(x,y)xA,yB,学生x学习喜欢的课程y R1R2=(x,y)xA,yB,学生x学习不喜欢课程y R1 R2=(x,y)xA,yB,学生x学习不喜欢课程y,或者学生x喜欢课程y但不学习课程y,逆关系,定义2 设A和B是两个集合,R是从A到B的一个二元关系。令R=(x,y)BA(y,x)R 称之为R的逆关系。,复合关系,定义3 设A，B，C是三个任意集合，R1是从A到B的一个二元关系，R2是从B到C的一个二元关系。令：R1R2(x,y)AC存在zB，使得(x,z)R1,(z,y)R2 它表示一个从A到C的二元关系，称之为R1与R2 的复合关系。,当 ABC，且 R1R2=R时，RR记为R2。,例(p77),设S1，S2是自然数集N上两个二元关系，S1(x,y)x,yN，且y=x2 S2(x,y)x,yN，且y=x+1求 S1,S2,S1S2,S2S1,S12。,解：,S1(y,x)x,yN，且y=x2 S2(y,x)x,yN，且y=x+1 S1S2(x,y)x,yN，且y=x2+1 S2S1(x,y)x,yN，且y=(x+1)2 S12(x,y)x,yN，且y=x4,定理,设 A、B、C、D是四个任意集合，R1、R2、R3分别是从A到B，从B到C，从C到D的二元关系。则有：R1 B=A R1=R1 R1=R1 R1R2=R2R1(R1 R2)R3=R1(R2 R3),证明 R1 B=A R1=R1,仅证 R1 B=R1 对于任意的x，y,若(x,y)R1B，则存在bB，使得(x,b)R1，(b,y)B，即 by，(x,y)=(x,b)R1 即有 R1 B R1 反过来，对于任意的x，y，若(x,y)R1，则 yB，(y,y)B 由(x,y)R1，(y,y)B(x,y)R1 B。即有 R1 R1 B 综上所述，结论R1 B=R1得证。,证明 R1R2=R2R1,对于任意的x,y,若（x,y）R1R2，则(y，x)R1R2，所以存在bB，使得（y，b）R1，（b，x）R2，即有（x，b）R2，（b，y）R1，（x，y）R1R2。故有 R1R2 R2R1 反之，对于任意的x,y,若（x,y）R2R1，则存在bB，使得（x，b）R2，（b，y）R1，即（y，b）R1，（b，x）R2，（y，x）R1R2，亦即（x，y）R1R2。故有 R2R1 R1R2,证明(R1 R2)R3=R1(R2 R3),对于任意的x，y，若（x，y）(R1 R2)R3，则存在eC，使得(x，e)R1 R2，(e，y)R3，由(x，e)R1R2,则存在bB,使得(x,b)R1,(b,e)R2 由(b，e)R2,(e，y)R3,则(b，y)R2R3。由(x，b)R1,(b，y)R2R3,则(x,y)R1(R2R3)故有(R1 R2)R3 R1(R2R3)同理可证 R1(R2R3)(R1 R2)R3 所以最后结论得证。,Rn,当R为某一集合A上的二元关系时，记RR=R2 由于关系的复合满足结合律(详见性质)，可以定义：R0=A RnRRR n个,命题：对于任意自然数m，n，有 RmRnRm+n,(Rm)nRmn,
