哈工大《离散数学》教科书习题答案南京廖华答案网

哈工大《离散数学》教科书习题答案下载本文

文章发布时间 : 2024/5/6 14:53:24星期一

教材习题解答

第一章集合及其运算

P8习题

3. 写出方程x2?2x?1?0的根所构成的集合。

解：x2?2x?1?0的根为x??1，故所求集合为{?1} 4.下列命题中哪些是真的，哪些为假

a)对每个集A，??A；b)对每个集A，??A； c)对每个集A，A?{A}；d)对每个集A，A?A； e)对每个集A，A?A；f)对每个集A，A?{A}； g)对每个集A，A?2A；h)对每个集A，A?2A； i)对每个集A，{A}?2A；j)对每个集A，{A}?2A； k)对每个集A，??2A；l)对每个集A，??2A； m)对每个集A，A?{A}；n)??{?}；

o){?}中没有任何元素；p)若A?B，则2A?2B

q)对任何集A，A?{x|x?A}；r)对任何集A，{x|x?A}?{y|y?A}；

{x|x?A}?{A|A?A}；s)对任何集A，y?A?y?{x|x?A}；t)对任何集A，

答案：假真真假真假真假真假真真假假假真真真真真 5.设有n个集合A1,A2,?,An且A1?A2???An?A1，试证：

A1?A2???An

证明：由A1?A2?A4???An?A1，可得A1?A2且A2?A1，故A1?A2。同理可得：A1?A3?A4???An 因此A1?A2?A3???An 6.设S?{?,{?}}，试求2S？

解：2S?{?,{?},{{?}},{?,{?}}}

7.设S恰有n个元素，证明2S有2n个元素。

证明：（1）当n＝0时，S??,2S?{?},2S?1?20，命题成立。

（2）假设当n?k(k?0,k?N)时命题成立，即2S?2k（S?k时）。那么对于?S1（S1?k?1），2S1中的元素可分为两类，一类为不包含S1中某一元素x的集合，另一类为包含x的集合。显然，这两类元素个数均为2k。因而2S1?2k?1，亦即命题在n?k?1时也成立。由（1）、（2），可证得命题在n?N时均成立。

P16习题

1.设A、B是集合，证明:

(A\\B)?B?(A?B)\\B?B??

证：?当B??时，显然(A\\B)?B?(A?B)\\B，得证。

?假设B??，则必存在x?B，使得x?(A\\B)?B但x?(A?B)\\B，故

(A\\B)?B?(A?B)\\B与题设矛盾。所以假设不成立，故B??。

2.设A、B是集合，试证A???B?A?B

证：?显然。

?反证法：假设A??，则?x0?A，若x0?B，则x0?左，但x0?右，矛盾。若x0?B，则x0?左，但x0?右，矛盾。故假设不成立，即A??。 3. 设A，B，C是集合，证明：

(A?B)?C?A?(B?C)

证：(A?B)?C?[(A\\B)?(B\\A)]?C?[(A?BC)?(B?AC)]?C

?[(A?BC)?(B?AC)\\C]?(C\\((A?BC)?(B?AC)))?(A?B?C)?(B?A?C)?(C?((A?B)?(B?A)))CCCCCC

?(A?BC?CC)?(B?AC?CC)?(C?((AC?BC)?(A?B)))

?(A?BC?CC)?(AC?B?CC)?(AC?BC?C)?(A?B?C)

由上式可以看出此展开式与A、B、C的运算顺序无关，因此，

(A?B)?C?A?(B?C)

4.设A，B，C为集合，证明A\\(B?C)?(A\\B)\\C

证：因为A\\(B?C)?A?(B?C)C?A?BC?CC= (A?BC)\\C= (A\\B)\\C。 5.设A，B，C为集合，证明：

(A?B)\\C?(A\\C)?(B\\C)

证：(A?B)\\C?(A?B)?CC?(A?CC)?(B?CC)＝(A\\C)?(B\\C)。 6.设A，B，C为集合，证明：

(A?B)\\C?(A\\C)?(B\\C)

证明：(A?B)\\C?(A?B)?CC?A?B?CC?(A?CC)?(B?CC) =(A\\C)?(B\\C)

7.设A，B，C都是集合，若A?B?A?C且A?B?B?C，试证B=C。

证：证1： ?x?B，则

若x?A，则x?(A?B)。由于A?B?A?C，故x?(A?C)，即x?C；

若x?A，则x?(A?B)，由于A?B?A?C，故x?A?C。又x?A，只能有x?C。因此，?x?B，总有x?C，故B?C。

同理可证，C?B。因此B?C。

证2： B?B?(A?B)?B?(A?C)?(B?A)?(B?C) ?(C?A)?(B?C)?C?(A?B)?C?(A?C)?C 8.设A，B，C为集合，试证：

(A\\B)\\C?(A\\B)\\(C\\B)

证：证Ⅰ?x?(A\\B)\\C，有x?A,x?B,x?C，因此，x?(A\\B)，x?(C\\B)。故x?(A\\B)\\(C\\B)，即(A\\B)\\C?(A\\B)\\(C\\B)。

?x?(A\\B)\\(C\\B)，A\\B)，x?(C\\B)。反之，有x?(因此x?A,x?B,x?C。

故x?(A\\B)\\C，即(A\\B)\\(C\\B)?(A\\B)\\C。

所以 (A\\B)\\C＝(A\\B)\\(C\\B)。

证Ⅱ：(A\\B)\\(C\\B)?(A?BC)?(C?BC)C?(A?BC)?(CC?B) ?(A?BC)?CC?(A\\B)\\C 9.设X?Y?Z，证明Z\\(Y\\X)?X?(Z\\Y)

证：证1：?x?Z\\(Y\\X)?Z?(Y?XC)C?Z?(YC?X)，有x?Z且x?Y 或x?X。则

若x?Z且x?Y，则x?Z\\Y，于是x?X?(Z\\Y)。若x?Z且x?X，则x?X?(Z\\Y)，从而

Z\\(Y\\X)?X?(Z\\Y)。

反之，?x?X?(Z\\Y)，则x?X或x?Z\\Y。

若x?X，则由X?Y?Z有x?Y,x?Z，故x?Y\\X，因此x?Z\\(Y\\X)。若x?Z\\Y，则x?Z但x?Y，故x?Y\\X，因此x?Z\\(Y\\X)。从而

X?(Z\\Y)?Z\\(Y\\X)。

由集合相等的定义，Z\\(Y\\X)?X?(Z\\Y)。

证2：Z\\(Y\\X)?Z?(Y?XC)?Z?(YC?X)?(Z?YC)?(Z?X)，因为X?Z，所以Z\\(Y\\X)?(Z?YC)?X?X?(Z\\Y)。 10.下列命题是否成立？

(1)(A\\B)?C?A\\(B\\C)；(2)A?(B\\C)?(A?B)\\C； (3)A\\(B?C)?(A?B)\\B。

解：（1），（2），（3）都不成立。反例如下：

（1）A??,C?{1},B任意，则(A\\B)?C?C?{1};A\\(B\\C)??。（2）A?{1},B??,C?{1}，则A?(B\\C)?{1};(A?B)\\C??。

（3）A??,B?{1},C?{1,2}，则A\\(B?C)??;(A?C)\\B?{2}。 11．下列命题哪个为真？

a)对任何集合A,B,C，若A?B?B?C，则A=C。 b)设A,B,C为任何集合，若A?B?A?C，则B=C。 c)对任何集合A,B，2A?B?2A?2B。 d)对任何集合A,B，2A?B?2A?2B。 e)对任何集合A,B，2A\\B?2A\\2B。 f)对任何集合A,B，2A?B?2A?2B。答案：d是真命题。

12．设R,S,T是任何三个集合，试证：

（1）S?T?(S?T)?(S?T)；（2）R?(S?T)?(R?S)?(R?T)；

（3）(R?S)?(R?T)?R?(S?T)?(R?S)?(R?T)；（4）R?(S?T)?(R?S)?(R?T) 证：（1）?x?S?T?(S\\T)?(T\\S)，则

若x?S，则x?T。因而x?(S?T)且x?(S?T)，故x?(S?T)?(S?T)；若x?S，则x?T，同理可得x?(S?T)?(S?T)。故

S?T?(S?T)?(S?T)。

反之，因为(S?T)?(S?T)，故

(S?T)?(S?T)＝(S?T)\\(S?T)[?(S?T)\\(T?S)??]。

?x?(S?T)?(S?T)?(S?T)\\(S?T)，有x?(S?T),x?(S?T)。若x?S，则x?T，故x?S?T；若x?S，则x?T，故x?S?T。因此

(S?T)?(S?T)?S?T。

所以 S?T＝(S?T)?(S?T)。

（2）证：?x?(R?S)?(R?T)，有x?(R?S)且x?(R?T)。则若x?R，则x?S且x?T，故x?(S?T)，x?R?(S?T)。

若x?R，则x?S且x?T。故x?(S?T)，因此x?R?(S?T)。于是

(R?S)?(R?T)?R?(S?T)。

