离散数学（第3版）课件ch3(2) 集合与关系 3.3-3.5贲

13.1集合的概念和表示法3.2集合的运算3.3有序对与笛卡儿积3.4关系及其表示3.5关系的运算3.6关系的性质3.7关系的闭包3.8集合的划分与覆盖3.9等价关系和等价类3.10相容关系和相容类3.11偏序关系3.12偏序集与哈斯图3.13应用案例第3章集合与关系23.3有序对与笛卡儿积

定义3.10由两个元素x和y（允许x=y）按一定顺序排列成的二元组叫做一个有序对或序偶，记作<x,y>。其中x是它的第一元素，y是它的第二元素。例如，平面直角坐标系中的一个点的坐标就构成为一个有序实数对,用<x,y>表示。3定义3.11设A，B为集合,用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作A×B。笛卡儿积的符号化表示为

A×B={<x,y>|x

A∧yB}。

如果A，B都是有限集，|A|=n，|B|=m，

根据排列组合原理，|A×B|=nm=|A||B|。3.3有序对与笛卡儿积(续)

4

笛卡儿积的运算性质：

(1)对任意集合A，根据定义有A×

＝

,

×A＝

(2)笛卡儿积运算不满足交换律，即

A×B≠B×A(当A≠

∧B≠

∧A≠B时)

(3)笛卡儿积运算不满足结合律，即

(A×B)×C≠A×(B×C)(当A≠

∧B≠

∧C≠

时)

(4)笛卡儿积运算对并和交运算满足分配律，即

A×(B∪C)=(A×B)∪(A×C)(B∪C)×A=(B×A)∪(C×A)

A×(B∩C)=(A×B)∩(A×C)(B∩C)×A=(B×A)∩(C×A)

(5)A

C∧B

D

A×B

C×D5我们给出性质(4)第一个式子的证明。A×(B∪C)=(A×B)∪(A×C)

证明任取<x,y>

<x,y>

A×(B∪C)

x∈A∧y

B∪C

x∈A∧(y

B∨y

C)

(x

A∧y

B)∨(x

A∧y

C)

<x,y>

A×B∨<x,y>

A×C

<x,y>

(A×B∪A×C)

所以有A×(B∪C)＝(A×B)∪(A×C)。6注意性质(5)的逆命题不成立，可分以下情况讨论。①当A＝B＝

时，显然有A

C和B

D成立。

②当A≠

且B≠

时，也有A

C和B

D成立，证明如下：

任取x

A，由于B≠

,必存在y

B,因此有

x∈A∧y

B

<x,y>

A×B

<x,y>

C×D

x

C∧y

D

x

C从而证明了A

C。同理可证B

D。

③当A＝

而B≠

时，有A

C成立，但不一定有B

D成立。反例：令A＝

,B＝{1},C＝{3},D＝{4}。

④当A≠

而B＝

时，有B

D成立，但不一定有A

C成立。(5)A

C∧B

D

A×B

C×D7例3.11

设A＝{1,2},求P(A)×A。例3.12

设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由。

(1)A×B＝A×C

B＝C

(2)A－(B×C)＝(A－B)×(A－C)

(3)A＝B∧C＝D

A×C＝B×D

(4)存在集合A，使得A

A×A

不一定为真不一定为真为真为真83.1集合的概念和表示法3.2集合的运算3.3有序对与笛卡儿积3.4关系及其表示

3.5关系的运算3.6关系的性质3.7关系的闭包3.8集合的划分与覆盖3.9等价关系和等价类3.10相容关系和相容类3.11偏序关系3.12偏序集与哈斯图3.13应用案例第3章集合与关系9定义3.12如果一个集合满足以下条件之一：

(1)集合非空，且它的元素都是有序对。

(2)集合是空集。则称该集合为一个二元关系，记作R。

二元关系也可简称为关系。对于二元关系R，如果<x,y>

R，可记作xRy。说明:(1)把关系这种“无形”的联系用集合这种“有形”的实体来描述。

(2)有序对是讲究次序的。3.4关系及其表示

Arelation,R,onsomeunderlyingset,S,issomecharacteristicofcertainorderedpairsofelementsofS.10onnumbers:a=ba<ba≥bonintegers:a|bonsubsets:A

B|A|=|B|onpeople:aismarriedtobaisyoungerthanbaisadescendantofb.11T.JenkynsandB.Stephenson,FundamentalsofDiscreteMathforComputerScience:AProblem-SolvingPrimer,UndergraduateTopicsinComputerScience,Springer-VerlagLondon

2013《离散数学解题指导（第2版）》，清华大学出版社，2016贲可荣等12定义3.13设A，B为集合，A×B的任何子集称为从A到B的二元关系。特别当A＝B时，称为A上的二元关系。思考：若|A|=n，则A上的二元关系有多少个？3.4关系及其表示(续)

例1设集合A={a,b}，B={1,2}，

