洪帆《離散數(shù)學(xué)基礎(chǔ)》(第三版)課后習(xí)題答案

第1章集合

1、列舉以下集合的元素

(1)小于20的素?cái)?shù)的集合

(2)小于5的非負(fù)整數(shù)的集合

(3)一101—24<0且5WiW15}

答：(1){1,3,5,7,11,13,17,19]

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

(3)(5,6,7,8,9,10,11)

2、用描述法表示以下集合

(1){4，生，%，％，6}

答：{az.|IG7,1</<5}

⑵{2,4,8,??}

答：{25wN}

(3){0,2,4,..100)

答:{2"ieZ,0WiW50}

3、卜面哪些式子是錯(cuò)誤的？

⑴{〃}￡{{〃}}答：正確

(2){a}q[{。}}答：錯(cuò)誤

(3){〃}￡({〃},〃}答：正確

(4)答：正確

4、已給S={2,出⑶,4}和/?={{〃},3,4』},指出下面哪些論斷是正確的?哪些是錯(cuò)誤的？

(1){〃}￡S錯(cuò)誤

⑵正確

(3){々,4,{3}}±S正確

(4){{0,1,3,4)三大正確

(5)R=S錯(cuò)誤

(6){a}=S正確

(7){a}qR錯(cuò)誤

(8)正確

(9)?？趝{〃}}qR正確

(10){掰土S錯(cuò)誤

(11)錯(cuò)誤

(12)(q{{3},4}正確

5、列舉出集合AB,C的例子，使其滿(mǎn)足AEB,BwC且A任C

答：A={a}f6={{〃}},顯然AcB,C={{{〃}}},顯然BwC,但是/UC。

6、給出以下集合的新集

(1)Mb}}

答：幕集{。,{〃},{{0}},{&{〃}}

⑵{點(diǎn)?{〃}}

答：幕集{0,{。},⑷,{{0}},{4°},{0,{a}},{4{』},{，,〃,{〃}}}

7、設(shè)4={〃},給出A和2A的箱集

答:2A={私⑷}2J{我{⑷},{{〃}},0{〃}}}

8、設(shè)A={qM2,…‘4}由％和4所表示的A的子集各是什么?應(yīng)如何表示子集{生外,的}

和{4,4}

答:Bl7=5(X)010001={。4'%}

{。2口6，%}=8()1000110=%'{%，%}=510KxMXX)=^160

9、設(shè)。={1,2,3,4,5},9={1,4},9={1,2,5},9={2,4},確定集合:

(1)Ac9(2)(AcB)uC'(3)Au(BnC)(4)(4DB)C(ADC)

(5)(Ac6)'(6)ALE(7)(B^cy(8)6'cC(9)2A-2c(10)2八c20

答：(1)B'={3,4},Ac&={4}

(2)Ac3={l},C={1,3,5},(AC3)DC'={1,3,5}

(3)BnC={2),AD(3CC)={1,2,4}

(4)AD8={1,2,4,5},ADC={1,2,4},(AUB)C(ADC)={1,2,4}

(5)(Ac8)，={2,3,4,5}(6)4={2,3,5},AD9={2,3,4,5}

(7)BuC={l,2,4,5},(BuC/={3}

(8)8'={3,4},C={1,3,5},B,r>C={3}

(9)2'={我{1},{4},{1,4}},2C={^{2},{4},{2,4}},2A-2C={{1},{1,4})

(10)24n2c={^,{4}}

10、給定自然數(shù)集N的以下子集：

A={1,2,7,8),8={“/<50},C={i|i可被3整數(shù),0</<30}

求以下集合：

(1)A535CU。))

答：3={1,2,3,4,5,6,7},

C={0,3,6,9,12,15,18,21,24,27,30},D={1.2.4.8.16,32.64)

(2)4c(Bc(CcO))二°

(3)B-(AuC)

解:AuC={0,1,2,3,6,7,8,9,12,15,18,21,24,27,30},-Q={4,5}

(4)(AcB)uO

解：Ac8=8—A={3,4,5,6},(Ac8)uO={1,2,3,4,5,6,8,16,32,64}

11、給定自然數(shù)集N的以下子集

A={n\n<\2},^={/?|/?<8},C={n\n=2k,kN]tD={n\n=3k.keN}

將以下集合表示為由A8,C,O,E產(chǎn)生的集合：

(1)(2,4,6,8)(2)(3,6,9)(3){10)(4){〃|〃=3或〃=6或鹿之9}

(1)假設(shè)AcB=4cC,那么B=C

答：不正確，反例，設(shè)A=”,那么不管伐。是什么集合，都有AcB=AcC=。，但顯然

B,C不一定相等。

(2)當(dāng)且僅當(dāng)有AqB；

答：正確，證明如下：假設(shè)=那么對(duì)VQWA,有awAuB=B,那么有awB,

因此有AqB。反之，假設(shè)A=那么=8顯然成立。

(3)當(dāng)且僅當(dāng)Ac3=A,有AqB

答：正確，證明如下：假設(shè)AcB=A,那么對(duì)VawA,因此awAcB,那么awB,那么

有AqB。假設(shè)AqB,那么VawA,有awB,因此由OEA,可以得出aw4c4,因此

A(^Ar\B,又AcBqA,有Ac8=A。

(4)當(dāng)且僅當(dāng)AqC,有Ac(B—C)=。

答：不正確，因?yàn)?c(8-C)=Ac3cC,因此不一定需要滿(mǎn)足AqC,而假設(shè)AcB=。

也可以滿(mǎn)足。例如：A={o,b,c},B={d,e},C={〃,0,Ac(3-C)=。成立，而A=C不

成立。

(5)當(dāng)且僅當(dāng)BqC,有(4-8)uC=A

答：不正確，因?yàn)榧僭O(shè)B=有(A-5)=C=4成立，但是反之不成立，反例如下：

A={1,2,3,4,5},B={1,6),C={1,2),而A-3={2,3,45},(A-B)uC={1,2,3,45),但是

8qC不成立。

14、設(shè)A8,C,O是集合，下述哪些論斷是正確的？哪些是錯(cuò)誤的？說(shuō)明理由。

(1)假設(shè)那么AuCc(8u。)

答：正確，證明：對(duì)VacADC,那么。￡4或。6(7,因?yàn)?口8,?？?。，因此?！?或aw。，

因此〃￡“口力，即47。工(87。)成立。

(2)假設(shè)4a5,CqO,那么AcCq(Bca)

答：正確

(3)假設(shè)Au3,Cu。，那么A=Cu(8u。)

答：正確

(4)假設(shè)Au員CuD,那么AcCu(3cD)

答：不正確。例如假設(shè)Au區(qū)CuD,但是AcC=0,BcO=°,那么0=AcCq(6cO)=°。

15、設(shè)A8是兩個(gè)集合，問(wèn)：

(1)如果A—4=A,那么A和8有什么關(guān)系？

答：因?yàn)?一笈=笈，而A—B=AcM=B,即對(duì)WOEB有A〃e3',因此A=3=°。

(2)如果A—3=8—A,那么A和3有什么關(guān)系？

答：充要條件是A=8。證明：因?yàn)?—3=8—A的(4—B)uA=(B—4)uA,從而有