（3）证：?x?(R?S)?(R?T)，有x?(R?S)且x?(R?T)。则若x?R，则x?S,x?T，故x?(S?T)，因此x?R?(S?T)；若x?R，则x?S,x?T，故x?(S?T)，x?R?(S?T)。于是

(R?S)?(R?T)?R?(S?T)

反之，?x?R?(S?T)，则

若x?R，则x?(S?T)，故x?S,x?T，因而x?(R?S),x?(R?T)。即

x?(R?S)?(R?T)；

若x?R，则x?(S?T)，故x?S或x?T。因此x?(R?S)或x?(R?T)，从而x?(R?S)?(R?T)。

综上可得：R?(S?T)?(R?S)?(R?T)。于是

(R?S)?(R?T)?R?(S?T)?(R?S)?(R?T)

证：?x?(R?S)?(R?T)，则

若x?(R?S)，则x?(R?T)，因而x?R,x?T,x?S。故x?S?T，于是

x?R?(S?T)；

若x?(R?S)，则y?(R?T)，与上同理可得x?R?(S?T)。综上可得：R?(S?T)?(R?S)?(R?T)。

14．设A为任一集，{B?}??I为任一集族（I??），证明：

A?(?B?)??(A?B?)

??I??I 6

证：?x?A?(?B?)，则

??I若x?A，则x?A?B?(??I)，因而x??(A?B?)；

??I若x?A，则???I,x?B?，因而???I,x?A?B?，故x??(A?B?)。于

??I是

A?(?B?)??(A?B?)。

??I??I反之，设x??(A?B?)，则???I,x?A?B?。

??I若x?A，显然x?A?(?B?)；

??I若x?A，则???I,x?B?，因而x??B?，即x?A?(?B?)。所以，

??I??I(A?B?)?A?(?B?)。 ????I?I综上可得，A?(?B?)＝?(A?B?)。

??I??I15．填空：设A,B是两个集合。

(a)x?A?B?__________________； (b)x?A?B?__________________；

(c)x?A\\B?___________________； (d)x?A?B?___________________；

解：(a) x?A且x?B； (b) x?A或x?B

（a）(A\\B)?(A\\C)；（b）(A?B)\\(A?C) （c）(A\\B)?(A\\C)；（d）(A?B)\\(A?C) （e）(A?B)?(A?C) 答案：c。

(A\\B)?(A\\C)?(A?BC)?(A?CC)?A?(BC?CC)?A?(B?C)?A\\(B?C)P20习题

1．设A,B,C为集合，并且A?B?A?C，则下列断言哪个成立？

(1)B?C；(2)A?B?A?C；(3)A?BC?A?CC；(4)AC?B?AC?C。答案：d。

在AC?B?AC?C两边同时并上A即得A?B?A?C。 2．设A,B,C为任意集合，化简

(A?B?C)?(AC?B?C)?(A?BC?C)?(A?B?CC)?(A?B?C)?(A?B?C)?(A?B?C)CCCCCC

证：证1：原式＝(B?C)?(A?BC)?(B?CC)?(AC?BC?C)

?B?(A?BC)?(AC?BC?C)?(A?B)?(AC?BC?C)?(A?B)?((A?B)?C)?A?B?C证2：令原式＝T，全集为S，则

S?T?(AC?BC?CC)且T?(AC?BC?CC)??，故 T?(AC?BC?CC)C?A?B?C。

3．证明：（1）A?B?(A?B)?(AC?BC)；（2）(A?B)C?(A?B)?(AC?BC)；

（3）(A?B)C?(AC?B)?(A?BC)

证：（1）(A?B)?(AC?BC)?((A?B)?AC)?((A?B)?BC) ?(B?AC)?(A?BC)?(A\\B)?(B\\A)?(A?B)

（2）证：(A?B)C?((A?B)?(AC?BC))C 〔根据（1）〕

?(A?B)C?(AC?BC)C?(AC?BC)?(A?B)

（3）证：(AC?B)?(A?BC)?((AC?B)?A)?((AC?B)?BC) 〕 ?(A?B)?(AC?BC)?(A?B)C 〔根据（2）

4．设M1,M2,?和N1,N2,?是集合S的子集的两个序列，对i?j,i,j?1,2,?，有

Ni?Nj??。令Q1?M1,Qn?Mn?(?Mk)C,n?2,3,?。试证：

k?1n?1Nn?Qn??(Ni?Mi)。

i?1n证：?x?Nn?Qn?(Nn\\Qn)?(Qn\\Nn)

当n＝1时，x?N1?Q1?N1?M1??(Ni?Mi)，故Nn?Qn??(Ni?Mi)

i?1i?1nn当n≥2时，设x?N?Q?N(Q\\n)Q(nN?\\n)nnn则

有x?(Nn\\Qn)或x?(Qn\\Nn)。

1.若x?(Nn\\Qn)，则x?Nn但x?Qn?Mn?(?Mk),即x?Mn或x??Mk，

ci?1i?1n?1n?1因此有x?Mn或x?Mi(i?n?1)。于是

（1）若x?Nn且x?Mn，有x?Nn\\Mn?Nn?Mn??(Ni?Mi)；

i?1n（2）若x?Nn且x?Mi(i?n?1)，由Ni?Nj??(i?j)，有x?Ni(i?n?1)且

x?Mi，于是x?Mi\\Ni?Mi?Ni??(Ni?Mi)。

i?1n2.若x?Qn\\Nn，则x?Qn?Mn?(?Mk)c，即x?Mn但x?Nn。于是

i?1n?1x?Mn\\Nn?Mn?Nn??(Ni?Mi)。

i?1n综上可得：Nn?Qn??(Ni?Mi)

i?1n5．设X是一个非空集合，An?X,An?1?An,n?1,2,3,?试证：?n，有

An??(Am?Am?n? cm?1)??Am。

m?n? cm?n，故Am?An，显证明：由于Am?1?Am，故Am?Am?1?Am\\Am?1。因为

??然有?(Am?Am?n cm?1)??Am?An。

m?n对于?x?An，假设存在p(p?n)，使得x?Ap，必可找到其中最小的值p0，使得x?Ap0\\Ap0?1，故x??(Am?Am?n? cm?1)??Am；

m?n? 9

假如不存在p，则x??Am，故x??(Am?Am?nm?n?? cm?1)??Am。

m?n?综上可得：An?

?m?n?(A?m?A cm?1)??Am。

m?n?所以An＝?(Am?Am?n cm?1)??Am。

m?n?6．设V是任一集合，证明：

?S,T,W?2V有S?T?W当且仅且S?T?S?W且S?W。证：?因为S?T?W，故S?T?T\\S?W\\S?S?W。

?先证S?T。设x?S，则

若x?T，则x?S\\T?S?T?S?W?W\\S，故x?W且x?S，矛盾。所以x?T，即S?T。

其次，证明T?W。设x?T，则有两种情况：若x?S。则x?T\\S?S?T?S?W?W\\S，故x?W。若x?S。由S?W，知x?W。总之，?x?T，有x?W，故T?W。

7．设A1,A2,?为一集序列，记A为这样的元素的全体形成的集合：x?A当且仅当在序列A1,A2,?中有无穷多项An含有x。集合A称为集序列A1,A2,?的上极限，记为limAn，即limAn?A。又记A为这样的元素全体形成的集合；序列A1,A2,?n??n??中只有有限项不含有这样的元素。称A为序列A1,A2,?的下极限，并记

limAn?A。证明；

n??（1）limAn???Ak；（2）limAn???Ak。

n??n?1k?nn??n?1k?n????证：（1）?x?limAn，在序列A1,A2,?中只有有限项不含x，在不含x的

n??项中必可找到下标最大的一项Ap?1（若各项均含x，则令p＝0），有x??Ak，

k?p? 10

故x???Ak，即

n?1k?n??limAn???Ak。

n??n?1k?n??反之，?x???Ak，必?p使得x??Ak，即?k?p时，x?Ak。而集合

n?1k?n???k?pA1,A2,?,AP?1中即使都不含有x，但也仅有有限项不含x，故x?limAn。因此

n??n?1k?n??Ak?limAn。

n????综上可得：limAn＝??Ak。

n??n?1k?n??（2）?x?limAn，因为A1,A2,?中有无穷多项含有x，故?N，当n?N时，

n??x?An，因此x??Ak，从而x???Ak，即

k?nn?1k?n???limAn???Ak

n??n?1k?n??反之，?x???Ak，则?n?1,x??Ak，即A1,A2,?中有无穷多项多含x，

n?1k?n???k?n所以x?limAn，即

n??n?1k?n??Ak?limAn

n????综上可得：limAn???Ak。

n??n?1k?n??8．证明：limAn?limAn

n??n??证：?x?limAn，由limAn定义可知：序列A1,A2,?中只有有限项不含x，故

n??n??必可找

到不含x的下标最大的一项AP，可见此时AP?1,AP?2,?均含x，即有无限项含x，故x?limAn。因此

n??limAn?limAn。

n??n??

P25习题

1．设A?{a,b,c},B?{e,f,g,h},C?{x,y,z}。求A?B,B?A,A?C,A2?B。

