5集合与关系(部编)课件

集合的概念与表示一集合的运算二

第五章集合与关系第一节集合

三集合中元素的计数5.1集合一、集合的概念与表示1.集合的概念

集合：“所要讨论的一类对象的整体”；或“可确定的可相互区别的事物汇集在一起所组成的整体”.

通常，用大写的英文字母A,B,C,…表示集合；

例如，1.二十六个英文字母可以看成是一个集合.2.所有的自然数看成是一个集合.

3.长沙民政学院2009级的全体学生可看成是一个集合.4.这间教室中的所有座位可看成是一个集合.5.1集合一、集合的概念与表示集合的元素:组成一个集合的那些对象称为这个集合的元素。通常，用小写的英文字母a,b,c,…表示.元素可以是单个的数字也可以是字母，还可以是集合.元素与集合的关系：属于∈；不属于

.若a是集合A中的元素记为a

A，读作a属于A；若a不是集合A中的元素，则记为a

A，读作a不属于A.例如：A是正偶数集合，则2

A，8

A，36

A；而3

A，9

A，17

A

集合元素具有的特点：确定性，互异性，无序性.如：A={a,c,b};B={{a},{b},{c}，D}5.1集合如：C={x|0<x<10}，V={x|x是元音字母}，Ｅ={x|x=a2,a是自然数}.2.集合的表示法

列举法(列元素法)；将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，

描述法(谓词表示法)；将集合元素的条件或性质用文字或符号在花括号内竖线后面表示出来。

例如：V={a,e,i,o,u}或B={1,4,9,16,25,36……}.一、集合的概念与表示5.1集合{b,c}

Ab

A{{d}}A{d}Ad

A

再如，根据右图写出集合AA={a,{b,c},d,{{d}}}指出集合与元素之间的关系5.1集合

【定义1】设A，B是两个集合，若Ａ中的每个元素都是Ｂ的元素，则称Ａ是Ｂ的子集，也称A被B包含（或B包含Ａ），记作Ａ

Ｂ

（或Ｂ

Ａ）.若Ａ

Ｂ

，且A

B，则称Ａ是Ｂ的真子集，也称A真包含于B,记作A

B，或Ｂ

Ａ.二、

集合的运算1.集合间的关系集合的包含关系也可表成：A

B

(

x)(x

A

x

B)这表明，要证明A

B，只需对任意元素x，有下式x

A

x

B

成立即可.5.1集合例如：对于A={1,{2,3},{{4}}}，

1∈A,{2,3}∈A,3

A.可以用树形图表示这种关系.

A1

{2,3}{{4}}

23{4}

42.集合的表示法5.1集合

【定义2】当两个集合A和B的元素完全一样，即A，B实际上是同一个集合时，则称集合A，B相等，记作A=B.

符号化表示为：A=B

A

B∧B

A例如，设A={x|x是偶数，且0<x<10}，B={2,4,6,8}，则A=B.

A=B可形式表为：

A=B

(

x)(x

A

x

B).或者

A=B

(

x)(x

A

x

B)

(

x)(x

B

x

A).证明集合A与B相等时，只需考察：对于任意元素x，应有下式

xAx

B成立即可.二、

集合的运算5.1集合

【定义3】约定，存在一个没有任何元素的集合，称为空集，记为

，有时也用{}来表示.空集是任何集合的子集.约定，所讨论的对象的全体称为全集，记作E或U.我们所讨论的集合都是全集的子集。全集是相对的.二、

集合的运算5.1集合只有一、二年级的学生才爱好体育运动※【例1】请指明下列的对应关系

F:一年级大学生的集合S：二年级大学生的集合

R：计算机系学生的集合M：数学系学生的集合

T：选修离散数学的学生的集合

L：爱好文学学生的集合P:爱好体育运动学生的集合TM(RS)RST(MF)T=MLPP

（FS）S(MR)P除去数学和计算机系二年级学生外都不选修离散数学所有计算机系二年级学生都选修离散数学数学系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运动5.1集合

【定义4】以集合A的所有子集为元素构成的集合，称为A的幂集,记作P(A)。

符号化表示为P(A)={x|xA}.例：设A={a,b,c}，则P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}.

【注意】一个集合的幂集是指该集合所有子集的集合，即是由这些子集所组成的集合族.1.若A为有穷集，|A|=n，则

|Ｐ(A)

|=Cn0+Cn1+