A=A<JB>即AqB,同理可證明區(qū)qA,因此4=A。

16、設(shè)A3是任意集合，下述論斷哪些是正確的？哪些是錯(cuò)誤的？說(shuō)明理由。

⑴2"。=2八"

答：不正確。例如A={a,/?},B={b,c}?那么={g/?,c}

2人={4{〃},{〃},{。力}},2嗔{么{〃},{<,}的?}

顯然不成立。

⑵2s8=2Ac2^答：成立。證明：對(duì)VC￡2八c2“，那么C￡2人且C￡2^,那么CqA,C工8,

那么C^AcB,因此。反之，假設(shè)X/CW2ACB,那么c=4c8,那么CqA且CqB,

因此。￡2狐且Cw2j因此。￡2，'C2J即2叱8=2入門(mén)28。

(3)2*=(2八)’

答：顯然不成立，因?yàn)樽筮吋峡隙ê?。，而右邊不含有?/p>

17、在一個(gè)班級(jí)的50個(gè)學(xué)生中，有26人在離散數(shù)學(xué)的考試中取得了優(yōu)秀的成績(jī)；21人在

程序設(shè)計(jì)的考試中取得了優(yōu)秀的成績(jī)。假設(shè)有17人在兩次考試中都沒(méi)有取得優(yōu)秀成績(jī)，問(wèn)

有多少人在兩次考試中都取得了優(yōu)秀成績(jī)？

答：分別用A3表示在離散和程序設(shè)計(jì)的考試中取得優(yōu)秀成績(jī)的學(xué)生集合，U表示全體學(xué)

生集合：那么#(A)=26,#(3)=21,#(AuB)=50-17=33,那么兩次考試中都取得了優(yōu)

秀成績(jī)的學(xué)生人數(shù)為26+21-33=14人。

18、設(shè)A&C是任意集合，運(yùn)用成員表證明：

(1)(AD3)C(A'DC)=(ACC)5A'C8)

證明：

ABCArAr^CA^B4cCAc笈左邊右邊

0001100000

0011100000

0101110111

0111110111

1000010000

1010111011

1100010000

1110111011

(3)4—(BuC)=(4—B)c(A—C)

證明：

ABcA-BA-C(A-B)n(A-C)BDCA-(BuC)

00000000

00100010

01000010

01100010

10011101

10110010

11001010

11100010

由上得證左右兩邊相等。

19、由S和7的成員表如何判斷s=r?應(yīng)用成員表證明或否認(rèn)

答：先分別給出集合(AD3)C(5DCY和Ac9的成員表如下:

ABcA^)BBuC(Bucy(AuB)n(BuCyB'Ac?

00000i010

001010010

010110000

011110000

100101111

101110011

110110000

111110000

觀察上述表格，我們發(fā)現(xiàn)(ADB)c(BuCy所標(biāo)記的列中，僅在第五列為1,這意味著當(dāng)元

素〃w4,“促B且〃任C時(shí)，〃W(ADB)C(8DC)',而在其他情形下，元素

”(AuB)c(BuCy。而集合Ac8所標(biāo)記的列中,第五和第六行均為1,這意味著

〃eA〃史Z?且〃任。時(shí)，〃eAc3',當(dāng)〃?A,〃信/?,且時(shí)，也有〃EAC"。所以當(dāng)

兀素〃￡(ADB)C(4DC)'時(shí)也有“￡AC8’，反之不然，因此(AuB)c(BuC)'qAc3'成

立。

20、A，4,…,4為U的子集，A，4,…,4至多能產(chǎn)生多少不同的子集？

答：構(gòu)造由4,4，,4所產(chǎn)生的集合的成員表，顯然該成員表由2,個(gè)行所組成。在該成員

表中不同的列可由2「為的二進(jìn)制數(shù)0000-11111分別表示，而不同的列所標(biāo)記的集合

不相同的，因此由4,4,…,A.至多可以產(chǎn)生27個(gè)不同的集合。

21、證明分配律、等尋律和吸收律9'

1分配律Ac(3uC)=(AcB)u(4cC)

證明：對(duì)€Ac(3uC),那么有aeA且4￡即有且或aeC,也即

有asAc8或AcC,即ae(Ac3)u(AcC),因此左邊q右邊。

對(duì)Va￡(AcB)D(AcC),那么4cAe3或awAcC,即A且awB,或a￡A且。GC,

即有awA或awBuC,因此awAC(8DC),因此右邊q左邊。

2吸收律Ac(Au8)二A

證明：Ac(Au8)=A顯然成立，對(duì)4,那么顯然有ae因此有aw4clAD8),

因此有AuAc(AuB)成立。

22、設(shè)A氏C是任意集合，運(yùn)用集合運(yùn)算定律證明：

(1)55(AU5)CA)'=U

左邊=8u(AuB)"A

證明：=8U(ACB')D4=BD((4UA)C(A'DB))

=8D(UC(AD8))=8U(AD8)=U=右邊

(2)(Au區(qū))C(3UC)C(CUA)=(AC4)D(NCC)D(CCA)

左邊=(3u(AcC))c(C7A)

、『目=((CU4)CB)U((CD4)C(ACC))

證明：

二(CCB)5BCA)5(ACCCA)U(ACCCC)

