复旦大学计算机科学与工程系 吴永辉 离散数学 集合论 第二章 关系

第二章关系

2.1二元关系

22关系的性质

23关系的运算

2.4关系数据库的一个实例

25关系的闭包

26等价关系与划分

2.7次序关系

引言

■在现实生活中，集合与集合之间还存在着某

种联系。

■现实世界中的二元关系

1,同一个集合中的二元关系：同学关系、同

桌关系..

2,两个不同集合之间的二元关系：师生关系、

学生和选修课程的关系.……

■现实世界中的多元关系

学生、课程和任课教师的关系

关系在现实世界和信息世界中的表示

■关系在现实世界中的表示：

表格

■关系在信息世界中的表示

数据库

形式化和非形式化的描述

■形式化描述

数学、精确无二义、难理解

■非形式化描述

自然语言、不精确、易理解

2.1一*兀关系

■一定义2.1(二元关系)

设/和理任意两个集合，/X耶子集碉为从

/到即二元关系。当/=加寸，称R为/上的二元关

系。若(a,b)^R,则称a与相关系/?,记为aRb。

术语：

(a,b)任R：a与白没有关系/?

R=0z空关系

R=AxB・.全关系

■由定义2」，得出：

■1）二元关系是集合；

■2）二元关系的元素是有序对。

2.1—^兀关系

■例：设力=",Z3,4,5},4上共有多少个二

元关系？

■因物上的二元关系及是4x4的子集，是4x4

的募集中的元素。

■西安交通大学1998考研

■解：

■因为4上的二元关系R是4x4的子集,

\AxA\=25,\P(AxA)\=225

■所以4上的二元关系R的个数是2海。

2.1—兀关系

■二定义22（定义域，值域）

设/?是从/到弼二元关系，/的一个子集｛研存

在仇使得&勿e©称为/?的定义域，记为DomR。

稣勺一个子集矽|存在a使得©切e号称为/?的

值域，记为RanR。

/称为/?的前域，时为/?的陪域，并且。0/77

R^A,RanRqB。

例2.1,2.2,2.3

■例2.1整除关系

设/=23,4},B={3,4,5,6,7},定义从＞4到

耶二元关素/?;⑶勿eRos整除小

R={(2,4),(2,6),(3,3),(3,6),(4,4)}

DomR={2,3,4},RanR={3,4/6}.

■例2.2A={1,2,3,4}上的小于关系R:(a,b)eR

oavb.

■R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

■练习：

■A={1,2,3,4}上的小于等于关系:R={(1,1),(2,

2),(3,3),(4,4),(1,2),(1,3),(1,4),(2,3),(2,

4),(3,4)}

■A={1,2,3,4}上的不等关系:R"={(1,2),(1,3),

(1,4),(2,3),(2,4),(3,4),(2,1),(3,1),(4,1),

(3,2),(4,2),(4,3)}

2.1—兀关系

■三定义2.3（"元关系）

设力〃……,4是3任意集合，定义

Atx……X。的子集/?为4,……,4的"元关系。

当4=……=/〃时，减为力上的〃元关

系。

实例：表格

2.2关系的性质

■一定义2.4(关系的性质)

设/?是集合力上的二元关系。

(1)如果对任意数4有切W,则称R是自反的。

(2)如果对任意3』，有何刃)?,则称/?是反自反的。

(3)对任意团白右4如果郁也必有力?a则称/?是对称的。

(4)对任意?力&4,如果郁力且"W,必有d=h则称/?

是反对称的。

如果3/乃且a纳，必有(b,a)任R,则称/?是反对称的。

(5)对任意吃。=4如果郁?勿由饮G必有切匕贝ij称

/?是传递的。

■实例1:自反与反自反

■自反：小于等于关系

■反自反：小于关系

■A={1,2,3,4/上的关系1),(1,2)},贝2

既不是自反，也不是反自反；所以，力上的

二元关系尺可以既不是自反，也不是反自反

■实例2：对称与反对称

■对称：不等关系

■反对称：小于关系

■A={1,2,3,4}上的关系区={(2,1),(1,2),

(1,3)},则R既不是对称，也不是反对称；

所以，4上的二元关系及可以既不是对称，

也不是反对称

■实例3：传递关系

