离散数学最全课后答案(屈婉玲版)

离散数学习题解

(1) G上的二元运算为矩阵乘法,给出G的运算表 (2) 试找出G的所有子群

(3) 证明G的所有子群都是正规子群.

46

将G中矩阵依次记为A,B,?B,?A.

? A

(1)运算表为B A A B B ?B??A B ?B??A A ??A ?B ??A ?B

A B

B A

?B?B ??A ??A

(2)子群: {A}, {A,?A}, {A, ?B}, {A,B},G (3)G是Abel群, 所有的子群都是正规的.

11.27. 11.28. 11.29.

略 略

令G={?,+}是整数加群.求商群?/4?,?/12?和4?/12?. ?/4?={4?,4?+1,4?+2,4?+3} (4?+a)+(4?+b)=4?+(a+b)mod4

?/12?={12?,12?+1,12?+2,12?+3,…,12?+11}

(12?+a)+(12?+b)=12?+(a+b)mod124?/12?={12?,12?+4,12?+8} (12?+a)+(12?+b)=12?+(a+b)mod12

11.30. 对以下各小题给定的群G1和G2以及f:G1?G2,说明f是否为群G1到G2的同态.如果是,说明G

是否为单同态,满同态和同构,并求同态像f(G1)和同态核kerf. (1)G1=??,+?,G2=?\\*,·?,其中\\*为非零实数的集合,+和·分别表示数的加法和乘法.

f:??\\*,f(x)=??

??1 x是偶

数x是??1

奇数

(2) G1=??,+?,G2=?A,·?,其中+和·分别表示数的加法和乘法

A={x|x∈??|x|=1},其中?为复数集合.

f:??A,f(x)=cosx+isinx

(3)G1=?\\,+?,G2=?A,·?,+和·以及A的定义同(2).

f:\\?A,f(x)=cosx+isinx(1)同态,不是单同态,也不是满同态.

同态像为{?1,1},同态核为2?.

(2)同态,单同态,不是满同态,同态像为{cosx+isinx|x∈?},同态核为{0}.(3)同态,满同态,不是单同态,同态像为A,同态核为{2kπ|k∈?}.

11.31. 11.32.

略

设?是群G1到G2的同构,证明??1是G2到G1的同构.

易见???1为G2到G1的双射函数.

任取G2中的元素x,y,存在G1中元素a,b使得??(a)=x,??(b)=y.因此, ???1(xy)=???1(??(a)??(b))=???1(??(ab))=ab=???1(x)???1(y) 从而证明了???1为同构.

11.33.

略

离散数学习题解

11.34.

设G1为循环群,??是群G1到G2的同态,证明??(G1)也是循环群.

47

设G1=?a?,任取??(G1)的元素x,存在ai∈G1,使得??(ai)=x.

x=??(ai)=(??(a))i

这证明了??(a)为??(G1)的生成元. 11.35. 设G=?a?是15阶循环

群.(1) 求出G的所有的生成元. (2) 求出G的所有子群.

(1)生成元: a,a2,a4,a7,a8,a11,a13,a14

(2)子群:?a?,?a3?={e,a3,a6,a9,a12},?a5?={e,a5,a10}, G

11.36.

12 3 4 5???1 2 3 4 5? ??

?????, ????? ??? ?

???2 1 4 5 3? ??3 4 5 1 2?

?1?1?1

(1)计算??,??,?,?,????

(2)将??,??1,??1??表成不交的轮换之积.

(3) 将(2)中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换.

设?,?是5元置换,且

??1 2 3 4 5????????, ? 4 3 1 2 5????

1 2 3 4 5????????????

4 5 3 2 1??? ?1 1 2 3 4 5???

??(1)

??? 1 5 3 ??? 4?2 1 2 3 4 5????1 ????? 5 1 2 ??? ?43?

1 2 3 4 5?????????1??????5 4 1 3 2?

?

??????1423??

(2)

??

???1???14253?????1??????15243??

??????14??12??13??

(3)

???1???14??12??15??13?????1??????15??12??14??13??

??为奇置换,??1,??1??为偶置换.

11.37.

*证明群中运算满足消去律

任取G中元素a,b,c,若ab=ac,则有

a?1(ab)=a?1(ac)

即(a?1a)b=(a?1a)c,从而有b=c. 同理可证右消去律的成立. 11.38.

*设G是有限群,K是G的子群, H是K的子群,证明[G:H]=[G:K][K:H].

由拉格朗日定理有

|G|=[G:K]|K|,|K|=[K:H]|H|,

代入得

|G|=[G:K][K:H]|H|

再根据拉格朗日定理有|G|=[G:H]|H|,比较两个等式,命题得证.

离散数学习题解 48

习题十二

12.1.设A={a+bi|a,b∈?,i2=?1},证明A关于复数的加法和乘法构成环,称为高斯整数环.

12.2.略

12.3.(1) 设R1,R2是环,证明R1与R2的直积R1×R2也是环.

(2)若R1和R2为交换环和含幺环,证明R1×R2也是交换环和含幺环. 12.4.判断下列集合和给定运算是否构成环,整环和域,如果不能构成,说明理

由.(1)A={a+bi|a,b∈?},其中i2=?1,运算为复数的加法和乘法. (2)A={?1,0,1},运算为普通加法和乘法.

(3)A=M2(?),2阶整数矩阵的集合,运算为矩阵加法和乘法.(4) A是非零有理数集合Q*,运算为普通加法和乘法. 12.5.略

12.6.略

12.7.略

12.8.证明定理12.1(3)

离散数学习题解 49

习题十三

13.1.