…+Cnn

=2n。2.xP(A)当且仅当x

A。3.设A、B是两个集合，A

B当且仅当P(A)P(B).幂集的性质5.1集合文氏图

用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素。例如：集合V={a,e,i,o,u}，用文氏图表示如下:EVauoie5.1集合并

A

B={x|x

A

x

B

}交

A

B={x|x

A

x

B}相对差A

B={x|x

A

x

B}对称差

A

B=(A

B)

(B

A)=(A

B)(A

B)

绝对补

A=E

A

2.集合的基本运算二、

集合的运算5.1集合文氏图表示5.1集合并和交运算可以推广到有穷个集合上，即

A1

A2

…An

={x|x

A1

x

A2

…

x

An

}

A1

A2

…An

={x|x

A1

x

A2

…

x

An

}某些重要结果

A

B

A

A

B

A

B=

A

B=

A

B=A5.1集合1.等幂律：A∪A=A(1)

A∩A=A，(2)2.结合律：

(A∪B)∪C=A∪(B∪C)(3)

(A∩B)∩C=A∩(B∩C)(4)3.交换律：A∪B=B∪A(5)

A∩B=B∩A(6)4.分配律：A∪(B∩C)=(A∪B)∩(A∪C)(7)

A∩(B∪C)=(A∩B)∪(A∩C)(8)5.同一律：

∪A=A

(9)E∩A=A(10)对于任意集合A,B,C有如下算律：5.1集合6.零律： E∪A=E(11)

∩A=

(12)7.排中律A∪~A=E(13)矛盾律A∩~A=(14)8.吸收律：A∪(A∩B)=A(15)

A∩(A∪B)=A

(16)9.摩根律：A-(B∪C)=(A-B)∩(A-C)(17)

A-(B∩C)=(A-B)∪(A-C)(18)

~(B∪C)=~B∩~C(19)~(B∩C)=~B∪~C(20)~

=E(21)~E=

(22)10.双重否定律~(~A)=A(23)5.1集合

A∩BA,A∩BB(24)A

A∪B,B

A∪B(25)A-B

A(26)A-B=A∩~B(27)A∪B=BABA∩B=A

A-B=

(28)AB=BA(29)(AB)C=A(BC)(30)

A

=A(31)AA=

(32)AB=ACB=C(33)5.1集合

有限集A中所含元素的个数称为集合的基数，记作：|A

|(或记作cardA).如：A

={1,3,2,4,5,9}则|A

|=

6

．

设B是所有英文字母组成的集合，则

B=26．三、

集合中元素的计数【定理1】若A,B,C为任意的集合，则有(2)A∪B∪C=

A+

B+

C--

AB-

AC--

BC+

ABC

．

推论设A1,A2,…,An是n个集合，则

(1)A∪B

=A

+

B

--AB，A=E--；5.1集合