解：

A?B?{(a,e),(a,f),(a,g),(a,h),(b,e),(b,f),(b,g),(b,h),(c,e),(c,f),(c,g),(c,h)}B?A?{(e,a),(e,b),(e,c),(f,a),(f,b),(f,c),(g,a),(g,b),(g,c),(h,a),(h,b),(h,c)}A?C?{(a,x),(a,y),(a,z),(b,x),(b,y),(b,z),(c,x),(c,y),(c,z)} A2?B?{((a,a),e),((a,a),f),((a,a),g),

((a,a),h),((a,b),e),((a,b),f),((a,b),g),((a,b),h),((a,c),e),((a,c),f),((a,c),g),((a,c),h),((b,a),e),((b,a),f),((b,a),g),((b,a),h),((b,b),e),((b,b),f),((b,b),g),((b,b),h),((b,c),e),

((b,c),f),((b,c),g),((b,c),h),((c,a),e),((c,a),f),((c,a),g),((c,a),h),((c,b),e),((c,b),f),((c,b),g),((c,b),h),((c,c),e),((c,c),f),((c,c),g),((c,c),h)}2．设A,B为集合，试证：A×B＝B×A的充要条件是下列三个条件至少一个成立：

（1）A??；（2）B??；（3）A?B。

证：?若（1）成立，A?B???B?A。若（2）成立，同上。

若（3）成立，A×B=B×B=B×A。

?假设必要性不成立，即A??,B??,A?B。故不妨设?x使得x?A,x?B。设y?B，则(x,y)?A?B,(x,y)?B?A，矛盾。于是，假设不成立。因而必要性成立。

必要性也可以如下证明：

1.若A?B?B?A??，则A??或B??。

,y?B2.若A?B?B?A??，则?x?A，有(x,y)?A?B?B?A。于是x?B,y?A，因此A?B且B?A，故A=B。

3．设A,B,C,D为任四个集合，证明：

(A?B)?(C?D)?(A?C)?(B?D)

证：?(x,y)?(A?B)?(C?D)，有x?A?B,y?C?D，即

x?A,x?B,y?C,y?D。所以(x,y)?A?C,(x,y)?B?D，因此

(x,y)?(A?C)?(B?D)，从而

(A?B)?(C?D)?(A?C)?(B?D)。

反之，?(x,y)?(A?C)?(B?D)，有x?A,x?B,y?C,y?D。即

(x,y)?(A?B)?(C?D)，从而

(A?C)?(B?D)?(A?B)?(C?D)。

因此，(A?B)?(C?D)＝(A?C)?(B?D)。 4．设E1,E2,E3,E4为任意集合，试证：

(E1?E2)\\(E3?E4)?((E1\\E3)?E2)?(E1?(E2\\E4))

证：?(x,y)?(E1?E2)\\(E3?E4)，有x?E1,y?E2且x?E3或y?E4。则若x?E3，则x?E1\\E3)，故(x,y)?(E1\\E3)?E2)，即

(x,y)?((E1\\E3)?E2)?(E1?(E2\\E4))。

若y?E4，同理可证(x,y)?((E1\\E3)?E2)?(E1?(E2\\E4))。从而

(E1?E2)\\(E3?E4)?((E1\\E3)?E2)?(E1?(E2\\E4))。

反之，?(x,y)?((E1\\E3?)E2?)(E1?(E2\\E4，))则(x,y)?(E1\\E3)?E2)或

(x,y)?E1?(E2\\E4)，即x?E1，y?E2但x?E3或x?E1，y?E2但y?E4。从而有(x,y)?E1?E2，但(x,y)?E3?E4，即(x,y)?(E1?E2)\\(E3?E4)，从而

((E1\\E3)?E2)?(E1?(E2\\E4))?(E1?E2)\\(E3?E4)。

综上可得：(E1?E2)\\(E3?E4)＝((E1\\E3)?E2)?(E1?(E2\\E4))。 5．设A?X,B?Y，试证：(A?B)C?(AC?B)?(A?BC)?(AC?BC)

证：?(x,y)?(A?B)C，则(x,y)?(A?B)，故x?A或y?B。于是 1. 若x?A，则x?AC。因此

(1)若y?B，则(x,y)?AC?B?(AC?B)?(A?BC)?(AC?BC)。

(2) 若y?B，则y?BC，即(xy,)?ACB?2.若x?A，则必有y?B，故(x,y)?A?BCC?(ACB?)(A?B?)C(AB??)CCC?(AC?B)(A?B?)C(A?B?)C。。

综上可得：(A?B)C?(AC?B)?(A?BC)?(AC?BC)。反之，?(x,y)?(AC?B)?(A?BC)?(AC?BC)，则

(x,y)?AC?B或(x,y)?A?BC或(x,y)?AC?BC，于是，

(1)若(x,y)?AC?B，则x?A且x?B，即(xy于是(x,y)?(A?B)C。 ,)?AB?，

