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

1、精品文档教材习题解答第一章 集合及其运算p8习题3. 写出方程 x 2 +2 x +1 =0 的根所构成的集合。解： x2+2 x +1 =0 的根为 x =-1，故所求集合为 -14. 下列命题中哪些是真的，哪些为假a)对每个集 a， f a ；b)对每个集 a， f a ；c)对每个集 a， a a；d)对每个集 a， a a ；e)对每个集 a， a a ；f)对每个集 a， a a；g)对每个集 a， a 2 a ；h)对每个集 a， a 2 a ；i)对每个集 a， a 2a；j)对每个集 a， a2a；k)对每个集 a， f2a；l)对每个集 a， f 2a；m)对每个集 a， a

2、 = a；n) f=f；o) f中没有任何元素；p)若 a b ，则 2a 2bq)对任何集 a， a =x | x a；r)对任何集 a， x | x a = y | y a；s)对任何集 a，y a y x | x a；t)对任何集 a，x | x a a | a a； 答案 ：假真真假真假真假真假真真假假假真真真真真5. 设有 n 个集合 a , a , l , a 且 a a l a a ，试证：1 2 n 1 2 n 1a =a =l =a1 2 n证明 ：由 a a a l a a ，可得 a a 且 a a ，故 a =a 。 1 2 4 n 1 1 2 2 1 1 2同理可得：

3、 a =a =a =l =a1 3 4 n因此 a =a =a =l =a1 2 3 n6. 设 s =f,f ，试求 2 s ？.s精品文档解： 2s=f,f,f,f,f7. 设 s 恰有 n 个元素，证明 2s有 2n个元素。证明 ：（1）当 n0 时， s =f,2s=f, 2s=1 =20，命题成立。（2）假设当 n =k (k 0, k n ) 时命题成立，即 2s=2k（ s =k 时）。那么对于 s （ s =k +1），2 s1中的元素可分为两类，一类为不包含 s 中某一元素 x 的 1 1 1集合，另一类为包含 x 的集合。显然，这两类元素个数均为 2k。因而 21=2k +

4、1，亦即命题在 n =k +1 时也成立。由（1）、（2），可证得命题在 n n 时均成立。p16习题1. 设 a、b 是集合，证明:( a b ) u b =( a u b ) b b =f证： 当 b =f时，显然 ( a b ) u b =( a u b ) b ，得证。 假设 b f，则必存在 x b ，使得 x ( a b ) u b 但 x ( a u b ) b ，故 ( a b ) u b ( a u b ) b 与题设矛盾。所以假设不成立，故 b =f。2. 设 a、b 是集合，试证 a =f 证： 显然。 b =adb 反证法：假设 a f，则 $x a ，若 x b ，则