【解】设A，B分别表示熟悉FORTRAN和PASCAL语言的程序员集合，则A∪B="至少熟悉一种语言"，~(A∪B）="两种语言都不熟悉"

【例3】有100名程序员，其中47名熟悉FORTRAN语言，35名熟悉PASCAL语言，23名熟悉这两种语言。问有多少人对这两种语言都不熟悉.所以，两种语言都不熟悉的有41人=100-59=41

~(A∪B)=E

--

A∪B

=47+35-23=59

A∪B

=A

+

B

-

AB

2423125.1集合

【解法二】设A，B分别表示熟悉FORTRAN和PASCAL语言的程序员集合，将熟悉两种语言的对应人数23人添到A∩B的区域内，不难得到A-B和B-A的人数分别为

A-B=A-A∩B=47-23=24

B-A=B-A∩B=35-23=12从而得A∪B=24+23+12=59

~(A∪B)=100-59=41所以，两种语言都不熟悉的有41人47352412请用方程解此题用方程解此题:设两种语言都不熟悉的人为x,则100-47-35+23=x，

解之得x=41235.1集合

【例4】求在1和1000之间不能被5或6,也不能被8整除的数的个数.

【解】设1到1000之间的整数构成全集E，A，B，C分别表示其中可被5，6或8整除的数的集合。A∪B∪C表示能被5或能被6，或能被8整除的数。在A∩B∩C中的数一定可被5,6和8的最小公倍数5,6,8=120整除，即

A∩B∩C=1000/5,6,8=8.同理得

A=1000/5

=200．

B=1000/6=166．

C=1000/8=125．

从而得A∪B∪C

=

A+

B+

C--

AB-

AC--

BC+

ABC

=200+166+125-33-25-41+8=400．

所以,不能被5或6,也不能被8整除的数有600个．

A∩B=1000/5,6=33．

A∩C=1000/5,8=25．

B∩C=1000/6,8=41．5.1集合

【解法二】对上述子集计数：

|S|=1000,|A|=

1000/5

=200,|B|=1000/6=133，

|C|=1000/8

=125,|A

B|=1000/30

=33,|B

C|=1000/40

=25,|A

C|=1000/24

=41,|A

B

C|=1000/120

=8.代入公式

N=1000

(200+133+125)+(33+25+41)

8=600.26--X21--XX175.1集合

【例5】

一个班里有50个学生，在第一次考试中有26人合格，在第二次考试中有21人考试合格，如果两次考试都不合格的有17人，则两次考试都合格的有多少人？

【解】

画出文氏图,如下图所示.首先要填入AB中的人数，它正是要求的数，所以设它为X，然后填入其他区域中的数字，并列出方程如下：解得A--BABB--AABAB175.1集合

【解法二】

画出文氏图，设A、B分别表示第一、第二次考试合格的人，则有ABAB5.1集合

【练习】

一个班里有100个学生，在第一次考试中有70人合格，在第二次考试中有78人考试合格，如果两次考试都不合格的有16人，则（1）两次考试中至少有一次合格的人为多少？（2）两次考试都合格的有多少人？

【解】

画出文氏图，设A、B分别表示第一、第二次考试合格的人的集合，则有笛卡尔积一关系的表示二

第五章集合与关系第二节关系

关系的运算三关系的性质四关系的闭包五

等价关系和偏序关系六5.2

关系一、笛卡尔积

【定义1】(1)由两个元素x,y（允许x=y）按一定顺序排列成的二元组叫做一个有序对(或序偶)，记作<x,y>,其中x是它的第一元素，y是它的第二元素。实例：平面直角坐标系中点的坐标<3,

4>.有序对<x,y>具有以下性质：(1)当x≠y时，<x,y>≠<y,x>

(2)<x,y>=<a,b>x=a且

y=b解得【例1】已知<x+3,y-2>=<y+7,3y-x>，求x和y.

【解】由有序对相等的充要条件得5.2

关系

※【定义1】(2)

一个有序n元组

(n≥3)是一个有序对，其中第一个元素是一个有序n-1元组.一个有序n元组记作<x1,x2,…,xn>,即<x1,x2,…,xn>=<

<x1,x2,…,xn-1>,xn>

※例如：空间直角坐标系中点的坐标<1,-1,3>,<2,4.5,0>等都是有序3元组。

n维空间中点的坐标或n维向量都是有序n元组。形式上也可以把<x>看成有序1元组。5.2

关系

【定义2】设A，B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作A×B。即笛卡儿积的符号化表示为：

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

y∈B}例如：若A={1,2},B={a,b,c},则

A×B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}

B×A={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}易知：若|A|=m(即集合A的元素的个数)，|B|=n，则|A×B|=|B×A|=mn．一、笛卡尔积5.2

关系

笛卡儿积的符号化表示为：

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

y∈B}

【练习】设A={2,8},B={b,c,d},求A×B，B×A，B×B.

【解】

A×B={<2,b>,<2,c>,<2,d>,<8,b>,<8,c>,<8,d>},

B×A={<b,2>,<b,8>,<c,2>,<c,8>,<d,2>,<d,8>},

B×B={<b,b>,<b,c>,<b,d>,<c,b>,<c,c>,<c,d>,

<d,b>,<d,c>,<d,d>}.5.2

关系有序对与集合的区别由定义知：有序对就是有顺序的数组．

如<x,y>，x,y

的位置是确定的，不能随意放置.注意：有序对<a，b>

<b,a>，但以a,b为元素的集合{a,b}={b,a}；有序对<a，a>有意义，而集合{a,a}不成立，因为它只是单元素集合，应记作{a}.

笛卡儿积是一种集合合成的方法，把集合A，B合成集合A×B，规定

A×B＝{<x,y>

x

A,y

B}.由于有序对<x,y>中x,y的位置是确定的，因此A×B的记法也是确定的，不能写成B×A. 5.2

关系笛卡儿积的性质：1．对任意集合A，根据定义有

