【教学课件】第2章关系(第一部分).ppt

《【教学课件】第2章关系(第一部分).ppt》由会员分享，可在线阅读，更多相关《【教学课件】第2章关系(第一部分).ppt（48页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第2 2章章 关关 系（第一部分）系（第一部分）1内容提要:1.关系的定义、有序对与笛卡尔积 2.二元关系概念及其表示方法 3.二元关系的基本类型与判定方法 22.1 2.1 关系关系(Relation)Relation)和和有序对有序对(ordered pair)ordered pair)n宇宙中存在着形形色色的关系,人与人之间：父子关系、师生关系、同学关系 数之间：大小关系、平方关系、整除关系、集合之间：包含关系、真包含关系、相等关系n集合论为刻划这种联系提供了一种数学模型:关系。n关系是一个集合,以具有该种联系的事物对为其成员。因而在关系的研究中可方便地使用集合论的概念、方法和成果。3

2、定义：由两个具有固定次序的个体组成的序列,称为序偶(ordered pair),记作或(a,b)。其中,a是第一元素,b是第二元素.n有序，即：ab (a,b)(b,a)（区别于集合元素的无序性）n相等：(a,b)=(c,d)a=c 且 b=dn(a,a)可为有序对 （区别于集合的元素不重复）有序对(ordered pair)4 定义：定义：有序对的集合称为二元关系；令A1,2,3,4,，A元素间的小于关系为：(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)二元关系(binary relation)5有序n元组(n-tuple)定义：由n个具有给定次序的个体a1,a2,a

3、n 组成的序列,称为有序n元组,记作(a1,a2,an),其中ai称为第i个分量。（1）有序，(1,2,3,4,5)(5,4,3,2,1)（2）(a1,a2,an)=(b1,b2,bn)当且仅当ai=bi(i=1,2,n)。（3）(a,a,a)可为有序对。定义：有序n元组的集合为n元关系。62.2 笛卡尔积(Cartesian product)笛卡尔积也叫卡氏积，是一种重要的集合运算,是向量概念的推广,也是数据库重要术语“元组”的基础。定义：定义：设A1,A2,An是任意的n个集合,所有有序n元组(a1,a2,an)组成的集合,称为集合A1,A2,An 的笛卡尔积,并用A1 A2 An 表示。

4、其中 ai Ai(i=1,2,n)。即 A1A2An=(a1,a2,an)|aiAi,i=1,2,n注意：（1）可表示不含任何有序组的笛卡尔积。（2）若Ai=，则A1A2An=7笛卡尔积(Cartesian product)举例例：例：设A=a,b,c,B=0,1,则 AB=(a,0),(a,1),(b,0),(b,1),(c,0),(c,1)BA=(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)AA=(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)B B=(0,0),(0,1),(1,0),(1,1)特别地：特别