=(Cc8)u(8cA)u(AcC)u(AcC)=右邊

(3)(AD3)C(3DC)C(ADC)=(AC3)5/VC3CC)5AC3'CC)

右邊=(2/c((A'cC)JA))U(Ac8'cC')

二(BC(A'DA)C(ADC))D(ACB'CC)

二(8C(AUC))5AC8'CC)

、〒口口二(8cA)D(3CC)U(4CB'CC)

證明：，

,

=(BnC)u(An(<(Br>C)uB))

二(BCC)5AC(3'UB)C(BUC))

=(BnC)o(An(BuC))

=(8cC)5AcB)5AcC)

由上題的證明可知左邊二右邊，得證。

23、用得摩根定律證明(ACQ)D(AC(3DC))補(bǔ)集是(AD8)C(ADE)C(AUC)。

((AC3')5AC(8UC')))’

=((4cBry)c(Ac(Buc)y

證明：=(A'DB)C(A53UC')')

=(A'DB)C(AU(B'CC))

二(Ai」B)c(4IJB')c(4ijC)

24、設(shè)A,為某些實(shí)數(shù)的集合，定義為

試證明：(JA=A)

1=1

證明：設(shè)。,那么比存在整數(shù)3使得?！陜?，因此有r/＜1--,于是,因此。G4)0

i=\%

另一方面，設(shè)QE4,那么有。＜1，假設(shè)。＜0,那么有4,因此。。假設(shè)0＜。＜1,

1]+1,其中表示_L的整數(shù)局部，那么有上〉1

那么令b=l-a,a=l-b=\

㈤b%

因此。=1-，7＜1—，即〃￡人,于是。因此得證。

%kr=l

25、設(shè)｛&&，…,4｝是集合A的一個(gè)分劃,試證明AcB,4c&4cB中所有非空集合

構(gòu)成AcA的一個(gè)分劃。

證明：因?yàn)椋?「4,…,AJ是集合A的一個(gè)分劃，因此由分劃的定義，可得Od=A,且

rr

4c4=0，iH),而(AcB)c(Ac8)=0，iwj，且U(Ac8)=(UA)cB(分配律)=AcB,

J=1r=l

因此4c民A2c民，c。中所有非空集合構(gòu)成Ac8的一個(gè)分劃o

26、〃個(gè)元素的集合，有多少中不同的方法可以分劃成兩塊？

答:當(dāng)〃奇數(shù)時(shí)有C+c；++C^T種不同的方法，當(dāng)〃為偶數(shù)時(shí)有C；+C；+…種不

同的方法。

第2章關(guān)系

1、假設(shè)A={0』},8={1,2},確定集合：

(l)Ax{l}xB(2)A2XB(3)(BxA)2

解：Ax{1}xB={(0,1,1),(0,1,2),(1,1,1),(1,1,2)}

2、在通常的具有X軸和Y軸的笛卡爾坐標(biāo)系中，假設(shè)有

試給出笛卡爾根Xxy的幾何解釋

解：表示橫坐標(biāo)x的范圍在-3?工42,縱坐標(biāo))，的范圍在-2W)，W0的二維點(diǎn)集所構(gòu)成的集

合。

3、設(shè)A,B,C和D是任意的集合，證明

(1)4x(BnC)=(AxB)n(AxC)

(2)Ax(B-C)=(AxB)-(AxC)

(3)(AcA)x(CcO)=(AxC)c(3cO)

證明：(3)首先，因?yàn)?CcD=C,所以

類(lèi)似地，(Ac8)x(CcQ)q8x。，所以有：

反之，假設(shè)(工,y)w(AxC)c(8x。)，那么(x,y)w(4x。)，(x,y)e(BxD)

那么且即XEACB,yGCnD

所以，(x,y)e(4cB)c(Cx。)

所以(AxC)c(3xD)三(AcB)c(Cx。)

所以(Ac8)x(Cc￡>)=(AxC)c(8c。)

4、對(duì)以下每種情形，列出由A到B的關(guān)系0的元素，確定0的定義域和值域，構(gòu)造。的

關(guān)系矩陣：

(1)A={0,l,2},B={0,2,4},p={(a,〃)|a〃￡Ac8}

解：AnB={073),1P=1=1(0,0),(0,2),(0,4),(1,0),(2,0),(1,2)}

關(guān)系矩陣M『=110

