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

1、2021/4/22021/4/21 12022-3-812021/4/22021/4/22 23-4 序偶与笛卡尔积 一、序偶一、序偶二、笛卡尔积。二、笛卡尔积。2021/4/22021/4/23 31.1.定义定义 两个元素两个元素x,yx,y按给定顺序组成的按给定顺序组成的2 2元组称为一个元组称为一个序偶（有序对），序偶（有序对），记作记作xy: :其中其中x x是它的第一元是它的第一元素，素， y y是它的第二元素。是它的第二元素。序偶主要用来表示两个个体之间的联系序偶主要用来表示两个个体之间的联系例：平面直角坐标系中的一个点的坐标就构成为一个有序例：平面直角坐标系中的一个点的坐标就构

2、成为一个有序序偶，我们可用序偶，我们可用xy表示。表示。，一、序偶一、序偶( (有序有序2 2元组元组) )2021/4/22021/4/24 42.2.序偶的性质序偶的性质如果如果xy,xy,则则 两个序偶相等，两个序偶相等，x=v，当且仅当，当且仅当x=ux=u且且y=vy=v。注：序偶是有次序的。序偶是有次序的。例：和是表示平面上两个不同的点，这与集这与集合不同合不同，1，3和3，1是两个相等的集合。序偶中的两个元素可以相等序偶中的两个元素可以相等例：代表一个序偶，而在集合中在集合中xx，xx与与xx相同相同。序偶的概念可以扩展到三元组的情况序偶的概念可以扩展到三元组的情况一、序偶一、序

3、偶( (有序有序2 2元组元组) )2021/4/22021/4/25 53.3.有序元组有序元组: x: y，z=z4.4.有序有序n n元组：元组： ,x,xn n= x = = 的充的充要条件是要条件是x xi i=y=yi i，i=1i=1，2 2，n n。注注N N元组的第一个分量应该是元组的第一个分量应该是n-1n-1元组元组 ,x,x3 3 = =x xx1 1, , 序偶中的两个元素可以来自不同集合序偶中的两个元素可以来自不同集合 例：例： 表示牛要喝水表示牛要喝水因此任给两个集合因此任给两个集合A A和和B B，我们可以定义一种序偶，我们可以定义一种序偶的集合。的集合。 一、

4、序偶一、序偶2021/4/22021/4/26 61.1.定义：定义：设设A A和和B B是任意两个集合，由是任意两个集合，由A A中元素作第一中元素作第一元素，元素，B B中元素作第二元素构成序偶，中元素作第二元素构成序偶，所有这样序偶的所有这样序偶的集合集合称集合称集合A A和和B B的笛卡尔积的笛卡尔积或或直积直积。记作。记作A A B B。即。即AB=|xAyB二、笛卡尔积二、笛卡尔积所以所以A A B B表示：表示：来自来自A A的元素的元素与与来自来自B B的元素的元素所所构成的构成的所有序偶所有序偶的集合的集合2021/4/22021/4/27 7例题例题 若若A= ， ，B=1

5、，2，3，求求A B， B A， A A， B B以及以及(A B) (B A)。解：A B=, B A=, A A=,B B=, (AB)(BA)=注意：注意：1）若A、B均是有限集，|A|=m，|B|=n，则|AB|=mn2）一般， A B与与B A不相等不相等，即集合的笛卡尔积运算不满足交换不满足交换律律。反例反例: A=1, B=2.AB=, BA=.二、笛卡尔积二、笛卡尔积约定：若约定：若A=或或B=，则，则A B= ，B A=2021/4/22021/4/28 82.n2.n个集合的笛卡尔积个集合的笛卡尔积：集合A1，A2，An，则特别地，二、笛卡尔积二、笛卡尔积2021/4/22