5、 x 左，但 x 右，矛盾。0 0 0 0若 x b ，则 x 左，但 x 右，矛盾。故假设不成立，即 a =f。0 0 03. 设 a，b，c 是集合，证明：( adb) dc =ad(bdc )证： ( adb ) dc =( a b ) u ( b a)dc =( a i b c ) u ( b i ac )dc=( a i b c ) u ( b i ac ) c u (c ( a i b c ) u ( b i ac )=( a i bc i c c ) u ( b i ac i c c ) u (c i ( ac i b ) i ( b ci a)=( a i bci cc) u

6、( b i aci cc) u (c i ( aci bc) i ( a i b ).精品文档=( a i bci cc) u ( aci bi cc) u ( aci bci c ) u ( a i b i c )由 上 式 可 以 看 出 此 展 开 式 与 a 、 b 、 c 的 运 算 顺 序 无 关 ， 因 此 ， ( adb) dc =ad(bdc )4. 设 a，b，c 为集合，证明 a ( b uc ) =( a b ) c证：因为 a ( b uc ) =a i ( b uc )c=a i bci cc= ( a i bc) c = ( a b ) c 。5. 设 a，b，c

7、 为集合，证明：( a u b ) c =( a c ) u ( b c )证： ( a u b ) c =( a u b ) i cc=( a i cc) u ( b i c c ) ( a c ) u ( b c ) 。6. 设 a，b，c 为集合，证明：( a i b ) c =( a c ) i ( b c )证明： ( a i b ) c =( a i b ) i c c =a i b i c c = ( a i c c ) i ( b i c c )= ( a c ) i ( b c )7. 设 a，b，c 都是集合，若 a u b =a uc 且 a i b =b i c ，试证

8、 b=c。证：证 1： x b ，则若 x a ，则 x ( a i b ) 。由于 a i b =a i c ，故 x ( a i c ) ，即 x c ；若 x a ，则 x ( a u b ) ，由于 a u b =a uc ，故 x a uc 。又 x a ， 只能有 x c 。因此， x b ，总有 x c ，故 b c 。同理可证， c b 。因此 b =c 。证 2： b =b i ( a u b ) =b i ( a uc ) =( b i a) u ( b i c )=(c i a) u ( b i c ) =c i ( a u b ) =c i ( a uc ) =c8.

9、设 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 ) ，有 x ( a b ) ，x (c b ) 。因此 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

10、 b ) =( a i bc) i (c i bc)c=( ai bc) i (ccu b )=( ai bc) i cc=( a b ) c9. 设 x y z ，证明 z (y x ) =x u ( z y )证：证 1：x z (y x ) =z i(y i xc)c=z i(ycu x ) ，有 x z 且 x y或 x x 。则若 x z 且 x y ，则 x z y ，于是 x x u ( z y ) 。若 x z 且 x x ，则 x x u ( z y ) ，从而z (y x ) x u ( z y ) 。反之， x x u ( z y ) ，则 x x 或 x z y 。若

11、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 u ( z y ) z (y x ) 。由集合相等的定义， z (y x ) =x u ( z y ) 。证 2： z (y x ) =z i (y i x c ) =z i (y c u x ) =( z i y c ) u ( z i x ) ，因为 x z ，所以 z (y x ) =( z i y 10.下列命题是否成立？c) u x =x u ( z y ) 。(1) ( a b )

12、uc =a ( b c ) ；(2) a u ( b c ) =( a u b ) c ；(3) a ( b uc ) =( a u b ) b 。解：（1），（2），（3）都不成立。反例如下：（1） a =f,c =1, b 任意，则 ( a b ) uc =c =1; a ( b c ) =f（2） a =1, b =f,c =1 ，则 a u ( b c ) =1;( a u b ) c =f。.精品文档（3） a =f, b =1, c =1,2 ，则 a ( b uc ) =f;( a uc ) b =2。11下列命题哪个为真？a) 对任何集合 a,b,c，若 a i b =b i

13、c ，则 a=c。b) 设 a,b,c 为任何集合，若 a u b =a uc ，则 b=c。c) 对任何集合 a,b， 2d) 对任何集合 a,b， 2aubai b=2=2aau 2i 2bb。e)对任何集合 a,b， 2a b=2a 2b。f)对任何集合 a,b， 2 adb =2 a d2b 。答案 ：d 是真命题。12设 r,s,t 是任何三个集合，试证：（1） s dt =( s ut ) d(s i t ) ；（2） rd(s i t ) ( rds) i ( rdt ) ；（3） ( rds) i ( r dt ) r d(s ut ) ( rds) u ( rdt ) ；（4