,)?AB?，(2)若(x,y)?A?BC，则x?A且x?B，即(xy于是(x,y)?(A?B)C。 ,)?AB?，(3)若(x,y)?AC?BC，则x?A且x?B，即(xy于是(x,y)?(A?B)C。

综上可得：(AC?B)?(A?BC)?(AC?BC)?(A?B)C。于是(A?B)C?(AC?B)?(A?BC)?(AC?BC)。 7．设A,B,C是三个任意集合，证明：

A?(B?C)?(A?B)?(A?C)

证：A?(B?C)?A?((B\\C)?(C\\B))?A?(B\\C)?A?(C\\B)

?((A?B)\\(A?C))?((A?C)\\(A?B))?(A?B)?(A?C)

8．设A,B为集合，下列命题哪些为真？

（1）(x,y)?A?B?x?A且y?B （2）(x,y)?A?B?x?A或y?B （3）2A?B?2A?2B

（4）若A?C?B?C，则A?B。（5）若A?C?B?C,C??，则A?B。

答案：（2），（5）为真。

9．设A有m个元素，B有n个元素，则A×B是多少个序对组成的？A×B有多少个不同的子集？

答：A×B有mn个序对；A×B有2mn个不同子集。

10．设A,B是两个集合，B??，试证：若A?B?B?A，则A?B。

证：?x?A，因为B??，故在B中任取一元素y，必有(x,y)?A?B，因而

(x,y)?B?B，故x?B。从而A?B。

反之，?x?B，因为B??，故在B中任取一元素y，必有(x,y)?B?B，因而(x,y)?A?B，故x?A。从而B?A。

于是A?B。

P33习题

1.某班学生中有45％正在学德文，65％正在学法文。问此班中至少有百分之几的学生正同时学德文和法文？

解：设A,B分别为正在学德文和法文的学生的集合，班级总人数为n，则

A?n?45%,B?n?65%，于是同时学习德文和法文的人数为A?B，故 A?B?A?B?n?n?10%。

于是全班至少百分之十的学生同时学德文和法文。

2．求1到250之间不能被2，3，5，7中任一数整除的数的个数。

解：设S?{1,2,?,250}，在S上的定义性质Pn具有性质P11,P2,P3,P4,?n?S，（相应地P2,P3,P4）当且仅当2|n(3|n,5|n,7|n)。

令Ai为S中具有性质Pi之集，i?1,2,3,4，则

??250??A1??2k|k?1,2,?,???2??????250??A2??3k|k?1,2,?,???3????

??250??A3??5k|k?1,2,?,???5??????250??A4??7k|k?1,2,?,???7????所求为：

S?A1?A2?A3?A4?250?((125?83?50?35)?(41?25?17?16?11?7)?(8?5?3?2)?1)

?250?(293?117?18?1)?57 15

3．设A,B是两个有限集，试求22解：22A?BA?B??

?22A?B?22A?B?22A?B

4．马大哈写n封信，n个信封，把n封信放入到n个信封中，求全部装错的概率是多少？

解：Sn?n!，令A表示所有信都装错的集合，即

A?{i1,i2,?,in|i1?1,i2?2,?,in?n}。

令Ai表示第i个信封恰好装对的集合，则AiC?A。所以全部装错的集合为：

CC。 A?A1C?A2???An于是，易得

Ai?(n?1)!,Ai?Aj?(n?2)!,i?j。

对于1?i1?i2???ik?n，有 Ai1?Ai2???Aik?(n?k)!。又

A?A?A???A?S??Ai?n!??Ai?C1C2Cni?1i?1nn1?i?j?n?Ai?Aj???(?1)?n!(1?n?Ai?1ni12n?n!?Cn(n?1)!?Cn(n?2)!???(?1)nCn(0)!1111?????(?1)n)，故1!2!3!n!AA?1111?P????1??????(?1)n??e?1?0.3678Snn!?1!2!3!n!?

〔答案：0.3679，当n≥10时，概率都近似等于0.3679〕。

5．毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，

但未能与所有姑娘跳过。同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。证明：在所有参加舞会的小伙与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。

证：设F?{f1,f2,?,fn}是小伙的集合，G?{g1,g2,?,gm}是姑娘的集合。与f1跳舞的姑娘的集合用Gf1表示；与f2跳舞的姑娘的集合用Gf2表示；

? ? ?

与fn跳舞的姑娘的集合用Gfn表示；

于是，由题意：Gf1?Gf2???Gfn?G且Gfi??且Gfi?G，i?1,2,3,?,n。若存在Gfi,Gfj(i?j)，使得Gfi?Gfj且Gfj?Gfi，则结论成立。反证法：假设不存在Gfi和Gfj满足Gfi?Gfj且Gfj?Gfi。于是

?i,j(i?j),Gfi与Gfj应满足：Gfi?Gfj或Gfj?Gfi必有一个成立。因此把Gf1，Gf2，?，Gfn重新排列有：Gf i1?Gfi2???Gfin。从而fin与所有的姑娘都跳过舞，矛盾。

因此假设不成立，本题得证。

第二章映射

P39习题

1. 设A，B是有穷集，A?m,B?n

（1）计算AB；（2）从A到A有多少个双射？解：（1）AB?mn；（2）从A到A共有m!个双射。

2. 设X是一个有穷集合，证明：从X到X的部分映射共有(X?1)X个。

证：设f:A?X,A?X，则f是X到X的一个部分映射。设X?n

00当A??时，f的个数为Cnn?1 11当A是单元素集时，f的个数为Cnn?n 22当A中有2个元素时，f的个数为Cnn

kk当A中有k个元素时，f的个数为Cnn

nn当A中有n个元素时，f的个数为Cnn

0011kknn因此f的总个数为Cnn+Cnn+?+Cnn+?+Cnn＝(1?n)n

＝(X?1)X

即从X到X的部分映射共有(X?1)X个。

4.设u1,u2,?,umn?1是一个两两不相交的整数构成的数列，则必有长至少为n?1的递增子序列或有长至少为m?1的递减子序列。

证：令A?{u1,u2,?umn?1}，则A?mn?1。设以ui为首项的最长递增子序列的长度为??i，设以ui为首项的最长递减子序列的长度为??i。

反证法：假设题中结论不成立，则??,2,3,?,mn?1。 i?n,?i?m,i?1??是单射。令?:A?{1,2,?,n}?{1,2,?,m},?ui?A，?(ui)?(??,?ii)，则

实际上，?ui,uj?A且ui?uj(i＜j)，则

?????若ui＞uj，则??i＞?j，所以(?i,?i)?(?j,?j)；

即?(ui)??(uj)。

?????若ui＜uj，则??i＞?j，所以(?i,?i)?(?j,?j)；

即?(ui)??(uj)。

故?为单射，从而就有mn?1?mn矛盾。

P43习题

1. 证明：从一个边长为1的等边三角形中任意选5个点，那么这5个点中必有2个点，它们之间的距离至多为1/2，而任意10个点中必有2个点其距离至多是1/3。

证：(1) 将边长为1的等边三角形4等分，得到4个边长为1/2的小等边三角形。

任给5个点，由鸽巢原理可知必有一个小等边三角形里面至少有2个点，又因为小等边三角形中任意两个点之间的距离至多为1/2，因此5个点中必有2个点，它们之间的距离至多为1/2。

(2) 连接各边的三等分点，则可得到9个边长都为1/3的小等边小角形，每个小等边三角形中任意两个点之间的距离至多为1/3。将10个点放入该大等边三角形中，则由鸽洞原理，必有一个小等边三角形中至少有2个点，因此任意10个点中必有2个点其距离至多为1/3。

2.已知m个整数a1,a2,?am，试证：存在两个整数k,?,0?k＜??m，使得

ak?1?ak?2???a?能被m整除。

证：考察下式：

a1a1?a2a1?a2?a3?a1?a2???am

若第i式能被m整除，则显然成立，此时k?0,??i；

若任一式都不能被m整除，则考察各式被m整除后的余数，如下式：

a1?q1m?r1a1?a2?q2m?r2a1?a2?a3?q3m?r3?a1?a2???am?qmm?rm

由于每一个都不能被m整除，故共有m个余数—相当于m个物体。而任意整数被m除后，只有m－1个余数——相当于m－1抽屉，于是由鸽巢原理可知必有两个余数相等。设这两个余数为ri,rj,i?j(i＜j)，对应两式相减便有：

ai?1?ai?2???aj可被m整除，此时k?i,??j。

3. 证明在52个整数中，必有两个整数，使这两个整数之和或差能被100整除。

证：设a1,a2,?,a52是52个整数，令?i为ai被100除后所得的余数，即

ai?100qi??i,0??i?99,i?1,2,?,52[相当于52个物体]。

任意一个整数被100除以后的余数为0，1，2，…，99，把它们分成51个类，即{0},{1,99},{2,98},…{49,51},{50}[相当于51个盒子]。

把52个余数?i,i?1,2,?,52放入到51个类中，必在两个余数放在一个类里。设在一个类中的两个余数分别为?i与?j，i?j。则有

（1）若?i??j，则?i??j?0，即ai?aj能被100整除。（2） ?i??j，则?i??j?0，即ai?aj能被100整除。

5.设a1,a2,?,an为1,2,3,?,n的任一排列，若n是奇数且

(a1?1)(a2?2)?(an?n)?0，

则乘积为偶数。

解：反证法：若(a1?1)(a2?2)?(an?n)为奇数，则(ai?i)中的ai与i必是一

?n??n?个为奇数，一个为偶数。而n为奇数，故奇数个数为???1比偶数??多一个，

?2??2?这是不可能的。

P46习题

1.设f:X?Y，C,D?Y，证明f?1(C\\D)?f?1(C)\\f?1(D)

证1：?x?f?1(C\\D)，则f(x)?C\\D，即f(x)?C但f(x)?D。于是

x?f?1(C)但x?f?1(D)，因此x?f?1(C)\\f?1(D)，故f?1(C\\D)?f?1(C)\\f?1(D)

反之，设x?f?1(C)\\f?1(D)，有x?f?1(C)且x?f?1(D) 因此f(x)?C且f(x)?D，即f(x)?C\\D 从而x?f?1(C\\D)

故f?1(C)\\f?1(D)?f?1(C\\D)

因而f?1(C\\D)?f?1(C)\\f?1(D)

证2：f?1(C\\D)?f?1(C?Dc)?f?1(C)?f?1(DC)

?f?1(C)?(f?1(D))C?f?1(C)\\f?1(D)

2. 设f:X?Y, A,B?X，证明

（1）f(A?B)?f(A)?f(B) （2）f(A?B)?f(A)?f(B) （3）f(A)\\f(B)?f(A\\B)

证：（1）设y?f(A?B)，则?x?A?B使得y?f(x)。于是，x?A或x?B。因此，y?f(A)或y?f(B)，所以y?f(A)?f(B)，故

f(A?B)?f(A)?f(B)

反之，设y?f(A)?f(B)，则y?f(A)或y?f(B)。于是?x?A或x?B，使得f(x)?y。因此不论何种情况都?x?A?B，使得f(x)?y。因此y?f(A?B)，故

f(A)?f(B)?f(A?B)

因此，f(A)?f(B)?f(A)?(B)

（2）设y?f(A?B)，则?x?A?B，使得y?f(x)。于是，x?A且x?B。从而，y?f(A)且y?f(B)，所以y?f(A)?f(B)，故

f(A?B)?f(A)?f(B)

（3）设y?f(A)\\f(B)，则y?f(A)但y?f(B)。于是?x?A使得f(x)?y，且x?B，从而?x?A\\B，使得f(x)?y。

故y?f(x)?f(A\\B)，即

f(A)\\f(B)?f(A\\B)。

3.设f:X?Y，A?X,B?Y，证明：

f(f?1(B)?A)?B?f(A)

证：设y?f(f?1(B)?A)，则?x?f?1(B)?A，使得f(x)?y。于是x?f?1(B)且x?A，即f(x)?B且f(x)?f(A)，因此y?f(x)?B且y?f(A)，即

y?B?f(A)，从而

f(f?1(B)?A)?B?f(A)。

反之，设y?B?f(A)，则y?B且y?f(A)。于是?x?A且x?f?1(B)，使得f(x)?y。从而?x?f?1(B)?A，使得f(x)?y，因此y?f(f?1(B)?A)。从而

B?f(A)?f(f?1(B?A)) 因此，f(f?1(B?A))?B?f(A)。

4.设f:X?Y,A?X,B?Y。以下四个小题中，每个小题均有四个命题，这四个

命题有且仅有一个正确，请找出正确的那个。

（1）（a）若f(x)?f(A)，则x未必在A中（b）若f(x)?f(A)，则x?A （c）若f(x)?f(A)，则x?A

（d）若f(x)?f(A)，则x?Ac

（2）（a）f(f?1(B))?B （b）f(f?1(B))?B

（c）f(f?1(B))?B （d）f(f?1(B))?Bc （3）（a）f?1(f(A))?A （b）f?1(f(A))?A

（c）f?1(f(A))?A （d）上面三个均不对（4）（a）f(A)?? （b）f(B)??

（c）若y?Y,则f?1(y)?x （d）若y?Y,则f?1(y)?x 答案：（a）（b）（c）（d）

7.设f:X?Y,A?X,则(f(A))c?f(Ac)成立吗？

解：不成立。

反例：设X?{1,2,3},Y?{a,b,c}。

f:X?Y,f(1)?a,f(2)?a,f(3)?b。

1 o 2 o o a o b o c X Y 令A?{1,2}，则Ac?{3}。

f(A)?{a}，(f((A))?{b,c},但f(A)?b。

cc3 o 8.设X是一个无穷集合，f:X?Y。证明：存在X的一个真子集E使得f(E)?E。

证：取x0?X，令x1?f(x0),x2?f(x1),?,xn?f(xn?1),?。若到某一位与前面有重复项，设为第k项，即f(xk)?xi(i?k)。令E?{x0,x1,x2,?,xk}?X，则

f(E)?E且E?X。

若xi互不相同，令E1?X\\{x0}?X，则f(E1)?E1。 [不去掉x0可能就会有E1?X]

9.设f:A?B，证明?T?2B，都有f(f?1(T))?T?f(A)

证；若T??，则f(f?1(T))??,T?f(A)??,因而f(f?1(T))?T?f(A)。若T??，设y?f(f?1(T))，则?x?f?1(T)，使得f(x)?y且x?A，于是

y?f(x)?T且y?f(x)?f(A)，因此y?T?f(A)。

故f(f?1(T))?T?f(A)

反之，设y?T?f(A)，则y?T且y?f(A)。于是?x?f?1(T)且x?A，使得f(x)?y。从而，f(x)?f(f?(T)且f(x)?f(A)，因此y?f(x)?f(f?1(T)?A))，而f?1(T)?A，所以f(f?1(T)?f(A)，于是y?f(f?1(T))，故

T?f(A)?f(f?1(T))

从而T?f(A)?f(f?1(T))

P50习题

1.设X?{a,b,c},Y?{0,1},Z?{2,3},f:X?Y,f(a)?f(b)?0，

f(c)?1;g:Y??，g(0)?2,g(1)?3，试求g?f。

解：

g?f(a)?g(0)?2g?f(b)?g(0)?2 g?f(c)?g(1)?3因此g?f:X?Z,g?f(a)?2,g?f(b)?2,g?f(c)?3。

2.设X,Y,Z是三个非空集合，Z?2。证明：f:X?Y是满射当且仅当不存在从Y到Z的映射g1和g2，使得g1?g2，但g1?f?g2?f。

证：?因f:X?Y且f为满射，故?y?Y,?x?X，使得f(x)?y。假设存在g1,g2,g1?g2，但g1?f?g2?f。因为g1?g2，所以?y0?Y，使得对于上面的y0，?x0?X（f是满射），使得g1(f(x0))?g2(f(x0)) g1(y0)?g2(y0)。

[g1(y0)?g2(y0)]，即g1f(x0)?g2f(x0)。故g1?f?g2?f与g1?f?g2?f，矛盾。

所以假设不成立。也可以用如下方法：

f满射?f右可逆??h:Y?X，使得f?h?IY?假设g1?f?g2?f得到

g1?g2，命题得证。

?f:X?Y，假设f不是满射，则?y0?Y，使得?x?X,f(x)?y0。构造两个映射g1,g2:Y?Z，

当y?y0时，g1(y0)?g2(y0)；当y?y0时，g1(y)?g2(y)。因为Z?2，故此时g1?g2，但

?x?X,g1?f(x)?g1(y?y0)?g2(y?y0)?g2?f(x)

即g1?f＝g2?f，与假设不存在g1?g2，但g1?f?g2?f矛盾，故f一定是满射。 3.设X,Y,Z是三个非空的集合，X?2，证明：f:X?Y是单射当且仅当不存在从Z到X的映射g1,g2，使得g1?g2，但f?g1?f?g2。

证：?f是单射，则?x1,x2,x1?x2，有f(x1)?f(x2)。假设存在g1和g2：

Z?X,g1?g2，因为X?2，于是?z0?Z，使得g1(z0)?g2(z0)。

而由于f为单射，故f(g，，故?f(g)即f?g?g1(z0))2(z0)1(z0)?f2(z0)f?g1?f?g2矛盾。

可以用：f单射?f左可逆的??h使得hf?IX?由f?g1?f?g2?g1?g2得证。

逆否命题：g1?g2?fg1?fg2。

则?x1,x2?X,x1?x2，但f(x1)?f(x2)。构造两个映射g1?假设f不是单射，

和g2:Z?X,?z?Z,令g1(z)?x1,g2(z)?x2，由于X?2，故若x1?x2，则有

g1?g2。但?z?Z,f?g1(z)?f(x1)?f(x2)?f?g2(z)，于是有f?g1?f?g2矛盾。

P55习题

1. 设N?{1,2,3,?}，试构造两个映射f和g：N?N，使得

（1）fg?IN，但gf?IN；（2）gf?IN，但fg?IN。

解：（1）fg?IN但gf?IN，故f是满射，但f不是单射。于是令：

f:N?N,f(1)?1,f(n)?n?1,n?2，g:N?N,?n?N,g(n)?n?1，则

fg?IN但gf?IN。事实上，当n＝1时，gf(1)?g(f(1))?g(1)?2，故gf?IN。

（2）自己做。 2.设f:X?Y则

（1）若存在唯一的一个映射g:Y?X，使得gf?IX，则f是可逆的吗？（2）若存在唯一的一个映射g:Y?X，使得fg?IY，则f是可逆的吗？答案：（1）f不一定可逆。当X?1时，f不一定可逆。当X?2时，f可逆。（2）f一定可逆。

证：由fg?IY，得f是单射。假设f不是满射，则g不唯一，矛盾。 3.设f:X?Y,X?m,Y?n，则

（1）若f是左可逆的，则f有多少个左逆映射？（2）若f是右可逆的，则f有多少个右逆映射？解：令X?(x1,x2,?,xm),Y?(y1,y2,?,yn)，则（1）如图1(a)所示：有mn?m；（2）如图1(b)所示：有

f?1(y1)?f?1(y2)???f?1(yn)。

x1x2x3xmy1y2y3ymn-m个y1y2y3yn（a） (b)

图1

5. 是否有一个从X到X的一一对应f，使得f?f?1，但f?IX？解：存在。f为对换即可。

P63习题

?12345??12345??1?11.设?1???，?2＝??，求?1?2,?2?1,?1,?2。

?43215??32514?解：

?12345??12345??1?2???,?2?1???15234???23541??1?1???12345??1?12345??,?2???43215???42153?

?123456789?2.将置换??分解成对换的乘积。

?791652348??123456789?解： ????173??29846?

791652348??=(1 7)(1 3)(2 9)(2 8)(2 4)(2 6)

3.设?是任一n次置换，试证：?与??1的奇偶性相同。

证：假设?与??1的奇偶性不同，不妨设?为奇置换，??1为偶置换。因为

???1?I（I为恒等置换），又I?(ij)(ij)，因而I是偶置换。

??1是奇置换与I是偶置换矛盾。而??因而假设不成立，故?与??1奇偶性相同。

5.任一偶置换均可被分解成3－循环置换（123），（124）…（12n）中若干之乘积。

证：?i,j,s,t?{1,2,?,n}, i?j,s?t

(ij)(st)?(1i)(1j)(1i)(2s)(2t)(2s)?(1i)(1j)(2s)(1j)(2t)(2s)

?(1i)(2s)(1j)(2t)(1i)(2s)

?(12s)(12i)(12t)(12j)(1 2 s)(1 2 i)

?12s??12i??12si?因为(12s)(12i)?????????(1i)(2s)

2s12i1is21???????12t??12(12t)(12j)?????2t1??2j因此本题得证。 6. 证明下列置换等式

（1）(ac1?chbd1?dk)(ab)?(ac1?ch)(bd1?dk)

j??12tj??????(1j)(2t) 1??jt21??ac1c2?chbd1?dk?证：(ac1?chbd1?dk)(ab)???(ab)

?c1c2c3?bd1d2?a??ac1c2?chbd1?dk?＝??

ccc?add?b12?123??(ac1?ch)(bd1?dk)

?ac1?chbd1?dk?（2）(ac1?ch)(bd1?dk)(ab)???(ab)

?c1c2?ad1d2?b??ac1?chbd1?dk?????(ac1?chbd1?dk) cc?bdd?a?1212?8.在所有的n次置换中，有多少个n—循环置换？

?ii?in?解：(i1,i2,?,in)??12?

?i2i3?i1?对i1，有n种选择对i2，有（n-1）种选择 ??

对in有1种选择

因此共有n!种排列

对每个n－循环置换，均有n种排列，因此

n!n－循环置换的个数为?(n?1)!个

nP70习题

3. 找一个既不满足交换律又不满足结合律的二元运算

解：n维向量空间中向量的叉积运算。 4. 给出一个三元运算的例子

解：求三个正整数的最大公因数。

5. 设A?{a,b,c,d}，A上的代数运算“?”如表所示。代数运算“?”是否满足交换律？结合律？“?”有单位元吗？

解：不满足交换律，因为运算表不对称。d?c?a,c?d?d,d?c?c?d。也不

(b?b)?c?a?c?c满足结合律，b?(b?c)?b?a?b

(b?b)?c?b?(b?c)单位为a o a b c d a a b c d b b a a c c c a b a d d c d b 6.设N?{1,2,3,?}，?m,n?N,m?n?nlog10m。

那么“?”是N上的代数运算吗？为什么？解：当m=1时，log10m?0，nlog10m?0,0?N

因此“?”不是N上的代数运算。

7. 设“?”是X上的代数运算，则应该怎样定义“?”的逆运算？回忆一下，逆运算通常比原运算“难算”，这是为什么？例如，积分比微分难，减法比加法难，除法比乘法难，开方比幂方运算难。

解：“?”的逆运算可以这样定义：一个从X到X?X?X???X?Xn的映射 “?”称为X上的n元运算的逆运算

“?”的逆运算的象集所在的集合X?X?X???X的元素的个数是X的元素个数的mn?1倍（设X?m），因而逆运算的个数很多，因此得到其中的一种就较困难，故逆运算较难算。

第三章关系

P86习题

1.给出一个既不是自反的又不是反自反的二元关系？

解：设X?(a,b,c),R是X上的一个二元关系且R?{(a,a),(a,b)}即可。 2.是否存在一个同时不满足自反性，对称性，反对称性，传递性和反自反性的二元关系？

解：存在。

设X?{a,b,c}，R是X上的二元关系R?{(a,a),(a,c),(a,b),(c,a)}。 3.设R，S是X上的二元关系，下列命题哪些成立：

a)若R与S是自反的，则R?S,R?S分别也是自反的。 b) 若R与S是对称的，则R?S,R?S分别对称的 c) 若R与S是传递的，则R?S也是传递的 d) 若R与S不是自反的，则R?S也不是自反的 e) 若R与S是反自反的，则R?S,R?S也是反自反的 f) 若R是自反的，则Rc也是反自反的。