6、021/4/29 9例：设A，B，C，D是任意集合，判断下列命题是否正确？(1)A B A CB C不正确，当不正确，当A，B C时，AB=AC=。(2)A-(B C)=(A-B) (A-C)不正确不正确，当A=B=1，C=2时，A-(BC)=1-=1，而(A-B)(A-C)=1=。(3)A=C，B=DA B=C D正确正确，由定义可以证明，在非空前提下是充要条件在非空前提下是充要条件。(4)存在集合存在集合A使得使得A A A正确正确，当A=时，AAA。(5)(A B) C = A (B C)错。错。当A=B=C=1. (AB)C=,1, A(BC)=1,. (除非 A= B= C=)二、笛

7、卡尔积二、笛卡尔积设x A,y B,所以 ABA=C,B=D,所以x C,y D 所以 CD得证不满足结合律不满足结合律2021/4/22021/4/210103 3、笛卡尔积的性质、笛卡尔积的性质对于任意集合对于任意集合A A，A A= =， A=A= 。笛卡尔积运算笛卡尔积运算不满足交换律不满足交换律，当，当A A，B B，A A B B时时A A B B B B A A。笛卡尔积运算不笛卡尔积运算不满足结合律满足结合律，即当，即当A A，B B，C C均非均非空时空时(A(A B)B) C C A A (B(B C)C)。 二、笛卡尔积二、笛卡尔积2021/4/22021/4/21111

8、定理定理1 1：对任意三个集合对任意三个集合A、B、C，有，有(a)A (B C)=(A B) (A C) (b)A (B C)=(A B) (A C)(c)(B C) A=(B A) (C A) (d)(B C) A=(B A) (C A)由以上两条有：由以上两条有：A (B C) (A B) (A C)证明两个证明两个集合相等，集合相等，可以证明可以证明它们互相它们互相包含。包含。则则a A，b B C，即，即a A，b B，且，且b C，证明：证明：(b) A (B C)，即即 A B且且 A C，有有 (A B) (A C)，得，得A (B C) (A B) (A C) (A B) (

9、A C)，则则 A B且且 A C，则则a A，b B，且，且a A，b C，则，则b B C。所以所以 A (B C)，所以，所以(A B) (A C) A (B C)二、笛卡尔积二、笛卡尔积2021/4/22021/4/21212定理定理2 2：对于任意集合对于任意集合A A、B B、C C，若，若C C，则，则1)A1)A B B A A C C B B C C2)A2)A B B C C A A C C B B证明：1) 设xA，因C ，设y C ， 有AC，因为AB，xB 所以BC,所以A A C C B B C C 设AC，则xA，yC， 又因ACBC ，所以 BC ，所以 xB,

10、 y C，所以AB同样，定理的第二部分同样，定理的第二部分A B C A C B可以类似地可以类似地证明。证明。二、笛卡尔积二、笛卡尔积2021/4/22021/4/21313定理定理3 3：对任意四个非空集合，：对任意四个非空集合，A A B B C C D D的充的充分必要条件是分必要条件是A A C C，B B D D。证明：充分性。设AC，BD。由定理由定理2，因BD，A，所以A B A D。 又AC，D ，所以A D C D，所以所以A B C D。必要性。设 ABCD。 x A，y B，所以AB，又因ABCD，所以CD，所以xC，y D，所以所以A C，B D证明定理证明定理3用到

11、集合包含的用到集合包含的传递性：传递性： (A B)(B C) (A C)二、笛卡尔积二、笛卡尔积2021/4/22021/4/21414练习练习105页页(2)-(5)2021/4/22021/4/21515105页（2）设A=a,b，构成集合 P(A)A。解 P(A)=,a,b,a,bP(A)A=,2021/4/22021/4/21616105页（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 =(A

12、C) (BC)2021/4/22021/4/21717a)(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)2021/4/22021/4/21818b)(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)2021/4/2

13、2021/4/21919c)(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)2021/4/22021/4/22020d)(A - B) C =(AC) - (BC)成立.证明 因为(A - B) C =|(xA-B)yC所以 (A - B) C x(A-B)yC xAx ByCxAyCx B) (xAyCy C) xAyC(x ByC) xAyC (x B y C)A C B C (AC) - (BC)2021/4/22

