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

离散数学(DiscreteMathematics)2024/1/312024/1/313-4序偶与笛卡尔积一、序偶二、笛卡尔积。1.定义两个元素x,y按给定顺序组成的2元组称为一个序偶〔有序对〕，记作<x，y>:其中x是它的第一元素，y是它的第二元素。序偶主要用来表示两个个体之间的联系例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们可用<x，y>表示。，一、序偶(有序2元组)2.序偶的性质如果x≠y,那么<x,y>≠<y,x>两个序偶相等，<x，y>=<u，v>，当且仅当x=u且y=v。注：序偶是有次序的。例：<1，3>和<3，1>是表示平面上两个不同的点，这与集合不同，{1，3}和{3，1}是两个相等的集合。序偶中的两个元素可以相等例：<x,x>代表一个序偶，而在集合中{x，x}与{x}相同。序偶的概念可以扩展到三元组的情况一、序偶(有序2元组)3.有序３元组:<<x，y>，z>=<x，y，z>4.有序n元组：

<<x1,x2,…,xn-1>,xn>=<x1,x2,…,xn-1,xn><x1，x2，…，xn-1，xn>=<y1，y2，…，yn-1，yn>的充要条件是xi=yi，i=1，2，…，n。注N元组的第一个分量应该是n-1元组<<x1,x2>,x3>=<x1,x2,x3>≠

<x1,<x2,x3>>序偶中的两个元素可以来自不同集合

例：<牛，水>表示牛要喝水因此任给两个集合A和B，我们可以定义一种序偶的集合。一、序偶1.定义：设A和B是任意两个集合，由A中元素作第一元素，B中元素作第二元素构成序偶，所有这样序偶的集合称集合A和B的笛卡尔积或直积。记作AB。即AB={<x，y>|xA∧yB}二、笛卡尔积所以AB表示：来自A的元素与来自B的元素所构成的所有序偶的集合例题假设A={，}，B={1，2，3}，求AB，BA，AA，BB以及(AB)(BA)。解：AB={<,1>,<,2>,<,3>,<,1>,<,2>,<,3>}BA={<1,>,<1,>,<2,>,<2,>,<3,>,<3,>}AA={<,>,<,>,<,>,<,>}BB={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}(AB)(BA)=注意：1〕假设A、B均是有限集，|A|=m，|B|=n，那么|AB|=mn2〕一般，AB与BA不相等，即集合的笛卡尔积运算不满足交换律。反例:A={1},B={2}.AB={<1,2>},BA={<2,1>}.二、笛卡尔积约定：假设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,2>}={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,1>,1>},A(BC)={<1,<1,1>>}.(除非A=B=C=)二、笛卡尔积设x∈A,y∈B,所以<x,y>∈

A

BA=C,B=D,所以x∈C,y∈D所以<x,y>∈

CD得证不满足结合律3、笛卡尔积的性质对于任意集合A，A=，A=。笛卡尔积运算不满足交换律，当A

，B，AB时A

BBA。笛卡尔积运算不满足结合律，即当A，B，C均非空时(AB)CA(BC)。二、笛卡尔积定理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)证明两个集合相等，可以证明它们互相包含。那么aA，bBC，即aA，bB，且bC，证明：(b)

<a，b>

A

(B

C)，即<a，b>

A

B且<a，b>

A

C，有<a，b>

(A

B)

(A

C)，得A

(B

C)

(A

B)

(A

C)

<a，b>

(A

B)

(A

C)，那么<a，b>AB且<a，b>AC，那么aA，bB，且aA，bC，那么bBC。所以<a，b>

A

(B

C)，所以(A

B)

(A

C)

A

(B

C)二、笛卡尔积定理2：对于任意集合A、B、C，假设C，那么1)ABACBC2)ABCACB证明：1)设xA，因C，设yC，有<x，y>AC，因为AB，xB所以<x，y>BC,所以ACBC设<x，y>AC，那么xA，yC，又因ACBC，所以<x,y>BC，所以xB,yC，所以AB同样，定理的第二局部ABCACB可以类似地证明。二、笛卡尔积定理3：对任意四个非空集合，A