R1={<a,1>,<a,2>}R2={<a,1>,<b,1>,<b,2>}R3={<a,a>,<b,b>}R4={<a,a>,<b,a>,<a,b>}13特殊二元关系

对任意集合A，空集

是A×A的子集，叫做A上的空关系。全域关系为EA={<x,y>|x

A∧y

A}=A×A，恒等关系为IA={<x,x>|x

A}。例2设集合A={0,1,2}，B={a,b}，试求IA、IB和EB

。3.4关系及其表示(续)

14常用的关系:

LA＝{<x,y>|x,y

A∧x≤y}，其中AR

DB＝{<x,y>|x,yB∧x整除y}，其中BZ*

R

＝{<x,y>|x,yA∧xy}，其中A是集合族例3设集合A={1,2,3}，试求LA、DA。3.4关系及其表示(续)

15描述法列举法关系图关系矩阵关系表示法：例4

设A={1,2,3,4}，用描述法表示A上的关系R。

(1)R={<x,y>|x是y的倍数}(2)R={<x,y>|(x-y)2

A}

(3)R={<x,y>|x≠y}3.4关系及其表示(续)

列举法(1)R＝{<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}

(2)R＝{<1,2>,<1,3>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,2>,<4,3>}

(3)R＝{<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}16设A={x1,x2,…,xn},R是A上的关系。令rij=(i,j=1,2,…,n),

则MR

=是R的关系矩阵，记作MR。

3.4关系及其表示(续)

例5