14、） r u ( s dt ) ( r u s ) d(r ut )证：（1） x s dt =( s t ) u(t s ) ，则若 x s ，则 x t 。因而 x ( s ut ) 且 x ( s i t ) ，故 x ( s ut ) d(s i t ) ； 若 x s ，则 x t ，同理可得 x ( s ut ) d(s i t ) 。故s dt ( s ut ) d(s i t ) 。反之，因为 ( s i t ) ( s ut ) ，故( s ut ) d(s i t ) ( s ut ) ( s i t ) u(s it ) (t us ) =f 。x ( s ut ) d(s

15、 i t ) =( s ut ) ( s i t ) ，有 x ( s ut ), x ( s i t ) 。 若 x s ，则 x t ，故 x s dt ；若 x s ，则 x t ，故 x s dt 。因此( s ut ) d(s i t ) s dt 。所以s dt ( s ut ) d(s i t ) 。.精品文档（2）证： x ( r ds) i ( r dt ) ，有 x ( r ds) 且 x ( rdt ) 。则若 x r ，则 x s 且 x t ，故 x ( s i t ) ， x rd(s i t ) 。若 x r ，则 x s 且 x t 。故 x ( s i t )

16、 ，因此 x r d(s i t ) 。于是( rds) i ( r dt ) rd(s i t ) 。（3）证： x ( rds) i ( rdt ) ，有 x ( rds) 且 x ( r dt ) 。则若 x r ，则 x s , x t ，故 x ( s ut ) ，因此 x r d(s ut ) ；若 x r ，则 x s , x t ，故 x ( s ut ) ， x rd(s ut ) 。于是( rds) i ( r dt ) r d(s ut )反之， x r d(s ut ) ，则若 x r ，则 x ( s ut ) ，故 x s , x t ，因而 x ( r ds),

17、x ( rdt ) 。即 x ( r ds) u ( r dt ) ；若 x r ，则 x ( s ut ) ，故 x s 或 x t 。因此 x ( rds) 或 x ( r dt ) ， 从而 x ( r ds) u ( r dt ) 。综上可得： r d(s ut ) ( r ds) u ( r dt ) 。于是( rds) i ( r dt ) r d(s ut ) ( rds) u ( rdt )证： x ( r u s ) d(r ut ) ，则若 x ( r u s ) ，则 x ( r ut ) ，因而 x r, x t , x s 。故 x s dt ，于是 x r u (

18、s dt ) ；若 x ( r u s ) ，则 y ( r ut ) ，与上同理可得 x r u ( s dt ) 。综上可得： r u ( s dt ) ( r u s ) d(r ut ) 。14设 a 为任一集， b x xi为任一集族（ i f），证明：a u ( i b ) =i ( a u b )x xxixi.精品文档证： x a u (i b ) ，则xxi若 x a ，则 x a u b (xxi ) ，因而 x i ( a u b ) ；x是xi若 x a ，则 xi, x b ，因而 xi, x a u b ，故 x i ( a u b ) 。于x x xxia u (

19、i b ) i ( a u b ) 。x xxi xi反之，设 x i ( a u b ) ，则 xi, x a u b 。x xxi若 x a ，显然 x a u (i b ) ；xxi若 x a ，则 xi, x b ，因而 x i b ，即 x a u (i b ) 。所以，x x xixi( a u b ) a u (i b ) 。x xxixi综上可得， a u (i b ) i ( a u b ) 。x xxixixi15填空：设 a,b 是两个集合。(a) x a u b _；(b) x a i b _；(c) x a b _；(d) x adb _；解： (a) x a 且 x

20、 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 i c ) ？ （a） ( a b) i ( a c ) ；（b） ( a i b ) ( a i c )（c） ( a b) u ( a c ) ；（d） ( a u b ) ( a uc )（e） ( a u b ) i ( a uc )答案：c。( a b) u ( a c ) =( a i bc) u ( a i cc) =a i ( bcucc)=a i ( b i c ) p 习题20

21、c=a ( b i c )1设 a,b,c 为集合，并且 a u b =a uc ，则下列断言哪个成立？.n -1nu精品文档(1) b =c ；(2) a i b =a i c ；(3) a i bc=a i cc；(4) aci b =aci c 。答案：d。在 aci b =aci c 两边同时并上 a 即得 a u b =a uc 。2设 a,b,c 为任意集合，化简( a i b i c ) u ( ac i b i c ) u ( a i b c i c ) u ( a i b i c c ) u( ac i b c i c ) u ( a i b c i c c ) u ( ac

22、 i b i c c)证：证 1：原式 ( b i c ) u ( a i bc) u ( b i cc) u ( aci bci c )=b u ( a i bc) u ( aci bci c ) =( a u b ) u ( aci bci c )=( a u b) u ( a u b )ci c ) =a u b uc证 2：令原式t，全集为 s，则s =t u ( aci bci cc) 且 t i ( aci bci cc) =f，故 t =( ac i b c i c c ) c =a u b uc 。3证明：（1） adb =( a u b ) i ( acu bc) ；（2）