(2)4={1,2,3小},食=岷2,3},夕={"|。=從}

解:p={(l,l),(4,2))

關(guān)系矩陣M廣(100]

5、設(shè)4={1,2,3/,@,6。，期以下每一種情形，構(gòu)造A上的關(guān)系圖，并確定「的定義域和值

域00°

(1)"川飛00

解：圖略'

2=A,

定義域。Rp=A

(2)夕={(仃)|灌陶}

解:2={(1,1),(1,2),(1,3),(1,4)05),(1,6),(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}

定義域。夕=4,R,=A

(3)夕={?,力I遢/的倍數(shù)}

解:。={(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(2,1),(31)

定義域，如陽(yáng)46,1)礙縱<6,2),(6,3)}

(4)p={(ij)\i>j]

解：。={(6,5),(6,4),(6,3),(6⑵,(6,1)

定義域出身翕聞?dòng)葘O(孫L(5,4,3,2,1)

⑸P={磔*中"』)

解:定義圖隔門(mén)'{&4,3,2,1},(二{6,5,4,3,2}

(6)P={GJ)|UJ,Z/<10)

解:9={(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,2),(2,3)

定義域。給4M5⑷?刀,(3,&國(guó)6遂陽(yáng)斗矽)),(6,1)}

⑺p={(z,J)|z*J,(Z-j)2eA)

解:p={(l,1),(1,2),(1,3),(2,1),(2,2),(2,3),(2,4),(3,1)

定義域。夕移孫(初(見(jiàn)4),(3,5),(4,2),(4,3),(4,4),(4,5)

(8)夕={&?陟用素?cái)\”(5,5),(5,6),(6,4),(6,5),(6,6)}

解：p={(2,1),(3,1),(5,1),(4,2),(6,3),(6,2)}

定義域。夕={2,3,4,5,6},々={1,2,3}

6、設(shè)。={(1,2),(2,4),(3,3)}和夕2={(1,3),(2,4),(4,2)},試求出乃=P?㈤c.,以一和，

并證喔>(巧^^uA傷Dp\&2DpRAcp介

解:p,up2={(l,2),(2,4),(3,3),(1,3),(4,2)}

%={1,2,3},4={1,2,4},(={2,4,3},5={3,4,2}

證明：0ss尸叫

設(shè)xw/53),那么必存在y,使得(X,.y)￡g，所以(x,y)￡月或者*,y)￡自，因此，

工￡4或者工￡%,即xwD用。匕，所以。(巧“)之?

反之，設(shè)X￡Q',NOp2，那么工￡。外或者工￡。2，所以存在,，使得(尤,)￡月，或者存

在必，使得“，%)￡夕2，由并集的定義知，(乂)；)￡月-1夕2，或者",%)￡月2夕2，總之有

xG0

Dp12P”故外2DQCD"p"

證明:RidR外

設(shè))，￡/?/恒科，那么必存在x,使得(x,y)wg,(x,y)e0，因此人eR巧且〃e%,，由交集的

定義bwRQR^,故R*心后R，QRc。

7、A1和4是分別具有基數(shù)%和〃2的有限集，試問(wèn)有多少個(gè)A到4的不同關(guān)系？

答：AX4的所有子集都是用到A2的一個(gè)關(guān)系，所以共有2"岫心個(gè)不同的關(guān)系。

8、找出集合A=…，牝}上普遍關(guān)系和恒等關(guān)系的關(guān)系矩陣和關(guān)系圖的特征。

答：A上的普遍關(guān)系o=A?的關(guān)系矩陣是全1矩陣，而恒等關(guān)系的關(guān)系矩陣是單位矩陣。

9、以下是集合A={0』,2,3}上的關(guān)系：自={億加/="域者)=〃2},22={(，，*，=，+2},

試確定如下的復(fù)合關(guān)系：

⑴P\，P?⑵Pi'Px(3)8/261(4)p\

解：⑴g={(0,1),(1,2),(2,3),(0,0),(2,1)},臼={(2,0)，(3,1)}

⑵￡?自={(2J),(Z0),(3,1)}

(3)A={(11)，。。).(22)}

(4)A2={(0,2),(1,3),(1JX(0,1),(0,0),(2,2))

10、設(shè)8,02,夕3是集合A上的關(guān)系,試證明：如果那么有：

(1)Px'Py^Pi'Py(2)p3-p.cp3-p2(3)p\jpz

證明：⑴對(duì)V(x,y)￡p[由復(fù)合關(guān)系的定義,3zeAf使得，([z)wp],(z,y)ep3,

因?yàn)樗?X,Z)￡"2，所以(X,y)￡〃2，所以夕I,夕3G0，夕3

(2)對(duì)V(x,y)wa，由復(fù)合關(guān)系的定義，MZEA,使得，(x,z)￡/?j>')eA?因

為Pi=Pz,所以(z,y)w夕2,所以(x,y)丘凸-金，所以夕3=03G。

(3)對(duì)W(x,y)￡P(guān)1,有(y,x)wp],因?yàn)樽怨ば?，所?卜幻^公所以。,)”02，也即

Pi￡夕2。

11、給定乃二{(0,1),(1,2),(3,4)),8,0={(1,3),(1,4),(3,3)}求一個(gè)基數(shù)最小的關(guān)系，使?jié)M足0

的條件。一般地說(shuō)，假設(shè)給定夕[和夕]?夕2，生能被唯一確實(shí)定嗎？基數(shù)最小的心能被唯一

確定嗎？

答：2={(2,3),(2,4),(4,3)}。一般地說(shuō)，假設(shè)給定乃和8?.，0不能被唯一確實(shí)定?；?/p>

數(shù)最小的02也不能被唯一確定。

12、給定集合4，4,4,設(shè)0是由A到&得關(guān)系，02和。3是由&到43得關(guān)系，試證明：

⑴自?(02")=(。"2)5。"3)