1.图13.9中给出6个偏序集的哈斯图.判断其中哪些是格.如果不是格,说明理由.

d

f d c b a (b) (c) e d f e

c b a (a) g f d e b a c

f d d c e b b f e

c a (f) b a

c a (d) (e)

图13.9

(a),(c),(f)是格.(b)中的{e,d}没有最大下界. (d)中的{d,e}没有最大下界. (e)中的{a,b}没有最大下界.

13.2.2.下列各集合对于整除关系都构成偏序集,判断哪些偏序集是

格.(1)L= {1,2, 3,4,5} (2)L= {1, 2, 3,6,12}

(3)L ={1, 2,3,4, 6,9,12,18,36} (4)L={1,2,22,...,2n},n??+ (1)不是格,其他都是.

13.3.3.(1)群??12,??的子群格.

(2)画出3元对称群S3的子群格.见答图.

离散数学习题解 50

?12

S3

?2?? ?3??

?(12)??

?4??

?(123)???(23)???(13)??

?6??

?0??(1)

?(1)??

(2)

第3题答图

13.4.4.设L是格,求以下公式的对偶式:

(1)a??(a?b)?a

(2)a??(b?c)?(a?b)??(a?c)

(3)b??(c?a)?(b?c)?a. (1)a?(a?b)“a

(2)a??(b?c)“(a?b)??(a?c) (3)b??(c?a)“(b?c)?a

13.5.5.设?为集合S上可交换,可结合的二元运算,若a,b是S上关于?运算的幂等元,证明a?b也是关于?运算的

幂等元.证

a??b =b??c

(a??b)??(a??b)=((a??b)??a)??b=(a??(a??b))??b=((a??a)??b)??b=(a??a)??(b??b)=a??b.

13.6.6.设L是格,a,b,c?L,且a?b?c,证明

a??b =b??c

a??b =b; b??c=b.

13.7.7.针对图13.4中的格L1,L2和L3,求出他们的所有子格. d d1 d1b a c a1 L2 L3 c2 b2 a2

L1

图13.10

L1的子格:{a},{b}, {c},{d}, {a,b},{a,c},{a, d},{b, d},{c,d},{a, b,d},{a, c,d}, L1.L2的子格: {a1},{d1},L2

L3的子格: {a2},{b2}, {c2},{d2},{a2,b2},{a2,c2}, {a2,d2},{b2,c2},{b2, d2},{c2,d2},{a2,b2, c2},{a2,b2,d2}, {a2, c2,d2},{b2,c2, d2},L3

离散数学习题解 1

习题一

1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略

1.10． 略 1.11． 略

1.12． 将下列命题符号化,并给出各命题的真值:

(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4的充要条件是3+3?6.(3)2+2?4与3+3＝6互为充要条件.(4)若2+2?4, 则3+3?6,反之亦然.

(1)p?q,其中,p: 2+2＝4,q: 3+3＝6, 真值为1.(2)p??q,其中,p:2+2＝4,q:3+3＝6,真值为0. (3)?p?q,其中,p:2+2＝4,q:3+3＝6,真值为0.(4)?p??q,其中,p:2+2＝4,q:3+3＝6,真值为1.

1.13． 将下列命题符号化, 并给出各命题的真

值:(1)若今天是星期一,则明天是星期二.(2)只有今天是星期一,明天才是星期二.(3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一,则明天是星期三.

令p: 今天是星期一;q:明天是星期二;r:明天是星期三.(1) p?q ??1. (2) q?p ??1. (3) p?q??1.

(4)p?r当p ??0时为真; p ??1时为假.

1.14． 将下列命题符号化. (1)

刘晓月跑得快,跳得高.(2)老王是山东人或河北人.

(3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组.

(5)李辛与李末是兄弟.

(6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨,他就乘班车上班.(9)只有天下大雨,他才乘班车上班.(10)除非天下大雨,他才乘班车上班.(11)下雪路滑, 他迟到了.

(12)2与4都是素数,这是不对的.

(13)“2或4是素数,这是不对的”是不对的.

离散数学习题解

(1)p?q,其中, p:刘晓月跑得快, q: 刘晓月跳得高.(2)p?q,其中, p:老王是山东人, q: 老王是河北人.(3)p?q, 其中,p:天气冷, q:我穿了羽绒服.

(4)p, 其中,p:王欢与李乐组成一个小组,是简单命题.(5)p, 其中,p:李辛与李末是兄弟.

(6)p?q,其中, p:王强学过法语, q: 刘威学过法语.(7)p?q,其中, p:他吃饭,q:他听音乐.

(8)p?q, 其中,p:天下大雨, q:他乘班车上班.

(9)p?q, 其中,p:他乘班车上班, q: 天下大雨.(10)p?q, 其中,p: 他乘班车上班,q:天下大雨.(11)p?q, 其中,p: 下雪路滑, q:他迟到了.

12)??(p?q)或?p??q,其中,p:2是素数,q:4是素数.(13)???(p?q)或p?q,其中,p:2 是素数,q:4是素数.

2

1.15．

设p:2+3=5. q: 大熊猫产在中国.r: 复旦大学在广州.求下列复合命题的真值: (1)(p?q)?r(2)(r??(p?q))???p(3)?r??(?p??q?r)

(4)(p?q??r)??((?p??q)?r) (1)真值为0. (2)真值为0. (3)真值为0. (4)真值为1.

注意:p, q是真命题,r是假命题.

1.16． 1.17． 1.18． 1.19．

略 略 略

用真值表判断下列公式的类

型:(1)p??(p?q?r) (2)(p??q)??q (3)??(q?r)?r (4)(p?q)??(?q??p) (5)(p?r)??(?p??q)(6)((p?q) ??(q?r))??(p?r)(7)(p?q) ??(r?s)

离散数学习题解

(1), (4),(6)为重言式. (3)为矛盾式.

(2), (5),(7)为可满足式.

3

1.20． 1.21． 1.22． 1.23． 1.24． 1.25． 1.26． 1.27． 1.28． 1.29． 1.30． 1.31．

略 略 略 略 略 略 略 略 略 略 略

将下列命题符号化,并给出各命题的真

值:(1)若3+＝4,则地球是静止不动的. (2)若3+2＝4,则地球是运动不止的. (3)若地球上没有树木,则人类不能生存. (4)若地球上没有水,则3是无理数.

(1)p?q,其中, p: 2+2＝4,q:地球静止不动,真值为0.(2)p?q,其中, p: 2+2＝4,q:地球运动不止,真值为1.

(3)?p??q,其中,p:地球上有树木,q:人类能生存,真值为1.(4)?p?q,其中,p:地球上有水,q: 3 是无理数,真值为1.

离散数学习题解 4

习题二

2.1.设公式A=p?q,B=p??q,用真值表验证公式A和B适合德摩根律:

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

p 0 0 1 1 q 0 1 0 1 A =p?q B=p??q 1 1 0 1 0 0 1 0 ?(A?B) ?A??B 0 0 0 0 0 0 0 0

因为?(A?B)和?A??B的真值表相同,所以它们等值.

2.2. 略

2.3. 用等值演算法判断下列公式的类型, 对不是重言式的可满足式,再用真值表法求出成真赋值.(1)??(p?q?q) (2)(p??(p?q))??(p?r)

(3)(p?q)??(p?r)

(1)??(p?q?q)????(?(p?q)??q)????(?p???q??q)??p?q??q??p?0??0??0.矛盾式.(2)重言式.

(3) (p?q)??(p?r)???(p?q)??(p?r)???p??q??p?r易见,是可满足式,但不是重言式.成真赋值为:000,001, 101, 111

p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 ?p???q?p?r 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1

2.4.用等值演算法证明下面等值

式:(1)p??(p?q)??(p??q) (3)??(p?q)??(p?q)???(p?q)

(4)(p??q)??(?p?q)??(p?q)???(p?q) (1)

(p?q)??(p??q)??p??(q??q)??p??1??p.(3)??(p?q)

离散数学习题解

???((p?q)??(q?p)) ???((?p?q)??(?q?p)) ??(p??q)??(q??p)

??(p?q)??(p??p)??(?q?q)??(?p??q)

5

??(p?q) ???(p?q) (4)(p??q)??(?p?q)

??(p??p)??(p?q)??(?q??p)??(?q?q)

??(p?q) ???(p?q)

2.5.求下列公式的主析取范式,并求成真赋

值:(1)(?p?q)??(?q?p) (2)??(p?q)?q?r

(3)(p??(q?r)) ??(p?q?r) (1)(?p?q)??(?q?p) ???(p?q) ??(?q?p)

???p??q???q??p???p??q???q??p(吸收律)??(p??p)??q??p?(q??q) ??p??q??p??q??p?q??p??q ??m10??m00??m11??m10 ??m0??m2??m3 ???(0, 2,3).

成真赋值为00,10, 11.

(2)主析取范式为0, 无成真赋值,为矛盾式.(3)m0?m1?m2?m3?m4?m5?m6?m7,为重言式.

2.6. 求下列公式的主合取范式, 并求成假赋值:(1)??(q??p)??p (2)(p?q)??(?p?r)

(3)(p??(p?q))?r (1) ??(q??p)???p ???(?q??p)???p ??q?p???p ??q?0 ??0

??M0?M1?M2?M3

这是矛盾式.成假赋值为00, 01,10,11. (2)M4,成假赋值为100. (3)主合取范式为1, 为重言式.

离散数学习题解

(8)加法不封闭,乘法封闭(9)加法不封闭,乘法封闭(10)加法不封闭,乘法封闭

41

10.5.对于上题中封闭的二元运算判断是否适合交换律,结合律和分配律.

(1)没有交换律, 没有结合律 (3)加法适合交换与结合律；乘法只适合结合律；乘法对于加法有分配律. (4)乘法适合结合律

(6)加法有交换, 结合律；乘法有交换,结合律；乘法对于加法有分配律.(7)结合律

(8)乘法有交换, 结合律 (9)乘法有交换, 结合律 (10)乘法有交换,结合律

10.6.对习题4中封闭的二元运算找出它的单位元,零元和所有可逆元素的逆元.

(1)没有单位元, 零元和可逆元素.

(3)加法单位元为n阶全0矩阵,没有零元,任意n阶矩阵M有加法逆元?M；乘法单位元为n阶单位矩阵,零元为n阶全0矩阵,可逆矩阵M(行列式不为0)有乘法逆元M?1. (4)乘法单位元为n阶单位矩阵,没有零元,任何M有乘法逆元M?1.

(6)加法单位元为0, 没有零元,x的加法逆元是?x；乘法零元为0, 当n=1时单位元为1,1和?1有乘法逆元,就是自身.

(7)没有单位元, 零元与可逆元素 (8)单位元为1,没有零元,1的乘法逆元是1 (9)单位元为1,零元是0,1的乘法逆元是1 (10)没有单位元,零元与可逆元素.

10.7.略 10.8.S=_×_,_为有理数集,?为S上的二元运算, ??a,b?,?x,y?∈S有

?a,b???x,y?=?ax,ay+b??

(1)?运算在S上是否可交换,可结合?是否为幂等的?

(2)?运算是否有单位元,零元?如果有, 请指出,并求S中所有可逆元素的逆元.

(1)不可交换,可结合,不满足幂等律.

(2)单位元为?1,0?,没有零元,当a?0,?a,b?的逆元为??

1 a

,?

b a

??

10.9.\\为实数集,定义以下六个函数f1,…,f6.?x,y∈\\有 f1(?x,y?)=x+y, f2(?x,y?)=x?y, f3(?x,y?)=x·y, f4(?x,y?)=max(x,y),f5(?x,y?)=min(x,y), f6(?x,y?)=|x?y| (1)指出哪些函数是\\上的二元运算.

(2)对所有\\上的二元运算说明是否为可交换,可结合,幂等的. (3)求所有\\上二元运算的单位元,零元以及每一个可逆元素的逆元.

离散数学习题解

(1)都是\\上的二元运算

(2)f1, f3, f4,f5,f6可交换,f1,f3, f4,f5可结合, f4,f5幂等；

(3)f1的单位元为0,没有零元,x的逆元为?x；f2没有单位元, 零元与可逆元素；f3的单位元为1, 零元为0,x (x?0)的逆元为 ；f4, f5, f6没有单位元,零元与可逆元素.

42

1 x

10.10. 令S= {a,b},S上有4个二元运算:?,○,i和□,分别由表10.8确定.表10.8 ? a b a a a a a ○ a b a a b b b a i a b a b a b a a □ a b a a b b b a b (1) 这4个运算中哪些运算满足交换律,结合律,幂等律 (2) 求每个运算的单位元,零元及所有可逆元素的逆元.

(1)?,○,·可交换；?,○,□可结合；□幂等.

(2)?没有单位元和可逆元素,零元为a；○的单位元为a,没有零元,每个元素都是自己的逆元；·和□没有单位元,零元和可逆元素.

10.11. 设S= {1, 2, …, 10}, 问下面定义的运算能否与S构成代数系统?S,????如果能构成代数系统则说

明?运算是否满足交换律,结合律,并求?运算的单位元和零元. (1)x?y=gcd(x,y),gcd(x,y)是x与y的最大公约数. (2)x?y=lcm(x,y),lcm(x,y)是x与y的最小公倍数.(3)x?y=大于等于x和y的最小整数. (4)x?y=质数p的个数,其中x≤p≤y. (1)构成；满足交换律,结合律,没有单位元,零元为1.(2)不构成. (3)构成；单位元为1,零元为10,只有1有逆元,就是1. (4)不构成.

10.12. 10.13. 10.14. 10.15. 略 略 略

下面各集合都是?的子集,它们能否构成代数系统V=??,+?的子代数:(1){x|x∈??x可以被16整除} (2){x|x∈??x与8互质} (3){x|x∈??x是40的因子} (4){x|x∈??x是30的倍数}.

(1)构成. (2)不构成. (3)不构成. (4)构成.

10.16. 设V=??,+,·?,其中+和·分别代表普通加法和乘法,对下面给定的每个集合确定它是否构成V的子

代数, 为什么?

(1)S1={2n|n∈?} (2)S2={2n+1|n∈?} (3)S3={－1,0,1}

(1)是,因为S1对于加法和乘法封闭.(2)不是,因为S2对于加法不封闭.(3)不是,因为S3对于加法不封闭.

离散数学习题解 43

10.17. 设V1=?{1,2,3},○,1?,其中x○y表示取x和y之中较大的数.V2=?{5,6},?,6?,其中x?y表示取x和y之

中较小的数.求出V1和V2的所有子代数.指出哪些是平凡子代数,哪些是真子代数.

V1的子代数为{1},{1,2},{1,3},{1,2,3},平凡子代数是{1}和{1,2,3}；V2的子代数为{6}和{5,6},都是平凡子代数.

离散数学习题解 44

习题十一

11.1.设A={0,1},试给出半群?AA,○?的运算表,其中○为函数的复合运算.

AA={f1,f2,f3,f4},其中

f1={?0,0?,?1,0?},f2={?0,0?,?1,1?}, f3={?0,1?,?1,0?},f4={?0,1?,?1,1?} 运算表为 ○ f1f2f3f4 f1 f1f1f1f1 f2 f1f2f3f4 f3 f4f3f2f1 f4 f4 f4 f4 f4 11.2.略 11.3.略 11.4.略 11.5.略 11.6.略 11.7.设G={a+bi|a,b∈?},i为虚数单位,即i2=?1.验证G关于复数加法构成群.复数加法在G上封闭,有结合律,单位元为0=0+0i,a+bi的逆元为?a?bi. 11.8.略

11.9.设?为整数集合,在?上定义二元运算○如下:

?x,y∈?,x○y=x+y?2

问?关于○运算能否构成群?为什么?

易见该运算封闭,任取整数x,y,z,

(x○y)○z=(x+y?2)○z=x+y?2+z?2=x+y+z?4x○(y

○z)=x+(y+z?2)?2=x+y+z?4=x+y+z?4 结合律成立.单位元为2. X的逆元为4?x.

11.10.

设A={x|x∈\\?x?0,1}.在A上定义六个函数如下: f1(x)=x, f2(x)=x?1, f3(x)=1?x,f4(x)=(1?x) ?1, f5(x)=(x?1)x?1, f6(x)=x(x?1)?1

令F为这6个函数构成的集合,○运算为函数的复合运算.(1)给出○运算的运算表. (2)验证?F,○?是一个群.

离散数学习题解 45

○ f1 f2

(1)f3

f1 f1 f2 f3 f4 f5 f6 f2 f2 f1 f5 f6 f3 f4 f3 f3 f4 f1 f2 f6 f5 f4 f4 f3 f6 f5 f1 f2 f5 f5 f6 f2 f1 f4 f3 f6 f6 f5 f4 f3 f2 f1 f4 f5 f6

(2)易见封闭性满足,函数合成满足结合律,单位元是f1, ?1 ?1 ?1 ?1 ?1 ?1

f1 =f1,f2 =f2,f3 =f3,f4 =f5,f5 =f4,f6 =f6. 11.11. 11.12. 11.13. 11.14.

略 略 略

设G为群,且存在a∈G,使得G={ak|k∈?},证明G是交换群.

任取ai,aj,aiaj=ai+j =aj+i=ajai

11.15. 11.16.

略

设G为群,若?x∈G有x2=e,证明G为交换群.

任取G中元素a,b, 由于a,b为二阶元,a=a?1,b=b?1, 从而

ab=a?1b?1=(ba)?1=ba 11.17.

设G为群,证明e为G中唯一的幂等元.

设a为幂等元,那么aa=a,由消去律得a=e. 11.18. 11.19.

略

*证明4阶群必含2阶元.

设G为4阶群, 若G中含有4阶元a,那么a2是2阶元；若G中不含4阶元,根据拉格朗日定理,G中元素的阶只能是2或1,而G不是平凡群,必有非单位元存在,这些非单位元就是2阶元. 11.20.

*设G是非阿贝尔群,证明G中存在元素a和b,a?b,且ab=ba.

先证G中必含3阶或3阶以上的元素.假设G中只有1阶或2阶元,那么G中任意元素a都有a2=e.根据第 7题的结果,G为Abel群,与已知矛盾. 设a为G中元素,且|a|>2,那么a?a?1,令b=a?1,则有ab=ba. 11.21. 11.22. 11.23.

略 略

11.设H是群G的子群,x∈G,令

xHx?1={xhx?1|h∈H},

证明xHx?1是G的子群,称为H的共轭子群.

e是xHx?1中的元素,因此xHx?1非空.任取xhx?1,xkx?1∈xHx?1,h,k∈H,则有

(xhx?1)(xkx?1)?1=(xhx?1)(xk?1x?1)=x(hk?1)x?1

因为H为子群,hk?1属于H,从而x(hk?1)x?1属于xHx?1.由判定定理,命题得证. 11.24. 11.25. 11.26.

略

证明定理11.11. *设

???1 0????1 0?????1 0?????1 0?????

?? ??? ??? ??? ?G? ??, , ,

??0 ?1???????0 1???0 ?1???1????0

离散数学习题解

A??=?,A?{{?}}={?{?},??},A[{{?}}]=??

31

7.16.设A={a,b,c,d},R1,R2为A上的关系,其中

R1={?a,a?,?a,b?,?b,d?} R2={?a,d?2 ,?b,c?,?b,d?,?c,b?} 3

求R1○R2,R2○R1,R1,R2.

R1○R2={?a,a?,?a,c?,?a,d?},R2○R1={?c,d?}, R2={?a,a?,?a,b?,?a,d?}, 1 3

R2 ={?b,c?,?b,d?,?c,b?}

7.17.设A={a,b,c}, 试给出A上两个不同的关系R1和R2,使得R1=R1, R2=R2.

R1={?a,a?,?b,b?}, R2={?b,c?,?c,b?}

7.18.证明定理7.4的(1), (2),(4).

2

3

(1)F○(G∪H)=F○G∪F○H 任取?x,y?,

?x,y?∈F○(G∪H)

??t(?x,t?∈F??t,y?∈G∪H)

??t(?x,t?∈F??(?t,y?∈G??t,y?∈H))

??t((?x,t?∈F??t,y?∈G) ??(?x,t?∈F??t,y?∈H)) ??t(?x,t?∈F??t,y?∈G) ??t(?x,t?∈F??t,y?∈H)) ??x,y?∈F○G??x,y?∈F○H ??x,y?∈F○G∩F○H 所以有F○(G∩H)??F○G∩F○H.

(2)(G∪H)○F=G○F∪H○F 任取?x,y?,

?x,y?∈(G∪H)○F

??t(?x,t?∈(G∪H)??t,y?∈F)

??t((?x,t?∈G??t,y?∈H)??t,y?∈F))

??t((?x,t?∈G??t,y?∈F) ??(?x,t?∈H??t,y?∈F)) ??t(?x,t?∈G??t,y?∈F) ??t(?x,t?∈H??t,y?∈F)) ??x,y?∈G○F??x,y?∈H○F ??x,y?∈G○F∪H○F