23、( adb )c=( a i b ) u ( aci bc) ；（3） ( adb)c=( acu b ) i ( a u bc)证：（1） ( a u b ) i ( ac u b c ) =( a u b ) i ac ) u ( a u b ) i b c ) =( b i ac ) u ( a i b c ) =( a b ) u ( b a) =( adb)（2）证： ( adb)c=( a u b ) i ( acubc)c根据（1）=( a u b )cu ( acubc)c=( aci bc) u ( a i b )（3）证： ( ac u b ) i ( a u b c )

24、= ( ac u b ) i a) u ( ac u b ) i b c )=( a i b ) u ( aci bc) =( adb)c根据（2）4设 m , m , l 和 n , n ,l 是集合 s 的子集的两个序列，对 i j, i, j =1,2, l ，有1 2 1 2n i n =f。令 q =m , q =m i ( u m ) c , n =2,3, l 。试证：i j 1 1 n n kk =1n dq ( n dm ) 。n n i ii =1证： x n dq =( n q ) u (q n )n n n n n n.n nn -1 n -1nnn -1nn精品文档当

25、 n1 时， x n dq =n dm u ( n dm ) ，故 n dq u ( n dm )1 1 1 1 i i n n i ii =1 i =1当 n2 时，设 x n dq =( n q ) u (q n ) 有 x ( n q ) 或 x (q n ) 。n n n n n n n n n n则1. 若 x ( n q ) ，则 x n 但 x q =m i (u m ) c , 即x m 或x u m ，n n n n n k n ki =1 i =1因此有 x m 或x m (i n -1) 。于是n i（1）若 x n 且 x m ，有 x n m n dm u ( n d

26、m ) ；n n n n n n i ii =1（2）若 x n 且 x m (i n -1) ，由 n i n =f(i j ) ，有 x n (i n -1) 且n i i j ix m ，于是 x m n m dn i i i i iui =1( n dm ) 。 i i2. 若 x q n ，则 x q =m i (u m )n n n n ki =1x m n m dn u ( n dm ) 。n n n n i ii =1综上可得： n dq u ( n dm )n n i ii =1c，即 x m 但 x n 。于是 n n5设 x 是一个非空集合， a x , an n +1

27、a , n =1,2,3, l 试证： n ，有 na =u ( a i a cn m m +1 m =n) u i a 。mm =n证明 ：由于 am +1 a ，故 a i a c m m m +1=a am m +1。因为 m n ，故 a a ，显m n然有 u ( a i a cm m +1m =n) u i a a 。m nm =n对于 x a ，假设存在 p( p n ) ，使得 x a ，必可找到其中最小的值 p ， n p 0使得 x a a p0p +10，故 x um =n( a i a c m m +1) u i a ；mm =n. i精品文档假如不存在 p，则 x i

28、 a ，故 x mm =num =n( a i a c m m +1) u i a 。mm =n综上可得： a num =n( a i a c m m +1) u i a 。mm =n所以 a u ( a i a cn m m +1 m =n) u i a 。mm =n6设 v 是任一集合，证明：s , t ,w 2v 有 s t w 当且仅且 s dt s dw 且 s w 。证： 因为 s t w ，故 s dt =t s w s s dw 。 先证 s t 。设 x s ，则若 x t ，则 x s t s dt s dw =w s ，故 x w 且 x s ，矛盾。 所以 x t ，即