A×φ=φ×A=φ．2．一般来说，笛卡儿积不满足交换律，即

A×B≠B×A（当A≠B，B≠φ、A≠φ时）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.2

关系

※【定义2′】设A1,A2,…,An,是集合(n≥2),它们的n阶笛卡儿积，记作A1×A2×…×An，其中A1×A2×…×An={<x1,x2,…,xn

>

|x1

A1∧x2

A2∧…∧xn

An

}.

当A1=A2=…=An=A时，记作An．

例如，A={a,b},则

A3=A×A×A={a,b}×{a,b}×{a,b}

={<a,a,a>,<a,a,b>,<a,b,a>,<a,b,b>,

<b,a,a>,<b,a,b>,<b,b,a>,<b,b,b>}.5.2

关系

例3

设集合A＝{1,2},求A×P(A)。解

P(A)表示以Ａ的所有子集为元素所组成的集合：

P(A)={

,{1},{2},{1,2}} .于是可得

A×P(A)＝{1,2}×{

,{1},}{2},{1,2}

={<1,

>,<2,

>,<1,{1}>,<2,{1}>,<1,{2}>,<2,{2}>,

<1,{1,2}>,<2,{1,2}>}.5.2

关系二、关系的表示

1.关系的概念人与人之间的“同志”关系、“同学”关系；“朋友”关系、“师生”关系、“上下级”关系、“父子”关系.两个数之间有“大于”关系、“等于”关系和“小于”关系，两个变量之间有一定的“函数”关系.计算机内两电路间有导线“连接”关系、程序间有“调用”关系等等.现在研究集合内元素间的关系以及集合之间元素之间的关系.它对研究计算机科学中的许多问题如数据结构、数据库、情报检索、算法分析、计算理论等都是很好的数学工具.5.2

关系二元关系：集合中两个元素之间的某种关系

【引例1】

甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲,甲胜丙，乙胜丙.比赛结果可表示为：{<乙,甲>，<甲,丙>，<乙,丙>}，其中<x,y>表示x胜y，它表示了集合{甲,乙,丙}中元素之间的一种胜负关系.

【引例2】

有A、B、C三个人和四项工作G1、G2、G3、G4,已知A可以从事工作G1和G4,B可以从事工作G3,C可以从事工作G1和G2.那么，人和工作之间的对应关系可以记作R＝

{<A,G1>,<A,G4>,<B,G3>,<C,G1>,<C,G2}它表示了集合{A,B,C}到工作{G1,G2,G3,G4}之间的关系.5.2

关系

【引例3】设一旅馆有n个房间，每个房间可住两个旅客，所以一共可住2n个旅客．在旅馆内,旅客与房间有一定关系，用R表示“某旅客住在某房间”这种关系．我们可用图形和集合来来表示关系R.设n=3表示旅馆共有3个房间,分别记为1,2,3．六个旅客分别记为a,b,c,d,e,f．这些旅客住的房间如右下图所示.123abcdef

满足R的所有关系可看成是一个有序对的集合，这个集合可叫R：R={<a,1>,<b,1>,<c,2>,<d,2>,<e,3>,<f,3>}若令A={a,b,c,d,e,f}，

B={1,2,3}，则引例中关系的每一个元素均属于A×B，亦即R是A×B的子集，并称此关系为从A到B的关系R。5.2

关系

【定义3】(1)如果一个集合为空集或者它的元素都是有序对,则称该集合为一个二元关系，记作R，简称关系。

例如,上引列中，A={a,b,c,d,e,f}，

B={1,2,3}，关系R={<a,1>,<b,1>,<c,2>,<d,2>,<e,3>,<f,3>}，则有aＲ1,bR1，eR3，

对于二元关系R，若<x,y>∈R，则记作xRy;如果<x,y>R,则记作．1．关系的概念二、关系的表示5.2

关系

※二元关系是两种客体之间的联系．例如某学生学习的课程有语文、数学、外语，表示为A＝{语文,数学,外语},功课的成绩分四个等级，记作B＝{A，B，C，D},于是该生成绩的全部可能情况可表示为A×B：

A×B＝{<语文,A>,<语文,B>,<语文,C>,<语文,D>,<数学,A>,<数学,B>,<数学,C>,<数学,D>,<外语,A>,<外语,B>,<外语,C>,<外语,D>}.假定该生的实际成绩为