(4)(G∩H)○F?G○F∩H○F 任取?x,y?,

?x,y?∈(G∩H)○F

??t(?x,t?∈(G∩H)??t,y?∈F)

??t((?x,t?∈G??t,y?∈H)??t,y?∈F))

??t((?x,t?∈G??t,y?∈F) ??(?x,t?∈H??t,y?∈F)) ??t(?x,t?∈G??t,y?∈F) ??t(?x,t?∈H??t,y?∈F)) ??x,y?∈G○F??x,y?∈H○F ??x,y?∈G○F∪H○F

7.19.证明定理7.5的(2), (3).

(2)F[A∪B]=F[A]∪F[B]

任取y,

离散数学习题解

y∈F[A∪B]

??x(?x,y?∈F?x∈A∪B) ??x(?x,y?∈F??(x∈A?x∈B))

??x((?x,y?∈F?x∈A) ??(?x,y?∈F?x∈B)) ??x(?x,y?∈F?x∈A) ??x(?x,y?∈F?x∈B) ?y∈F[A]?y∈F[B] ?y∈F[A]∪F[B]

所以有F[A∩B]=F[A]∪F[B].

(3)F?(A∩B)?F?A∩F?B

任取?x,y??

?x,y?∈F?(A∩B) ??x,y?∈F?x∈(A∩B) ??x,y?∈F??(x∈A?x∈B)