g) 若R与S是传递的，则R\\S是传递的答案：真真真假真真假

4.实数集合上的“小于”关系?是否市反自反的？集合X的幂集上的“真包含”关系?是否是反自反的？为什么？

证：实数集合上的“小于”关系?是反自反的；

集合X的幂集上的“真包含”关系?也是反自反的。

5.设R、S是X上的二元关系。证明：

（1）(R?1)?1?R；（2）(R?S)?1?R?1?S?1

（3）(R?S)?1?R?1?S?1；（4）若R?S，则R?1?S?1

证：（1）?(x,y)?(R?1)?1，则(y,x)?R?1，即(x,y)?R，因此(R?1)?1?R。反之，?(x,y)?R，则(y,x)?R?1，即(x,y)?(R?1)?1，因此R?(R?1)?1。从而(R?1)?1?R

（2）?(x,y)?(R?S)?1，则(y,x)?R?S，

即(y,x)?R或(y,x)?S。于是(x,y)?R?1或(x,y)?S?1，即(x,y)?R?1?S?1，因而(R?S)?1?R?1?S?1。反之，?(x,y)?R?1?S?1，则(x,y)?R?1或(x,y)?R?1。于是(y,x)?R或(y,x)?S，即(y,x)?R?S。从而(x,y)?(R?S)?1，因此，R?1?S?1?(R?S)?1。故(R?S)?1?R?1?S?1

