洪帆《离散数学基础》(第三版)课后习题答案

第1章集合

1、列举以下集合的元素

(1)小于20的素数的集合

(2)小于5的非负整数的集合

(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、卜面哪些式子是错误的？

⑴{〃}£{{〃}}答：正确

(2){a}q[{。}}答：错误

(3){〃}£({〃},〃}答：正确

(4)答：正确

4、已给S={2,出⑶,4}和/?={{〃},3,4』},指出下面哪些论断是正确的?哪些是错误的？

(1){〃}£S错误

⑵正确

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

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

(5)R=S错误

(6){a}=S正确

(7){a}qR错误

(8)正确

(9)。口{{〃}}qR正确

(10){掰土S错误

(11)错误

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

5、列举出集合AB,C的例子，使其满足AEB,BwC且A任C

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

6、给出以下集合的新集

(1)Mb}}

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

⑵{点©{〃}}

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

7、设4={〃},给出A和2A的箱集

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

8、设A={qM2,…‘4}由％和4所表示的A的子集各是什么?应如何表示子集{生外,的}

和{4,4}

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

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

9、设。={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、给定自然数集N的以下子集：

A={1,2,7,8),8={“/<50},C={i|i可被3整数,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、给定自然数集N的以下子集

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

将以下集合表示为由A8,C,O,E产生的集合：

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

(1)假设AcB=4cC,那么B=C

答：不正确，反例，设A=”,那么不管伐。是什么集合，都有AcB=AcC=。，但显然

B,C不一定相等。

(2)当且仅当有AqB；

答：正确，证明如下：假设=那么对VQWA,有awAuB=B,那么有awB,

因此有AqB。反之，假设A=那么=8显然成立。

(3)当且仅当Ac3=A,有AqB

答：正确，证明如下：假设AcB=A,那么对VawA,因此awAcB,那么awB,那么

有AqB。假设AqB,那么VawA,有awB,因此由OEA,可以得出aw4c4,因此

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

(4)当且仅当AqC,有Ac(B—C)=。

答：不正确，因为4c(8-C)=Ac3cC,因此不一定需要满足AqC,而假设AcB=。

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

成立。

(5)当且仅当BqC,有(4-8)uC=A

答：不正确，因为假设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、设A8,C,O是集合，下述哪些论断是正确的？哪些是错误的？说明理由。

(1)假设那么AuCc(8u。)

答：正确，证明：对VacADC,那么。£4或。6(7,因为4口8,。口。，因此。£3或aw。，

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

(2)假设4a5,CqO,那么AcCq(Bca)

答：正确

(3)假设Au3,Cu。，那么A=Cu(8u。)

答：正确

(4)假设Au员CuD,那么AcCu(3cD)

答：不正确。例如假设Au区CuD,但是AcC=0,BcO=°,那么0=AcCq(6cO)=°。

15、设A8是两个集合，问：

(1)如果A—4=A,那么A和8有什么关系？

答：因为4一笈=笈，而A—B=AcM=B,即对WOEB有A〃e3',因此A=3=°。

(2)如果A—3=8—A,那么A和3有什么关系？

答：充要条件是A=8。证明：因为4—3=8—A的(4—B)uA=(B—4)uA,从而有

A=A<JB>即AqB,同理可证明区qA,因此4=A。

16、设A3是任意集合，下述论断哪些是正确的？哪些是错误的？说明理由。

⑴2"。=2八"

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

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

显然不成立。

⑵2s8=2Ac2^答：成立。证明：对VC£2八c2“，那么C£2人且C£2^,那么CqA,C工8,

那么C^AcB,因此。反之，假设X/CW2ACB,那么c=4c8,那么CqA且CqB,

因此。£2狐且Cw2j因此。£2，'C2J即2叱8=2入门28。

(3)2*=(2八)’

答：显然不成立，因为左边集合肯定含有。，而右边不含有。

17、在一个班级的50个学生中，有26人在离散数学的考试中取得了优秀的成绩；21人在

程序设计的考试中取得了优秀的成绩。假设有17人在两次考试中都没有取得优秀成绩，问

有多少人在两次考试中都取得了优秀成绩？

答：分别用A3表示在离散和程序设计的考试中取得优秀成绩的学生集合，U表示全体学

生集合：那么#(A)=26,#(3)=21,#(AuB)=50-17=33,那么两次考试中都取得了优

秀成绩的学生人数为26+21-33=14人。

18、设A&C是任意集合，运用成员表证明：

(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?应用成员表证明或否认

答：先分别给出集合(AD3)C(5DCY和Ac9的成员表如下:

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

00000i010

001010010

010110000

011110000

100101111

101110011

110110000

111110000

观察上述表格，我们发现(ADB)c(BuCy所标记的列中，仅在第五列为1,这意味着当元

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

”(AuB)c(BuCy。而集合Ac8所标记的列中,第五和第六行均为1,这意味着

〃eA〃史Z?且〃任。时，〃eAc3',当〃©A,〃信/?,且时，也有〃EAC"。所以当

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

立。

20、A，4,…,4为U的子集，A，4,…,4至多能产生多少不同的子集？

答：构造由4,4，,4所产生的集合的成员表，显然该成员表由2,个行所组成。在该成员

表中不同的列可由2「为的二进制数0000-11111分别表示，而不同的列所标记的集合

不相同的，因此由4,4,…,A.至多可以产生27个不同的集合。

21、证明分配律、等寻律和吸收律9'

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

证明：对€Ac(3uC),那么有aeA且4£即有且或aeC,也即

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

对Va£(AcB)D(AcC),那么4cAe3或awAcC,即A且awB,或a£A且。GC,

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

2吸收律Ac(Au8)二A

证明：Ac(Au8)=A显然成立，对4,那么显然有ae因此有aw4clAD8),

因此有AuAc(AuB)成立。

22、设A氏C是任意集合，运用集合运算定律证明：

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

左边=8u(AuB)"A

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

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

(2)(Au区)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))补集是(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、设A,为某些实数的集合，定义为

试证明：(JA=A)

1=1

证明：设。,那么比存在整数3使得。£儿，因此有r/＜1--,于是,因此。G4)0

i=\%

另一方面，设QE4,那么有。＜1，假设。＜0,那么有4,因此。。假设0＜。＜1,

1]+1,其中表示_L的整数局部，那么有上〉1

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

㈤b%

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

%kr=l

25、设｛&&，…,4｝是集合A的一个分划,试证明AcB,4c&4cB中所有非空集合

构成AcA的一个分划。

证明：因为｛4「4,…,AJ是集合A的一个分划，因此由分划的定义，可得Od=A,且

rr

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

J=1r=l

因此4c民A2c民，c。中所有非空集合构成Ac8的一个分划o

26、〃个元素的集合，有多少中不同的方法可以分划成两块？

答:当〃奇数时有C+c；++C^T种不同的方法，当〃为偶数时有C；+C；+…种不

同的方法。

第2章关系

1、假设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轴的笛卡尔坐标系中，假设有

试给出笛卡尔根Xxy的几何解释

解：表示横坐标x的范围在-3«工42,纵坐标)，的范围在-2W)，W0的二维点集所构成的集

合。

3、设A,B,C和D是任意的集合，证明

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

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

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

证明：(3)首先，因为=CcD=C,所以

类似地，(Ac8)x(CcQ)q8x。，所以有：

反之，假设(工,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、对以下每种情形，列出由A到B的关系0的元素，确定0的定义域和值域，构造。的

关系矩阵：

(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)}

关系矩阵M『=110

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

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

关系矩阵M广(100]

5、设4={1,2,3/,@,6。，期以下每一种情形，构造A上的关系图，并确定「的定义域和值

域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遢/的倍数}

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

定义域，如阳46,1)碍纵<6,2),(6,3)}

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

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