14、021/4/22121e)(AB) C =(AC) (BC)成立。证明 (AB) C =(A-B)(B-A) C=(A-B) C(B-A) C=(A C）-（B C）(B C）-（A C）=(AC) (BC)（定理（定理1c)）d)(A - B) C =(A C) - (B C)2021/4/22021/4/22222105页（4）证明：若XX=YY，则X=Y。提示：证明XY且YX证明：设任意x X，则 XX，因为 XX=YY YY，x Y，所以XY。同理可证YX。故X=Y2021/4/22021/4/22323105页（5）证明：若XY=XZ，且X，则Y=Z。证明：若Y=，则XY=，从而XZ

15、=， 即Z=，所以Y=Z。 若Y，设任意yY，因为X， 令aX，则 XY，即XZ，故y Z，所以Y Y Z Z。同理可证ZY。即Y=Z 2021/4/22021/4/22424作业1.证明：证明：A B=B A(A=)(B=)(A=B)。2021/4/22021/4/225252022-3-8252021/4/22021/4/22626一、二元关系一、二元关系二、几个特殊的二元关系二、几个特殊的二元关系三、关系的运算三、关系的运算四、二元关系的表示四、二元关系的表示3-5关系及其表示2021/4/22021/4/227273-5关系及其表示关系举例：关系举例：1）兄弟关系、长幼关系、同学关系、

16、邻居关系，上下级关系等。2）在数学上有大于关系、小于关系，整除关系。例如：“3小于5”，“x大于y”， “点a在b与c之间”我们知道序偶可以表达两个客体、三个客体或n个客体之间的联系，因此用序偶表达这个概念是非常自然的。一、二元关系一、二元关系2021/4/22021/4/22828例如：火车票与座位之间有对号关系。设X表示火车票的集合，Y表示座位的集合，则对于任意的 xX 和 y Y，必定有 x x 与与y y有有“对号对号”关系关系 x x 与与y y没有没有“对号对号”关系关系。二者之一令 R R表示表示“对号对号”关系，则上述问题可以表示为 xRyxRy 或 xRy xRy 。 亦可表

17、示为 R 或 R，因此我们看到对号关系是一个序偶的集合因此我们看到对号关系是一个序偶的集合。2021/4/22021/4/229291.1.二元关系定义二元关系定义1 1任一序偶的集合称为一个二元关系，简称关系，记任一序偶的集合称为一个二元关系，简称关系，记作作R R。如果如果 R,可记作：可记作：aRb，称为，称为a与与b有关系有关系R；如果如果 R,可记作：可记作：aRb，称为，称为a与与b没有关系没有关系R；这种记法称为中缀记法中缀记法。例：R=,则中缀记法为：aR1, bR2, bR2,a一、二元关系一、二元关系2021/4/22021/4/23030例1: 在自然数中关系“”可记作

18、R =“”=|x,yN且x y。 R,即3R2，读作“3大于2”例2: R1=, R1是二元关系. 例3: A=,a,1 A不是关系. 说明：1）我们把关系R这种无形的联系同集合这种“有形”的实体来描述，在今后的描述和论证带来方便2）有序对是讲究次序的，如R未必有R，即a与b有关系R,b与a有关系R.例：甲与乙有父与子的关系，则乙与甲肯定没有父与子的关系。一、二元关系一、二元关系2021/4/22021/4/231312.2.二元关系定义二元关系定义2 2A A B B的任何子集的任何子集R R称为称为A A到到B B的二元关系的二元关系。R R是是A A到到B B的二元关系的二元关系 R R

19、 A A B B R R P (AP (A B)B)（幂集）（幂集）若若|A|=m, |B|=n, |A|=m, |B|=n, 则则|A|A B|= mn , B|= mn , 故故|P (A|P (A B)|B)|=2mn，即即A A到到B B不同的二元关系共不同的二元关系共有有2mn个个一、二元关系一、二元关系2021/4/22021/4/232323.3.二元关系定义二元关系定义3 3A A上的二元关系：上的二元关系： A A A A的任意子集的任意子集R R称为称为A A上的二元关系上的二元关系 R R A A A A R R P (A(A A)A)。若若|A|=m, |A|=m, 则