證明：根據(jù)并集和復(fù)合關(guān)系的定義，p\?(02U夕3)和(P1?P2)不(。|63)都是A到A3上的關(guān)

系，下只需要證明它們由完全相同的序偶組成。

設(shè)(a,c)￡0i?(夕2。夕3)，必存在〃E4，使得(a,b)wpi，(b,c)wp22P3,所以有(瓦。)€「2

或者S,c)e03,所以有3,c)。"或者3，c)eq63,也即3?w(8?夕2)5巧j)，也

即夕]?(.7〃3)工3.夕2)-3，〃3)；反之，假設(shè)(a,c)j3?/2)=3.，3)，也即(a,c)j

("1?0)或者(a,c)€=3。必)，假設(shè)(a,c)j(月-.2)，那么存在〃￡&?使得，

GE

(b,c)ep2,那么(a,b)wp[,(/?,c)p2up3,那么(〃,c)p1＜心，假設(shè)(。?￡(自?p1

同理可得,因此有(P[?夕2)=(。|，夕3)1Pl，(P2DR)。那么8，(。2U03)=(Pl夕2)只(。|?03)。

(2)A-(p2np3)c(p,-p2)n(p,np3)

證明：設(shè)(〃,c)￡p]?(「2cp3)，那么存在人￡&，使得,(a,b)wpi，(b,c)wp2cp3,那么

(九《)￡22，且(友。)￡03，所以(。，。)€。1?22，且(。，。)￡夕1，P3,即(4,C)￡(P1,0)C(8?23),

所以自?(02c03)=(p]-p2)C(p|CP3)。

13、給定夕={(ij)IiJw/,j-，=1},pn是什么？

答:/={???「3,-2,-1,0,1,2,3,…},p={...,(-2-1),(-1,0),(0,1),(1,2),(2,3),(3,4),-..)

"(一3,-1),(-2,0),(0,2),(1,3),(2,4),(3,5),…},那么/〃={(")|i,J€/,J-i=川

14、對(duì)第9題中的關(guān)系，構(gòu)造關(guān)系矩陣

(1)例0(2)Mpt

解:p、={(0,1),(1,2),(2,3),(0,0),(2,1)}p2={(2,0),(3,1))

⑶ro00os

解：p-p,={(2,1),(2,0),(3,1)(。0。0

2A/=

15、設(shè)A是有〃個(gè)元素的有限集,3是A*的啜臬，°試證明必存在兩個(gè)正整數(shù)AJ,使得

"=P'0.0100

證明：因?yàn)橄κ茿上的關(guān)系，所以對(duì)于任意正整數(shù)〃，p’也是A上的關(guān)系，另一方面，因

為#(A)=〃，所以#(AXA)=〃2,#(2,“八)=2收加八)=2'「，也即A上只有2"個(gè)不同的關(guān)系，

因此在關(guān)系，…,02,夕2匕1中必有兩個(gè)是相同的，也即存在兩個(gè)正整數(shù)使得

pk=p',其中I4U42/+1。

16、設(shè)0是由A到B的關(guān)系，0是由B到C的關(guān)系，試證明"「a=XV8。

證明：由題設(shè)知道和P2-g都是由C到A的關(guān)系，因此只要證明它們由完全相同的序

倡組成。設(shè)(c，a)￡Qi?22，那么(。，。)￡外夕2,因此必存在元素此3，使得他力)€自,

e，C)2,所以，(。,。)￡小，所以(CM)W/Y。。反之，設(shè)(CM)W%Pl，那么

必存在元素加￡8,使得《,//)￡■，(阮。)￡01,所以(。萬(wàn))￡。1,&,c)e/?2,所以

9,c)wp\?p2,所以(c,a)ep]?02，所以自。2=。2,8。

17、(1)設(shè)Pl和02是由A到8的關(guān)系，問(wèn)P]=P|U0成立嗎？

答：成立

(2)設(shè)P是集合4上的關(guān)系，如果°是自反的，那么。一定是自反的嗎？

答：是的。證明：假設(shè)p是自反的，那么對(duì)所有的?！?,有(。間)ep,那么一定有(a,a)Gp,

那么萬(wàn)也是自反的。

(3)假設(shè)0是對(duì)稱(chēng)的，那么。也是對(duì)稱(chēng)的嗎？答：是的。

(4)假設(shè)夕是可傳遞的，那么萬(wàn)也是可傳遞的嗎？答：是的

證明：假設(shè)「是可傳遞的，由定義可知，假設(shè)(x,y)￡0,(y,z)e/9,那么一定有(x,z)￡;9,

由逆關(guān)系的定義，也即，假設(shè)(m/)￡萬(wàn)，(Z,y)￡萬(wàn)，一定有(z,x)e萬(wàn)，，那么。也是可傳

遞的。

18、圖2?9給出了集合{12345,6}上的關(guān)系夕的關(guān)系圖，試畫(huà)出關(guān)系爐和爐的圖，并利用

關(guān)系圖求出關(guān)系0的傳遞閉包。

解：

圖2-9

關(guān)系夕={(1,3),(1,5),(2,5),(4,5),(5,4),(6,3),(6,6)}

因?yàn)橄?=夕2，所以夕5=03,p8=p2

傳遞閉包F+=p2P'2p、

19、試證明：假設(shè)「是基數(shù)為〃的集合A上的一個(gè)關(guān)系，那么夕的傳遞閉包為A=0"

證明：由定義，=Y〃，要證明X"二z",因?yàn)樗灾灰C明