P＝{<语文,B>,<数学,A>,<外语,D>}

可看出P是A×B的一个子集，它表示了功课与其成绩的一种关系.由此可见：两个集合之间的二元关系，实际上就是两个元素之间的某种相关性.5.2

关系

【定义3】(2)

设A，B为集合，A×B的任何子集R，称为从A到B的二元关系.特别当A=B时，则称R是A上的二元关系.

【例2】若A={a,b}，B={2,5,8}，则

A×B

={<a,2>,<a,5>,<a,8>,<b,2>,<b,5><b,8>}令R1={<a,2>,<a,8>,<b,2>},R2={<a,5>,<b,2><b,5>},R3={<a,2>}.因为R1

A×B，R2

A×B，R3

A×B，所以R1，R2和R3均是由A到B的二元关系.因为只讨论二元关系，所以今后无特别声明，术语“关系”皆指二元关系.5.2

关系

又如：若A={a,b}，B={2,5,8}，则

B×A={<2,a>,<2,b>,<5,a>,<5,b>,<8,a><8,b>}令R4={<2,a>,<2,b>},R5={<5,a>,<8,a><8,b>},因为R4B×A，R5B×A，所以R4和R5均是由B到A的关系.又B×B={<2,2>,<2,5>,<2,8>,<5,2>,<5,5>,<5,8>,<8,2>,<8,5>,<8,8>}

,令R6={<2,2>,<5,2>,<8,2>},

R7={<8,5>,<5,2><2,8>,<2,5>}.因为R6B×B，R7B×B，所以R6和R7均是集合B上的关系.5.2

关系

三类特殊的关系对于任何集合A，空集φ是A×A的子集，叫做A上的空关系．定义EA={<x,y>|x∈A

且

y∈A}=A×A为全域关系．定义IA={<x,x>|x∈A}为恒等关系．例如，若A={1,2}，则

EA={<1,1>,<1,2>,<2,1>,<2,2>}，

IA={<1,1>,<2,2>}.5.2

关系

除上述三类特殊的关系外，还有一些常用的关系，如：

LA={<x,y>|x,y∈A

且

x≤y}(A

R)为实数集上的小于等于关系.

DA={<x,y>|x,y∈A

且x整除y}(A

N)为自然数集上的整除关系.

R

={<x,y>|x,y∈A

且xy}(A是集合族)为集合上的包含关系.类似地还可以定义大于等于关系、大于关系、小于关系、真包含关系等.5.2

关系【例4】设A={1,2,3,4}，请表示下列关系。(1)R={<x,y>|x是y的倍数},(2)R={<x,y>|(x-y)2∈A},(3)R={<x,y>|x≠y}.

【解】(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<2,1>,<3,1>,<4,1>,<4,2>}.(2)R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<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>}.5.2

关系

2.关系矩阵和关系图

例如，关系R={<2,8>,<2,12>,<2,14>,<3,9>,<3,12>,<4,8>,<4,12>}的关系矩阵可表示为

891214

21011

R的关系矩阵为MR=30110

41010

【定义5】若，为从A到B的关系，则称矩阵为R的关系矩阵，其中

当B=A时，A上的二元关系R的关系矩阵为方阵.5.2

关系

设A={1,2,3,4},R是A上的二元关系且有R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},则R的关系矩阵MR和关系图GR如下：【实例】5.2

关系

【实训】设A={1,2,3,4}，R为A上的小于关系，且R为：R={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}

.

则R的关系矩阵为：

0111

0011

00

0

1

00

0012341234MR

=5.2

关系

例如,

设R:AB，A={x1,x2,x3,x4},B={y1,y2,y3}R={<x1,y2>,<x2,y1>,<x2,y3><x3,y3>}

则R的关系图如下所示x1x2x3x4y1y2y3【定义6】设，，R为从A到B的关系．用空心小圆点分别表示A和B的元素．如果，则画一条由点到点的有向边，箭头指向，这样的图称为R的关系图.5.2

关系

【例如】设R:AA，A={a,b,c,d}，R={<a,b>,<a,c>,<b,a>,<b,c>,<c,c>}

则R的关系如下图所示abcd其中c到c的边称为环5.2关系【解】（１）（２）（３）关系图如下：2461357【例5】设（１）用列举法写出关系；，（２）写出的关系矩阵；（３）画出的关系图.5.2

关系三、关系的运算

【定义7】

设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∪ranR5.2