29、 s t 。其次 ，证明 t w 。设 x t ，则有两种情况：若 x s 。则 x t s s dt s dw =w s ，故 x w 。若 x s 。由 s w ，知 x w 。总之， x t ，有 x w ，故 t w 。7设 a , a ,l 为一集序列，记 a 为这样的元素的全体形成的集合： x a 当且仅1 2当在序列 a , a ,l 中有无穷多项 a 含有 x 。集合 a 称为集序列 a , a ,l 的上极限， 1 2 n 1 2记为 lim a ，即 lim a =a 。又记 a 为这样的元素全体形成的集合；序列 a , a ,l n n 1 2n n 中 只 有 有 限

30、项 不 含 有 这 样 的 元 素 。 称 a 为 序 列 a , a ,l 的 下 极 限 ， 并 记1 2lim a =a 。证明；nn （1） lim a =u i a ；（2） lim a =i u a 。n k n kn n =1k =n n n =1k =n证： （1） x lim a ，在序列 a , a ,l 中只有有限项不含 x，在不含 x 的n 1 2n 项中必可找到下标最大的一项 a.p -1（若各项均含 x，则令 p0），有 x a ，kk =p ik =p u k =n u k =n n n 精品文档故 x u i a ，即kn =1k =nlim a u i a 。

31、n kn n =1k =n反之， x u i a ，必 $p 使得 x a ，即 k p 时， x a 。而集合k k kn =1k =na , a , l , a 1 2 p -1中即使都不含有 x，但也仅有有限项不含 x，故 x lim a 。因此nn u i a lim a 。k nn =1k =n n 综上可得： lim a u i a 。n kn n =1k =n（2） x lim a ，因为 a , a ,l 中有无穷多项含有 x，故 $n ，当 n n 时，n 1 2n x a ，因此 x a ，从而 x i u a ，即n k kn =1k =nlim a i u an kn

32、n =1k =n反之， x i u a ，则 n 1, x a ，即 a , a ,l 中有无穷多项多含 x，k k 1 2n =1k =n所以 x lim a ，即nn u i a lim ak nn =1k =n n综上可得： lim a =u i a 。n kn n =1k =n8证明： lim a lim an nn 证： x lim a ，由 lim a 定义可知：序列 a , a ,l 中只有有限项不含 x，故n n 1 2n n 必可找到不含 x 的下标最大的一项 a ，可见此时 a , ap p +1 p +2含 x，故 x lim a 。因此nn lim a lim a 。n

33、 nn ,l 均含 x，即有无限项.习题p251设 a =a, b, c, b =e, f , g , h, c = x, y, z 。求 a b , b a, a c , a 解：2精品文档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 )