即可。設(shè)(。,與Gup1,那么必存在‘正整屐&，使得(。力)€”,假設(shè)ZWn,那么(〃向G，

假設(shè)〃>〃，那么在A中必存在4-1個(gè)元素4,氣,…,a*’使得：

因?yàn)槿?gt;〃，所以在a,4,%,…必…/這Z+1個(gè)元素中心有兩個(gè)元素%=%(0<r<t<k,

記〃為喝，記〃為黑)，因比下述關(guān)系

成立，這說(shuō)明年ki=k-Q-r),k\〈k。假設(shè)占>〃，用類(lèi)似的方法又可找到&<匕，

便…，最后必可找到一正整〃，使C7//Z?且〃<〃，因此(〃/)￡,故。

202以正善系中哪一個(gè)是自反的、對(duì)稱(chēng)的、反對(duì)稱(chēng)的或者可傳遞的？，=，

(1)當(dāng)且7又當(dāng)|%-，2區(qū)時(shí)，有歷2；

答：是自反的，對(duì)稱(chēng)的，非可傳遞的，例如13P9,9pl,但13夕1不成立。

⑵當(dāng)且僅當(dāng)〃g〉8(〃”％￡N)時(shí)，有4a2；

答：非自反的，因?yàn)镮pl不成立，但kN。對(duì)稱(chēng)的，非可傳遞的，因?yàn)?川0,1002,但

是1夕2不成立。

(3)當(dāng)且僅當(dāng)斗S弓|(斗,0wR)時(shí),有KPG。

答：自反的，非對(duì)稱(chēng)的，非可傳遞的，因?yàn)?0(-8),-80,但是5Pl不成立。

21、設(shè)q和0是集合4上的任意兩個(gè)關(guān)系，判斷以下命題是否正確，并說(shuō)明理由：

(1)假設(shè)夕?和0是自反的，那么0].22也是自反的：

答：正確。因?yàn)?和夕2是自反的，因此對(duì)任意A，有apw，ap2a,因此年g。，所以0,P2

也是自反的。

(2)假設(shè)乃和0是非自反的，那么8也是非自反的；

答:錯(cuò)誤；例如A={a,〃,c},pt={(a9a),(b,b),(c,a)},0={(4〃),(4b),(〃,c)},p1和凸都

是非自反的，但是8?02=3,〃),(")}是自反的。

(3)假設(shè)P[和夕2是對(duì)稱(chēng)的,那么01，夕2也是對(duì)稱(chēng)的;

答：錯(cuò)誤，設(shè)A={〃/,(?},"]={(〃,/?),SM)},0={(〃,c),(c,a)},顯然P]和02是對(duì)稱(chēng)的，

但是夕I,p2={S?}是非對(duì)稱(chēng)的。

(4)假設(shè)Pl和22是反對(duì)稱(chēng)的，那么?夕2也是反對(duì)稱(chēng)的;

答:錯(cuò)誤，設(shè)4={凡仇c},Pl={(〃/),(")},夕2={S，c)，(c，a)}，顯然Pl和22是反對(duì)稱(chēng)的，

但是Pi={(a，c)，(c，。)}不是對(duì)稱(chēng)的。

(5)假設(shè)q和0是可傳遞的，那么也是可傳遞的；

答：錯(cuò)誤,設(shè)A={a〃,c},a={(〃,〃),(〃,c),(。,c)},p2={(b,c\(c9a),(b,d)},顯然p”?是

可傳遞的，但是P1?p[={(a,c),(4,a),S,。)}卻是不可傳遞的。

22、證明假設(shè)「是對(duì)稱(chēng)的，那么對(duì)任何整數(shù)"也是對(duì)稱(chēng)的。

證明：數(shù)學(xué)歸納法，當(dāng)左=2時(shí)，假設(shè)(。/)￡02,那么根據(jù)復(fù)合關(guān)系的定義，存在元素c,

使得(a,c)￡「,(c,〃)￡/?,因?yàn)橄κ菍?duì)稱(chēng)的，所以(c,a)e0,(/“)￡/?,所以因此

"是對(duì)稱(chēng)的，假設(shè)當(dāng)〃=攵時(shí)成立，那么當(dāng)〃=4+1時(shí)，假設(shè)(〃/)￡，“，那么存在元素q,

使得(a，G)ep\(G，Z?)Gp,因?yàn)橄?是對(duì)稱(chēng)的，因此(G，a)G爐,(b,cjwp,所以

(瓦。)￡/,因此：

〃=4+1時(shí)成立，即得證。

23、2={1,2,3,4}和定義在月上的關(guān)系0={(1,2),(4,3),(2,2),(2』),(3』)},試證明夕不是可傳

遞的。求出一個(gè)關(guān)系夕?3夕，使得P1是可傳遞的，你能求出另一個(gè)關(guān)系々衛(wèi)P也是可傳遞

的嘛？

答：證明：夕顯然不是可傳遞的，因?yàn)?l,2)wp,(2,l)ep,但是(1,1)任0。

月={(1,2),(4,3),(2,2),(2,1),(3,1),(1,1),(4,1),(4,2)},能找出另一個(gè)關(guān)系。

啟={(1,2),(4.3),(2,2),(2,1),(3,1),(1,1),(4,1),(4,2),(3,3)}。

24、圖2-10表示在{1,2,3}上的12個(gè)關(guān)系的關(guān)系圖。試對(duì)每一個(gè)這樣的圖，確定其表示的

關(guān)系是自反的還是非自反的；是對(duì)稱(chēng)，非對(duì)稱(chēng)還是反對(duì)稱(chēng)；是可傳遞的還是不可傳遞的？

自反的、可傳遞的

自成可傳遞的

非勺、可傳遞的

I、可傳遞的

25、圖2-11給出了{(lán)1,2,3:些關(guān)系是等價(jià)的嗎？

答：

答:」),(2,2)(似0」)}具有自反性，對(duì)稱(chēng)性，但是

不/.(1,3)”,二不是等價(jià)關(guān)系。

圖(I2,2),(3,3),(Z性，對(duì)稱(chēng)性，傳遞性，因此是

等仇K不。

26、在N上的關(guān)系P定義為當(dāng)且僅當(dāng)々/%可以用形式2，”表示時(shí)，有叩叫，這里加是任意

整數(shù)：

⑴證明夕是等價(jià)關(guān)系

證明：對(duì)V〃wN,〃/〃=1=2°,因此〃夕〃，所以關(guān)系p具有自反性。

對(duì)假設(shè)如\即存在加，使得〃j=2?那么有〃i=2.設(shè)因此有jpi。所以關(guān)系

〃具有對(duì)稱(chēng)性。

為ijkwN,假設(shè)，為，且jpk,即存在班,嗎，使得〃j=2叫，j/k=小,那么〃k=2網(wǎng)f,

因此有03所以關(guān)系.具有傳遞性。

綜上可得關(guān)系「是等價(jià)關(guān)系。

(2)找出0的所有等價(jià)類(lèi)

答：

27、物：蝦唾默工而黃總:%磁文寸需的且可傳遞的，那么它也是自反的，其理由

是，覷黃穌輸"http://福需岫4便得aiPa.,o

答:寰種需覆霜船:隔版2心/斜4%,=}{Q2),(2/),(1,1)},顯然p是對(duì)稱(chēng)的，且p

