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

1,第2章 关 系（第一部分）,2,内容提要:,1.关系的定义、有序对与笛卡尔积 2.二元关系概念及其表示方法 3.二元关系的基本类型与判定方法,3,2.1 关系(Relation)和有序对(ordered pair),宇宙中存在着形形色色的关系,人与人之间：父子关系、师生关系、同学关系 数之间：大小关系、平方关系、整除关系、集合之间：包含关系、真包含关系、相等关系集合论为刻划这种联系提供了一种数学模型:关系。关系是一个集合,以具有该种联系的事物对为其成员。因而在关系的研究中可方便地使用集合论的概念、方法和成果。,4,定义：由两个具有固定次序的个体组成的序列,称为序偶(ordered pair),记作或(a,b)。其中,a是第一元素,b是第二元素.有序，即：ab(a,b)(b,a)（区别于集合元素的无序性）相等：(a,b)=(c,d)a=c 且 b=d(a,a)可为有序对（区别于集合的元素不重复）,有序对(ordered pair),5,定义：有序对的集合称为二元关系；令A1,2,3,4,，A元素间的小于关系为：(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),二元关系(binary relation),6,有序n元组(n-tuple),定义：由n个具有给定次序的个体a1,a2,an 组成的序列,称为有序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元关系。,7,2.2 笛卡尔积(Cartesian product),笛卡尔积也叫卡氏积，是一种重要的集合运算,是向量概念的推广,也是数据库重要术语“元组”的基础。定义：设A1,A2,An是任意的n个集合,所有有序n元组(a1,a2,an)组成的集合,称为集合A1,A2,An 的笛卡尔积,并用A1 A2 An 表示。其中 ai Ai(i=1,2,n)。即 A1A2An=(a1,a2,an)|aiAi,i=1,2,n注意：（1）可表示不含任何有序组的笛卡尔积。（2）若Ai=，则A1A2An=,8,笛卡尔积(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)特别地：n=2时，只有2个集合参与运算，称作二维笛卡尔积。,9,二维笛卡尔积的性质,非交换:AB BA(除非 A=B 或 A=或 B=)非结合:(AB)C A(BC)(除非 A=或 B=或 C=)分配律:A(BC)=(AB)(AC)A(BC)=(AB)(AC)其他:AB=A=或 B=注意：笛卡尔积的性质具有明显的矢量特征。,10,笛卡尔积非交换性,非交换:AB BA(除非 A=B 或 A=或 B=)反例:A=1,B=2.AB=(1,2),BA=(2,1).,11,笛卡尔积非结合性,非结合:(AB)C A(BC)(除非 A=或 B=或 C=)反例:A=B=C=1.(AB)C=(1,1),1),A(BC)=(1,(1,1).,12,笛卡尔积的分配律(证明),证明：A(BC)=(AB)(AC)proof:对于任意的 x,y A(BC)xA 并且 y(BC)/*卡氏积定义的逆运用*/xA 并且(yB 且 yC)(xA 且 yB)并且(xA 且 yC)(x,y)AB 并且 x,yAC/*卡氏积定义*/x,y(AB)(AC)。,13,笛卡尔积分配律,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)另外7个公式可类似地证明。,14,例题1,设A,B,C,D是任意集合,判断下列结论是否正确AB=A=或 B=若A,则 ABAC BC.AC 且 BD ABCD,ABCD AC 且 BDAnswer：(1)(2)(3)正确。(4)仅当(A=B=)或(A 且 B)时,ABCD AC 且 BD成立,15,例题1(证明(2),(2)若A,则ABAC BC.证明:()若 B=,显然，BC.若 B,对于任意 yB 由A,任选 xA(x,y)AB(x,y)AC xA 且 yC yC.BC,16,例题1(证明(2),续),(2)若A,则ABAC BC.证明(续):()若 B=,则AB=AC成立.若 B.任选AB xA且yB xA且yC AC ABAC.注意:在()中不需要条件 A.,17,例题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。,18,n维笛卡尔积(性质),非交换:ABCBCA(要求A,B,C均非空,且互不相等)非结合:(AB)CA(BC)分配律:例如AB(CD)=(ABC)(ABD)其他:如 ABC=A=或 B=或 C=.,19,2.3 关系问题的再定义,定义：笛卡尔积A1 A2 An 的任意一个子集R称为A1,A2,An 上的一个n元关系。特别地,A1 A2的任意一个子集称A1到A2的一个二元关系。A1 A1的任意一个子集称A1上的一个二元关系。二元关系主要是描述两个集合之间元素与元素的关系或者是一个集合内部元素之间的关系。,20,二元关系判别,二元关系(简称关系):是集合,其元素全是有序对.例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 Answer：R1、R2和R3是二元关系，R4不是关系。,21,二元关系的记号,设R是二元关系,则(x,y)R x与y具有R关系(x与yR相关)x R y对比:x R y(中缀(infix)记号)R(x,y)(前缀(prefix)记号)(x,y)R(后缀(suffix)记号)例如:215(2,15)（2,15）,注意：x R y 称作x与y不具有关系R。,22,A到B的二元关系的数目,若R是A到B的二元关系 RP(AB)若|A|=m,|B|=n,A到B不同的二元关系共有几个？AB中有序对数目：|AB|=m*n,故|P(AB)|=2m*n 即A到B不同的二元关系共有2m*n个,23,A到B的二元关系(举例),例:设 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=,.,24,A上的二元关系的数目,A上的二元关系:是AA的任意子集 R是A上的二元关系RAA RP(AA)若|A|=m,则|AA|=m2,故|P(AA)|=即A上不同的二元关系共有 个,25,A上的二元关系(例1),例1:设 A=a1,a2,则A上的二元关系共有16个:AA=,R1=,R2=,R3=,R4=,R5=,26,A上的二元关系(例1,续1),R6=,R7=,R8=,R9=,R10=,R11=,27,A上的二元关系(例1,续2),R12=,R13=,R14=,R15=,R16=,.说明：要求一个集合A上的所有二元关系，相当于求P(AA)。,28,1.关系中的元素是有序对，有序对内第一元素与第二元素之间是有序的，但有序对之间是无序的。2.关系就是笛卡儿积的子集。一般我们讨论二元关系。3.关系肯定是集合，但集合不一定是关系。,二元关系的几点注意：,29,一些特殊关系,空关系恒等关系全域关系整除关系小于等于关系,包含关系,真包含关系,30,特殊关系1,设A是任意集合,则可以定义A上的:空关系:空集为n(2)元空关系全(域)关系:若一个n元关系R本身是笛卡尔积A1A2An,则称R为全(域)关系。EA=AA=|xA 且 yA,31,特殊关系(续),恒等关系:设关系IA是A上的二元关系并且IA=|xA 特征：恒等关系的有序对中，第一元素和第二元素相等。例：A=1,2,3,则IA=,32,特殊关系2,设AZ,则可以定义A上的整除关系DA:整除关系:x|y:读作x整除yDA=|xA 且 yA 且 x|y 例:A=1,2,3,4,5,6,则 DA=,.,33,特殊关系3,设AR,则可以定义A上的:小于等于(less than or equal to)关系:LEA=|xA,yA 且 xy 小于(less than)关系,LA=|xA，yA且 x|xA，yA 且 x=y大于(greater than)关系,GA=|xA，yA且 xy,34,特殊关系3（举例）,令A=1,3,5,A上的小于等于关系为:,A上的小于(less than)关系,A上的大于等于(greater than or equal to)关系,A上的大于(greater than)关系,注意：要列出所有满足该关系的有序对,35,特殊关系4,设A为任意集合,则可以定义P(A)上的:包含关系:A=|xA,yA 且 xy真包含关系:A=|xA,yA 且 xy,36,与二元关系有关的概念,前域（定义域）,值域,域,37,前域（定义域）,值域,域,对任意关系R，设为R中任意一个序偶，定义:R的前域(domain)（定义域）:所有x组成的集合dom R=x|存在y，满足：xRy)R的值域(range):所有y组成的集合ran R=y|存在x，满足：xRy)R的域(field):所有x与所有y组成的集合fld R=dom R ran R,38,定义域,值域,域(举例),设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。,39,2.4 关系表示法,关系的表示方法:集合 表格 矩阵(关系矩阵)图形(关系图),40,集合表示法,例如：R=(2,a),(3,b),(4,d),(6,d)DA=(x,y)|xA 且 yA 且 x|y,41,表格表示法,设有集合A=a1,a2,am、B=b1,b2,bn，|A|=m,|B|=n,R为A到B的二元关系，R的表格表示为：绘制一个nm行的表格，将A中的元素顺序标记在横行的左方，将B中的元素顺序标记在竖行的上方，则第i行第j列的方格表示有序对。nm个表格恰好表示了AB中的有所有序对。当ap与bqR相关(具有关系R)时，则在表格的第p行和第q列的方格上填写标记。,42,表格表示法举例,A=1,2,3,4，B=a,b,c,d,R为A到B的二元关系，并且 R=,，R的表格表示为：,a b c d,1 2 3 4,43,关系矩阵(matrix),设 A=x1,x2,xn,B=y1,y2,ym,RAB,则R的关系矩阵 M(R)=(rij)nm,满足：例：设A=a,b,c,B=1,2,3,4 R1是A上的二元关系，R2是A到B的二元关系,并且 R1=,R2=,则 M(R1)和M(R1)分别为：,44,图形(graph),设 A=a1,a2,an,B=b1,b2,bm,RAB,若A和B中的每个元素用一个“”表示(称为顶点),R中的每个有序对用一条从顶点ai指向顶点bj的有向边表示,这样得到的图称为R的图形（关系图）G(R).例：设A=a,b,c,B=1,2 A上的关系R1和A到B的关系R2分别为：R1=,R2=,请画出G(R1)和G(R2)。,45,关系矩阵,图形(讨论),当A和B中元素标定次序后,RAB的集合表达式,矩阵,图形三者均可以唯一互相确定。对于RAB,|A|=n,|B|=m,关系矩阵M(R)是nm阶的,关系图G(R)中的边都是从A中元素指向B中元素的.,46,重点掌握：,理解关系的概念，掌握关系的数学定义。关系的四种表示方法和不同表示方法之间的转换,47,练习,P24：7、9、11、14,48,作业,P24：2、8,