??(?x,y?∈F?x∈A) ??(?x,y?∈F?x∈B) ??x,y?∈F?A??x,y?∈F?B

??x,y?∈F?A∩F?B 所以有F?(A∪B)?F?A∩F?B.

32

7.20.设R1和R2为A上的关系,证明:

(1)(R1∪R2)?1=R1 ∪R2

(2)(R1∩R2) ?1=R1 ∩R2

?1 ?1 ?1

?1 ?1

(1)(R1∪R2)?1=R1 ∪R2

任取?x,y??

?x,y?∈(R1∪R2) ?1 ??y,x?∈(R1∪R2) ??y,x?∈R1??(y,x)∈R2) ?1

?1

??x,y?∈R1 ?1 ??x,?y1 ?∈R2 ??x,y?∈R1 ??R1 2 ?1

?1

所以(R1∪R2)=R1 ∪R2

(2)(R1∩R2)?1=R1 ∩R2

?1

?1

?1

任取?x,y??

?x,y?∈(R1∩R2)?1 ??y,x?∈(R1∩R2) ??y,x?∈R1??(y,x)∈R2) ?1

?1

??x,y?∈R1 ?1 ??x,?y1 ?∈R2 ??x,y?∈R1 ?R2

所以(R1∪R2)?1=R1 ∩R2