是可傳遞的，但是它不是自反的。

28、設(shè)有集合A和A上的關(guān)系p,對(duì)于所有的《,力,《￡A,假設(shè)由q/嗎和%夕知可推得

akpa.,,那么稱(chēng)關(guān)系°是循環(huán)的，試證明當(dāng)且僅當(dāng)P是等價(jià)關(guān)系時(shí)，夕是自反且循環(huán)的。

證明：先證充分性

假設(shè)「是等價(jià)關(guān)系，那么夕是自反的，對(duì)稱(chēng)的，可傳遞的。對(duì)于所有的4，%,6￡A,假設(shè)

4/勺且勺P4,那么4P%,由對(duì)稱(chēng)性那么有見(jiàn)pq,因此關(guān)系0是循環(huán)的。

再證必要性

假設(shè)對(duì)于所有的GA,假設(shè)有又由自反性，有a.pa),那么由夕是循環(huán)的，

可得成立，即。具有對(duì)稱(chēng)性。

假設(shè)對(duì)于所有的q嗎,4eA,假設(shè)由《小??和知/見(jiàn)，由/?是循環(huán)的有&pa,,由對(duì)稱(chēng)性可

得生叫，因此夕具有可傳遞性。

又由「是自反的，那么。是等價(jià)的。

29、設(shè)q和2是A上的等價(jià)關(guān)系，試證明：當(dāng)且僅當(dāng)片中的每一等價(jià)類(lèi)都包含于片的某

一等價(jià)類(lèi)中時(shí)，有夕1722。

證明：先證充分性

設(shè)片中的每一個(gè)等價(jià)類(lèi)都包含于嫉的某一個(gè)等價(jià)類(lèi)中，對(duì)任一(《嗎)￡月，有生「百，因

比q￡［里卜嗎。又由假設(shè)必有某元素人￡斗存在，使得口］八c［b］p2,因此有q，

勺日勿處，所以(《,叫)￡.，故有8￡02。

再證必要性：

設(shè)8102，并設(shè)⑷門(mén)是片中任一等價(jià)類(lèi)，對(duì)任一代⑷回，有qgx,即(《,外￡百，由假

設(shè)(a.,x)ep2t即x￡［叭,故有⑷四口％o

30、8和心是集合A上分別有秩6和G的等價(jià)關(guān)系，試證明gC0也是A上的等價(jià)關(guān)系,

它的秩最多為八4，再證明8口2不一定是A上的等價(jià)關(guān)系。

證明：由交集的定義gc夕2={(。,b)I(a,b)G月且(a,b)ep2}

對(duì)于VawA,因?yàn)镻1,a都是自反的，所以(a,a)Eg,且(。，幻金2，因?yàn)?a,a)egcp2,

所以8cp2是自反的。

對(duì)于V./EA,假設(shè)(〃,〃)￡/91c0,那么(a,/?)￡Q|,(4,/?)￡P(guān)2，由。?和0的對(duì)稱(chēng)性知

3,“)《="，且(b,a)tp2,因而有(〃,a)erip2,故"］r\p?是對(duì)稱(chēng)的。

對(duì)于Va/,c￡A,假設(shè)(4,/?￡月rip2，(瓦c)￡Q|C夕2,那么有(。/)￡月，(b?wpi,

(a,b)ep2t(b,c)ep2,由〃,9的傳遞性知3?￡8，(a,c)ep2,因而(〃,c)￡“cq2，故

01cp2是可傳遞的。所以PlC「2也是A上的等價(jià)關(guān)系。

對(duì)于自U「2，由并集的定義知月。夕2={(〃，〃)I(〃』，)￡P(guān)l或者(〃，〃)€2)

對(duì)于V.cA,因?yàn)镻l是自反的，所以(。,4)￡夕1，因而(兄4)￡月D0，所以是自反

的。對(duì)于假設(shè)(a,〃)￡gup2，那么(。,〃)￡8或者(〃/)w々，由于月和生都是

對(duì)稱(chēng)的，因此有(匕,。)￡夕|或者(。,〃)￡夕2，因而有up?，故gup?也是對(duì)稱(chēng)的。

對(duì)于任意的a,2,ceA,假設(shè)Dp?,(b,c)ep、2p?，那么(a,/?)￡g或者(凡^^金；

(b,c)€g或者S,c)€02，因?yàn)?力和(瓦c)不一定能同時(shí)屬于P［,也不一定能同時(shí)屬于2，