B

C

D的充分必要条件是A

C，B

D。证明：充分性。设A

C，B

D。由定理2，因B

D，A

，所以A

B

A

D。

又A

C，D

，所以A

D

C

D，所以A

B

C

D。必要性。设A

B

C

D。

x

A，y

B，所以<x，y>

A

B，又因A

B

C

D，所以<x，y>

C

D，所以x

C，y

D，所以A

C，B

D证明定理3用到集合包含的传递性：(AB)∧(BC)

(AC)二、笛卡尔积练习105页(2)-(5)105页〔2〕设A={a,b}，构成集合

P(A)

A。解

P(A)={,{a},{b},{a,b}}P(A)

A={<

,a>,<

,b>,<{a},a>,<{a},b>,<{b},a>,<{b},b>,<{a,b},a>,<{a,b},b>,}105页〔3〕以下各式中哪些成立？哪些不成立？为什么？a)(A∪B)(C∪D)=(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)(A∪B)(C∪D)=(AC)∪(BD)不成立。设A={a}，B={b}，C={c}，D={d}，那么A∪B={a，b}，C∪D={c，d}，(A∪B)(C∪D)={<a,c>,<a,d>,<b,c>,<b,d>}，AC={<a,c>}，BD={<b,d>}，(AC)∪(BD)={<a,c>,<b,d>}故(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)={<e,c>,<e,f>}，AC={<a,c>,<a,f>,<e,c>,<e,f>}，BD={<a,d>,<b,d>}，(AC)-(BD)={<a,c>,<a,f>,<e,c>,<e,f>}，故(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)={<a,c>,<a,d>,<b,c>,<b,d>}，AC={<a,c>}，BD={<b,d>}，(AC)(BD)={<a,c>,<b,d>}故(AB)(CD)(AC)(BD)d)(A-B)

C=(A

C)-(BC)成立.证明因为(A-B)

C={<x,y>|(x

A-B)∧y

C}所以

<x,y>

(A-B)

C

x(A-B)∧y

C

x

A∧x

B∧y

C

(x

A∧y

C∧x

B)

∪(x

A∧y

C∧y

C))

(x

A∧y

C)∧(x

B∪y

C)

(x

A∧y

C)∧┐(x

B∧y

C)

<x,y>

A

C∧

<x,y>

B

C

<x,y>

