二元关系PPT讲稿.ppt
《二元关系PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《二元关系PPT讲稿.ppt(148页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、二元关系二元关系第1页,共148页,编辑于2022年,星期四第三篇第三篇 二元关系二元关系第第6 6章章 二元关系二元关系第2页,共148页,编辑于2022年,星期四6.0 6.0 内容提要内容提要关系的性质关系的性质3关系的闭包运算关系的闭包运算4二元关系二元关系1关系的运算关系的运算2第3页,共148页,编辑于2022年,星期四6.16.1本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 二元关系的二元关系的概念和表示概念和表示2 2 关系的复合关系的复合与逆运算与逆运算3 3 关系的性质关系的性质31 n1 n重有序组重有序组2 n2 n个集合的个集合的笛卡儿积笛
2、卡儿积3 n3 n重有序组重有序组相等的判定相等的判定21 1 关系的闭包关系的闭包运算运算第4页,共148页,编辑于2022年,星期四第三篇第三篇 二元关系二元关系 关系理论历史悠久。它关系理论历史悠久。它与集合论、数理逻辑、组与集合论、数理逻辑、组合学、图论和布尔代数合学、图论和布尔代数都有密切的联系。都有密切的联系。关系是关系是日常生活以及数学日常生活以及数学中的一个基本概念,例如:中的一个基本概念,例如:兄弟关系,师生关系、位置关系、大小关系、等于关系、兄弟关系,师生关系、位置关系、大小关系、等于关系、包含关系等。包含关系等。第5页,共148页,编辑于2022年,星期四第三篇第三篇 二
3、元关系二元关系另外,关系理论还广泛用于另外,关系理论还广泛用于计算机科学技术计算机科学技术,如,如l计算机程序的输入、输出关系;计算机程序的输入、输出关系;l数据库的数据特性关系;数据库的数据特性关系;l数据结构本身就是一个关系等。数据结构本身就是一个关系等。在某种意义下,在某种意义下,关系是有联系的一些对象相互之间的关系是有联系的一些对象相互之间的各种比较行为。各种比较行为。第6页,共148页,编辑于2022年,星期四6.2 6.2 二元关系二元关系6.2.1 6.2.1 序偶与笛卡尔积序偶与笛卡尔积上上,下下;左左,右右;3434;中中国国地地处处亚亚洲洲;平平面面上上点点的的坐坐标标(x
4、,yx,y)等。)等。特征:特征:成对出现、具有一定的顺序。成对出现、具有一定的顺序。定定义义6.2.16.2.1由由两两个个元元素素x,yx,y按按照照一一定定的的次次序序组组成成的的二二元元组组称称为为有有序序偶偶对对(序序偶偶),记记作作,其其中中x x为为第一个元素,第一个元素,y y为第二个元素。为第二个元素。第7页,共148页,编辑于2022年,星期四例例6.2.16.2.1用序偶表示下列语句中的次序关系用序偶表示下列语句中的次序关系(1)(1)平面上点平面上点A A的横坐标是的横坐标是x,x,纵坐标是纵坐标是y,x,yRy,x,yR;(2)(2)成都是四川的省会;成都是四川的省会
5、;(3)(3)英语课本在书桌上;英语课本在书桌上;(4)(4)左,右关系。左,右关系。解解 各语句的序偶表示如下:各语句的序偶表示如下:(1)(1),x,yRx,yR;(2)(2);(3)(3);(4)(4)。第8页,共148页,编辑于2022年,星期四序偶相等判定定理序偶相等判定定理定义定义6.2.2 6.2.2 给定序偶给定序偶和和,如果如果a=ca=c,b=db=d,则,则=。第9页,共148页,编辑于2022年,星期四N N重有序组重有序组定义定义6.2.36.2.3由由n n个元素个元素a a1 1,a,a2 2,a,a3 3,a,an n按照一定次序组成按照一定次序组成的的n n元
6、组称为元组称为n n重有序组重有序组(n-Type)(Vector)(n-Type)(Vector),记作记作:a 例例6.2.26.2.2 用用n n重有序组描述下列语句。重有序组描述下列语句。(1 1)中国四川成都电子科技大学计算机学院;)中国四川成都电子科技大学计算机学院;(2 2)20062006年年9 9月月1010日日1818点点1616分分2525秒;秒;(3 3)1616减减5 5再加再加3 3除以除以7 7等于等于2 2。解解:(:(1 1)(2 2);(3 3)。第10页,共148页,编辑于2022年,星期四N N重有序组重有序组定定 义义6.2.46.2.4给给 定定n
7、n重重 有有 序序 组组和和b1,b2,bn。如如果果aiaibi(ibi(i1,2,1,2,,n)n),则则=b1,b2,=bn。第11页,共148页,编辑于2022年,星期四笛卡尔乘积笛卡尔乘积定义定义6.2.56.2.5 设设A A,B B是两个集合,称集合:是两个集合,称集合:AB AB|(xA)(yB)|(xA)(yB)为集合为集合A A与与B B的的笛卡尔积笛卡尔积(DescartesProduct)(DescartesProduct)。注意注意:(1 1)集合)集合A A与与B B的笛卡儿积的笛卡儿积ABAB仍然是集合;仍然是集合;(2 2)集合)集合ABAB中的元素是序偶,序偶
8、中的第一个元中的元素是序偶,序偶中的第一个元素取自素取自A A,第二个元素取自,第二个元素取自B B。第12页,共148页,编辑于2022年,星期四例例6.2.36.2.3设设A=a,B=b,c,C=,D=1,2A=a,B=b,c,C=,D=1,2,请分别请分别写出下列笛卡儿积中的元素。写出下列笛卡儿积中的元素。(1 1)AB,BAAB,BA;(;(2 2)AC,CAAC,CA;(3 3)A(BD),(AB)DA(BD),(AB)D。解解 根据根据笛卡儿积的定义笛卡儿积的定义,有,有(1 1)AB=AB=,BA=,BA=,;(2 2)AC=AC=,CA=,CA=;第13页,共148页,编辑于2
9、022年,星期四例例6.2.3 6.2.3 解(续)解(续)(3 3)因为)因为BD=BD=,,所以所以A(BD)=A(BD)=a,a,a,a,a,a,a,a,。同理同理,(AB)D=(AB)D=,1,2,1,2,1,2,1,2。第14页,共148页,编辑于2022年,星期四注意注意由例由例6.2.36.2.3我们可以看出:我们可以看出:(1 1)笛卡儿积不满足交换律;)笛卡儿积不满足交换律;(2 2)AB=AB=当且仅当当且仅当A=A=或者或者B=B=;(3 3)笛卡儿积不满足结合律;)笛卡儿积不满足结合律;(4 4)对有限集)对有限集A,BA,B,有,有|AB|=|BA|=|A|B|AB|
10、=|BA|=|A|B|第15页,共148页,编辑于2022年,星期四集合相等集合相等两个集合互相包含两个集合互相包含等式成立等式成立两个集合相等两个集合相等定理定理6.2.16.2.1设设A,B,CA,B,C是任意三个集合,则是任意三个集合,则(1 1)A(BC)=(AB)(AC)A(BC)=(AB)(AC);(2 2)(BC)A=(BA)(CA)(BC)A=(BA)(CA);(3 3)A(BC)=(AB)(AC)A(BC)=(AB)(AC);(4 4)(BC)A=(BA)(CA)(BC)A=(BA)(CA)。分析分析显然,待证等式两端都是集合显然,待证等式两端都是集合第16页,共148页,编
11、辑于2022年,星期四定理定理6.2.1 6.2.1 分析分析对(对(1 1)A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)A(BC)(AB)(AC),(AB)(AC)(AB)(AC),(AB)(AC)A(BC)A(BC)利用利用按定义证明方法按定义证明方法,首先叙述包含关系的定义,即首先叙,首先叙述包含关系的定义,即首先叙述述A(BC)A(BC)(AB)(AC)(AB)(AC)的定义:的定义:对任意对任意A(BC)A(BC),有有(AB)(AC)(AB)(AC),则则A(BC)A(BC)(AB)(AC)(AB)(AC)。同理可分析同理可分析(AB)(AC)(AB)(AC)
12、A(BC)A(BC)。第17页,共148页,编辑于2022年,星期四定理定理6.2.1 6.2.1 证明证明(1 1)对任意)对任意A(BC)A(BC),由由笛卡儿积笛卡儿积的定义知,的定义知,xAxA且且yBCyBC;由由并运算并运算定义知,定义知,yByB或者或者yCyC。于是有于是有xAxA且且yByB或者或者xAxA且且yCyC。从而,从而,ABAB或者或者ACAC。即即(AB)(AC)(AB)(AC),所以,所以,A(BC)A(BC)(AB)(AC)(AB)(AC)。第18页,共148页,编辑于2022年,星期四定理定理6.2.1 6.2.1 证明(续)证明(续)另一方面,对任意另一
13、方面,对任意(AB)(AC)(AB)(AC),由由并运算定义并运算定义知知,AB,AB或者或者ACAC。由由笛卡儿积的定义笛卡儿积的定义知知,xA,xA且且yByB或或xAxA且且yCyC。进一步有进一步有xAxA且且yBCyBC,从而从而A(BC)A(BC)。所以所以(AB)(AC)(AB)(AC)A(BC)A(BC)。于是,根据定理于是,根据定理1.2.21.2.2,有有A(BC)=(AB)(AC)A(BC)=(AB)(AC)。(2)(2)、(3)(3)和和(4)(4)的证明作为练习,自证。的证明作为练习,自证。第19页,共148页,编辑于2022年,星期四定理定理6.2.26.2.2设设
14、A,B,C,DA,B,C,D是任意四个集合,则是任意四个集合,则(AB)(AB)(CD)(CD)A A C C,B B D D。证明证明 充分性充分性():对任意对任意ABAB,有,有xAxA且且yByB。又因为又因为A A C C,B B D D,所以有,所以有xCxC且且yDyD,即,即CDCD,从而,从而(AB)(AB)(CD)(CD)。第20页,共148页,编辑于2022年,星期四定理定理6.2.2 6.2.2 证明(续)证明(续)设设A,B,C,DA,B,C,D是任意四个集合,则是任意四个集合,则(AB)(AB)(CD)(CD)A A C C,B B D D。证明证明 必要性必要性(
15、):对任意的对任意的xAxA,yByB,有,有ABAB。又因为又因为(AB)(AB)(CD)(CD),所以,所以CDCD。根据笛卡儿积的定义有根据笛卡儿积的定义有xCxC且且yDyD,从而,从而A A C C,B B D D。综上所述,定理成立。综上所述,定理成立。第21页,共148页,编辑于2022年,星期四定义定义6.2.66.2.6设设A A1 1,A,A2 2,A,An n是是n n个集合,称集合个集合,称集合A A1 1AA2 2AAn n =a=|(a|(ai iAAi i)i1,2,3,n)i1,2,3,n为集合为集合A A1 1,A,A2 2,A,An n的的笛卡儿积笛卡儿积(
16、DescartesProduct)DescartesProduct)当当A A1 1=A=A2 2=A=An n=A=A时,有时,有A A1 1AA2 2AAn n=A An n。第22页,共148页,编辑于2022年,星期四定理定理6.2.36.2.3当集合当集合A A1 1,A,A2 2,A,An n都是都是有限集有限集时,时,|A|A1 1AA2 2AAn n|=|A|=|A1 1|A|A2 2|A|An n|。第23页,共148页,编辑于2022年,星期四6.2.26.2.2关系的定义关系的定义问题:问题:某学校组织学生看电影,电影院里共有某学校组织学生看电影,电影院里共有n n个个座
17、位,看电影的学生共有座位,看电影的学生共有m m个(个(mnmn),每个学生),每个学生坐一个座位。请问,坐一个座位。请问,怎样表示学生和座位之间的从怎样表示学生和座位之间的从属关系?属关系?a1a2a3amABbnb3b2b10图6.2.1假设假设A,BA,B分别表示某学校所有分别表示某学校所有学生的集合学生的集合和电影院里所有和电影院里所有座位的集合座位的集合,即,即A=aA=a1 1,a,a2 2,a,am m,B=,B=bb1 1,b,b2 2,b,bn n。第24页,共148页,编辑于2022年,星期四定义定义6.2.7 6.2.7 设设A,BA,B为两个非空集合,称为两个非空集合,
18、称ABAB的任何的任何子集子集R R为为从从A A到到B B的二元关系的二元关系,简称关系,简称关系(Relation)(Relation)。如如A AB B,则称,则称R R为为A A上的二元关系上的二元关系。二元关系二元关系设一有序对设一有序对:若若RR,则记为则记为xRyxRy,读作读作“x“x对对y y有关系有关系R”R”;若若 R R,则记为则记为xRyxRy,读作读作“x“x对对y y没有关系没有关系R”R”。注:注:当当R=R=时,称时,称R R为为空关系空关系(emptyrelation);当当R=A BR=A B时,则称时,则称R R为为全关系全关系(TotalRelatio
19、n)。第25页,共148页,编辑于2022年,星期四例例6.2.46.2.4假设假设A=a,bA=a,b,B=c,dB=c,d,写出从,写出从A A到到B B的所有不的所有不同关系。同关系。解解 因为因为A=a,b,B=c,dA=a,b,B=c,d,所以,所以AB=,AB=,。于是。于是ABAB的所的所有不同子集为:有不同子集为:00元子集:元子集:;11元子集:元子集:,;22元子集:元子集:,b,c,;第26页,共148页,编辑于2022年,星期四例例6.2.4 6.2.4 解(续)解(续)33元子集:元子集:,;44元子集:元子集:,。注意:注意:当集合当集合A,BA,B都是有限集时,都
20、是有限集时,ABAB共有共有2 2|A|A|B|B|个不同个不同的子集,即,的子集,即,从从A A到到B B的不同关系共有的不同关系共有2 2|A|A|B|B|个。个。第27页,共148页,编辑于2022年,星期四其中,其中,A A称为称为R R的的前域前域,B B称为称为R R的的后后域。域。D D A A,C C B B满足:满足:D Dx|x|RR,C Cy|y|RR,称,称D D为为R R的的定义域定义域,记为,记为D DdomRdomR;称称C C为为R R的的值域值域,记记C CranRranR;并称并称fldRfldRDCDC为为R R的域的域。第28页,共148页,编辑于202
21、2年,星期四假假设设A=aA=a1 1,a,a2 2,a,a3 3,a,a4 4,a,a5 5,a,a6 6,B=b,B=b1 1,b,b2 2,b,b3 3,b,b4 4,b,b5 5,C=aC=a3 3,a,a4 4,a,a6 6,D=b,D=b1 1,b,b2 2,b,b4 4,b,b5 5,R=aR=,。显显然,然,R R CDCD ABAB。第29页,共148页,编辑于2022年,星期四求定义在求定义在Z Z上关系的定义域、值域和域。上关系的定义域、值域和域。(1 1)R R1 1=|(x,yZ)y=x=|(x,yZ)y=x2 2;(2 2)R R2 2=|(x,yZ)|x|=|y|
22、=7=|(x,yZ)|x|=|y|=7。解解(1 1)domRdomR1 1=Z,ranR=Z,ranR1 1=Z=Z+0,fldR0,fldR1 1=Z=Z;(2 2)domRdomR2 2=7,7,ranR=7,7,ranR2 2=7,7,=7,7,fldR fldR2 2=7,7=7,7。例例6.2.56.2.5第30页,共148页,编辑于2022年,星期四例例6.2.66.2.6设设H=f,m,s,dH=f,m,s,d表示一个家庭中父母子女四个人表示一个家庭中父母子女四个人的集合,确定的集合,确定H H上的一个长幼关系上的一个长幼关系R RH H,指出该关系,指出该关系的定义域、值域和
23、域。的定义域、值域和域。解解 R RH H=,=,;domRdomRH H=f,m,ranR=f,m,ranRH H=s,d=s,d,fldRfldRH H=f,m,s,d=f,m,s,d定义定义6.2.8 6.2.8 设设A A1 1,A,A2 2,A,An n为为n n个非空集合,称个非空集合,称A A1 1AA2 2AAn n的任意子集的任意子集R R为以为以A A1 1AA2 2AAn n为为基的基的n n元关系元关系(n-Relation)(n-Relation)。第31页,共148页,编辑于2022年,星期四6.2.36.2.3关系的表示法关系的表示法1.1.集合表示法集合表示法(
24、枚举法和叙述法枚举法和叙述法)例例6.2.76.2.7(1 1)设)设A=a,B=b,cA=a,B=b,c,用枚举法写出从,用枚举法写出从A A到到B B的不同关系;的不同关系;(2 2)用叙述法写出定义在)用叙述法写出定义在R R上的上的“相等相等”关系。关系。解解(1 1)A A到到B B的不同关系有:的不同关系有:R R1 1=,R,R2 2=,=,R R3 3=,R=,R4 4=,=,;(2 2)设)设R R上的上的“相等相等”关系为关系为S S,则,则S=|(x,yR)(x=y)S=|(x,yR)(x=y)。第32页,共148页,编辑于2022年,星期四6.2.3 6.2.3 关系的
25、表示法关系的表示法2.2.关系图法关系图法(1 1)A AB B设设A Aaa1 1,a,a2 2,.,a,.,an n,B,Bbb1 1,b,b2 2,.,b,.,bn n,R R是是从从A A到到B B的一个二元关系,则规定的一个二元关系,则规定R R的关系图如下:的关系图如下:.设设a a1 1,a,a2 2,.,a,.,an n和和b b1 1,b,b2 2,.,b,.,bn n分分别别为为图图中中的的结结点点,用用“。”表示表示;.如如a R,R,则从则从a ai i到到b bj j可用有向边可用有向边a ai i。b bj j相连。相连。a 为对应图中的有向边。为对应图中的有向边。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二元关系 PPT 讲稿
限制150内