所以無(wú)法推出(4,c)G2［或者(a,c)Gp2,因而也就無(wú)法推出(4,c)eP\2p》這說(shuō)明g的

可傳遞性不一定能成立，因此推不出8uq是A上的等價(jià)關(guān)系。

反例：設(shè)A={1,2,3},A上的關(guān)系月={(1,1),(2,2),(3,3),(1,3),(31)},

°2={(1,1),(2,2),(3,3),(1,2),(21)},顯然g和心均是等價(jià)關(guān)系。

p,up2={(1,1),(2,2),(3,3),(1,3),(3,1),(1,2),(2,1)),這里夕?02是自反的，對(duì)稱(chēng)的，但是小可

傳遞的。

31、設(shè)8是集合集上的一個(gè)關(guān)系,只2={3切存在c,使3，C)￡8且(。向。試證明：假

設(shè)月是一個(gè)等價(jià)關(guān)系，那么.也是一個(gè)等價(jià)關(guān)系。

證明：因?yàn)镻1是自反的，因此對(duì)VacA,有(a,a)epi,由(a,a)epi,因此有(〃M)ep2,

故0是自反的。

對(duì)于任意的。力￡A,假設(shè)(4,〃)￡。2,那么必有元素ceA，使得且(。,〃)￡月，

由P］的對(duì)稱(chēng)性又有S,c)W/9］且(c,〃)wg,因而有(仇〃)￡「2，故夕2是對(duì)稱(chēng)的。

對(duì)任意的〃力,cwA,假設(shè)(a,b)w/?2，(b,c)wP2,那么必有元素使得：

由.的可傳遞性,又有(a,b)w月，(b,c)w2,于是又有(a,c)￡0,故p2是可傳遞的。

由上得證心是一個(gè)等價(jià)關(guān)系。

32、設(shè)A是由4個(gè)元素組成的集合，試問(wèn)在A上可以定義多少個(gè)不同的等價(jià)關(guān)系？

答：根據(jù)等價(jià)關(guān)系與分劃一一對(duì)應(yīng)，將4分劃為一塊：有一種方法，將4分劃為兩塊：2+2

方式有1/2C：種，1+3方式有C種

將4分劃為三塊：只能是1+1+2方式，有C：種

將A分劃為四塊：有一種方法

因此集合A上不同等價(jià)關(guān)系的個(gè)數(shù)為15種。

33、設(shè)g和生是集合A上的等價(jià)關(guān)系，以下各式哪些是A上的等價(jià)關(guān)系？為什么？

(l)(AxA)-Pl

答：不是等價(jià)關(guān)系，因?yàn)椴痪哂凶苑葱?/p>

⑵P1-P2

答：不是等價(jià)關(guān)系，因?yàn)椴痪哂凶苑葱?/p>

⑶

答：是等價(jià)關(guān)系，證明如下：乃是自反的，浦顯然也是自反的。假設(shè)(〃/)￡，，那么有

復(fù)合關(guān)系的定義，存在CSA,使得(4,C)E0],(c,b)￡P(guān)1,由Pl的對(duì)稱(chēng)性有(C")￡P(guān)|,

(瓦C)￡01,由復(fù)合關(guān)系的定義有(仇4)￡夕；，因此";是對(duì)稱(chēng)的。假設(shè)(4,/?),(/“)￡0；,由復(fù)

合關(guān)系的定義，皿￡4,(a,d)wp,(d,b)GPl

由對(duì)稱(chēng)性,,(d,a)wpi，(b,d)epi=>(b,@眸M(Z?,e)e",(e,c)￡g

所以(4〃)￡除?柏環(huán)的瘠稱(chēng)性？倭?與用，因此0：具有傳遞性。因此夕：是A上的等價(jià)關(guān)

系。

(4)r(p,-p2)

答：不一定是A上的等價(jià)關(guān)系。例如4={1,2,3},2={(1/)，⑵2),(3,3),(2,3),(3,2)},g為A

上的普遍關(guān)系，那么—(夕「"2)={(1，1)，(2,2),(3,3),(1,2),[21),(1,3),(3』)}不具有傳遞性，因?yàn)?/p>

(2,1),(1,3)」(月一夕2)，但是(2,3)￡“自一心)。

34、對(duì)于以下集合中的‘整除'關(guān)系，畫(huà)出次序圖:

次序圖，并指出哪些是全序

答:

非3

36、Q1):合.，關(guān)系，且試證明：pc(BxB)是B上的偏序關(guān)系。

證明：對(duì)任意的awa,a)sBxB,又因?yàn)椤A及P的自反性，所以(a,a)￡/9,因

此(。,。)Gpr\(BxE(BxB)是自反的。

對(duì)任意的假設(shè)(4”)J/廣3),且(),4)G/7c(6x8),那么有且

(瓦4)￡夕，由夕的反對(duì)稱(chēng)性，有。=〃，因此℃(8x8)是反對(duì)稱(chēng)的。

對(duì)任意的。，仇c￡B,假設(shè)(a,b)Gpc(BxB),(b,c)Gpc(BxB),那么(a,b)e0,且(b,c)ep,

由月的可傳遞性必有(a,c)￡〃，由3x3的定義，(a,c)w3x3,于是(a,c)￡/?c(6x8),因

此0c(BxB)是可傳遞的，由上得證°c(8xB)是8上的偏序關(guān)系。

37、給出一個(gè)集合4的例子，使得