（3）?(x,y)?(R?S)?1，则(y,x)?R?S。于是(y,x)?R且(y,x)?S，从而(x,y)?R?1且(x,y)?S?1，即(x,y)?R?1?S?1 因此(R?S)?1?R?1?S?1

反之，设(x,y)?R?1?S?1，则(x,y)?R?1且(x,y)?S?1 于是(y,x)?R且(y,x)?S，即(y,x)?R?S。从而(x,y)?(R?S)?1，因此R?1?S?1?(R?S)?1 故R?1?S?1?(R?S)?1

（4）?(x,y)?R?1，则(y,x)?R

因为R?S，所以(y,x)?S，于是(x,y)?S?1 因而R?1?S?1

6.设R是X上的二元关系，证明：R?R?1是对称的二元关系。

证1：(R?R?1)?1?R?1?(R?1)?1，故R?R?1是对称的。

证2：则(x,y)?R或(x,y)?R?1，即(y,x)?R?1或(y,x)?R。 ?(x,y)?R?R?1，于是(y,x)?R?R?1，因此R?R?1是对称的。

9.有人说：“若R是X上的二元关系，只要R是对称的和传递的，则R必是自反的。”他的证明如下：若xRy，则由R的对称性便知有yRx。于是由xRy和yRx以及R的传递性即得xRx。所以，R是自反的。他的推论错在什么地方？这个结论是否对呢？

解：若R??，则R是对称的，传递的，反自反的。

若R??，只有?x?X使得xRx，才能说R是自反的。此人只是说明了X中的部分元素满足了xRx，因而是错误的。

所以这个结论不对。

P92习题

1.“父子“关系的平方是什么关系？

解：“父子“关系的平方是”祖孙“关系

2.设X={1,2,3,4},R={(1,2),(2,2),(3,4)},S={(2,3),(3,1),(4,2)}

试求：R?S,S?R,R2,S2,R?(S?R),(R?S)?R。解：

R?S?{(1,3),(2,3),(3,2)}S?R?{(2,4),(3,2),(4,2)} R?{(1,2),(2,2)} S2?{(2,1),(4,3)}2

