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

教材习题解答

第一章 集合及其运算

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?

1

解: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)))

2

?(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)。

3

?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??。

4

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

5

(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

(c) x?A或x?B; (d) (x?A且x?B)或(x?A且x?B) 16.设A,B,C为三个集合,下列集合表达式哪一个等于A\\(B?C)?

(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习题

C

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

7

(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,则

C

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)

8

当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??

11

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,因此

12

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

13

(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。

14

证:?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表示;

16

于是,由题意: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与所有的姑娘都跳过舞,矛盾。

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

17

第二章 映 射

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。

18

反证法:假设题中结论不成立,则??,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整除。

证:考察下式:

19

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必是一

20

?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)

21

反之,设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。以下四个小题中,每个小题均有四个命题,这四个

22

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

(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]

23

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,矛盾。

24

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

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矛盾。

25

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)。

26

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奇偶性相同。

27

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种选择

28

因此共有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),因而逆运算的个数很多,因此得到其中的一种就较困难,故逆运算较难算。

29

第三章 关 系

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,

30

即(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是自反的。他的推论错在什么地方?这个结论是否对呢?

31

解:若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)

32

故这步推理错误

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?。

34

解: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两两不相等。

35

解:存在。

设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)。

36

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)?是等价关系显然。

37

(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

38

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),则

39

(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,?)即可

40

(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上的全序关系。

41

第四章 无穷集合及其基数

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},则?是A的子集的特征函数。

?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对应的小数也不同,故?是单射。而可数集A的

42

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

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

7.设A是有限集,B是可数集,证明:BA?{f|f:A?B}是可数的。

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

(BA中的每个f实际上就是B的一个有限子集,可数集的有限子集是可数的。于是由4题即可证明)

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

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

证1:设有限字母?上所有字(包括空字?)所形成的集??,则??是可数的。

A1={长度为1的字符串} A2={长度为2的字符串}

? ?

An={长度为n的字符串}

? ?

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

证2:不妨假设??{a,b,c}(令?={0,1}也是可以),则可按字典序排序为:

43

由于?*的全部元素可以排成无重?,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?

44

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,?任一个,矛盾。

45

联系客服:779662525#qq.com(#替换为@)