7.21.略 7.22.略 7.23.略 7.24.略 7.25.略 7.26.略 7.27.略 7.28.略 7.29.略 7.30.略 7.31.略 7.32.略 7.33.略 7.34.略 7.35.略 7.36.略 7.37.略 7.38.略 7.39.略 7.40.略

?1 ?1

离散数学习题解

7.41.略 7.42.略 7.43.略 7.44.略 7.45.略 7.46.略 7.47.略 7.48.略 7.49.略 7.50.略

33

离散数学习题解 34

习题八

8.1.1设f:???,且

?1 ?f(x)??????x 2 ??若x为奇数若x为偶数

求f(0),f({0}),f(1),f({1}), f({0,2, 4, 6,…}), f({4,6,8}),f({1,3, 5,7})

f(0) = 0,

f({0})={f(0)}={0},

f(1)=1,f({1})={f(1)}={1},

f({0,2, 4, 6, …})= {f(0),f(2),f(4), f(6), …}={0, 1, 2, 3, …}=?, f({4,6, 8})= {f(4),f(6),f(8)}= {2,3,4}, f({1,3,5, 7})={1, 1,1, 1}={1}. 8.2.2.设A={1,2},B={a,b, c}, 求BA.

BA={f1,f2, f3,f4,f5,f6,f7, f8, f9}

f1= {?1, a?,?2,a?}, f2 ={?1,a?,?2,b?},f3= {?1,a?,?2,c?}, f4= {?1, b?,?2,a?}, f5 ={?1,b?,?2,b?},f6= {?1,b?,?2,c?}, f7= {?1, c?,?2,a?}, f8 ={?1, c?,?2, b?},f9= {?1,c?,?2,c?}.

8.3.3.给定函数f和集合A,B如

下:(1)f:R?R,f(x)=x,A={8},B={4} (2)f:R?R+, f(x)=2x, A={1},B={1,2}

(3)f:N?N?N,f(x)=?x,x+1},A={5},B={?2,3?} (4)f:N?N, f(x)=2x+1,A={2, 3},B={1,3} (5)f:Z?N,f(x)=|x|, A={?1, 2},B={1}

(6)f:S?S,S=[0, 1],f(x)=x/2+1/4, A=(0,1),B=[1/4,1/2] (7)f:S?R,S=[0, +∞),f(x)=1/(x+1),A={0,1/2},B={1/2} (8)f:S?R+,S=(0, 1),f(x)=1/x,A=S, B={2, 3}. 对以上每一组f和A,B,分别回答以下问题:

(a)f是不是满射,单射和双射的?如果f是双射的,求f的反函数.(b)求A在f下的像f(A)和B在f下的完全原像f-1(B).

8.4.4.判断下列函数中那些是满射的?哪些是单射的?哪些是双射

的?(1)f:???,f(x)=x2+2

(2)f:???,f(x)=(x)mod3,x除以3的余数. (3)f:???,f(x)????

?1 ?0

?0 ?1

若x为奇数若x为偶数

若x为奇数 若x为偶数

(4)f:??{0,1},f(x)????

(5)f:??{0}?R,f(x)=log10x (6)f:R?R, f(x)=x2?2x?15

离散数学习题解

(1)单射,∵f(x)=x2+2在?上是单调的. 不是满射,∵?x??,f(x) =x2+2??0.

35

(3)不是单射的, ∵f(0)= f(2) = 0.不是满射的, ∵?x??,

?0 f(x)???

?1

若x为奇

??2.

数若x为偶数

(5)是单射的,∵ f(x)=log10x在?上是单调的.不是满射的,∵?x??,f(x)=log10x??2.

