第二章關系

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},pb5rztd,{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