关系【例6】

设R1={<1,2>,<2,4>,<3,3>}，R2={<1,3>,<2,4>,<4,2>}，求其定义域和值域.

【解】domR1={1,2,3}，domR2={1,2,4}.

ranR1={2,4,3}，

ranR2={3,4,2

}.

如求R1∪R2及

R1∩R2定义域和值域,则因为R1∪R2={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}.R1∩R2={<2,4>}.所以

dom(R1∪R2))

={1,2,3,4}.

ran(R1∪

R2)={2,3,4}.5.2

关系

【例7】下列关系都是整数集Z上的关系，分别求出它们的定义域和值域。R1={<x,y>|x,yZ且x≤y}(2)R2={<x,y>|x,yZ且x2+y2=1}(3)R3={<x,y>|x,yZ且y=2x}

R4={<x,y>|x,yZ且|x|=|y|=3}解(1)domR1=ranR1=Z,(2)R2={<0,1>,<0,-1>,<1,0>,<-1,0>},

domR2={0,1,-1},

ranR2={0,1,-1}.(3)domR3=Z,

ranR3={2z|zZ},即偶数集.

domR4={-3,3},

ranR4={-3,3}.10-1-101domR2ramR2R2…43210-1-2-3-4……210-1-2…domR3=ZramR3R35.2

关系

【定义8】

设R为A到B的关系，S为B到C关系，

R={<x,y>|x∈A，y∈B}，则

(1)R的逆记作R-1,

R-1={<y,x>|xRy}.

逆关系设R是一个X到Y的关系，则Y到X的关系R-1：

R-1={<y,x>|<x,y>R}，称为R的逆关系。

【例8】设X={1,2,3}Y={a,b,c}，且R是从X到Y的关系：R={<1,a>,<2,b>,<3,c>}，则

R-1={<a,1>,<b,2>,<c,3>}。5.2

关系（2）设R是一个X到Y的关系,S是一个Y到Z的关系,则S与R的复合关系(或合成关系)S

R为：

S

R

={<x,y>|

z(xRz∧zSy}.

【例9】

设X={x1,x2,x3},Y={y1,y2,y3},Z={z1,z2,z3}

从X到Z的关系R={<x1,z1>,<x1,z2>,<x2,z2>}从Z到Y的关系S={<z1,y2>,<z2,y3>,<z3,y3>}则X到Y的关系S

R={<x1,y2>,<x1,y3>,<x2,y3>}x3S

Ry2x1x2y1y3SRx1x2x3z1z2z3y1y3y2XZYXY5.2

关系

【例10】设

G={<2,1>,<3,4>},

R={<1,2>,<1,3>,<3,2>}，

求R-1,R

G，G

R。

【解】

R-1={<2,1>,<3,1>,<2,3>}，

R

G

={<2,2>,<2,3>}，

G

R={<1,1>,<1,4>,<3,1>}。

【注意】逆运算的优先级高于其他运算，而所有的关系运算都优于集合运算。5.2

关系

【定义8】设R为A到B的关系，S为B到C关系，

R={<x,y>|x∈A，y∈B}，则

(2)

R与S的复合，记作R

S，其中

R

S={<x,y>|

z(xSz且zRy}．（注意上式中R和S的顺序）或S

R={<x,y>|

z(xRz∧zSy}

. 5.2

关系

【例11】

设集合A={4,5,8,15},B={3,4,5,9,11}，

C={1,6,8,13},F是由A到B的关系,G是由B到C的关系,分别定义为

F={<a,b>||b-a|=1}，

G={<b,c>||b-c|=2或|b-c|=4},求合成关系G

F和F

G.

解先求G

F,由已知条件可得：F={<4,3>,<4,5>,<5,4>,<8,9>}.G={<3,1>,<4,6>,<4,8>,<5,1>,<9,13>,<11,13>}.G

F={<4,1>,<5,6>,<5,8>,<8,13>}.FG={<4,9>}.5.2

关系逆与合成

R

1={<y,x>|<x,y>

R},

R∘S=|<x,y>|

z(<x,z>

S且<z,y>

R)}.

【练习１】设R={<1,2>,<2,3>,<1,4>,<2,2>}，

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}，求，R∘S，S∘R.

【解】

R

1={<2,1>,<3,2>,<4,1>,<2,2>}，

R∘S={<1,2>,<1,4>,<3,2>,<3,3>}，S∘R={<1,3>,<2,2>,<2,3>}．5.2

关系

【定义9】

设R是A上的关系,n为自然数，则R的n次幂规定如下：

(1)R0={<x,x>|x∈A};(2)Rn=Rn-1

R,n≥1.由定义可知R0就是A上的恒等关系IA，不难证明下列等式

R

R0=R=R0

R．由这个等式可得R1=R0

R=R．【例12】

设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}，