20、则|A|A A|=mA|=m2 2, 故故| |P (A(A A)|= 2 A)|= 2 m m2 2 ，即，即A A上不上不同的二元关系共有同的二元关系共有2 2 m m2 2个。个。一、二元关系一、二元关系2021/4/22021/4/23333A A到到B B的二元关系举例的二元关系举例1: 1: 设 A=a1,a2, B=b, 则A到B的二元关系共有221=4个: R1=, R2=, R3=, R4=,B到A的二元关系也有4个: R5=, R6=, R7=, R8=,。 一、二元关系一、二元关系2021/4/22021/4/23434A A到到B B的二元关系举例的二元关系举例2: 2

21、: 设 A=a,b,c,d,e,f，为学生集合 B=,为课程集合, 则定义如下三个二元关系: R1=,可以是一个从A到B的选课关系； R2=,为一个A上的二元关系，可表示上下铺关系； R3=,为一个B上的二元关系，可表示先修课关系。 一、二元关系一、二元关系2021/4/22021/4/23535A A上的二元关系上的二元关系( (举例举例) )例1: 设 A=a1,a2, 则A上的二元关系共有16个: R1 = , R2 = , R3 = , R4 = , R5 = , R6 = , , R7 = , , R8 = , ,一、二元关系一、二元关系2021/4/22021/4/23636R9

22、= , ,R10 = , ,R11 = , , R12 = , ，R13 = , ，R14 = , , ，R15 = , ，R16 = , 一、二元关系一、二元关系2021/4/22021/4/23737例2: 设 B=b, 则B上的二元关系共有2个: R1=, R2=. 例3: 设 C=a,b,c, 则C上的二元关系共有29=512个! 一、二元关系一、二元关系A上的二元关系上的二元关系(举例举例)2021/4/22021/4/238384.4.前域和值域前域和值域定义：关系R中所有序偶的： 第一元素的集合称为关系R的前域记作Dom（R） 第二元素的集合称为关系R的前域记作Ran（R） 如果

23、R是A到B的关系，则D(R) A,R(R) B R的前域和值域一起称作R的域，记作FLDR。一、二元关系一、二元关系2021/4/22021/4/239394.4.前域和值域前域和值域例: A=a,b,c, B=1,2,3 R1=, 是A到B上的一个关系R2=,是B上的一个关系写出这两个关系的前域和值域D(R1)=a,b A, R(R1) =1,2,3 BD(R2)=1,2 B, R(R2) =1, 3 B一、二元关系一、二元关系2021/4/22021/4/240404.4.前域和值域前域和值域P106例题例题1 设A=1，2，3，5，B=1，2，4， H=， 求dom H，ran H， F

24、LD H。 解： dom H=1，2，3，ran H=2，4， FLD H=1，2，3，4 P107例题例题2 设X=1，2，3，4，求X上的关系及dom ，ran 。解：=， ，dom =2，3，4，ran =1，2，3一、二元关系一、二元关系2021/4/22021/4/24141二、几个特殊的二元关系二、几个特殊的二元关系设设A A是任意集合，是任意集合，1.1.称为称为A A上的上的空关系空关系2.I2.IA A = | a = | a A A 称为称为A A上的上的恒等关系恒等关系3.U3.UA A = A= A A = | xA = | x A A y y AA称为称为A A上上的

25、的全域关系全域关系例如：设集合例如：设集合A=0,1,2A=0,1,2U UA A=,2,=,2,是是A A上的全关系上的全关系I IA A=,=,是是A A上的恒等关系上的恒等关系|U|UA A|=|A|=|A A A|=9,| I|=9,| IA A |=|A|=3|=|A|=32021/4/22021/4/24242P107例题例题3 若H=f，m，s，d表示一个家庭的父、母、子、女，确定H上的全域关系和空关系，另外再确定H上的一个关系，指出该关系的值域和前域。解：设H上的同一家庭成员的关系为H1，H上的互不相识的关系为H2，则H1为全域关系，为H2空关系，设H上的长幼关系为H3 ， H