定义域出身翕闻尤孙(孙L(5,4,3,2,1)

⑸P={磔*中"』)

解:定义图隔门'{&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,&国6遂阳斗矽)),(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)

定义域。夕移孙(初(见4),(3,5),(4,2),(4,3),(4,4),(4,5)

(8)夕={&®陟用素擞”(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、设。={(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尸叫

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

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

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

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

xG0

Dp12P”故外2DQCD"p"

证明:RidR外

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

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

7、A1和4是分别具有基数%和〃2的有限集，试问有多少个A到4的不同关系？

答：AX4的所有子集都是用到A2的一个关系，所以共有2"岫心个不同的关系。

8、找出集合A=…，牝}上普遍关系和恒等关系的关系矩阵和关系图的特征。

答：A上的普遍关系o=A?的关系矩阵是全1矩阵，而恒等关系的关系矩阵是单位矩阵。

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

试确定如下的复合关系：

⑴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、设8,02,夕3是集合A上的关系,试证明：如果那么有：

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

证明：⑴对V(x,y)£p[由复合关系的定义,3zeAf使得，([z)wp],(z,y)ep3,

因为所以(X,Z)£"2，所以(X,y)£〃2，所以夕I,夕3G0，夕3

(2)对V(x,y)wa，由复合关系的定义，MZEA,使得，(x,z)£/?j>')eA»因

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

(3)对W(x,y)£P1,有(y,x)wp],因为自工小，所以(卜幻^公所以。,)”02，也即

Pi£夕2。

11、给定乃二{(0,1),(1,2),(3,4)),8,0={(1,3),(1,4),(3,3)}求一个基数最小的关系，使满足0

的条件。一般地说，假设给定夕[和夕]・夕2，生能被唯一确实定吗？基数最小的心能被唯一

确定吗？

答：2={(2,3),(2,4),(4,3)}。一般地说，假设给定乃和8・.，0不能被唯一确实定。基

数最小的02也不能被唯一确定。

12、给定集合4，4,4,设0是由A到&得关系，02和。3是由&到43得关系，试证明：

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

证明：根据并集和复合关系的定义，p\•(02U夕3)和(P1•P2)不(。|63)都是A到A3上的关

系，下只需要证明它们由完全相同的序偶组成。

设(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)；反之，假设(a,c)j3・/2)=3.，3)，也即(a,c)j

("1•0)或者(a,c)€=3。必)，假设(a,c)j(月-.2)，那么存在〃£&»使得，

GE

(b,c)ep2,那么(a,b)wp[,(/?,c)p2up3,那么(〃,c)p1＜心，假设(。©£(自•p1

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

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

证明：设(〃,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、对第9题中的关系，构造关系矩阵

(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、设A是有〃个元素的有限集,3是A*的啜臬，°试证明必存在两个正整数AJ,使得

"=P'0.0100

证明：因为夕是A上的关系，所以对于任意正整数〃，p’也是A上的关系，另一方面，因

为#(A)=〃，所以#(AXA)=〃2,#(2,“八)=2收加八)=2'「，也即A上只有2"个不同的关系，

因此在关系，…,02,夕2匕1中必有两个是相同的，也即存在两个正整数使得

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

16、设0是由A到B的关系，0是由B到C的关系，试证明"「a=XV8。

证明：由题设知道和P2-g都是由C到A的关系，因此只要证明它们由完全相同的序

倡组成。设(c，a)£Qi•22，那么(。，。)£外夕2,因此必存在元素此3，使得他力)€自,

e，C)2,所以，(。,。)£小，所以(CM)W/Y。。反之，设(CM)W%Pl，那么

必存在元素加£8,使得《,//)£■，(阮。)£01,所以(。万)£。1,&,c)e/?2,所以

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

17、(1)设Pl和02是由A到8的关系，问P]=P|U0成立吗？

答：成立

(2)设P是集合4上的关系，如果°是自反的，那么。一定是自反的吗？

答：是的。证明：假设p是自反的，那么对所有的。£4,有(。间)ep,那么一定有(a,a)Gp,

那么万也是自反的。

(3)假设0是对称的，那么。也是对称的吗？答：是的。

(4)假设夕是可传递的，那么万也是可传递的吗？答：是的

证明：假设「是可传递的，由定义可知，假设(x,y)£0,(y,z)e/9,那么一定有(x,z)£;9,

由逆关系的定义，也即，假设(m/)£万，(Z,y)£万，一定有(z,x)e万，，那么。也是可传

递的。

18、图2・9给出了集合{12345,6}上的关系夕的关系图，试画出关系炉和炉的图，并利用

关系图求出关系0的传递闭包。

解：

图2-9

关系夕={(1,3),(1,5),(2,5),(4,5),(5,4),(6,3),(6,6)}

因为夕4=夕2，所以夕5=03,p8=p2

传递闭包F+=p2P'2p、

19、试证明：假设「是基数为〃的集合A上的一个关系，那么夕的传递闭包为A=0"

证明：由定义，=Y〃，要证明X"二z",因为所以只要证明

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

假设〃>〃，那么在A中必存在4-1个元素4,气,…,a*’使得：

因为人>〃，所以在a,4,%,…必…/这Z+1个元素中心有两个元素%=%(0<r<t<k,

记〃为喝，记〃为黑)，因比下述关系

成立，这说明年ki=k-Q-r),k\〈k。假设占>〃，用类似的方法又可找到&<匕，

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

202以正善系中哪一个是自反的、对称的、反对称的或者可传递的？，=，

(1)当且7又当|%-，2区时，有历2；

答：是自反的，对称的，非可传递的，例如13P9,9pl,但13夕1不成立。

⑵当且仅当〃g〉8(〃”％£N)时，有4a2；

答：非自反的，因为Ipl不成立，但kN。对称的，非可传递的，因为1川0,1002,但

是1夕2不成立。

(3)当且仅当斗S弓|(斗,0wR)时,有KPG。

答：自反的，非对称的，非可传递的，因为50(-8),-80,但是5Pl不成立。

21、设q和0是集合4上的任意两个关系，判断以下命题是否正确，并说明理由：

(1)假设夕।和0是自反的，那么0].22也是自反的：

答：正确。因为0和夕2是自反的，因此对任意A，有apw，ap2a,因此年g。，所以0,P2

也是自反的。

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

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

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

(3)假设P[和夕2是对称的,那么01，夕2也是对称的;

答：错误，设A={〃/,(?},"]={(〃,/?),SM)},0={(〃,c),(c,a)},显然P]和02是对称的，

但是夕I,p2={S©}是非对称的。

(4)假设Pl和22是反对称的，那么・夕2也是反对称的;

答:错误，设4={凡仇c},Pl={(〃/),(")},夕2={S，c)，(c，a)}，显然Pl和22是反对称的，

但是Pi={(a，c)，(c，。)}不是对称的。

(5)假设q和0是可传递的，那么也是可传递的；

答：错误,设A={a〃,c},a={(〃,〃),(〃,c),(。,c)},p2={(b,c\(c9a),(b,d)},显然p”?是

可传递的，但是P1•p[={(a,c),(4,a),S,。)}却是不可传递的。

22、证明假设「是对称的，那么对任何整数"也是对称的。

证明：数学归纳法，当左=2时，假设(。/)£02,那么根据复合关系的定义，存在元素c,

使得(a,c)£「,(c,〃)£/?,因为夕是对称的，所以(c,a)e0,(/“)£/?,所以因此

"是对称的，假设当〃=攵时成立，那么当〃=4+1时，假设(〃/)£，“，那么存在元素q,

使得(a，G)ep\(G，Z?)Gp,因为夕和"是对称的，因此(G，a)G炉,(b,cjwp,所以

(瓦。)£/,因此：

〃=4+1时成立，即得证。

23、2={1,2,3,4}和定义在月上的关系0={(1,2),(4,3),(2,2),(2』),(3』)},试证明夕不是可传

递的。求出一个关系夕।3夕，使得P1是可传递的，你能求出另一个关系々卫P也是可传递

的嘛？

答：证明：夕显然不是可传递的，因为(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)},能找出另一个关系。

启={(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个关系的关系图。试对每一个这样的图，确定其表示的

关系是自反的还是非自反的；是对称，非对称还是反对称；是可传递的还是不可传递的？

自反的、可传递的

自成可传递的

非勺、可传递的

I、可传递的

25、图2-11给出了{1,2,3:些关系是等价的吗？

答：

答:」),(2,2)(似0」)}具有自反性，对称性，但是

不/.(1,3)”,二不是等价关系。

图(I2,2),(3,3),(Z性，对称性，传递性，因此是

等仇K不。

26、在N上的关系P定义为当且仅当々/%可以用形式2，”表示时，有叩叫，这里加是任意

整数：

⑴证明夕是等价关系

证明：对V〃wN,〃/〃=1=2°,因此〃夕〃，所以关系p具有自反性。

对假设如\即存在加，使得〃j=2〜那么有〃i=2.设因此有jpi。所以关系

〃具有对称性。

为ijkwN,假设，为，且jpk,即存在班,吗，使得〃j=2叫，j/k=小,那么〃k=2网f,

因此有03所以关系.具有传递性。

综上可得关系「是等价关系。

(2)找出0的所有等价类

答：

27、物：虾唾默工而黄总:%磁文寸需的且可传递的，那么它也是自反的，其理由

是，觑黄稣输"//福需岫4便得aiPa.,o

答:寰种需覆霜船:隔版2心/斜4%,=}{Q2),(2/),(1,1)},显然p是对称的，且p

是可传递的，但是它不是自反的。

28、设有集合A和A上的关系p,对于所有的《,力,《£A,假设由q/吗和%夕知可推得

akpa.,,那么称关系°是循环的，试证明当且仅当P是等价关系时，夕是自反且循环的。

证明：先证充分性

假设「是等价关系，那么夕是自反的，对称的，可传递的。对于所有的4，%,6£A,假设

4/勺且勺P4,那么4P%,由对称性那么有见pq,因此关系0是循环的。

再证必要性

假设对于所有的GA,假设有又由自反性，有a.pa),那么由夕是循环的，

可得成立，即。具有对称性。

假设对于所有的q吗,4eA,假设由《小?•和知/见，由/?是循环的有&pa,,由对称性可

得生叫，因此夕具有可传递性。

又由「是自反的，那么。是等价的。

29、设q和2是A上的等价关系，试证明：当且仅当片中的每一等价类都包含于片的某

一等价类中时，有夕1722。

证明：先证充分性

设片中的每一个等价类都包含于嫉的某一个等价类中，对任一(《吗)£月，有生「百，因

比q£［里卜吗。又由假设必有某元素人£斗存在，使得口］八c［b］p2,因此有q，

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

再证必要性：

设8102，并设⑷门是片中任一等价类，对任一代⑷回，有qgx,即(《,外£百，由假

设(a.,x)ep2t即x£［叭,故有⑷四口％o

30、8和心是集合A上分别有秩6和G的等价关系，试证明gC0也是A上的等价关系,

它的秩最多为八4，再证明8口2不一定是A上的等价关系。

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

对于VawA,因为P1,a都是自反的，所以(a,a)Eg,且(。，幻金2，因为(a,a)egcp2,

所以8cp2是自反的。

对于V./EA,假设(〃,〃)£/91c0,那么(a,/?)£Q|,(4,/?)£P2，由。।和0的对称性知

3,“)《="，且(b,a)tp2,因而有(〃,a)erip2,故"］r\p?是对称的。

对于Va/,c£A,假设(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上的等价关系。

对于自U「2，由并集的定义知月。夕2={(〃，〃)I(〃』，)£Pl或者(〃，〃)€2)

对于V.cA,因为Pl是自反的，所以(。,4)£夕1，因而(兄4)£月D0，所以是自反

的。对于假设(a,〃)£gup2，那么(。,〃)£8或者(〃/)w々，由于月和生都是

对称的，因此有(匕,。)£夕|或者(。,〃)£夕2，因而有up?，故gup?也是对称的。

对于任意的a,2,ceA,假设Dp?,(b,c)ep、2p?，那么(a,/?)£g或者(凡^^金；

(b,c)€g或者S,c)€02，因为3力和(瓦c)不一定能同时属于P［,也不一定能同时属于2，

所以无法推出(4,c)G2［或者(a,c)Gp2,因而也就无法推出(4,c)eP\2p》这说明g的

可传递性不一定能成立，因此推不出8uq是A上的等价关系。

反例：设A={1,2,3},A上的关系月={(1,1),(2,2),(3,3),(1,3),(31)},

°2={(1,1),(2,2),(3,3),(1,2),(21)},显然g和心均是等价关系。

p,up2={(1,1),(2,2),(3,3),(1,3),(3,1),(1,2),(2,1)),这里夕〜02是自反的，对称的，但是小可

传递的。

31、设8是集合集上的一个关系,只2={3切存在c,使3，C)£8且(。向。试证明：假

设月是一个等价关系，那么.也是一个等价关系。

证明：因为P1是自反的，因此对VacA,有(a,a)epi,由(a,a)epi,因此有(〃M)ep2,

故0是自反的。

对于任意的。力£A,假设(4,〃)£。2,那么必有元素ceA，使得且(。,〃)£月，

由P］的对称性又有S,c)W/9］且(c,〃)wg,因而有(仇〃)£「2，故夕2是对称的。

对任意的〃力,cwA,假设(a,b)w/?2，(b,c)wP2,那么必有元素使得：

由.的可传递性,又有(a,b)w月，(b,c)w2,于是又有(a,c)£0,故p2是可传递的。

由上得证心是一个等价关系。

32、设A是由4个元素组成的集合，试问在A上可以定义多少个不同的等价关系？

答：根据等价关系与分划一一对应，将4分划为一块：有一种方法，将4分划为两块：2+2

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

将4分划为三块：只能是1+1+2方式，有C：种

将A分划为四块：有一种方法

因此集合A上不同等价关系的个数为15种。

33、设g和生是集合A上的等价关系，以下各式哪些是A上的等价关系？为什么？

(l)(AxA)-Pl

答：不是等价关系，因为不具有自反性

⑵P1-P2

答：不是等价关系，因为不具有自反性

⑶

答：是等价关系，证明如下：乃是自反的，浦显然也是自反的。假设(〃/)£，，那么有

复合关系的定义，存在CSA,使得(4,C)E0],(c,b)£P1,由Pl的对称性有(C")£P|,

(瓦C)£01,由复合关系的定义有(仇4)£夕；，因此";是对称的。假设(4,/?),(/“)£0；,由复

合关系的定义，皿£4,(a,d)wp,(d,b)GPl

由对称性,,(d,a)wpi，(b,d)epi=>(b,@眸M(Z?,e)e",(e,c)£g

所以(4〃)£除?柏环的瘠称性？倭®与用，因此0：具有传递性。因此夕：是A上的等价关

系。

(4)r(p,-p2)

答：不一定是A上的等价关系。例如4={1,2,3},2={(1/)，⑵2),(3,3),(2,3),(3,2)},g为A

上的普遍关系，那么—(夕「"2)={(1，1)，(2,2),(3,3),(1,2),[21),(1,3),(3』)}不具有传递性，因为

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

34、对于以下集合中的‘整除'关系，画出次序图:

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

答:

非3

36、Q1):合.，关系，且试证明：pc(BxB)是B上的偏序关系。

证明：对任意的awa,a)sBxB,又因为。wA及P的自反性，所以(a,a)£/9,因

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

对任意的假设(4”)J/广3),且(),4)G/7c(6x8),那么有且

(瓦4)£夕，由夕的反对称性，有。=〃，因此℃(8x8)是反对称的。

对任意的。，仇c£B,假设(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上的偏序关系。

37、给出一个集合4的例子，使得