8.5.设X = {a,b, c,d},Y = {1,2,3},f={?a, 1?,?b, 2?,?c, 3?},判断以下命题的真假 (1)f是从X到Y的二元关系,但不是从X到Y的函数;(2) f是从X到Y的函数,但不是从满射,也不是单射(3)f是从X到Y的满射,但不是从单射; (4) f是从X到Y的双射. 8.6.对于给定的A, B和f,判断f是否为从A到B的函数f :A ??B.如果是,说明f是否为单射,满射,双射的. (1)A=?,B=?,f(x)=x2+1. (2)A=?,B=_,f(x)=1??x. (3)A=???,B=_,f(?x,y?)=x??(y+1).. (4)A = {1, 2,3},B={p,q,r}, f= {?1,q?,?2,q?,?3, q?}.(5)A=B=?,f(x)=2x. (6)A=B=\\?\\,f(?x,y?)=?y+1,x+1?.(7)A =???,B=?,f(?x,y?)= x2+2y2. (8)A=B=\\,f(x)=1 x??1. (9)A=???,B=?,f(?x,y,z?) =x+y??z. 8.7.7.设A = {a, b, c,d},B= {0,1, 2} (1)给出一个函数f :A??B, 使得f不是单射的也不是满射的;(2)给出一个函数f :A??B, 使得f不是单射的但是满射的;(3)能够给出一个函数f :A??B,使得f是单射但不是满射的吗? (4)设|A|=m,|B| =n,分别说明存在单射,满射,双射函数f :A??B的条件.

(1)答案不唯一.f={?a, 0?,?b, 0?,?c, 0?,?d, 0?}. (2)答案不唯一.f={?a, 0?,?b, 1?,?c, 2?,?d, 2?}.

(3)不能.事实上A到B不存在单射,∵|A| =4 >|B| =3.

(4)存在单射的条件是m ??n, 存在满射的条件是m ??n,存在双射的条件是m =n.

8.8.给出自然数集?上的函数f,使得

(1)f是单射的, 但不是满射

的;(2)f是满射的, 但不是单射的.

8.9.9.设A是n元集(n ??1),则从A到A的函数中有多少个双射函数?有多少个单射函数.

从A到A的函数中双射函数和单射函数都有n!个. 注:事实上, 从A到A的函数中满射函数也有n!个.

8.10.10.设f:??????,f(?x,y?)=x+y+1(1)说

明f是否为单射,满射,双射的;

(2)令A= {?x,y?|x,y??且f(?x,y?)=3}, 求A; (3)令B={f(?x, y?)|x,y?{1, 2, 3}且x=y},求B.

(1)f不是单射的,∵f (?0, 1?)=f(?0, 1?)=2.f不是满射的,∵??x??,f (?x,y?)> 0.从而f不是双射的.(2)要使f (?x,y?)=x+y+ 1=3,可取?x,y??=?1, 1?,?0, 2?,?2,0?.故A ={?1,1?,?0,2?,?2,0?}. (3)B= {f(?1,1?),f(?2,2?), f(?3,3?)} = {3,5,7}.

8.11.确定f是否为从X到Y的函数,并对f:X??Y指出哪些是单射,哪些是满射,那些是双射的.(1)X=Y=\\,\\为实数集,f(x)=x2–x;

(2)X=Y=\\,f(x)=??x;

离散数学习题解 36

(3)X=Y=\\,f(x)= +1 x ; x??1 x??1 (4)X=Y=?={x|x???,x>0},f(x)=x+1; (5)X=Y=?,f(x)=???x ?x?1 . 8.12.设f: S?T,证明 (1)f (A∩B) ??f(A) ∩f(B),其中A,B??S.(2)举出反例说明等式f(A∩B)= f(A)∩f(B)不是永远为真的.(3)说明对于什么函数,上述等式为真. 8.13.设A为非空集合,R为A上的等价关系,g:A??A/R 为自然映射. (1)设R为整数集合上的模n相等关系,求g(2).(2)说明g的性质(单射,满射,双射).(3)说明在什么条件下,g为双射函数. 8.14.设S为集合, A,B是S的子集, ?T表示T的特征函数, 且?A= {?a, 1?,?b,1?,?c, 0?,?d, 0?},?B={?a, 0?,?b, 1?,?c,0?,?d, 1?},求?AB. 8.15.15.设A={1,2,3, 4},A1={1,2},A2={1},A3=?,求A1,A2,A3和A的特征函数?A1,?A2, ?A3和?A. ∩

8.16.16.设A={a, b,c}.R为A上的等价关系,且

R={?a, b?,?b, a?}∪IA

求自然映射g: A?A/R.

8.17.17．设f,g, h∈RR,且 f(x)=x+3,g(x)=2x+1,h(x)=

1 2 求f○g,g○f,f○f,g○g,h○f,g○h,f○h,g○h○f.

8.18.18．设f,g,h∈?,且有

?

?0

f(n)=n+1,g(n)=2n,h(x)????

?1

求f○f, g○f,f○g,h○g,g○h,h○g○f

若x为偶数 若x为奇数

8.19.设f:\\??\\,f(x)=x2??2, g:\\??\\,g(x)=x+4, h:\\??\\,h(x)=x??1. (1)求g○f,f○g; (2)问g○f和f○g是否为单射,满射,双射的? (3)f, g,h中哪些函数有反函数?如果有,求出这些反函数. 8.20.20.设f,g是从?到?的函数,且 ?x?1 ?f(x)????0 ?x, ??(1)求f○g x??0,1,2,3 x??4 x??5 ?x ??g(x)???2 ??3 ?? x为偶数x为奇数 (2)说明f○g是否为单射,满射,双射的. 离散数学习题解 37

(1)这里的复合运算是右复合:f○g(x) =g(f(x)).当x = 1,3, 4以及大于5的偶数时, f(x)是偶数;当x= 0, 2以及大于5的奇数时,f(x)是奇数,所以