34、,( h, b ),( h, c ) a c =(a, x),( a, y ),( a, z ),( b, x ),( b, y),( b, z),( c, x ),( c, y ),( c, z )a2b =( 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,

35、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 为集合，试证：abba

36、 的充要条件是下列三个条件至少一个成立：（1） a =f；（2） b =f；（3） a =b 。证： 若（1）成立， a b =f=ba 。若（2）成立，同上。若（3）成立，ab=bb=ba。 假设必要性不成立，即 a f,b f,a b 。故不妨设 $x 使得 x a, x b 。 设 y b ，则 ( x, y ) a b ,( x, y ) b a ，矛盾。于是，假设不成立。因而必要性成立。必要性也可以如下证明：1. 若 a b =b a =f，则 a =f或b =f。1. 若 a b =b a f， 则 x a, y b ， 有 ( x, y ) a b =b a 。 于 是 x b

37、, y a ，因此 a b 且 b a ，故 a=b。3设 a,b,c,d 为任四个集合，证明：( a i b ) (c i d ) =( a c ) i ( b d )证： ( x, y ) ( a i b ) (c i d ) ，有 x a i b, y c i d ，即x a, x b, y c , y d 。所以 ( x, y ) a c ,( x, y) b d ，因此.精品文档( x, y ) ( a c ) i ( b d ) ，从而( a i b ) (c i d ) ( a c ) i ( b d ) 。反之， ( x, y ) ( a c ) i ( b d ) ，有 x

38、a, x b , y c , y d 。即( x, y ) ( a i b ) (c i d ) ，从而( a c ) i ( b d ) ( a i b ) (c i d ) 。因此， ( a i b ) (c i d ) ( a c ) i ( b d ) 。4设 e , e , e , e 为任意集合，试证：1 2 3 4( e e ) ( e e ) =( e e ) e ) u ( e ( e e )1 2 3 4 1 3 2 1 2 4证： ( x, y ) ( e e ) ( e e ) ，有 x e , y e 且 x e 或 y e 。则1 2 3 4 1 2 3 4若 x

39、e ，则 x e e ) ，故 ( x , y) ( e e ) e ) ，即3 1 3 1 3 2( x, y ) ( e e ) e ) u ( e ( e e ) 。1 3 2 1 2 4若 y e ，同理可证 ( x, y ) ( e e ) e ) u ( e ( e e ) 。从而4 1 3 2 1 2 4( e e ) ( e e ) ( e e ) e ) u ( e ( e e ) 。1 2 3 4 1 3 2 1 2 4反 之 ， ( x, y ) ( e e ) e ) u ( e ( e e ) ， 则 ( x , y ) ( e e ) e ) 或1 3 2 1 2

40、4 1 3 2( x, y ) e ( e e ) ，即 x e ， y e 但 x e 或 x e ， y e 但 y e 。从而1 2 4 1 2 3 1 2 4有 ( x , y ) e e ，但 ( x, y ) e e ，即 ( x, y ) ( e e ) ( e e ) ，从而 1 2 3 4 1 2 3 4( e e ) e ) u ( e ( e e ) ( e e ) ( e e ) 。1 3 2 1 2 4 1 2 3 4综上可得： ( e e ) ( e e ) ( e e ) e ) u ( e ( e e ) 。1 2 3 4 1 3 2 1 2 45设 a x ,

41、 b y ，试证： ( a b ) c =( ac b ) u ( a b c ) u ( ac b c )证： ( x, y ) ( a b ) c ，则 ( x , y ) ( a b ) ，故 x a 或 y b 。于是1. 若 x a ，则 x ac 。因此(1)若 y b ，则 ( x , y ) acb ( acb ) u ( a bc) u ( acbc) 。.精品文档(2) 若 y b ，则 y bc，即 ( x , y ) acbc ( acb ) u ( a bc) u ( acbc) 。2.若 x a ，则必有 y b ，故 ( x , y ) a bc ( acb )

42、u ( a bc) u ( acbc) 。综上可得： ( a b ) c ( ac b ) u ( a b c ) u ( ac b c ) 。反之， ( x , y) ( acb ) u ( a bc) u ( acbc) ，则( x, y ) acb 或 ( x, y) a bc或 ( x , y ) acbc，于是，(1)若 ( x, y ) ac b ，则 x a 且 x b ，即 ( x, y ) a b ，于是 ( x , y ) ( a b ) c 。(2)若 ( x, y ) a b c ，则 x a 且 x b ，即 ( x, y ) a b ，于是 ( x , y ) (

43、a b )c。(3)若 ( x , y ) acbc，则 x a 且 x b ，即 ( x, y) a b ，于是 ( x , y ) ( a b )c。综上可得： ( ac b ) u ( a b c ) u ( ac b c ) ( a b ) c 。于是 ( a b ) c =( ac b ) u ( a b c ) u ( ac b c ) 。7设 a, b , c 是三个任意集合，证明：a ( b dc ) =( a b ) d( a c )证： a ( b dc ) =a ( b c ) u (c b ) =a ( b c ) u a (c b )=( a b ) ( a c ) u ( a c ) ( a b ) =( a b )d( a c )8设 a,b 为集合，下列命题哪些为真？（1） ( x, y ) a b x a 且 y b（2） ( x, y ) a b x a 或