5、地：n=2时，只有2个集合参与运算，称作二维笛卡尔积。8二维笛卡尔积的性质n非交换:AB BA (除非 A=B 或 A=或 B=)n非结合:(AB)C A(BC)(除非 A=或 B=或 C=)n分配律:A(BC)=(AB)(AC)A(BC)=(AB)(AC)n其他:AB=A=或 B=n注意：笛卡尔积的性质具有明显的矢量特征。9笛卡尔积非交换性n非交换:AB BA (除非 A=B 或 A=或 B=)n反例:A=1,B=2.AB=(1,2),BA=(2,1).10笛卡尔积非结合性n非结合:(AB)C A(BC)(除非 A=或 B=或 C=)n反例:A=B=C=1.(AB)C=(1,1),1),A(

6、BC)=(1,(1,1).11笛卡尔积的分配律(证明)n证明：A(BC)=(AB)(AC)nproof:对于任意的 x,y A (BC)xA 并且 y(BC)/*卡氏积定义的逆运用*/xA 并且(yB 且 yC)(xA 且 yB)并且(xA 且 yC)(x,y)AB 并且 x,yAC/*卡氏积定义*/x,y(AB)(AC)。12笛卡尔积分配律1.A(BC)=(AB)(AC)2.A(BC)=(AB)(AC)3.(BC)A=(BA)(CA)4.(BC)A=(BA)(CA)5.A(B-C)=(AB)-(AC)6.(B-C)A=(BA)-(CA)n另外7个公式可类似地证明。13例题1设A,B,C,D是

7、任意集合,判断下列结论是否正确(1)AB=A=或 B=(2)若A,则 ABAC BC.(3)AC 且 BD ABCD,(4)ABCD AC 且 BD(5)(5)AnswerAnswer：(1)(2)(3)正确。(6)(4)仅当(A=B=)或(A 且 B)时,ABCD AC 且 BD成立14例题1(证明(2)(2)若A,则ABAC BC.证明:()若 B=,显然，BC.若 B,对于任意 yB 由A,任选 xA (x,y)AB (x,y)AC xA 且 yC yC.BC15例题1(证明(2),续)(2)若A,则ABAC BC.证明(续):()若 B=,则AB=AC成立.若 B.任选AB xA且yB

8、 xA且yC AC ABAC.注意:在()中不需要条件 A.16例题1(证明(3)设A,B,C,D为四个非空集合,则ABCD的充分必要条件是AC,BD证明证明:必要性:若ABCD,又A,B,C,D都不是空集,故对任意的xA,yB,x,yABCD,则xC,yD,因此AC,BD。充分性:若AC,因B非空,由(2)的结论故ABCB。又 B D,因C非空,由(2)的结论,故 C B C D。由包含关系的传递性质,A B C D。17n维笛卡尔积(性质)n非交换:ABCBCA (要求A,B,C均非空,且互不相等)n非结合:(AB)CA(BC)n分配律:例如AB(CD)=(ABC)(ABD)n其他:如 A

9、BC=A=或 B=或 C=.182.3 关系问题的再定义定义：笛卡尔积A1 A2 An 的任意一个子集R称为A1,A2,An 上的一个n元关系。特别地,A1 A2的任意一个子集称A1到A2的一个二元关系。A1 A1的任意一个子集称A1上的一个二元关系。n二元关系主要是描述两个集合之间元素与元素的关系或者是一个集合内部元素之间的关系。19二元关系判别n二元关系(简称关系):是集合,其元素全是有序对.n例1：判断下列集合是否二元关系 R1=(1,2),(3,4),(4,5)R2=(1,2),(,),(a,b)R3=(1,2),(3,4),(白菜,小猫)R4=(a,b),(1,2,3),a,1 An

10、swer：R1、R2和R3是二元关系，R4不是关系。20二元关系的记号n设R是二元关系,则(x,y)R x与y具有R关系(x与yR相关)x R yn对比:x R y (中缀(infix)记号)R(x,y)(前缀(prefix)记号)(x,y)R (后缀(suffix)记号)n例如:215 (2,15)（2,15）注意：注意：x R y 称作称作x与与y不具有关系不具有关系R。21A到B的二元关系的数目n 若R是A到B的二元关系 RP(AB)n若|A|=m,|B|=n,A到B不同的二元关系共有几个？AB中有序对数目：|AB|=m*n,故|P(AB)|=2m*n 即A到B不同的二元关系共有2m*n

11、个22A到B的二元关系(举例)n例:设 A=a1,a2,B=b,可知|A|=2,|B|=1,|P(AB)|=4.则A到B的二元关系共有4个:R1=,R2=,R3=,R4=,.B到A的二元关系也有4个:R5=,R6=,R7=,R8=,.23A上的二元关系的数目nA上的二元关系:是AA的任意子集 R是A上的二元关系RAA RP(AA)n若|A|=m,则|AA|=m2,故|P(AA)|=即A上不同的二元关系共有 个24A上的二元关系(例1)n例1:设 A=a1,a2,则A上的二元关系共有16个:AA=,R1=,R2=,R3=,R4=,R5=,25A上的二元关系(例1,续1)R6 =,R7 =,R8

12、=,R9 =,R10 =,R11 =,26A上的二元关系(例1,续2)R12=,R13=,R14=,R15=,R16=,.说明：要求一个集合A上的所有二元关系，相当于求P(AA)。271.关系中的元素是有序对，有序对内第一元素与第二元素之间是有序的，但有序对之间是无序的。2.关系就是笛卡儿积的子集。一般我们讨论二元关系。3.关系肯定是集合，但集合不一定是关系。二元关系的几点注意：28一些特殊关系n空关系n恒等关系n全域关系n整除关系n小于等于关系,n包含关系,n真包含关系29特殊关系1设A是任意集合,则可以定义A上的:n空关系:空集为n(2)元空关系n全(域)关系:若一个n元关系R本身是笛卡尔

13、积A1A2An,则称R为全(域)关系。EA=AA=|xA 且 yA30特殊关系(续)n恒等关系:设关系IA是A上的二元关系并且IA=|xA n特征：恒等关系的有序对中，第一元素和第二元素相等。例：A=1,2,3,则IA=,31特殊关系2设AZ,则可以定义A上的整除关系DA:n整除关系:x|y:读作x整除yDA=|xA 且 yA 且 x|y 例:A=1,2,3,4,5,6,则 DA=,.32特殊关系3设AR,则可以定义A上的:n小于等于(less than or equal to)关系:LEA=|xA,yA 且 xy n小于(less than)关系,LA=|xA，yA且 xy n大于等于(gr

14、eater than or equal to)关系GEA=|xA，yA 且 x=yn大于(greater than)关系,GA=|xA，yA且 xy 33特殊关系3（举例）令A=1,3,5,nA上的小于等于关系为:,nA上的小于(less than)关系,nA上的大于等于(greater than or equal to)关系,nA上的大于(greater than)关系,注意：要列出所有满足该关系的有序对34特殊关系4设A为任意集合,则可以定义P(A)上的:n包含关系:A=|xA,yA 且 xyn真包含关系:A=|xA,yA 且 xy35与二元关系有关的概念n前域（定义域）,值域,域36前域

15、（定义域）,值域,域对任意关系R，设为R中任意一个序偶，定义:nR的前域(domain)（定义域）:所有x组成的集合dom R=x|存在y，满足：xRy)nR的值域(range):所有y组成的集合ran R=y|存在x，满足：xRy)nR的域(field):所有x与所有y组成的集合fld R=dom R ran R37定义域,值域,域(举例)设A=1,2,3,4,5,6,B=a,b,c,d,A到 B的 关 系 R=2,a,2,b,3,b,4,d,6,d,则 dom R=2,3,4,6,ran R=a,b,d。382.4 关系表示法关系的表示方法:n 集合n 表格n 矩阵(关系矩阵)n 图形(关

16、系图)39集合表示法n例如：R=(2,a),(3,b),(4,d),(6,d)DA=(x,y)|xA 且 yA 且 x|y 40表格表示法n设有集合A=a1,a2,am、B=b1,b2,bn，|A|=m,|B|=n,R为A到B的二元关系，R的表格表示为：绘制一个nm行的表格，将A中的元素顺序标记在横行的左方，将B中的元素顺序标记在竖行的上方，则第i行第j列的方格表示有序对。nm个表格恰好表示了AB中的有所有序对。n当ap与bqR相关(具有关系R)时，则在表格的第p行和第q列的方格上填写标记。41表格表示法举例nA=1,2,3,4，B=a,b,c,d,R为A到B的二元关系，并且 R=,，R的表格

17、表示为：a b c d1 2 3 442关系矩阵(matrix)n设 A=x1,x2,xn,B=y1,y2,ym,RAB,则R的关系矩阵 M(R)=(rij)nm,满足：n例：设A=a,b,c,B=1,2,3,4 R1是A上的二元关系，R2是A到B的二元关系,并且 R1=,R2=,则 M(R1)和M(R1)分别为：43图形(graph)n设 A=a1,a2,an,B=b1,b2,bm,RAB,若A和B中的每个元素用一个“”表示(称为顶点),R中的每个有序对用一条从顶点ai指向顶点bj的有向边表示,这样得到的图称为R的图形（关系图）G(R).n例：设A=a,b,c,B=1,2 A上的关系R1和A到B的关系R2分别为：R1=,R2=,请画出G(R1)和G(R2)。abG(R1)ccbaG(R2)2144关系矩阵,图形(讨论)n当A和B中元素标定次序后,RAB的集合表达式,矩阵,图形三者均可以唯一互相确定。n对于RAB,|A|=n,|B|=m,关系矩阵M(R)是nm阶的,关系图G(R)中的边都是从A中元素指向B中元素的.45重点掌握：理解关系的概念，掌握关系的数学定义。关系的四种表示方法和不同表示方法之间的转换46练习nP24：7、9、11、1447作业nP24：2、848