??x?1 ???2 ,???0, g(x)????

?3, ??x ??2, ?

并且f○g: ????.

x??1,3

?1, ?2, ???0, x??4

????

x??0,2或??5的奇数 3,

??x x为大于的偶数

5 ?, ??2

x??1 x??3

x??4

x??0,2或??5的奇数 x为大于5的偶数

(2)f不是单射的,∵f(0) =f(2)= 3. f是满射的,∵ranf={0,1,2, 3}∪{x/2|x为大于5的偶数} = {0, 1,2,3}∪{3, 4,5,…,n,…}=?.

8.21.21.设f:??????,f(x)=?x,x+1?.(1)说明f是

否为单射和满射, 为什么

(2)f的反函数是否存在,如果存在,求出f的反函数; (3)求ranf.

(1)f是单射的,∵?x1, x2??,若x1??x2,则f(x1)=?x1, x1+ 1????f(x2)=?x2, x2+1?.F不是满射的,因为若?0, 0????ranf, 则?x??,使得f(x)=?x,x+ 1??=?0,0?,而这是不可能的.

(2)因为f={?x,?x,x+1??|x??}是单射,它的逆关系f?1={??x,x+1?,x?|x??}是函数,是从ranf到domf=? 的双射函数.但f?1不是??????的函数,因为domf?1=ranf????.(3)ranf={?n,n+1??n??}.

8.22.设f:????,f(x)=(x)modn.在?上定义等价关系R,?x,y??,

?x,y??R ??f(x)=f(y).

(1)计算f(?).(2)确定商集?/R.

8.23.设f1,f2,f3,f4为实数集\\到\\的函数,且

???1, x??0

,

??1, x??0 f2(x)=x,

??1, x为整数 f3(x)=??,

???1,否则

f1(x)=??f4(x)=1.

在\\上定义二元关系Ei,?x,y?\\,?x,y??Ei?f(x)=f(y),则Ei是\\上的等价关系,称 为fi导出的等价关系,求商集\\/Ei,i= 1,2, 3,4.

8.24.24.对于以下集合A和B,构造从A到B的双射函数f:

A?B.(1)A={1,2,3},B={a,b,c} (2)A=(0,1),B=(0, 2) (3) A={x|x???x<0},B=? (4) A=R,B=R+

8.25.25.设f:\\?\\?\\?\\,f(?x,y?)=??(x+y)/2,(x-y)/2?,证明f是双射的.

8.26.设f:A??B,g:B??C, 且f○g:A??C是双射.证

明:(1)f :A??B是单射的. (2)g: B??C是满射的.

8.27.按照阶从低到高的次序排列下列函数,如果f(n)与g(n)的阶相等,则表示为f(n)=?(g(n)).

x,??n, logn,n3,nlogn, 2n3+n,2n,(logn)2, lgn,n3+logn. 8.28.证明

(logn)logn=nloglogn.

4logn=n2;2logn=n; 2=n1/ logn;

离散数学习题解 38

22logn ??n2logn

离散数学习题解 39

习题九

9.1.1.设A={a,b,c},B=2A, 由定义证明P(A)≈2A.

9.2.2.设[1,2]和[0,1]是实数区间,由定义证明[1, 2]≈[0,1]. 9.3. 3.设A={2x|x∈?},证明A≈?.

9.4.4.证明定理9.1.

9.5.5.证明定理9.3的(1), (3).

9.6.设A,B,C,D是集合,且A≈C,B≈D,证明A×B≈C×D. 9.7. 找出三个不同的?的真子集,使得他们都与?等势. 9.8. 找出三个不同的?的真子集A,B,C,使得A?·?,B?·?,C?·?. 9.9.根据自然数的集合定义计

算:(1)3∪6,2∩5 (2)4?3,3?1 (3)∪4,∩1 (4)1×4,22. 9.10.略

9.11.设A,B为可数集,证明

(1)A∪B是可数集.(2)A×B是可数集.

离散数学习题解 40

习题十

10.1.列出以下运算的运算表:

1 1

(1)A={1,2, },?x∈A,○x是x的倒数,即○x= .

2 x

?x,y∈A有x○y=max(x,y),max(x,y)是x和y之中较大的数. (2)A={1,2,3,4},

x ○x 1 1 1 (1) 2 2

1 2 2

10.2.略 10.3.略

10.4.判断下列集合对所给的二元运算是否封

闭:(1) 整数集合?和普通的减法运算 (2) 非零整数集合?*和普通的除法运算

1 1 2 3 4 (2) 2 2 2 3 4 3 3 3 3 4 4 4 4 4 4

(3)全体n×n实矩阵集合Mn(\\)和矩阵加法及乘法运算,其中n≥2

(4)全体n×n实可逆矩阵集合关于矩阵加法和乘法运算,其中n≥2(5)正实数集合\\+和○运算,其中○运算定义为:

?a,b∈\\+,a○b=ab?a?b

(6) n∈?+,n?={nz|z∈?}.n?关于普通的加法和乘法运算.

(7)A={a1,a2,...,an},n≥2.○运算定义如下:?ai,aj∈A,ai○aj=ai.

(8) S={2x?1|x∈?+}关于普通的加法和乘法运算.

(9)S={0,1},S关于普通的加法和乘法运

算.(10)S={x|x=2n,n∈?+},S关于普通的加法和乘法运算.

(1)封闭

(2)不封闭 (3)加法与乘法都封闭 (4)乘法封闭,加法不封闭(5)不封闭 (6)加法与乘法都封闭 (7)封闭

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学最全课后答案(屈婉玲版)在线全文阅读。