设A＝{1,2,3,4}，R＝{<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，试求R的关系矩阵。关系矩阵MatrixRepresentation17A是有限集合，R是A上的关系，对A的每个元素画一个小圆，称为顶点；当且仅当aiRaj，画一个由顶点ai到顶点aj的箭头，称为边。这个图称为R的有向关系图。3.4关系及其表示(续)

例6

设A＝{1,2,3,4}，R＝{<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，试求R的关系图。例7

求集合A＝｛1,2,3,4｝上的恒等关系、空关系、全域关系和小于关系，并画出小于关系的关系图。关系图DirectedGraphRepresentation18例7

求集合A＝｛1,2,3,4｝上的恒等关系、空关系、全域关系和小于关系，并画出小于关系的关系图。IA={<1,1>,<2,2>,<3,3>,<4,4>}

EA={<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>}E<={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}19例8设集合A={a,b}，R是P(A)上的包含关系，请用列举法、描述法、关系图与关系矩阵四种方法表示R。3.4关系及其表示(续)

20LetS={1,2,3,4}andletR={<1,1>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,2>,<4,2>}213.1集合的概念和表示法3.2集合的运算3.3有序对与笛卡儿积3.4关系及其表示3.5关系的运算

3.6关系的性质3.7关系的闭包3.8集合的划分与覆盖3.9等价关系和等价类3.10相容关系和相容类3.11偏序关系3.12偏序集与哈斯图3.13应用案例第3章集合与关系223.5关系的运算

并运算交运算差运算补运算对称差运算例9设A={1,2,3,4}，A的上关系为R和S分别定义为

R={<x,y>|(x－y)/2是整数，x,yA}S={<x,y>|(x－y)/3是正整数，x,yA}

求R∪S,R∩S,R－S,A×A－R,R

S。第3章集合与关系23定义3.15设R是二元关系(1)R中所有的有序对的第一元素构成的集合称为R的定义域，记为domR。表示为：domR＝{x|

y(<x,y>

R)}。(2)R中所有有序对的第二元素构成的集合称为R的值域，记作ranR。表示为：ranR＝{y|x(<x,y>

R)}。

(3)R的定义域和值域的并集称为R的域，记作fldR。表示为：fldR＝domR∪ranR。例10

设R＝{<1,2>,<1,3>,<2,4>,<4,3>}，求domR、ranR和fldR

。3.5关系的运算（续）

24定义3.16

设A,B,C是三个任意集合,R是A到B的二元关系,S是B到C

的二元关系，则定义关系R和S的合成或复合关系

RοS＝{<a,c>|a

A,cC∧b

B,使<a,b>R且<b,c>S}。关系的复合运算(合成)例11

集合A＝{a,b,c},B＝{1,2,3}，R是A上关系，S是A到B的关系。

R＝{<a,a>,<a,c>,<b,b>}S＝{<a,1>,<b,2>}

求RοS，SοR，IAοR，RοIB。3.5关系的运算（续）

25复合运算的性质定理3.3设IA,IB为集合A,B上的恒等关系,R

A×B，

(1)IAοR＝RοIB＝R(2)

οR＝Rο＝

3.5关系的运算（续）

26例12

设集合A＝｛0,1,2,3,4｝，R，S均为A上的二元关系，且

R＝{<x,y>|x＋y＝4}＝{<0,4>,<4,0>,<1,3>,<3,1>,<2,2>}，

S＝{<x,y>|y－x＝1}＝{<0,1>,<1,2>,<2,3>,<3,4>}，求(1)RοS，SοR(2)(RοS)οR，Rο(SοR)复合运算的性质3.5关系的运算（续）

(3)RοR，(RοR)οR定理3.4设R是A到B的关系,S是B到C的关系,T是C到D的关系,

则(RοS)οT＝Rο(SοT)。27关系的逆运算定义9设R是集合A到B的二元关系，则定义一个B到A的二元关系R-1＝{<b,a>|<a,b>∈R}，称为R的逆关系，记作R-1。例13

设集合A＝{a,b,c,d}，A的关系为

R＝{<a,a>，<a,d>，<b,d>，<c,a>，<c,b>，<d,c>}，求R-1

，及MR和MR-1。3.5关系的运算（续）

28

说明：

(1)R-1就是将所有R中的有序对中的两个元素交换次序成为R-1，故|R|=|R-1|。

(2)R-1

的关系矩阵是R的关系矩阵的转置，即MR-1=MR-1。

(3)R-1的关系图就是将R的关系图中的有向边改变方向所得到的图。关系的逆运算3.5关系的运算（续）

29例14

集合A＝{a,b,c},B＝{1,2,3,4,5},R是A上关系，S是A到B的关系。

R＝{<a,a>,<a,c>,<b,b>,<c,b>,<c,c>}S＝{<a,1>,<a,4>,<b,2>,<c,4>,<c,5>}

求S－1οR－1和（RοS）－1。3.5关系的运算

（续）

解

RοS＝{<a,1>,<a,4>,<a,5>,<b,2>,<c,2>,<c,4>,<c,5>}R－1＝{<a,a>,<b,b>,<b,c>,<c,a>,<c,c>}S－1＝{<1,a>,<2,b>,<4,a>,<4,c>,<5,c>}S－1οR－1＝{<1,a>,<2,b>,<2,c>,<4,a>,<4,c>,<5,a>,<5,c>}（RοS）－1＝{<1,a>,<2,b>,<2,c>,<4,a>,<4,c>,<5,a>,<5,c>}30定理3.6设R是A到B的关系，S是B到C的关系，则（RοS）-1＝S-1οR-1逆运算的性质3.5关系的运算（续）

31例15

设集合A＝｛1，2｝，

R，S均为A上的二元关系，且

R＝{<1,1>,<1,2>}，

S＝{<1,1>,<1,2>,<2,2>}，求(1)(R－1)－1；

(2)（R∪S）－1

和R－1∪S－1；

(3)（R∩S）－1和R－1∩S－1；

(4)（R－S）－1和R－1－S－1。逆运算的性质3.5关系的运算（续）

32定理3.7

设R和S均是A到B的关系，则

(1)(R－1)－1＝R(2)（R∪S）－1=R－1∪S－1；

(3)（R∩S）－1=R－1∩S－1；

(4)（R－S）－1=R－1－S－1。逆运算的性质3.5关系的运算（续）

定理3.8

设R是任意的关系，则

domR－1＝ranR，ranR－1＝domR33定义10

设R为A上的关系，n为自然数，则R的n次幂定义为：

(1)R0＝{<x,x>|x

A}＝IA

(2)Rn＋1＝RnοR关系幂例16

设集合A＝｛1,2,3,4,5｝，

R={<1,2>,<2,1>,<2,3>,<3,4>,<4,5>}，求R0，R1，R2，R3，R4，R5。3.5关系的运算（续）

34例16

设集合A＝｛1,2,3,4,5｝，

R={<1,2>,<2,1>,<2,3>,<3,4>,<4,5>}，求R0，R1，R2，R3，R4，R5。R2={<1,1>,<1,3>,<2,2>,<2,4>,<3,5>}R3={<1,2>,<1,4>,<2,1>,<2,3>,<2,5>}，R4={<1,1>,<1,3>,<1,5>,<2,2>,<2,4>}，R5={<1,2>,<1,4>,<2,1>,<2,3>,<2,5>}

35

如果R是用关系矩阵M给出的，则Rn的关系矩阵是Mn，即n个矩阵M之积。与普通矩阵乘法不同的是，其中的相加是逻辑加，即1＋1＝1,1＋0＝0＋1＝1,0＋0＝0幂运算的关系矩阵例17

设A＝{a,b,c,d}，R＝{<a,b>,<b,a>,<b,c>,<c,d>}，求R的各次幂，分别用矩阵表示。3.5关系的运算（续）

363.5关系的运算（续）

例17

设A＝{a,b,c,d}，R＝{<a,b>,<b,a>,<b,c>,<c,d>}，求R的各次幂，分别用矩阵表示。解：R的关系矩阵为M＝

373.5关系的运算（续）

例17

设A＝{a,b,c,d}，R＝{<a,b>,<b,a>,<b,c>,<c,d>}，求R的各次幂，分别用矩阵表示。M2＝=

M3＝M2M＝=

38因此M4＝M2，即R4＝R2。因此可以得到

R2＝R4＝R6＝…

R3＝R5＝R7＝…

3.5关系的运算（续）

M4＝M3