离散数学课件3.4序偶与笛卡尔积-3.5关系及其表示

2020/4/30,1,离散数学(DiscreteMathematics),2020/4/30,1,3-4序偶与笛卡尔积,一、序偶二、笛卡尔积。,1.定义两个元素x,y按给定顺序组成的2元组称为一个序偶（有序对），记作:其中x是它的第一元素，y是它的第二元素。序偶主要用来表示两个个体之间的联系例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们可用表示。，,一、序偶(有序2元组),2.序偶的性质如果xy,则两个序偶相等，=，当且仅当x=u且y=v。注：序偶是有次序的。例：和是表示平面上两个不同的点，这与集合不同，1，3和3，1是两个相等的集合。序偶中的两个元素可以相等例：代表一个序偶，而在集合中x，x与x相同。序偶的概念可以扩展到三元组的情况,一、序偶(有序2元组),3.有序元组:，z=4.有序n元组：,xn=的充要条件是xi=yi，i=1，2，n。注N元组的第一个分量应该是n-1元组,x3=序偶中的两个元素可以来自不同集合例：表示牛要喝水因此任给两个集合A和B，我们可以定义一种序偶的集合。,一、序偶,1.定义：设A和B是任意两个集合，由A中元素作第一元素，B中元素作第二元素构成序偶，所有这样序偶的集合称集合A和B的笛卡尔积或直积。记作AB。即AB=|xAyB,二、笛卡尔积,所以AB表示：来自A的元素与来自B的元素所构成的所有序偶的集合,例题若A=，B=1，2，3，求AB，BA，AA，BB以及(AB)(BA)。解：AB=,BA=,AA=,BB=,(AB)(BA)=注意：1）若A、B均是有限集，|A|=m，|B|=n，则|AB|=mn2）一般，AB与BA不相等，即集合的笛卡尔积运算不满足交换律。反例:A=1,B=2.AB=,BA=.,二、笛卡尔积,约定：若A=或B=，则AB=，BA=,2.n个集合的笛卡尔积：集合A1，A2，An，则特别地，,二、笛卡尔积,例：设A，B，C，D是任意集合，判断下列命题是否正确？(1)ABACBC不正确，当A，BC时，AB=AC=。(2)A-(BC)=(A-B)(A-C)不正确，当A=B=1，C=2时，A-(BC)=1-=1，而(A-B)(A-C)=1=。(3)A=C，B=DAB=CD正确，由定义可以证明，在非空前提下是充要条件。(4)存在集合A使得AAA正确，当A=时，AAA。(5)(AB)C=A(BC)错。当A=B=C=1.(AB)C=,1,A(BC)=.(除非A=B=C=),二、笛卡尔积,设xA,yB,所以ABA=C,B=D,所以xC,yD所以CD得证,不满足结合律,3、笛卡尔积的性质对于任意集合A，A=，A=。笛卡尔积运算不满足交换律，当A，B，AB时ABBA。笛卡尔积运算不满足结合律，即当A，B，C均非空时(AB)CA(BC)。,二、笛卡尔积,定理1：对任意三个集合A、B、C，有(a)A(BC)=(AB)(AC)(b)A(BC)=(AB)(AC)(c)(BC)A=(BA)(CA)(d)(BC)A=(BA)(CA),由以上两条有：A(BC)(AB)(AC),证明两个集合相等，可以证明它们互相包含。,则aA，bBC，即aA，bB，且bC，,证明：(b)A(BC)，,即AB且AC，,有(AB)(AC)，得A(BC)(AB)(AC),(AB)(AC)，,则AB且AC，,则aA，bB，且aA，bC，则bBC。,所以A(BC)，所以(AB)(AC)A(BC),二、笛卡尔积,定理2：对于任意集合A、B、C，若C，则1)ABACBC2)ABCACB证明：1)设xA，因C，设yC，有AC，因为AB，xB所以BC,所以ACBC设AC，则xA，yC，又因ACBC，所以BC，所以xB,yC，所以AB,同样，定理的第二部分ABCACB可以类似地证明。,二、笛卡尔积,定理3：对任意四个非空集合，ABCD的充分必要条件是AC，BD。证明：充分性。设AC，BD。由定理2，因BD，A，所以ABAD。又AC，D，所以ADCD，所以ABCD。必要性。设ABCD。xA，yB，所以AB，又因ABCD，所以CD，所以xC，yD，所以AC，BD,证明定理3用到集合包含的传递性：(AB)(BC)(AC),二、笛卡尔积,练习105页(2)-(5),105页（2）,设A=a,b，构成集合P(A)A。解P(A)=,a,b,a,bP(A)A=,105页（3）,下列各式中哪些成立？哪些不成立？为什么？a)(AB)(CD)=(AC)(BD)b)(A-B)(C-D)=(AC)-(BD)c)(AB)(CD)=(AC)(BD)d)(A-B)C=(AC)-(BC)e)(AB)C=(AC)(BC),a)(AB)(CD)=(AC)(BD)不成立。设A=a，B=b，C=c，D=d，则AB=a，b，CD=c，d，(AB)(CD)=,，AC=，BD=，(AC)(BD)=,故(AB)(CD)(AC)(BD),b)(A-B)(C-D)=(AC)-(BD)不成立。设A=a,e，B=a,b，C=c,f，D=d，则A-B=e，C-D=c，f，(A-B)(C-D)=,，AC=,，BD=,，(AC)-(BD)=,，故(A-B)(C-D)(AC)-(BD),c)(AB)(CD)=(AC)(BD)不成立。设A=a，B=b，C=c，D=d，则AB=a，b，CD=c，d，(AB)(CD)=,，AC=，BD=，(AC)(BD)=,故(AB)(CD)(AC)(BD),d)(A-B)C=(AC)-(BC)成立.证明因为(A-B)C=|(xA-B)yC所以(A-B)Cx(A-B)yCxAxByC(xAyCxB)(xAyCyC)(xAyC)(xByC)(xAyC)(xByC)ACBC(AC)-(BC),e)(AB)C=(AC)(BC)成立。证明(AB)C=(A-B)(B-A)C=(A-B)C(B-A)C=(AC）-（BC）(BC）-（AC）=(AC)(BC),（定理1c)）,d)(A-B)C=(AC)-(BC),105页（4）,证明：若XX=YY，则X=Y。提示：证明XY且YX证明：设任意xX，则XX，因为XX=YYYY，xY，所以XY。同理可证YX。故X=Y,105页（5）,证明：若XY=XZ，且X，则Y=Z。证明：若Y=，则XY=，从而XZ=，即Z=，所以Y=Z。若Y，设任意yY，因为X，令aX，则XY，即XZ，故yZ，所以YZ。同理可证ZY。即Y=Z,作业,1.证明：AB=BA(A=)(B=)(A=B)。,2020/4/30,25,离散数学(DiscreteMathematics),2020/4/30,25,一、二元关系二、几个特殊的二元关系三、关系的运算四、二元关系的表示,2020/4/30,26,3-5关系及其表示,3-5关系及其表示,关系举例：1）兄弟关系、长幼关系、同学关系、邻居关系，上下级关系等。2）在数学上有大于关系、小于关系，整除关系。例如：“3小于5”，“x大于y”，“点a在b与c之间”我们知道序偶可以表达两个客体、三个客体或n个客体之间的联系，因此用序偶表达这个概念是非常自然的。,一、二元关系,例如：火车票与座位之间有对号关系。设X表示火车票的集合，Y表示座位的集合，则对于任意的xX和yY，必定有x与y有“对号”关系x与y没有“对号”关系。二者之一令R表示“对号”关系，则上述问题可以表示为xRy或xRy。亦可表示为R或R，因此我们看到对号关系是一个序偶的集合。,1.二元关系定义1任一序偶的集合称为一个二元关系，简称关系，记作R。如果R,可记作：aRb，称为a与b有关系R；如果R,可记作：aRb，称为a与b没有关系R；这种记法称为中缀记法。例：R=,则中缀记法为：aR1,bR2,bR2,a,一、二元关系,例1:在自然数中关系“”可记作R=“”=|x,yN且xy。R,即3R2，读作“3大于2”例2:R1=,R1是二元关系.例3:A=,a,1A不是关系.说明：1）我们把关系R这种无形的联系同集合这种“有形”的实体来描述，在今后的描述和论证带来方便2）有序对是讲究次序的，如R未必有R，即a与b有关系R,b与a有关系R.例：甲与乙有父与子的关系，则乙与甲肯定没有父与子的关系。,一、二元关系,2.二元关系定义2AB的任何子集R称为A到B的二元关系。R是A到B的二元关系RABRP(AB)（幂集）若|A|=m,|B|=n,则|AB|=mn,故|P(AB)|=2mn，即A到B不同的二元关系共有2mn个,一、二元关系,3.二元关系定义3A上的二元关系：AA的任意子集R称为A上的二元关系RAARP(AA)。若|A|=m,则|AA|=m2,故|P(AA)|=2m2，即A上不同的二元关系共有2m2个。,一、二元关系,A到B的二元关系举例1:设A=a1,a2,B=b,则A到B的二元关系共有221=4个:R1=,R2=,R3=,R4=,B到A的二元关系也有4个:R5=,R6=,R7=,R8=,。,一、二元关系,A到B的二元关系举例2:设A=a,b,c,d,e,f，为学生集合B=,为课程集合,则定义如下三个二元关系:R1=,可以是一个从A到B的选课关系；R2=,为一个A上的二元关系，可表示上下铺关系；R3=,为一个B上的二元关系，可表示先修课关系。,一、二元关系,A上的二元关系(举例)例1:设A=a1,a2,则A上的二元关系共有16个:R1=,R2=,R3=,R4=,R5=,R6=,R7=,R8=,一、二元关系,R9=,R10=,R11=,R12=,，R13=,，R14=,，R15=,，R16=,一、二元关系,例2:设B=b,则B上的二元关系共有2个:R1=,R2=.例3:设C=a,b,c,则C上的二元关系共有29=512个!,一、二元关系,A上的二元关系(举例),4.前域和值域定义：关系R中所有序偶的：第一元素的集合称为关系R的前域记作Dom（R）第二元素的集合称为关系R的前域记作Ran（R）如果R是A到B的关系，则D(R)A,R(R)BR的前域和值域一起称作R的域，记作FLDR。,一、二元关系,4.前域和值域例:A=a,b,c,B=1,2,3R1=,是A到B上的一个关系R2=,是B上的一个关系写出这两个关系的前域和值域D(R1)=a,bA,R(R1)=1,2,3BD(R2)=1,2B,R(R2)=1,3B,一、二元关系,4.前域和值域P106例题1设A=1，2，3，5，B=1，2，4，H=，求domH，ranH，FLDH。解：domH=1，2，3，ranH=2，4，FLDH=1，2，3，4P107例题2设X=1，2，3，4，求X上的关系及dom，ran。解：=，dom=2，3，4，ran=1，2，3,一、二元关系,二、几个特殊的二元关系,设A是任意集合，1.称为A上的空关系2.IA=|aA称为A上的恒等关系3.UA=AA=|xAyA称为A上的全域关系例如：设集合A=0,1,2UA=,是A上的全关系IA=,是A上的恒等关系|UA|=|AA|=9,|IA|=|A|=3,P107例题3若H=f，m，s，d表示一个家庭的父、母、子、女，确定H上的全域关系和空关系，另外再确定H上的一个关系，指出该关系的值域和前域。解：设H上的同一家庭成员的关系为H1，H上的互不相识的关系为H2，则H1为全域关系，为H2空关系，设H上的长幼关系为H3，H3=，domH3=f，m，ranH3=s，d,2020/4/30,42,二、几个特殊的二元关系,三、关系的运算,定理：若Z和S是从集合X到集合Y的两个关系，则Z和S的并、交、补、差仍是X到Y的关系。证明见书108页。,解：H=，S=HS=，HS=XX=，H=，S-H=,P107例题4设X=1，2，3，4，若H=|(x-y)/2是整数，S=|(x-y)/3是正整数，求HS，HS，H，S-H。,四、二元关系的表示,1.序偶集合的形式表达为直观地表示A到B的关系,我们采用如下的图示:用大圆圈表示集合A和B,里面的小圆圈表示集合中的元素;若aA,bB,且(a,b),则在图示中将表示a和b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。,此例中的1和2的图示如图1所示。,例设A1,2,3,4,5,Ba,b,c,则1(1,a),(1,b),(2,b),(3,a)是A到B的关系,而2(a,2),(c,4),(c,5)是B到A的关系。其集合表示法如下：,图1上例用图,四、二元关系的表示,2关系矩阵表示法：设A=a1,a2,an,B=b1,b2,bm,RAB,则R的关系矩阵MR=(rij)nm,其中rij=1,aiRbj或R0,aiRbj或R,例题：例如:A=2,3,4,5,6,A上关系R1=|a是b的倍数写出R1的关系矩阵解：1=,MR1=,说明：1）空关系的关系矩阵M的所有元素为02）全关系的关系矩阵MU的所有元素为13）恒等关系的关系矩阵MI的所有对角元素为1其他均为0，称为单位矩阵，记作I.,108页例题例题5设X=x1,x2,x3,x4,Y=y1,y2,y3,R=,，写出关系矩阵MR。例题6设A=1,2,3,4，写出集合A上大于关系的关系矩阵。,3.关系图表示法：A=a1,a2,an，B=b1,b2,bn，RAB,1