%={(>2),(2,3),(1,现是传递的；

R2={(1,2),(1,3”是传递的；

R3={(1,砂是传递的；

(=g/2),(2,切不是传递的；

如果在A上的二元关系R中,aRb且bRc,

但3,c)任R,则R不是传递的;否则R是传递

的。

A上的二元关系R,或者是传递的,或者

不是传递的,两者必居其一。

■例2.6集合A的暴集P(A)的性质:

■自反,反对称,传递

■下面的二元关系哪个是传递的？（）

■A）父子关系

■B）朋友关系

■C）集合的包含关系

■D）实数的不等关系

■/*重庆大学1998年考研试题*/

2.2关系的性质

■二定义2.5（关系矩阵）

设力和醍两个有限集/=伍〃,……，斗不

B={blf.・・・・・,b工/?是从/到说勺二元关系,

称/77M7阶矩阵螺=仞〃为/?的关系矩阵，其

中

右白"bj）ERjirijj=1

右（3卜b,金R,irijj=0

■例2.7整除关系的关系矩阵

■A={2f3f4},B={3,4,5,6,7)

(01010、

MK=10010

101000,

2.2关系的性质

■三关系图

设/=优〃……zaj,/?是/上的二元关系。/中每

个元素3用一个点装示，称该点为顶点3/。

如果响,则从顶点可到顶点可存在一条弧。

如果d/Rdp则从顶点可到顶点可存在一条封闭弧。

这样表示/?中关系的图形，称为/?的关系图。

例2.8

2.3关系的运算

■定义2.6

设&和/?2是从/到8的两个二元关系，对

于3G4beB,定义：

RiuR2：aR1b^aR2b；

R^R2：a(RgR2)boaR»aaRzb；

R^R2：4(RrRJbo白且(a,b)^/?2;

R1：aAibo(d/b)£(AxB)・Ri。

2.3关系的运算

■一逆运算

■定义2.7(逆关系)设A是从4到8的二

元关系，则从醺M的二元关系记为R4

定义为於={(bfa)l(afb)eR},称为/?的

逆关系。

■例如

2.3关系的运算

■定理2.1

(1)WR;

(2)8"沙=RJuR力

(3)(RgRJ・RJcR/;

(4)(AxB)』BxA；

(5)0^=0；

(6)(RP=；

⑺(Ri-RJi=Rj.R^i；

(8)若RgRz，则RJ&R'io

证明方法

(1)证明两个关系相等，因为关系是集合，采用基

本法证明关系相等：

证明：

(a,b)在式切e右式；则左式0右式；

⑶勿e右式n&勿e左式；则右式0左式；

则左式:=右式。

(2)证明满足某一性质

根据该性质的定义进行求证。

例如，要证明集合力上的二元关系/?是自反的，就

是证明对于任意的(a,a)£R。

证明两个关系相等

-(3)基本法证明：

■(a,b)£(RgR2Po(b,a)e(RgR,o(b,

且(b,a)eR2o(a,b)$RJ宣(a,

勿e&Z所以，(RQR)I=RJcR/。

■(1)，(2)同理，证明见书。

■(4)同理。

■(5)反证法。

■设0々0,则存在&勿金0】,那么心切

£0.导致矛盾。

■(6),(7),(8)基本法或公式法证明。

2.3关系的运算

■定理2.2

/?是/上的二元关系，贝U/?是对称的0/?=/?，

证明：

R是对称的=R=R"：（证明两个集合相等）

（a,b）困因为/?是对称的，所以。,a）eRf则&

b）eR-。所以R±RT。同理，R』R。则/?=/?，

R=Rin/?是对称的：（证明满足某一性质）

如果&勿因为A=/?Z所以©分次Z则麴

a）eR.所以/?是对称的。（根据对称的定义）

2.3关系的运算

・二复合运算

■定义2.8(复合关系)设均是从4到8

的二元关系，&是从俸UC的二元关系，

则从/到纸二元关系记为a°定

义为4°R2={(a,c)|aeA,ceC,且存

在灰蹶&b)E/?〃(b,C)ER溯为Rt

和&的复合关系。

2.3关系的运算

■定理2.3(结合律)

(RJR,R3=RJ(RYR3)

■证明方法：

采用基本法，证明两个关系相等。

即：(a,d)£(Ri。R/R弃向⑴次/(RTR3)，

0

则外。A2rRj^Ri(R2°R3)；

(〜d)£RJ(RKR3)=>(a,d)£(RJR)R3,

则&。(R2°R3)=(RJR2)°R3O

具体证明步骤见书4证明。

■不满足交换律，即R2^R2°R]

2.3关系的运算

■三塞运算

■定义29(幕运算)设R是/上的二元关系,

neN,/?的〃次幕记为定义如下：

(1)即是/上的恒等关系(即。={(a,a)|

aeA}^,记为4，又R・R；

[2}Rn+1=Rn°Ro

定理24

(1)Rm°Rn=Rm+n

(2)(Rmy二Rmn

证明方法：采用归纳法进行证明

设性质为2

归纳基础：证明％〃为真；

归纳步骤：对每一个企2,假设G0为真，并

且利用这一假设证明"为真。

■证明：(1)

■归纳基础：设,则根据幕运算的定义，Rm。Rl=

Rm+1；

■归纳步骤：设Jl=k,Rm°Rk=Rm+k成立;设

Rm°pk+1=pm°pk°f^l=pm+k0Rl=pm+k+l

■所以欣°Rn=Rm+n.

■(2)归纳基础：设〃=2,则根据幕运算的定义，

(Rm)・即。

■归纳步骤：没n=k,(Rmy=Rmk成立;没n=k+l,

(pmjk+l=(Rmp°(pm)=pmk0即=pmk+m=pm(k+l)

归纳证明的思想/思维过程

■归纳基础证明彳〃为真；

■根据归纳步骤，因为％〃为真，所以"⑵为

真；因为"0为真，所以々刃为真；……；

这个过程对所有的自然数继续下去，对于

所有的自然数，呐真。

2.3关系的运算

・四投影运算

■R为A。……的"元关系，定义R在/版……/加的

投影是一个/77元关系，它是通过选取R中的每个有

序〃元组的第/〃…,/6个分量组成有序;77元组作为闻

元关系中的元素，这个投影记为〃Aim(R)。

2.4关系数据库

■1.术语

1）数据库：一个由计算机操纵的表格的汇集。

2）属性：事物某一方面的特征

3）属性域：属性所取值的变化范围

4）键：在一个关系中，单个或多个属性的值唯

一地决定一个而组

■2.实例

表2.3

2.4关系数据库

■3.操作

■查询：从数据库中取出满足一定条件的数据；

■插入数据：将一些数据存放到数据库中；

■修改数据：修改数据库中指定的数据；

■删除数据：删除数据库中指定的数据；

■投影：从一个关系中选出属性A1，…,Am对应的

歹U,删去相同的行；

■选择：从关系R中选出满足条件F的元组子集；

■自然联接：RxS=n』…RO"八"R、(RXS)

4,…4”Bp+i，…(An_p+i-5|)A...A(An-Bp)，

2.5关系的闭包

■一自反，对称，传递闭包

定义2.11(自反，对称，传递闭包)

设/?是/上的二元关系，定义/?的自反(对称，传

递)闭包记为/?’,满足下列三个条件：

(1)々是自反的(对称的，传递的)；

(2)R=R；

(3)对任一自反(对称，传递关系)R',R=R",

贝叫/?”。

分别记为时，s(R),t(R)。

2.5关系的闭包

■二基本性质

■定理2.5设R是/上的二元关系，则

(1)R是自反的or(R)=R；

(2)A是对称的os(R)=R；

(3)R是传递的ot(R)=R；

■证明思想1:采用基本法、反证法进行证明，以/?是

自反的o侬2=/?为例：

■/?是自反的口金=凡因为根据的的定义，r(R)

是自反的，所以R是自反的；

■/?是自反的0例=/?：根据侬2的定义，R=「(R)，

证明假设内y)^r(R),但因y}R,贝肝

他以是自反的，「(R)-{(x,y)}卫R・,那么对于

g存在「(R)-{(x,y)}ER),R^r(R)-{(x,y)}

且〃砂-〃%匕〃是自反的；则与询的定义矛盾。

所以〃勾=用

■证明思想2:（证明满足某一性质）

■根据自反，对称和传递闭包定义进行证明，以/?是

自反的o为例的证明过程：

■/?是自反的就是证明R符合/?的自反

闭包定义的3个条件：（1）/?是自反的；（2）伫火；（3）

对任一自反关系/?"，R=R”,则%

■"/?）=/?=/?是自反的，就是证明R符合自反的定

义，即对于任意的（a,a）eR.

■（2）,（3）的证明类似.

■定理2.6设&和/?2是/上的二元关系，若

/?£■&则

⑴「(％)7r(R2)；

(2)S(R，=S(R9；

(3)t(R，=t(R2)o

■证明思想：反证法：

■（1）假设内切白〃?〃但因y）何便办则外?P

-心切痘是白反的，即人多如臬内切£&，

贝1J内切G&，那么内切白〃引，导致矛盾，所

以（X,y次g。则4P—怒切为a，则外切

不是&的自反闭包。矛盾。（X,y）£「（RJ。

「（RiE「（R》。

■（2）,（3）证明类似。

2.5关系的闭包

■三计算

■定理2.7r(R)=RuIA

■证明思想:根据自反闭包定义要满足的性

质进行证明。

■证明：设/?'=/?以，所以电/?',而且/?'是

自反的；假设&'是/上的自夜关系并且匕7?”,

对于&勿*/?',因为/?'=/?以，所以&

勿e姑者&勿口；如果&勿eR,则&

b)eR,J；如果&勿㊂立，因为々是自反的，

所以&勿次"，即/?匕*。

■所以R=R(R)=R5A。

■定理28s(R)=RuRT

■证明思想:根据对称闭包定义要满足的性

质进行证明。

■证明：令R'=RuRT。由于(RuR-i)-i=RuRi,

根据定理22,可知/?'=/?”?■】是对称的，且

R=R。假设/?堤/上的对称关系，并且

R*对于&b)eR有⑶勿日减者&

bjeRr1.如果&勿e/?,由于匕/?”，那么&

b)eRJ\如果&勿eR1，则心切e/?,所以

(b,a)eR\因为&'是对称的，所以&

b)eR\因此所以R=s(R片RuRL

・设A={a,b,c},R是^上的二元关系，且

R={(a,b),(b，(c,a)},贝心的=____

■/*重庆大学1999考研*/

■定理29t(R)=RuR2uR3u...

■/*证明思想:根据传递闭包定义要满足的性

质进行证明:令R'=RuR2uR3y..,证明R

满足传递闭包定义的3个条件。*/

■证明：

■/*R是传递的,即如果(〜b)£R,(>C)£R,

则(a,c)$R*/

■因为&勿必存在整数n,使&勿*/?〃；

同理，因为/0*/?’,必存在整数k,使/

C)£Rk；因为依°Rk=Rn+k,所以&

C)eRn+k,所以&0*8。

■证明：（续）

■/*RqR*/

■因为R，=RuR2^R3U…,所以尺U、。

■证明：(续)

■/*对于传递关系R',如果R'nR,则R?R.*/

■如果a/E4,(a,b)ER\则存在正整数/,使他

b)£%即存在/-/个元素Q,Q,…,勺-夜得侑

cJeR,(cpCJER,…(c”,b)£R.由下尺“邯，

所以他(cqeR",…(C”,b)eR\

又因为A”是传递的，因此侑勿QT。由此

证得R"3R'。由传递闭包的定义可知：

23

R'=t(R),^t(R)=RuRuRu...o

■定理2.10/?是/上的二元关系，且|/|二〃,

贝Ut(R)=RuR2uR3u...

■/*证明思想:基本法:由定理29可知,

RuR2uR3u.・.uRnut(R)；只要证明对任意

的k>0,*/

■证明：/*分而治之*/

■对于k9,必有Rk^RuR2uR3u...uRno

■对于左＞〃，若(a,坊£处,则存在元变个数为左+1的

元素序列。0,。刀・・・，c0=afck=b,并且对(c「

I，CJER。由于Q〃，所以在元素序列中必有元素

q不止出现一次,即侑5),(5,，…,&],c),(cp

cj,…,(Cq,cj,(cif生+)，…,化hi，b)eR,在删去C，

cj这一段后，如果序列中元素个数仍大

于小则继续上述过程，直到序列中元素个数左'刍

为止。此时有侑勿右邠1所以(a,b)eRuR2uR3口

…口Rn。

2.5关系的闭包

-四其他性质

■定理2.11设/?是力上的二元关系。

（1）若R是自反的，则s期口SW是自反的；

（2）若/?是对称的，则侬；和胸脚是对称的；

⑶若/?是传递的，则侬混传递的。

■证明思想：根据自反，对称和传递定

义所满足的性质进行证明

■定理2.12设/?是/上的二元关系。

(i)rs(R)=sr(R)

(2)rt(R)=tr(R)

(3)ts(R)?st(R)

公式法：等式推导；基本法

■证明：(公式法：等式推导)

■(1)右式二sr(R)

=s(R贞1/

=(R步⑺步(R少“t

=R"HR1少1不

=R少少IA

=r(R#K)

=「s(R)=左式

■证明：(公式法：等式推导)

■(2)右式二t「(R)=t(R5/

=(R5Qu(R5Au(R5Au……

n2n

/*可以证明(R5J=IAURURU...uR*/

2

=IAURURU......

=”(R)

=rt(R)二左式

■证明：(公式法：等式推导)

■(3)由于s的=/?”?-匕R根据定理26

有ts(R)3t(R),sts(R)卫st(R)。而由定理

2.11可缸均的是对称的，所以

sts(R)=ts(R)o因此国Rbst低)。

2.6等价关系与划分

-一等价关系与划分

■1定义2.12(划分)

■设/是一个集合。/白

/.=[/・・・//7o右c/A2Aj

cAj=0(ifj=l,…n,iwj)，则称片1〃

&…是/的一个划分。其中每个4

称为划分碘一个块。

■/*物以类聚，人以群分*/

■例2.21设A={a,b,c},A的子集组成的集

合：

■P={{azb}z{c}}

■S={{a\{b},{c}}

■T={{a,b,c}}

■U={{a},{c}}

■V={{a,b},{b,c}}

■W={{a,b},{a,c}z{c}}

■P,S,T是A的划分，其他不是A的划分。

-2划分的块数可以是无限的

■例2.22：整数I的划分：

■冗1={已0},其中E为偶数集，0为奇数集；

■兀2={{0},{T,1}，{-2,2},{-3,3},……}也

是I的一个划分。

■3定义2.13（等价关系）

■设、是/上的二元关系，若R是自反

的、对称的和传递的，则称/?是/上的等价

关系。若aRb,则称a与/T等价。

■例223设A是一个学生集合，定义A上二元

关系R:(a,b)sR当且仅当a与b同年龄.R是

等价关系.

2.6等价关系与划分

■二术语

・1定义2,14（等价类）

■设/?是/上的等价关系，对于每个

与得价的元素全体所组成的集合称为由3

生成的关于A的等价类，记为金，即白以

=仝|止4xRa},丽为该等价类的代表

JUo

6以简记为⑸

・2定义2.15（商集）

■设R是/上的等价关系，关于/?的等价类

全体所组成的集合族称为/上关于/?的商集,

记为A/R,^A/R={[a]/aeA}.

2.6等价关系与划分

■三性质

■定理2.13设/?是/上的等价关系，则

(1)对任一有de仅7；

(2)对名白/，如果a/乃，则何/=〃力

(3)对名6力，如果&勿区用则何M7=©

(4)1勿/刃=4

/*(1)根据定义的性质进行证明；*/

证明：由于/?是自反的，即3版,所以3s7。

/*(2)基本法证明；*/

证明：

/*先证明[旬=[句*/

对任一kce[a],有cRa,又由假设出?6,

根据R是传递的，必有。尺3即ce[瓦从而

⑷旦河；

/*再证明[瓦Id。]*/

对任一kce[Z>],有cRb，又由假设〃火6,

根据及是传递的，必有cRz,BPce[«],从而

[Z?上⑷；

所以⑷=[江

/*(3)反证法证明；*/

证明：没(a,b)^R,如果包n那声密假设

Ce/c[b],贝上£旬且：：£的从定义可知

cRa,cRbo由/?而对称性和传递性，必有

aRb,导致矛盾。所以[a]c[b]=0。

/*（4）基本法证明*/

证明：对任一。*%少［可，存在6使。式可。而

［瓦1=4，从而所以o

■定理2.13(1):A中每个元素所产生的等价类

都是非空的；

■定理2.13(2)(3):互相等价的元素属于同一

个等价类，不等价的元素所属的等价类没有

公共元素；

■定理2.13(4):A上关于R的商集A/R={[a]|

a^A}就是A的一个划分，[a]是该划分的一

个块.

2.6等价关系与划分

■定理2.14集合/上的任一划分可以确定/

上的一个等价关系兄

■由凝立的等价关系

X

R=(AtxAi)u(A2A2)^......

■证明/?=。1］必从442M引口...必3是

一个等价关系，即证明R是自反、对称和传

递的。

■构造性证明的思想

■例226设A={a,b,c,d,e,f}的一个划分

K={{a,b},{c,d},{e,f}}疝兀确定A上的一

个等价关系R：

■R=({a,b}x{a,b})u({c,d}x{c,d})u({e,

f}X{e,f})

■={(a,a),(a,b),(b,a),(b,b),(c,c),(c,d),

(d,c),(d,d),(e,e),(e,f),(f,e),(f,f)}

■定理2.15设&和/?2是/上的等价关系,

/?2=/?2<±>A/Rt=A/R2o

■定理2.13和定理2.15:任一等价关系唯一确

定一个划分.

■定理2.14和定理2.15:任一划分唯一确定一

个等价关系.

■定理2.16设4和/?2是/上的等价关系，

则是/上的等价关系。

■例:设人={1,2,3,4,5},A上的二元关系R

中，有多少个是等价关系？

■因为等价类划分和等价关系是一一对应的,

所以A上的二元关系中等价关系的个数等于

A的划分个数。

■西安交通大学1998考研

解：对于4的划分可分为如下几种情况:

（1）划分成5个都只含1个元素的块，共有1种;

（2）划分成1个都只含2个元素,3个都只含1个元素的

块，共有其种;

（3）划分成2个都只含2个元素,1个都只含1个元素的

块，共有15种；

（4）划分成1个都只含3个元素，2个都只含1个元素的

块，共有其种;

（5）划分成1个都只含3个元素，1个都只含2个元素的

块，共有其种;

（6）划分成1个都只含4个元素，1个都只含1个元素的

块，共有5种；

（7）划分成1个都只含5个元素的块，共有1种；

综上所述，4上的等价关系共有1+10+15+10+10+5+1=52

2.6等价关系与划分

■四、划分的积

■定义2.16（划分的积）

设a和&是/上的等价关系，由&和4

确定力的划分分别为犯和孙，力上的等价关

系&C/?利定的划分，称为有与犯划分的积，

记为兀1•兀2。

■例：/是学生集合，&是/上的同年级关系，

&是力上的同专业关系。则&C&是/上的同

年级并且同专业的关系。

■定义2.17（细分）

设商口力是力的划分，若万'的每一块

包含在溜一块中，称万'细分%，或称%'

加细须

■例：A是学生集合，乃是在A中按学院的划

分，一是在/中按专业的划分。

■定理2.17

设府口乃'是A的划分，它们确定力上的

等价关系密口/?’,则/细分〃当且仅当/?'=兄

例：A是学生集合，乃是在A中按学院的划分，

兀'是在/中按专业的划分。万和万'确定力上

的等价关系R和/?'分别是同学院同学关系和

同专业同学关系，R七R。

■证明：

■/*»细分万=>R七R,基本法*/

■对于任一(a,b)£R',存在k的某块S,使a,

beSo因为-细分兀，所以必存在一块S,

使S'QS。因此a,beS,从而(a,b)eRo

■/*R'=Rn»细分万*/

■设S'是是的一块，a^S'则

S,=[a]^={x|xR,a}o对S中的每一个x,因

为R'cR,所以由xR'a可推出xRa。因此

J即兀’的

，{x晶|xR包a含}在o{兀x|的xR一a馥},中，[/a]以R^/Z疝[a]分Rzo心

■定理2.18(犯•犯与犯和犯的联系)

设犯和物是/的划分，则

(1)兀1•犯细分有和兀k

(2)设%'是/的划分，若k细分与和万?

则一细分犯•犯。

■/*7rz,犯细分々和万2；并且是同时细分句和

犯的最小划分(划分块数最少)*/

■证明：

■(1)由RicRziRi,RicRziR2，即得。

■(2)若R匕Ri，R匕Ft2则R匕Rgl%即得。

■例2.27设学生集合A={a,b,c,d,e,f,g,h,i,j,

k}，

按同年龄分为一组，得A的划分：

={{a,b,c,d},{e,f,g},{h,i},{j,k}}。

按同班级分为一组，得A的划分：

兀2={{a,b,c,h},{d,i},{e,f,j,k},{g}}。

7C={{a,b,c},{d},{e,f},{g},{h},{i},{j,k}}

同一组内任两个学生既在同年龄组中，又在

同班级组中。

不在历,犯同一组中的两个学生，还可能在同

一年龄组中或同一班级组中。

■五、划分的和

■定理2.19

设a和&是/上的等价关系，则阳

是/上的等价关系。

■定义2.18（划分的和）

设a和&是/上的等价关系，由&和&

确定力的划分分别为犯和犯，力上的等价关

系外”？2/所确定/的划分称为犯和犯划分

的相，记为吗+兀2。

■定理220

设町和々是/的划分，则

(1)诙与犯细分有十兀2、

(2)设乃'是/的划分，若犯和犯细分k,

则诙々细分。

■为+犯被々与犯细分，并且是同时被町与犯

细分的最大划分(划分的块数最多)

■证明：

■⑴由a/?后火即得.

■(2)若/?&■*,&=*则次2=*,由闭包定

义的第三条件可知阳”?引七7?’，即

阳口4/是包含的最示的等价关系.

■例228在例227中，学生集合的划分为兀1,

九2，

■兀1+兀2={。,b,c,d,h,i},{e,f,j,k}}

■在兀i+叫同一组中的任两个学生不是在兀i中,

就是在兀2中，不在兀1+兀2同组中的任两个

学生必定不在同一年龄组中，也不在同一

班级组中。

■定理221

设集合4对于劣b^A,a,除兀1+兀2

的同一块中，当且仅当在/中存在元素序列

a,c»…，加b,使得序列中每相邻两个元

素在犯的同一块中或在孙的同一块中。

■证明：由犯+犯的定义可知，a,白在有子犯

的同一块中，对应于由

定理29知，存在正整数k+1,使

3(%3犷1优即存在k个元素金…/c6A,

施a(RiuR2)c>c葭RiuR^b。因为/?’R2

是力上的等价关系，所以在有或犯的同

一块中，…，分白在々或犯的同一块中，a

和白是链接的。反之亦然。

2.7次序关系

■一偏序关系、偏序集

■定义2.19（偏序关系）

设R是/上的二元关系，若/?是自

反的、反对称的和传递的，则称是/上

的偏序关系。又记为《（并不意味小于

等于）

常见的偏序关系：”……

■定义220（偏序集）

若集合/具有偏序关系A（或w）,

则称/为偏序集，记为为Q或CA,<）o

■哈斯图：表示偏序集。若）则结点d在

白之下；若d与白之间不存在其他元素G使d

<GCW白则在d与2之间用一线相连。

2.7次序关系

■例2.29

■例2.30

■题目类型：给出集合和集合上的二元关系，画出

哈斯图。

■判断是否正确，并说明理由。

■设Z和她集合，A是4的募集上的二元

关系，对所有STEP(A),(S,T)eR.当且

仅当|51«|71，A是偏序关系。

■/*复旦大学1999考研*/

■证明整除关系是正整数集合上的偏序关系

2.7次序关系

・二拟序关系

■定义2.21（拟序关系）

力上的二元关系/?是反自反的和传递的，称

/?为/上的拟序关系。称的处为拟序集，或记为

（4＜）。（不意味着小手）

■定理222

力上的二元关系/?是拟序的，则R必为反对称

的。

证明：反证法

2.7次序关系

■定理2.23

设/?是/上的二元关系，则

⑴若R是/上的拟序关系，则金次以是/上

的偏序关系；

(2)/?是/上的偏序关系，则是/上的拟序

关系；

■证明方法：根据定义给出的性质证明。

2.7次序关系

■三全序关系

■定义2.22（全序关系）

设袭集合力上的二元关系，如果对于/中任意两个

元素包白公，必有54白或白Wa则称//上的全序关系

（或线性次序关系）。

■定义2.23（全序集）

若集合力具有全序关系W或凡则称/为全序集或线

性次序集，记为外少或打，包。

实例：字典序

2.7次序关系

■四最大元、最小元、极大元、极小元

■定义222(最大元、最小元、极大元、极小元)

设偏序集的。)，BR,

(1)最大元、最小元

若存在一个元素白金8对所有魇口有"4"

则迎媚瑚最大元；若都有白W"则称墟耶最

小元；

(2)极大元、极小元

若存在一个元素白且在外不存在元素〃使

b#,b<b\则称求耶极大元；若在外不存在

元素〃使白z优bJ<b,则称墟耶极小元；

2.7次序关系

(3)上界、下界

若存在一个元素3Q，对所有瑞B

有"V,则称己是崩上界；对所有瑞B

宥3则称3是6的下界；

(4)上确界、下确界

若是崩上界且对8的每个上界3'

都有3W，，则称3是8的上确界(最小上

界)；若3公是崩下界且对崩每个下界3'

都有3V,则称3是8的下确界(最大下界)。

2.7次序关系

■定理2.24设偏序集的。）,BqA,若在肿存

在最大元（最小元），贝必电一。

■证明：（反证）

■定理2.25设偏序集（A,4）,BqA,在外存

在最大元（最小元）必为破大元（极小元）。

■例2.32,2.33（题目类型）

■写出集合＜=值,00的聂集％V，并画出

京需时户如寸的哈斯图。

■/*北京航空航天大学1996考研试题*/

数学教育对计算机科学专业人才的培养目的

-通过教学使学生掌握进一步学习这一学科

所需要的数学知识；

■通过严格的数学训练，使学生实现思维方

式或思维过程的数学化。

思维方式的数学化

■从普通人的思维方式转向数学家工作的思

维方式：

通过对事物的抽象，运用特殊的符号

或语言系统，研究事物在空间中的数量关

系、位置关系、结构关系和变换规律，研

究具有共同抽象概念、性质的一类事物的

某些内在规律，以此指导人们从另一个侧

面去认识事物。

实现思维方式数学化的步骤

■第一阶段

通过对数学分析、高等代数、概率统

计等数学课程的学习，使学生熟悉和习惯

于使用数学语言和符号系统对研究的数学

对象进行严格的分析、表述、计算和推演,

初步实现思维方式的数学化。

实现思维方式数学化的步骤

■第二阶段

数学学习转向以计算机科学为背景的离散

数学和理论计算机科学的学习，特别是通过对数

理逻辑系统的学习，使学生思维方式逐步上升为

系统的理性思维方式

■建议使用国内外优秀教材

■习题应全部作。

习题解析(内容一：关系的性质)

■关系的性质

1)举出/=々2不上关系A的例子，使其具有下述

性质：

a)既是对称的，又是反对称的；

b)既不是对称的，又不是反对称的；

c)是传递的。

解：a)R={(1,1),(2,2),(3,3)}

b)R={(L2),(2,1),(2,3)}

c)R={(1,2),(2,1),(1,1),(2,2),(3,3)}

■2)举出一个集合上关系的例子，分别适合于自反,

对称，传递中的两个且仅适合两个。

■解：A={a,b,c)

■A)R={(a,切对称，传递，不自反；

■B)R={⑶a),(b,b),(c,c),(a,奶自反，传递，

不对称；

■C)R={(a,a),(b,b),(c,c),(a,b),(b,c),(b,a),

©奶自反，对称，不传递

■24是非判断：设R和S是A上的二元关系，确

定下列命题是真还是假。如果命题为真，则证明

之；如果命题为假，则给出一个反例。

■(1)若R和S是传递的，贝URDS是传递的。

■假。R={(1,2)},S={(2,3))o

■(2)若R和S是传递的，贝URcS是传递的。

■真。反证法证明。假设RcS不是传递的，则(a,

b)eRnS,(b,c)eRnS,而(a,c)eRcS。所以(a,

b)eR,(b,C)eR；(a,b)eS,(b,C)eS；因为R和S

是传寇的,则(a,C)GR,(a,C)GS；就有(a,

c)eRnSo导致亲詹。

■(3)若R和S是传递的，贝ijRoS是传递的。

■假。R={(1,4)暇2,5)},S={(4,2),(5,3)}o

■(4)若R是传递的，则RT是传递的。

■真。反证法证明。假设RT不是传递的，则(a,

b)£R-i,(b,C)ERT,而(a,c)eRL所以(c,b)eR,

(b,a)eR；又因为R是传递的,所以(c,aRR。因

在(a,C)ERT。所以导致矛盾。

■(5)若R和S是自反的,则RuS是自反的。

■真。根据自反的性质证明。对于任意的&A,

(a,a)£&所以(a,a)£RuS。贝URDS是自反的。

■(6)若R和S是自反的，贝URcS是自反的。

■真。同理，根据自反的性质证明。对于任

意的a^A,(a,a)eR,(a,a)eS,所以(a,a)e

RnSo贝URcS是自反的。

■(7)若R和S是自反的，贝URoS是自反的。

■真。同理，根据自反的性质证明。对于任

意的a^A,(a,a)eR,(a,a)eS,所以(a,a)e

RoSo贝1JR0S是自反的。

■(8)若R是自反的，则R-i是自反的。

■真。同理，根据自反的性质证明。对于任

1

意的a《A,(a,a)eR,贝ij(a,a)eRo

■(9)若R和S是对称的，则RuS是对称的。

■真。根据对称的性质证明。对于任意的(a,

b)eRuS,则(a,b)£R或(a,b)eS；因为R和S是对

称的，所以(b,a)wR或(b,a)£S。因此(b,a)

ERUS,RDS是对称的。

■(10)若R和S是对称的，则RcS是对称的。

■真。同理，根据对称的性质证明。对于任意的(a,

b)eRnS,则(a,b)sR并且(a,b)eS；因为R和S是

对称的，所以(b,a)wR并且(b,a)wS。因此(b,a)

eRnS,RcS是对称的。

■(11)若R和S是对称的，贝URoS是对称的。

■假。R={(1,2),(2,1)},S={(2,3),(3,2)}o贝U

RoS={(l,3)}o

■(12)若R是对称的，则RT是对称的。

■真。根据对称的性质证明。对于任意的(a,b)£

RT,(b,a)eR;因为R是对称的，则(a,b)eR;所以

(b,a)eR-i。则RT是对称的。

■(13)若R和S是反对称的，则RuS是反对称的。

■假。R={(1,2)},S={(2,1)},则RuS={(l,2),(2,

l)}o

■(14)若R和S是反对称的，贝URcS是反对称的。

■真。反证法证明。设RcS不是反对称的。则存在

(a,b)eRnS,(b,a)eRnS,awb。则(a,b)eR,(b,

a)eR,与R是反对称的矛盾。

■(15)若R和S是反对称的，贝ijRoS是反对称的。

■假。R={(1,3),(2,4)},S={(3,2),(4,1)},则

RoS={(l,2),(2,1)},不是反对称的。

■(16)若R是反对称的，则RT是反对称的。

■真。反证法证明。设RT不是反对称的。则存在(a,

b)eR-i,(b,a)eRT,awb。贝炳b)eR,(b,a)eR,

与R是反对称的矛盾。

习题解析（内容二：等价关系）

■1）设%和/?2是/上的等价关系，G和Q分

别是力中关于&和&的划分。

证明：七改2,当且仅当G中的每个等价

类是包含手Q的一些等价类之中。

/*证明思想：划分与等价关系：由凝立的等

价关系/?=血必2人/出必幺口.7M/

习题解析(内容二)

■2)设/?是/上的二元关系，S={(a,b)|对

于某一c,有⑶b)eR,(b,c)eR},证明如

果/?是/上的等价关系，则毙力上的等价关

系。

■/*证明思想：证明S是等价关系，即证明S

是自反的，对称的和传递的。*/

习题解析(内容二)

■3)设&和R2是A上的等价关系，试确定以

下各式，哪些是A上的等价关系，对不是

的式子，提供反例。

a)(AxA)-Rp

b)Ri-R2；

c)RJ;

d)r(RrR2).

思想：判断是否自反、对称和传递

■2.19确定下列各式是不是A={1,2,3,4,5}上的等价

关系，如果是等价关系，请写出它的等价类。

■(1){(1」),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(1,5),

(5,1),(3,5),(5,3)}

■是

■等价类为：

■[1]=[3]=[5]={1,3,5)

■⑵={2}

■[4]={4}

⑵{(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(3,4),(4,3)};

不是.因为(1,3),(3,4)ER,而(1,4)任R.

(3){(1,1),(2,2),(3,3),(4,4)};

不是.因为A={1,2,3,4,5},而(5,5)任R

(4){(己力)|4整除上13}内,13£8

是

[1]=[5]={1,5},[2]={2},[3]={3},[4]={4}

(5){(a,b)|3整除a+b},a,b£A;

不是.

因为A={1,2,3,4,5},而1+1不能被3整除，故(1,1)任R

(6){(a,b)|a整除2-b},a,bwA。

不是.

因为A={1,2,3,4,5},而5不能整除2-5。3,故(5,5)任R

■2j£型E号些的传递和自反关系，设T是A

A史益言关系：(a，b)$T当且仅当(a,b)和

(b,a)都属于R,证明丁是一个等价关系。

■证明:(注意,T是A上的二元关系.)

■(1)自反：对任意&A,(关键证明(a,akT)；

因为R是A上的自反关系，所以(a,akR,

(a,a)eR,因此根据T的定义，有(a,a)£「

■(2)对称:若(a,b)£T,则(a,D)和(ba)都属于

R,因此(b,a)和但,和都属于R,所以(b,a)£「

■(3)传递：若(a,b)£T,(b,c)—(关键证明(a,c)〃，

即要证明(a,c)£R,(c,a)£R)°由于(a,b)cT,(b,c)£T,

则(a,b)和(b,a)都属于于(b,c)和(c,b)都属于于因为

R传递，所以当(a,b)和(b,c)都属于R时，有(a,c)属于

R,同样当(b,a)和(c,b)都属于R时，有(c,a)属于R。

因为(a,c)£R,(c,a)£R,所以为,C)ETQ

■2.23设R是一个二元关系，设S={(a,b)|存在

某个c,使(a,c)£R且(c,b)£R}。证明如巢R是

一个等价关系则S也是一个等价关系。

■证明：

■(1)自反:对任意&A,(证明(a,a)£S)。因

为R是A上的自反关系，所以(a,akR,

(a,a)eR,因此根据S的定义，有(a,a)£S,

■(2)对称:若(a,b)£S,则存在“A,使得(a,c)

和(c,b)都属于R,因%R对称，因此(c,a)和

(b,c)都属于R,即(b,c)和(c⑶都属于R,故根

据S的定义，有(b,a)£S。

■(3)传递：若(a,b)$S,(b,c)sS(关键证

明(a,c)eS,即要证明存在WA,使得(a,d)和

(d,c)都属于R)o由于(a,b)eS,所以存在

eeA,使得(a,e)和(e,b)都属于R,同样因为

(b,c)eS,所以存在"A,使得(b,f)和(f,c)

都属于R,因为R传递，所以当(a,e)和(e,b)

属于R时,有(a,b)eR,当(b,f)和(f,c)属于

R时,有(b,c)GR,现在(a,b)和(b,c)属于R,

根据S的定义，有(a,c)eSo

■2.24设R是A上的一个自反关系，证明R是一

个等价关系当且仅当若(a,b)eR,(a,c)eR则

(b5c)eRo

■证明:(1)R是一个等价关系，则当(a,b)£

R,(a,c)£R必有(b5c)eR(要说明的是，在

包力)£艮但©£区前提下导出(1)©£阳。若当

(a,b)£R,(a,c)£R,(要证明(b5c)eR),因为R对

称，所以当(a,b)£R时，有(b,a)£R,因为R传递,

所以当(b,a)£R,(a,c)£R时有(b,c)£R.

■(2)R是A上的一个自反关系，当(a,b)£R,(a,c)£RM

有(b,c)£R,证明R是等价关系

■自反:条件已知；

■对称：若(a,b)£R,因为R自反S,故(a,a)£R,现在

(a,b)eR,(a,a)eR,则根据条件(b,a)eR；

■传递：若(a,b)£R,(b,c)£R

(关键证明(a,c)£R,注意与条件不同，当

(a,b)eR,(a,c)eR必有(b,c)eR,而要证明的是

(a,b)GR,(b,c)GR导出(a,c