R?(S?R)?R?{((2,4),(3,2),(4,2)} ?{(1,4),(2,4),(3,2)}(R?S)?R={(1,3),(2,3),(3,2)}?R ={(1,4),(2,4),(3,2)}

3.设R与S为X上的任两个集合，下列命题哪些为真？

a）若R,S都是自反的，则R?S也是自反的。 b）若R,S都是对称的，则R?S也是对称的。 c）若R,S都是反自反的，则R?S也是反自反的。 d）若R,S都是反对称的，则R?S也是反对称的。 e）若R,S都是传递的，则R?S也是传递的。答案：真假假假假

4.设R1是A到B，R2和R3是B到C的二元关系，则一般情况下

R1?(R2\\R3)?(R1?R2)\\(R1?R3)。但有人声称等号成立，他的证明如下：设则?b?X，使得(a,b)?R1且(b,c)?R2\\R3。于是(b,c)?R2且(a,c)?R1?(R2\\R3)，

(b,c)?R3。从而(a,c)?R1?R2且(b,c)?R1?R3，所以(a,c)?(R1?R2)\\(R1?R3)，即R1?(R2\\R3)?(R1?R2)\\(R1?R3)。同理可证相反的包含关系成立，故等式成立，这个证明错在什么地方？

解：由(a,c)?R1,(b,c)?R2且(b,c)?R3，只能得到(a,b)?R1?R2。但(a,c)?R1?R3不一定成立。

例如(a,a)?R1,(a,c)?R3时，(a,c)?(R1?R3)

故这步推理错误

5.设R，S是X上的满足R?S?S?R的对称关系，证明R?S?S?R.

证1：设(x,z)?S?R，则?y?X,使得(x,y)?S且(y,z)?R。因为R，S均对称，所以R?R?1,S?S?1 于是(y,x)?S?1?S,(z,y)?R?1?R

从而(z,x)?R?S,(x,z)?(R?S)?1?(S?R)?1?R?1?S?1?R?S 因此S?R?R?S 故S?R?R?S

证2S?R?S?1?R?1?(R?S)?1?(S?R)?1?R?1?S?1?R?S，故S?R?R?S，于是R?S?S?R

6.设R为X上的对称关系，证明：?n?N,Rn是对称关系。

证1(Rn)?1?(R?R???R)?1?R?1?R?1???R?1?R?R??R?Rn，故R对称。证2?(x,y)?Rn，则?y1,y2,?,yn?1?X，使得

(x,y1)?R,(y1,y2)?R,?,(yn?1,y)?R。因为

R对称，所以

(y,yn?1)?R,(yn?1,yn?2)?R,?,(y2,y1)?R,(y1,x?R)，因此(y,x)?Rn，故R对称。

证3用数学归纳法对n进行归纳。当n=1时，Rn=R显然是对称的。假设当n=k时，Rk对称。

当n=k+1时，Rk?1?Rk?R?R?Rk。

?(x,y)?Rk?1，则?z?X，使得(x,z)?Rk,(z,y)?R。

因为Rk，R均是对称的，所以(y,z)?R,(z,x)?Rk，于是(y,x)?R?Rk?Rk?1。因此Rk+1对称。

综上，Rn对n?N都是对称关系。

7.设R1,R2,R3,?是X上的二元关系的一个无穷序列，则当每个Ri是对称关系时，

?Ri还是对称的吗？

i?1? 33

证：则?i0的使得(x,y)?Rio。因为Ri0对称，所以有(y,x)?Rio，?(x,y)??Ri，

i?1?故(y,x)??Ri。因此?Ri还是对称的。

i?1i?1??P98习题

1.设R是X上的二元关系，试证（1）

(R?)??R?,(2)(R*)*?R*,(3)R?R*?R*?R?R?,(4)(R?)*?(R*)??R?。证：（1）因为R??(R?)?显然成立。

其次，设(a,b)?(R?)?，因为(R?)?是一切包含R?的传递关系的交，而

R??(R?)?且R?是传递的，故(a,b)?R?，即(R?)??R?。

因此(R?)??R?。

（2）因为R??(R?)?显然成立。

其次，设(a,b)?(R?)?，因为(R?)?是一切包含R?的自反传递关系的交，而R?

本身是自反的也是传递的且R??(R?)?，故(a,b)?R?，即(R?)??R?，因此

(R?)??R?。

（3）R?R??R?(R0?R?R2??)?R?R2?R3???R?

R??R?(R0?R?R2??)?R?R?R2?R3???R? （4）先证(R?)??R?

(R?)??(R?)0?(R?)??IX?R??R? 再证(R?)??R?

因为(R?)?是包含R?的一切传递关系的交，又因为R??(R?)?且R?是传递的，所以(R?)??R?。

因此(R?)??(R?)??R?。

2.设X＝（a,b,c,d,e），R＝｛（a,b），（b,c），（c,d），（d,e）｝试求R?和R?。

解：R2?{(a,c),(b,d),(c,e)}

R3?{(a,d),(b,e)}R4?{(a,e)}R5??

故R??R?R1?R2?R3?R4?R5?{(a,b),(b,c),(c,d),(d,e),(a,c),

(b,d),(c,e),(a,d),(b,e),(a,e)}

R??IX?R??{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(b,c),(c,d),(d,e),(a,c),(b,d),(c,e),(a,d),(b,e),(a,e)}3.设R,S为X上的二元关系，试证：

（1）(R?S)??R??S? （2）(R?S)??R??S?。证：（1）因为R?R?S,S?R?S 所以R??(R?S)?,S??(R?S)? 因此R??S??(R?S)? （2）因为R?R?S,S?R?S 所以R??(R?S)?,S??(R?S)?

因此R??S??(R?S)? 〔证毕〕 6.举例说明s(t(R))与t(s(R))确定不相等。

解：设N?{1,2,3,?}，在N上定义小于关系“＜”，则

s(t(?))?s(?)?“不等关系≠”。 t(s(?))?t(?)?“全关系”。

因此的确不相等。

7.是否可以定义二元关系的反自反闭包与二元关系的反对称闭包？为什么？

解：不可以。

因为二元关系的反自反闭包和反对称闭包是空集，没有多少研究价值。因此不定义二元关系的反自反闭包和反对称闭包。

8.是否存在X（X=n）上的一个二元关系R使得R,R2,?,Rn两两不相等。

解：存在。

设X?{1,2,3,?,n}，则R是X上的二元关系且R?{(1,2),(2,3),?,(n?1,n)}即可满足要求。

9.证明：若R是对称的，则R＋也是对称的。

证：

?(x,y)?R??Ri，则?m?N，使得(x,y)?Rm。因为若R是对称的，所

?i?1?以R也是对称的，因此(y,x)?R??Ri。即R?也是对称的。

mm?i?110.设R1,R2是X上的二元关系，证明：

（1）r(R1?R2)?r(R1)?r(R2) （2）S(R1?R2)?s(R1)?s(R2) （3）t(R1?R2)?t(R1)?t(R2)

证：（1）因为r(R1)和r(R2)都是A上的自反关系，所以r(R1)?r(R2)也A上的自反关系。

由R1?r(R1),R2?r(R2)，得R1?R2?r(R1)?r(R2)，所以r(R1)?r(R2)是包含

R1?R2的自反关系。由自反闭包的定义可知：r(R1?R2)?r(R1)?r(R2)

又R1?R1?R2,R2?R1?R2，故r(R1)?r(R1?R2)，r(R2)?r(R1?R2)，因此

r(R1)?r(R2)?r(R1?R2)。从而r(R1?R2)?r(R1)?r(R2) （2）同（1）的证明。

（3）因为R1?R1?R2,R2?R1?R2，故t(R1)?t(R1?R2),t(R2)?t(R1?R2)，因此t(R1)?t(R2)?t(R1?R2)。

例：设X?{a,b,c}，A上的两个关系R1?{(a,b)},R2?{(b,c)}。于是

t(R1)?{(a,b)},t(R2)?{(b,c)}，故t(R1)?t(R2)?{(a,b),(b,c)}，但 R1?R2?{(a,b),(b,c)},t(R1?R2)?{(a,b),(b,c),(a,c)}。因此t(R1?R2)?t(R1)?t(R2)。

P113习题

1.设X?{1,2,3},Y?{1,2},S?{f|f:X?Y}。?是S上的二元关系：

（2）求等价类f,g?S,f?g?Im(f)?Im(g)。证明（1）?是S上的等价关系，的集合。

证：（1）等价关系显然。

（2）f:X?Y，共有8个，如图4所示。

123f112123f2112112123f323f42

123f521123f621123f721123f821图4

?f?S，[f]R?{g|Im(f)?Im(g)}，故

[f1]R?{f1}，[f2]R?{f2,f3,f4,f5,f6,f7}，[f3]R?{f3}。故等价类集合为{[f1]R,[f2]R,[f3]R}。

22.?P113?（1）等价关系显然。

(2)如图4所示。

?f?S，[f]R?{g|f(1)?f(2)?f(3)?g(1)?g(2)?g(3)}。故

[f1]R?{f1}?{g|g(1)?g(2)?g(3)?3},[f2]R?{f2,f3,f5}?{g|g(1)?g(2)?g(3)?4},[f4]R?{f4,f6,f7}?{g|g(1)?g(2)?g(3)?5},[f8]R?{f8}?{g|g(1)?g(2)?g(3)?6}.33. ?P113?（1）?是等价关系显然。

（2）?f?S，[f]R?{g|{f?1(y)|y?Y}?{g?1(y)|y?Y}}。

[f1]R?{f1,f8}?{{1,2,3},?}[f2]R?{f2,f7}?{{1,2},{3}}[f3]R?{f3,f6}?{{1,3},{2}}[f4]R?{f4,f5}?{{1},{2,3}}故等价类集合为{[f1]R,[f2]R,[f3]R,[f4]R}。

?124.由置换????36354856127?8上的一个关系?,,8}?确定了X?{1,27?4?:i,j?X,i?当且仅当ji与j在?的循环分解式中的同一循环置换中，证明：?是X上的等价关系，求X/?。

证；???135??26??48??7?

?i?X，i与i必在?的循环分解式中的同一个循环置换中，即i?i，则?是自反的。

?i,j?X，若i?j，即i与j在?的循环分解式中和同一个循环置换中，则

j与i也在?的循环分解式中的同一个循环置换中，故j?i。因而?是对称性的。

?i,j,k?X，若i?j,j?k，则i与j在?的循环分解式中的同一个循环置换

中，j与k在?的循环分解式的同一个循环置换中，因而i与k也在?的循环分解式中的同一个循环置换中，即i?k。因而?是传递性的。

所以?是X上的等价关系。

5.给出X＝{1,2,3,4}上两个等价关系R与S，使得R?S不是等价关系。

解：如R?{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)}

S?{(1,1),(2,2),(3,3),(4,4),(2,3),(3,2)}

R?S?{(1,1),(2,2),(3,3),(4,4),(2,3),(3,2),(1,2),(1,3),(2,1)}因为(1,3)?R?S，但(1,3)?R?S，所以R?S不对称.. 因此R?S不是等价关系。 13.设X是一个集合，X?n，试求：

（1）X上自反二元关系的个数；（2）X上反自反二元关系的个数；（3）X上对称二元关系的个数；（4）X上自反或对称关系的个数；解：（1）X上自反二元关系的个数为2n

2?n

（2）X上反自反二元关系的个数为2（3）X上对称二元关系的个数为2n2?n

n2?n2

?n（4）X上自反或对称关系的个数为2n2?2n2?n2?2n2?n2

P125习题

1.设[a,b]是一个有限区间。令S是区间[a,b]上的有限划分的集合，[a,b]的一个划分?是形如a?x1?x2???xn?b,n?N的点的集合。在S上定义二元关系R如下：

??1,?2?S,?1R?2??2的每个分点也是?1的分点。

证明：R是S上的偏序关系（注意，这里的划分与等价关系中的划分不同）。

证：???S,?的每个分点也是?的分点，故?R?，因此R是自反的；

??1,?2?S，若?1R?2且?2R?1，则?2的每个分点也是?1的分点且?1的每个分点也是?2的分点，故?1??2。因此R是反对称的；

??1,?2,?3?S，若?1R?2且?2R?3，则?2的每个分点是?1的分点，而且?3的每个分点也是?2的分点，因此?3的每个分点也是?1的分点，故?1R?3。因此R是传递的。

综上可知：R是S上的偏序关系。

2.设(S,?1),(T,?2)是偏序集。在S?T上定义二元关系T,?3如下：

?(s,t),(s?,t?)?S?T，(s,t)?3(s?,t?)?(s?1s?,t?2t?)。证明：（1）?3是S?T上的偏序关系；