26、3=，dom H3=f，m，ran H3=s，d二、几个特殊的二元关系二、几个特殊的二元关系2021/4/22021/4/24343三、关系的运算三、关系的运算定理：若定理：若Z Z和和S S是从集合是从集合X X到集合到集合Y Y的两个关的两个关系，则系，则Z Z和和S S的并、交、补、差仍是的并、交、补、差仍是X X到到Y Y的关系的关系。证明见书证明见书108108页。页。2021/4/22021/4/24444解：H=， ，S=HS=， ，HS=XX=， ，H=， ，S-H=P107例题例题4 设设X=1，2，3，4，若，若H=|(x-y)/2是整是整数数，S=|(x-y)/3是正整数

27、是正整数，求，求H S，H S， H，S-H。2021/4/22021/4/24545四、二元关系的表示四、二元关系的表示1.序偶集合的形式表达序偶集合的形式表达为直观地表示A到B的关系,我们采用如下的图示:用大圆圈表示集合A和B,里面的小圆圈表示集合中的元素;若aA,bB,且(a,b),则在图示中将表示a和b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。2021/4/22021/4/24646此例中的1和2的图示如图1所示。例例 设设A A1,2,3,4,51,2,3,4,5, ,B Ba a, ,b,cb,c, ,则则1 1(1,(1,a a),(1,),(1,b b),

28、(2,),(2,b b),(3,),(3,a a) )是是A A到到B B的关系的关系, ,而而2 2( (a a,2),(,2),(c c,4),(,4),(c c,5),5)是是B B到到A A的关系。的关系。其集合表示法如下：其集合表示法如下：2021/4/22021/4/24747图图1 上例用图上例用图 2021/4/22021/4/24848四、二元关系的表示四、二元关系的表示2关系矩阵表示法：关系矩阵表示法：设 A=a1,a2,an, B=b1,b2, ,bm,RAB, 则R的关系矩阵 MR=(rij)nm, 其中rij = 1, ai R bj 或 R 0, ai R bj 或

29、 R2021/4/22021/4/24949例题：例如: A=2,3,4,5,6, A上关系R1=|a是b的倍数写出R1的关系矩阵解：1=,MR1 = 1 0 0 0 00 1 0 0 01 0 1 0 00 0 0 1 01 1 0 0 1234562 3 4 5 6说明：说明：1）空关系的关系矩阵）空关系的关系矩阵M的所的所有元素为有元素为02）全关系的关系矩阵）全关系的关系矩阵MU的所的所有元素为有元素为13）恒等关系的关系矩阵）恒等关系的关系矩阵MI的的所有对角元素为所有对角元素为1其他均为其他均为0，称为单位矩阵，记作称为单位矩阵，记作I.2021/4/22021/4/2505010

30、8页例题例题5 设X=x1,x2,x3,x4,Y=y1,y2,y3,R=, , , , , , ，写出关系矩阵MR。例题6 设A=1,2,3,4，写出集合A上大于关系的关系矩阵。2021/4/22021/4/251513.关系图表示法：关系图表示法：A=a1,a2,an，B=b1,b2,bn ，RAB,1）首先在平面上做结点a1,a2,an ，b1,b2,bn以“”表示(称为顶点)， 2）若aiRbj ，则从结点ai向结点bj画有向边，箭头指向bj，若aiRbj , 则ai与bj之间没有线段连接，这样得到的图称为R的关系图 GR 。P109 例题7四、二元关系的表示四、二元关系的表示2021/4/22021/4/25252四、二元关系的表示四、二元关系的表示3.关系图表示法：关系图表示法：109109页例题页例题7 7 设设X=xX=x1 1,x,x2 2,x,x3 3,x,x4 4,Y=y,Y=y1 1,y,y2 2,y,y3 3,R=xR=, , , , , , , , x, , , , ，画出，画出R R的关系图的关系图。2021/4/22021/4/25353abcGR2abcGR13.关系图表示法关系图表示法：定义在集合定义在集合A上的关系图有所