[(A

C)-(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=(A

C)-(BC)105页〔4〕证明：假设XX=YY，那么X=Y。提示：证明XY且YX证明：设任意xX，那么<x,x>XX，因为XX=YY<x,x>YY，xY，所以XY。同理可证YX。故X=Y105页〔5〕证明：假设XY=XZ，且X，那么Y=Z。证明：假设Y=，那么XY=，从而XZ=，即Z=，所以Y=Z。假设Y，设任意yY，因为X，令aX，那么<a,y>XY，即<a,y>XZ，故yZ，所以YZ。同理可证ZY。即Y=Z

作业1.证明：AB=BA(A=)∨(B=)∨(A=B)。离散数学(DiscreteMathematics)2024/1/3252024/1/325一、二元关系二、几个特殊的二元关系三、关系的运算四、二元关系的表示3-5关系及其表示2024/1/3263-5关系及其表示关系举例：1〕兄弟关系、长幼关系、同学关系、邻居关系，上下级关系等。2〕在数学上有大于关系、小于关系，整除关系。例如：“3小于5〞，“x大于y〞，“点a在b与c之间〞我们知道序偶可以表达两个客体、三个客体或n个客体之间的联系，因此用序偶表达这个概念是非常自然的。一、二元关系例如：火车票与座位之间有对号关系。设X表示火车票的集合，Y表示座位的集合，那么对于任意的xX和yY，必定有x与y有“对号〞关系x与y没有“对号〞关系。二者之一令R表示“对号〞关系，那么上述问题可以表示为xRy或xRy。亦可表示为<x,y>R或<x,y>R，因此我们看到对号关系是一个序偶的集合。.1.二元关系定义1任一序偶的集合称为一个二元关系，简称关系，记作R。如果<a,b>R,可记作：aRb，称为a与b有关系R；如果<a,b>R,可记作：aRb，称为a与b没有关系R；这种记法称为中缀记法。例：R={<a,1>,<b,1>,<b,2>}那么中缀记法为：aR1,bR2,bR2,a一、二元关系例1:在自然数中关系“≥〞可记作R=“≥〞={<x,y>|x,yN且x≥y}。<3,2>R,即3R2，读作“3大于2〞例2:R1={<1,2>,<,>,<a,b>}R1是二元关系.例3:A={<a,b>,<1,2,3>,a,1}A不是关系.说明：1〕我们把关系R这种无形的联系同集合这种“有形〞的实体来描述，在今后的描述和论证带来方便2〕有序对是讲究次序的，如<a,b>R未必有<b,a>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的二元关系共有22×1=4个:R1=,R2={<a1,b>},R3={<a2,b>},R4={<a1,b>,<a2,b>}B到A的二元关系也有4个:R5=,R6={<b,a1>},R7={<b,a2>},R8={<b,a1>,<b,a2>}。

一、二元关系A到B的二元关系举例2:设A={a,b,c,d,e,f}，为学生集合B={β,δ,ω}为课程集合,那么定义如下三个二元关系:R1={<a,β>,<a,δ>,<c,ω>,<f,β>}可以是一个从A到B的选课关系；R2={<a,b>,<c,d>,<e,f>}为一个A上的二元关系，可表示上下铺关系；R3={<β,δ>,<δ,ω>}为一个B上的二元关系，可表示先修课关系。

一、二元关系A上的二元关系(举例)例1:设A={a1,a2},那么A上的二元关系共有16个:

R1=,R2={<a1,a1>},

R3={<a1,a2>},R4={<a2,a1>},

R5={<a2,a2>},R6={<a1,a1>,<a1,a2>},

R7={<a1,a1>,<a2,a1>},

R8={<a1,a1>,<a2,a2>},一、二元关系R9={<a1,a2>,<a2,a1>},R10={<a1,a2>,<a2,a2>},R11={<a2,a1>,<a2,a2>},R12={<a1,a1>,<a1,a2>,<a2,a1>}，R13={<a1,a1>,<a1,a2>,<a2,a2>}，R14={<a1,a1>,<a2,a1>,<a2,a2>}，R15={<a2,a1>,<a2,a1>,<a2,a2>}，R16={<a1,a1>,<a1,a2>,<a2,a1>,<a2,a2>}一、二元关系例2:设B={b},

那么B上的二元关系共有2个:

R1=,R2={<b,b>}.例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,3}R1={<a,1>,<b,2>,<a,3>}是A到B上的一个关系R2={<1,1>,<2,3>,<1,3>}是B上的一个关系写出这两个关系的前域和值域D(R1)={a,b}A,R(R1)={1,2,3}BD(R2)={1,2}B,R(R2)={1,3}B一、二元关系4.前域和值域P106例题1

设A={1，2，3，5}，B={1，2，4}，H={<1，2>，<1，4>，<2，4>，<3，4>}，求domH，ranH，FLDH。解：domH={1，2，3}，ranH={2，4}，FLDH={1，2，3，4}P107例题2设X={1，2，3，4}，求X上的关系>及dom>，ran>。解：>={<2，1>，<3，1>，<4，1>，

<3，2>，<4，2>，<4，3>}dom>={2，3，4}，ran>={1，2，3}一、二元关系二、几个特殊的二元关系设A是任意集合，1.称为A上的空关系2.IA={<a,a>|a

A}称为A上的恒等关系3.UA=A

A={<x,y>|x

A

y

A}称为A上的全域关系例如：设集合A={0,1,2}UA={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<2,2>},是A上的全关系IA={<0,0>,<1,1>,<2,2>},是A上的恒等关系|UA|=|AA|=9,|IA|=|A|=3P107例题3假设H={f，m，s，d}表示一个家庭的父、母、子、女，确定H上的全域关系和空关系，另外再确定H上的一个关系，指出该关系的值域和前域。解：设H上的同一家庭成员的关系为H1，H上的互不相识的关系为H2，那么H1为全域关系，为H2空关系，设H上的长幼关系为H3，H3={<f，s>，<f，d>，<m，s>，<m，d>}，domH3={f，m}，ranH3={s，d}二、几个特殊的二元关系2024/1/342三、关系的运算定理：假设Z和S是从集合X到集合Y的两个关系，那么Z和S的并、交、补、差仍是X到Y的关系。

证明见书108页。解：H={<1，1>，<1，3>，<2，2>，<2，4>，

<3，3>，<3，1>，<4，4>，<4，2>}S={<4，1>}H

S={<1，1>，<1，3>，<2，2>，<2，4>，<3，3>，

<3，1>，<4，4>，<4，2>，<4，1>}H

S=

XX={<1，1>，<1，2>，<1，3>，<1，4>，<2，1>，

<2，2>，<2，3>，<2，4>，<3，1>，<3，2>，<3，3>，<3，4>，<4，1>，<4，2>，<4，3>，<4，4>}

H={<1，2>，<1，4>，<2，1>，<2，3>，<3，2>，

<3，4>，<4，1>，<4，3>S-H={<4，1>}P107例题4设X={1，2，3，4}，假设H={<x，y>|(x-y)/2是整数}，S={<x，y>|(x-y)/3是正整数}，求HS，HS，H，S-H。四、二元关系的表示1.序偶集合的形式表达为直观地表示A到B的关系,我们采用如下的图示:用大圆圈表示集合A和B,里面的小圆圈表示集合中的元素;假设a∈A,b∈B,且(a,b)∈ρ,那么在图示中将表示a和b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。此例中的ρ1和ρ2的图示如图1所示。例设A＝｛1,2,3,4,5｝,B＝｛a,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或<ai,bj>R

0,aiRbj或<ai,bj>R例题：例如:A={2,3,4,5,6},A上关系R1={<a,b>|a是b的倍数}写出R1的关系矩阵解：1={<2,2>,<3,3>,<4,2>,<4,4>,<5,5>,<6,2>,<6,3>,<6,6>}MR1=

10000010001010000010110012345623456说明：1〕空关系的关系矩阵MΦ的所有元素为02〕全关系的关系矩阵MU的所有元素为13〕恒等关系的关系矩阵MI的所有对角元素为1其他均为0，称为单位矩阵，记作I.108页例题例题5设X={x1,x2,x3,x4},Y={y1,y2,y3},R={<x1,y1>,<x1,y3>,<x2,y2>,<x2,y3>,<x3,y1>,<x4,y1>,<x4,y2>}，写出关系矩阵MR。例题6设A={1,2,3,4}，写出集合A上大于关系>的关系矩阵。3.关系图表示法：A={a1,a2,…,an}，B={b1,b2,…,bn}，RAB,1〕首先在平面上做结点a1,a2,…,an，b1,b2,…,bn以“〞表示(称为顶点)，2〕假设aiRbj，那么从结点ai向结点bj画有向边<ai,bj>，箭头指向bj，假设aiRbj,那么ai与bj之间没有线段连接，这样得到的图称为R的关系图GR。P109例题7四、二元关系的表示四、二元关系的表示3.关系图表示法：109页例题7设X={x1,x2,x3,x4},Y={y1,y2,y3},R={<x1,y1>,<x1,y3>,<x2,y2