（2）若(s,t)?3(s?,t?)?s?1s?或t?2t?，则?3是S?T上的偏序关系吗？证：1.(1)?(s,t)?S?T，则s?S,t?T。由于(S,?1),(T,?2)是偏序集，故有

s?1s,t?2t?(s,t)?3(s,t)。

从而?3是自反的；

(2)?(s1,t1),(s2,t2)?S?T，若(s1,t1)?3(s2,t2)且(s2,t2)?3(s1,t1)，则

(s1?1s2且s2?1s1)且(t1?2t2且t2?2t1)。

由(S,?1),(T,?2)是偏序集可知，s1?s2且t1?t2，故(s1,t1)?(s2,t2)。因此“?3”是对称的。

(3)?(s1,t1),(s2,t2),(s3,t3)?S?T，若(s1,t1)?3(s2,t2)且(s2,t2)?3(s1,t1)，有由(S,?1),(T,?2)是偏序集可知：?1与?2是传(s1?1s2,s2?1s3)且(t1?2t2,t2?2t3)。

递的，所以s1?1s3且t1?2t3。故(s1,t1)?3(s3,t3)，因此?3是传递的。

综上可知：?3是S?T上的一个偏序关系。

2.此题若改为：(s,t)?3(s?,t?)?s?1t或s??2t?，则?3不是偏序关系。因为?3不满足反对称性。

例如：(I,?3)，则(1,2)?3(2,1)且(2,1)?3(1,2)，但(1,2)?(2,1)。故?3不满足反对称性，因此?3不是S?T偏序关系。

3.存在一个偏序关系?，使得(X,?)中有唯一的极大元素，但没有最大元素？若有请给出一个具体例子；若没有，请证明之。

解：存在。

设X?{i,1,2,3,?}，其中i??1。在X上定义的小于或等于关系“?”，则

(X,?)就是一个没有最大元素，但却有唯一极大元i的偏序集。

5.令S＝｛1，2，…，12｝，画出偏序集（S,|）的Hass图，其中“|”是整除关系，它有几个极大（小）元素？列出这些极大（小）元素

极大元素有6个，分别是7，8，9，10，11，12 极小元素有1个是1

6.设R是X的自反且传递的二元关系，则

（1）给出R的一个实例；

（2）在X上定义二元关系~是：x~y?xRy,yRx。

证明：~是X上的等价关系。

（3）在商集X~上定义二元关系?是：[a]?[b]?aRb。

证明：?是X~上的偏序关系。证：（1）(I,?)即可

（2）自反、对称显然。下面看传递性

因为若x~y且y~z?xRy,yRx且yRz,zRy；由R是传递的，有xRz，zRx。由题意有x~z，故~是传递的。

因此~是X上的等价关系。

（3）?[a]?X所以?是自反的；

?[a],[b]?X~~，因为R是X上的自反关系，故aRa。而aRa?a[]?a[]，

，若[a]?[b],[b]?[a]?aRb,bRa，则a与b在一个等类中，故

[a]?[b]，因此?是反对称的；

?[a],[b],[c]?X~]?[b],[]b[]?c?aRbbR,c，若[a，则由R的传递性有aRc，

即[a]?[c]。因此?是传递的。

综上可知：?是X~上的偏序关系。

7.设R是X上的偏序关系，证明：

R是X上的全序关系?X?X?R?R?1。

证：由于R是X上的全序关系，故(x,y)?R或(y,x)?R?1??(x,y)?X?X，必有一个成立。所以(x,y)?R?R?1，即X?X?R?R?1；

反之，因为R是X上的关系，故R?X?X，R?1?X?X，所以

R?R?1?X?X。

因此X?X?R?R?1。

? ?(x,y)?X?X?R?R?1，有(x,y)?R或(x,y)?R?1，即xRy与yRx必有一个成立，故R是X上的全序关系。

第四章无穷集合及其基数

P136习题 1.设A为由序列

a1,a2,?,an,?

的所有项组成的集合，则是否市可数的？为什么？

解：因为序列是可以重复的，故

若A是由有限个数组成的集合，则A是有限的集合；若A是由无限个数组成的集合，则A是可数的。故本题A是至多可数的。

2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。

证：在每个开区间中取一个有理数，则这些有理数构成的集合是整个有理数集合Q的子集，因此是至多可数的。

3.证明：单调函数的不连续点的集合至多可数。

证：设A是所有不连续点的集合，f是一个单调函数，则?x0?A,x0对应着一个区间(f(x0?0),f(x?0))，于是由上题便得到证明。 4.任一可数集A的所有有限子集构成的集族是可数集合。

证：设A?{a1,a2,?,an,?},B?{ai1,ai2,?,aik},则B?A且B?k??。令??{BB?A,B??}，

设?:A?{0,1}，则?是Ａ的子集的特征函数。

?B??,?(B)?｛0，1的有穷序列｝，即?ai?A，

若ai?B，则对应1；若ai?B则对应0。于是

?B??,?(B)就对应着一个由0，1组成的有限序列0，1，1，0，?，0，1。

此序列对应着一个二进制小数，而此小数是有理数。于是，可数集A的所有有限子集?对应着有理数的一个子集。

又?B1,B2??,B1?B2,B1,B2对应的小数也不同，故?是单射。而可数集Ａ的

所有有限子集?是无穷的，故?是可数的。 5．判断下列命题之真伪：

(1)若f:X?Y且f是满射，则只要X是可数的，那么Y是至多可数的； (2)若f:X?Y且f是单射，那么只要Y是可数的，则X也是可数的； (3)可数集在任一映射下的像也是可数的；答案：对，错，错。

7．设Ａ是有限集，Ｂ是可数集，证明：BA?{f|f:A?B}是可数的。

证：令A?{1,2,?,n},B?{b1,b2,?,bn,?}，Ｂ可数。设f:A?B,?i?A,f(i)?B。

（BA中的每个f实际上就是Ｂ的一个有限子集，可数集的有限子集是可数的。于是由４题即可证明）

（f(k1),f(k2),?,f(kn))?B?B???B?Bn。用数学归纳法可以证明BA是可数的，但Bn?BA。

8. 设?为一个有限字母表，?上所有字（包括空字）之集记为??。证明??是可数集

证１：设有限字母?上所有字（包括空字?）所形成的集??，则??是可数的。

Ａ1＝{长度为1的字符串} Ａ2＝{长度为2的字符串}

? ?

Ａn＝{长度为n的字符串}

? ?

因为Ａi 中每个长度都是有限的，而?＝?Ai，故??是至多可数的。又????i?1显然是无穷的，故??是可数的。

证2：不妨假设??{a,b,c}（令?＝{0,1}也是可以），则可按字典序排序为：

由于?*的全部元素可以排成无重?,a,b,c,aa,ab,ac,ba,bb,bc,?,aaa,aab,?。复项的无穷序列，故?*是可数的。

P142习题

2.找一个初等可数f(x)，使得它是(0,1)到实数R的一一对应。

?解：Ctgx,或tgx，或tg(x?)

23.试给出一个具体的函数，使得它是从(0,1)到[0,1]的一一对应。

111证：(0,1)中包含一个可数子集A?{,2,3,?}可数。

222111A1?A?{0,1}?{0,1,,2,3,?}——可数的，故A?A1。

222令?:(0,1)?[0,1],?x?(0,1)

当x?A?x?01?当x?2???(x)??11

当x??4??1当x?1,i?3??2i?22i?(x)即为所求。

4.证明：若A可数，则2A不可数。（用对角线方法）。

证：A可数，则令A?{1,2,3,?}。

假设2A可数，则A的子集（即2A的元素）是可数的，故2A中元素可排成一个无重复项的无穷序列：

A1,A2,?,An?

而2A~Ch(A)?{ff:A?{0,1}}，于是特征函Ch(A)可数，即Ch(A)可写成下列无穷序列形式：

f1,f2,?,fn?

f1:a11a12a13?f2:a21a22a23?f3:a31a32a33?　?　　　?　　　?fn:an1an2an3??　　　?　　　??造一个特征函数?。令??{bi}1

其中aij?0或1,j?1,2,3,?。

?1 若a11?0b1??；0 若a?1?11?1 若a22?0b2??；?0 若a22?1 ? ?1 若ann?0bn???0 若ann?1 ? 则??f1,f2,f3,?,fn,?,但?确实是A到{0,1}的一个映射，即?是A的子集的特征函数，矛盾。故2A不可数。

5．令N?{1,2,3,?}，S?{ff:N?{0,1}},利用康托对角线法证明S是不可数集。

证:假设从N到{0, 1}的所有映射之集可数，则可排成无重复项的无穷序列

f1,f2,f3,?。每个函数fi确定了一个0,1序列ai1,ai2,ai3,?。构造序列若aii?0；否则bi?0。该序列对应的函数f(i)?bi，i?N， b1,b2,b3,?,bi?1，

不为f1,f2,?任一个，矛盾。

Word文档下载：哈工大《离散数学》教科书习题答案.doc

搜索更多:哈工大《离散数学》教科书习题答案