求R0，R1，R2，R3，R4和R5

【解】

R0={<a,a>,<b,b>,<c,c>,<d,d>}R1=

R={<a,b>,<b,a>,<b,c>,<c,d>}

（两个关系的书写顺序）R2=R

R={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}.

5.2

关系

【例13】

设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}

求R，R1，R2，R3，R4和R5．

【解】R1=R={<a,b>,<b,a>,<b,c>,<c,d>}

R2=R

R={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R3=R2

R={<a,a>,<a,c>,<b,b>,<b,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}R4=R3

R={<a,b>,<b,a>,<b,c>,<a,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R5=R4

R={<a,a>,<a,c>,<b,b>,<b,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}5.2

关系

【定理3】设R是A上的关系,m,n为自然数，则下面的等式成立：(1)Rm

Rn=Rm+n

，(2)(Rm)n=Rmn．

【实训】设R＝{<1，2>，<2，1>

,<2，3>，<3，4>}

,S＝{<1，2>，<2，4>，<3，1>，<4，3>},求

R

S，S

R.

【答案】5.2

关系四、关系的性质

设R是A上的关系，R的性质主要有以下5种:

（自反性、反自反性、对称性、反对称性和传递性）(1)如果对于每个x(x∈A）,都有<x,x>∈R，则称R在A上是自反的。该定义表明，在自反的关系R中，除其他有序对外，必须包括A中每个x（x

A）所组成的元素<x,x>。在具有自反关系R的关系图中，每个顶点上都有环。例如：设A={1,2,3},R是A上的关系，且

R={<1,1>,<2,2>,<3,3>,<1,2>}则R是自反的。5.2

关系

(2)若

x(x

∈A），都有<x,x>R)，则称R在A上是反自反的.该定义表明，一个反自反的关系R中，不应包括有任何相同元素的有序对.在具有反自反关系R的关系图中，每个顶点上都没有环.例如：设A={1,2,3}，R是A上的关系，且

R={<2,3>,<3,2>},则R是反自反的.四、关系的性质5.2

关系

【注意】任何一个不是自反的关系，未必是反自反的；反之，任何一个不是反自反的关系，未必是自反的。这就是说，存在既不是自反的也不是反自反的二元关系。

例如，设A={1,2,3},R是A上的关系，且

R={<1,1>,<2,2>，<2,3>}则

R是既不是自反的，也不是反自反的。5.2

关系

(3)若<x,y>∈R，则<y,x>∈R，则称R在A上是对称的.该定义表明，在表示对称的关系R的有序对集合中，若有有序对<x,y>，则必定还会有有序对<y,x>.在具有对称关系R的关系图中，如果两个顶点之间有边，则一定有一对方向相反的边.例如：设A={1,2,3},R是A上的关系，且

R={<1,2>,<2,1>,<3,3>}

，则R是对称的.5.2

关系

(4)若<x,y>∈R且x≠y

，则<y,x>R,则称R在A上是反对称的。(隐含x=y<y,x>∈R)该定义表明，在表示反对称关系R的有序对集合中，若存在有序对<x,y>和<y,x>，则必定是x=y。或者说，在R中若有有序对<x,y>，则除非x=y，否则必定不会出现<y,x>。在具有反对称关系R的关系图中，如果两个顶点之间有边，则一定只有一条有向边。判断一个关系是否反对称,通俗地讲就是对于所有的a,b∈A,若a≠b,则序偶<a,b>,<b,a>至多只有一个出现在关系R中。如R={<1,2>,<1,1>,<3,1>}是反自反的.

例如：设A={1,2,3},R={<1,2>,<1,3>}

是A上的关系，

则R是反对称的.5.2

关系

【注意】有些关系既是对称的又是反对称的，还有的关系既不是对称的又不是反对称的。例如：设A={1,2,3},R6,R7是A上的关系，并且

R6={<1,1>}，

R7={<1,2>,<2,1>,<1,3>}既不是对称的又不是反对称的.则

R6是对称的，也是反对称的,R7既不是对称的又不是反对称的.再如，设A={a,c,b>,

R={<a,b>,<a,c>,<c,a>}，则关系R5.2

关系【例1】

设A={1,2,3,4,5},A上的关系R为

R={<a,b>|a-b是偶数}，试回答下列问题：①用列举法表示R，②R是否自反、对称、反对称？

【解】①R={<1,1>,<1,3>,<1,5>,<2,2>,<2,4>,<3,3><3,1>,<3,5>,<4,2>,<4,4>,<5,1>,<5,3>，<5,5>}.②R是自反的，也是对称的，但R不是反对称的.5.2

关系

(5)若<x,y>∈R且<y,z>∈R，则<x,z>∈R，

则称R在A上是传递的关系.该定义表明，在表示可传递关系R的有序对集合中，若有有序对<x,y>和<y,z>，则必有有序对<x,z>.在具有传递关系R的关系图中，如果顶点x到y有边,y到z有边，则从x到z一定有边.四、关系的性质5.2

关系【例2】

设A={1,2,3,4,5},A上的关系R为

R={<a,b>|a-b是偶数},①用列举法表示R.②R是否是可传递的？

【解】①R={<1,1>,<1,3>,<1,5>,<2,2>,<2,4>,<3,3><3,1>,<3,5>,<4,2>,<4,4>,<5,1>,<5,3>,<5,5>}.②对于任意的a,b,c∈A：

若a-b=2m,b-c=2n,则a-c=(a-b)+(b-c)=2(m+n)也是偶数.这就是说：若<a,b>∈R,<b,c>∈R,则有<a,c>∈R,因此R是可传递的.5.2

关系

【例3】

设A={1,2,3,4,5,6,7,8,9,10}R是A上的关系，

R={<x,y>|x,y∈A

∧x+y=10},说明R具有哪些性质.

【解】

R={<1,9>,<2,8>,<3,7>,<4,6>,<5,5>,

<9,1>,<8,2>,<7,3>,<6,4>}.易知R既不是自反的也不是反自反的,

R是对称的,

R不是反对称的,

R不是传递的.5.2

关系自反反自反对称反对称传递表达式IA

RR∩IA=

R=R

1

R∩R

1

IA

R

R

R关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)如果顶点xi连通到xk,则从xi到xk有边

四、关系的性质5.2

关系【例4】

试判断下图中关系的性质：

【解】图(a)中的关系在集合{1,2,3}上是对称的，因为结点1与2，1与3之间的有向边是成对出现且方向相反.图(b)中的关系是反自反的，因为每个结点上都没有环，它也是反对称的，因为两条边都是单向边.它也是传递的.123123123(a)(b)(c)

图(c)中的关系自反的，反对称的、但不是传递的.因为2到1有边，1到3有边，但2到3没有边.5.2

关系

※【定理】设R和S是A上的二元关系，则：(1)若R和S是自反的，则经过并、交、逆、合成运算后仍保持自反性.(2)若R和S是反自反的，则经过并、交、逆、差运算后仍保持反自反性.(3)若R和S是对称的，则经过并、交、逆、差运算后仍保持对称性.(4)若R和S是反对称的，则经过交、逆、差运算后仍保持反对称性.(5)若R和S是传递的，则经过交和逆运算后仍保持传递性.四、关系的性质5.2

关系

设A＝{1，2，3}，且

R1＝{<1，1>，<2，2>}、

R2＝{<1，1>，<2，2>，<3，3>，<1，2>}、

R3＝{<1，2>}、R4＝{<1，1>，<1，2>，<2，1>}、R5＝{<1，2>，<1，3>}、

R6＝{<1，2>，<2，1>，<1，3>}都是A上的关系，说明这些关系有哪些性质.

【实训】对称的，反对称的，传递的自反反自反，反对称，传递对称反自反，反对称，传递反自反5.2

关系

【定义10】设R是非空集合A上的关系，如果R′满足以下条件:(1)R′是自反的(对称的或传递的),(2)RR′,

(3)对A上的任何包含R的自反(对称或传递)关系R″都有R′R″,则称R′为R的自反闭包（对称闭包或传递闭包）.

一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R).

在所有包含R的自反关系中的最小关系R′,称为R的自反闭包.五、关系的闭包5.2

关系定理2

设R是非空集合A上的关系，则有(1)r(R)=R∪R0.