西南大学《离散数学》网上作业题及答案

[0004]《离散数学》网上作业题答案

第1次作业

[论述题]第1次作业

一、填空题

1. 设|A| = 5, |B| = 2, 则可定义A到B的函数( )个，其中有( )单射，( )个满射.

2. 令G(x): x是金子，F(x): x是闪光的，则命题“金子都是闪光的，但闪光的未必是金子”符号化为( ).

3. 设X是非空集合，则X的幂集P(X)关于集合的?运算的单位元是( )，零元是( )，P(X)关于集合的?运算的单位元是( ).

4. 6阶非Abel群的2阶子群共有( )个，3阶子群共有( )个，4阶子群共有( )个.

5. 对于n阶完全无向图Kn, 当n为( )时是Euler图，当n ? ( )时是Hamilton图，当n ( )时是平面图.

二、单选题

1. 幂集P(P(P(?))) 为( )

(A){{?}, {?, {?}}}. (B){?, {?, {?}}, {?}}. (C){ ?, {?, {?}}, {{?}}, {?}} (D){ ?, {?, {?}}}. 2. 设R是集合A上的偏序关系，则R?R是( ).

(A)偏序关系 (B)等价关系 (C)相容关系 (D)以上答案都不对 3. 下列( )组命题公式是不等值的.

(A)?(A?B)与A??B. (B) ?(A?B)与(A??B)?(?A?B). (C)A?(B?C)与(A??B)?C. (D)A?(B?C)与?A?(B?C). 4.下列代数结构(G, *)中，( )是群.

(A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q, “*”是数的乘法.

(C)G = Z, “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法. 5.4阶完全无向图K4中含3条边的不同构的生成子图有 (A)3 (B)4 (C)5 (D)2

第 1 页 共 12 页

?1

三、设A和B是集合，使A?B?B成立的充要条件是什么，并给出理由. 四、设R和S是集合A上的对称关系，证明R?S对称的充要条件是R?S?S?R. 五、分别利用(1)等值演算法和(2)真值表求命题公式

A?(?r?(q?p))?(p?(q?r))

的主析取范式和主合取范式.

六、设G是(n, m)无向图，若m?n，证明G中必存在圈.

参考答案：第1次作业答案

一、1. 32，0，30.

2.?x(G(x)?F(x))??x(F(x)??G(x)). 3.?，X，X. 4. 3，1，0.

5.n为奇数，3，n?4.

二、1(C); 2(B); 3(D); 4(D); 5(A). 三、证 A?B?B?A?B??. (?)显然.

(?)因为A?B?A?B，根据A?B?B得(A?B)?B?B?B，于是B = ?，进而A = ?.

四、解 由于R和S是对称的，所以R?1?R,S?1?S.

?1(?)因为R?S?S?R，两边取逆得(R?S)?(S?R)?1，而

(S?R)?1?R?1?S?1?R?S.

所以(R?S)?1?R?S，因此R?S是对称关系.

?1(?)由于R?S对称，所以(R?S)?R?S. 而(R?S)?1?S?1?R?1?S?R，因而

R?S?S?R.

五、解 (1)等值演算法 A的主合取范式:

A?(?r?(q?p))?(p?(q?r))

= (?r?(?q?p))?(?p?(q?r)) = ?(?r?(?q?p))?(?p?q?r)

第 2 页 共 12 页

= (r?q??p)?(?p?q?r) = ?p?q?r(由吸收律得到). 于是，A的主析取范式为

A?(?r?(q?p))?(p?(q?r))

= (?p??q??r)?(?p??q?r)?(?p?q??r)?(p??q??r)?

(p??q?r)?(p?q??r)?(p?q?r).

(2)真值表法

命题公式A?(?r?(q?p))?(p?(q?r))的真值表如下:

p, q, r 1, 1, 1 1, 1, 0 1, 0, 1 1, 0, 0 0, 1, 1 0, 1, 0 0, 0, 1 0, 0, 0 由表可知，A?(?r?(q?p))?(p?(q?r))的主合取范式为

(?r?(q?p)) 1 1 1 1 0 1 1 1 p?(q?r) 1 1 1 0 1 1 1 1 A 1 1 1 0 1 1 1 1 A??p?q?r.

A的主析取范式为

A = (?p??q??r)?(?p??q?r)?(?p?q??r)?(p??q??r)?

(p??q?r)?(p?q??r)?(p?q?r).

七、证(反证)假设G中不含圈. 设G有k(k ? 1)个连通分支G1,G2,...,Gk，其节点个数分别为n1,n2,...,nk，其边数分别为m1,m2,...,mk. 这时，Gi为树，根据树的基本性质有

mi?ni?1i(1?i?k). 进而m??mi??(ni?1)?n?k?n，与已知m?n矛盾. 证

i?1i?1kk毕.

第2次作业

第 3 页 共 12 页

[论述题]第2次作业

一、填空题

1.设A = {2, {3}, 4, a}, B = {1, 3, 4, {a}}, 则{3}( )A，{a}( )B，{{a}}( )B.

2. 设A = {1, 2, 3, 4, 5}上的关系R = {(1, 2), (3, 4), (2, 2)}, S = {(4, 2), (2, 5), (3, 1), (1, 3)}, 则R?S?{ }, S?R?{ },

R?R?{ }.

3. 在同构意义下，3阶群有( )个，4阶群有( )个，5阶群有( )个. 4.任意有限布尔代数(B,?,?,,0,1)均与集合代数( )同构，其元素个数为( ), 其中( )是B的所有原子组成的集合.

5. 不同构的5阶无向树有( )棵，不同构的5阶根树有( )棵.

二、单选题

1. 在有理数集合Q上定义运算“*”如下：对于任意x, y ? Q，x?y = x + y – xy，则Q关于*的单位元是( ).

(A)x. (B)y. (C)1. (D)0.

2. 设A = {1, 2, 3}, 下图分别给出了A上的两个关系R和S，则R?S 是( )关系.

1 2 GR

3 1 2 GS

3

(A)自反. (B)对称. (C)传递. (D)等价.

3.令T(x): x是火车，B(x): x是汽车，F(x, y): x比y快，则“某些汽车比所有的火车慢”符号化为( ).

(A)?y?B(y)??x?T(x)?H(x,y)??. (B)?y?B(y)??x?T(x)?H(x,y)??. (C)?x?y?B(y)??T(x)?H(x,y)??.

第 4 页 共 12 页

(D)?y?B(y)??x?T(x)?H(x,y)??.

4. 整数集合Z关于数的加法“+”和数的乘法“?”构成的代数结构(Z, +, ?)是( ). (A)域 (B)域和整环 (C)整环 (D) 有零因子环

5.设G是简单图，G是G的补图，若G?G，则称G为自补图. 5阶不同构的自补图个数为( ).

(A)0. (B)1. (C)2. (D)3.

三、设f:A?B,g:B?C, 若f?g是单射，证明f是单射，并举例说明g不一定是单

射.

四、设A = {a, b, c, d}上的关系R = {(a, b), (b, d), (c, c), (a, c)}, 画出R的关系图，并求出R

的自反闭包r(R)、对称闭包s(R)和传递闭包t(R).

五、设G是(6，12) 的简单连通平面图，则G的面由多少条边围成，为什么？ 六、任意6个人中，一定有3个人彼此认识或有3个人彼此不认识.

参考答案：第2次作业答案

一、1. ?，?，?.

2.{(1,5), (3, 2), (2, 5)}, {(4, 2), (3, 2), (1, 4)}, {(1, 2), (2, 2)}. 3. 1, 2, 1.

4. (P(X),?,?,,?, X), 2n, n. 5. 3, 9.

二、1(D); 2(B); 3(A); 4(C); 5(C).

三、证 对于任意x1,x2?A，若f(x1)?f(x2)，则g(f(x1))?g(f(x2))，于是

(f?g)(x1)?(g?f)(x2). 由于f?g是单射，所以x1?x2，因此f是单射.

例如，A = {a, b}, B = {1, 2, 3}, C = {?, ?, ?}, f = {(a, 1), (b, 2)}, g = {(a, ?), (b, ?), (c, ?)}, 这时f?g?{(1,?),(2,?)}，它是A到C的单射，但g不是单射. 四、解 R的关系图如下：

第 5 页 共 12 页

a

b

d

c

r(R)?{(a,b),(b,d),(c,c),(a,c),(a,a),(b,b),(d,d)}, s(R)?{(a,b),(b,d),(c,c),(a,c),(b,a),(d,b),(c,a)}. t(R)?{(a,b),(b,d),(c,c),(a,c),(a,d)}.

五、证 根据Euler公式，G的面数为r = 12 – 6 +2 = 8. 由握手定理知，

?deg(v)?2?12?24，而简单连通平面图的每个面至少由3条边围成，所以G的每个面

v恰由3条边围成.

六、证 用6个节点分别表示这6个人，可得6阶完全无向图K6. 若两个人认识，则在相应的两个节点所在的边上涂上红色，若两个人不认识，则在相应的两个节点所在的边上涂上蓝色.

对于任意的K6的节点v，因为deg(v)?5，与v邻接的边有5条，当用红、蓝颜色去

v2v3，v1v3涂时，至少3条边涂的是同一种颜色，不妨设vv1,vv2,vv3是红色. 若3条边v1v2，

是红色，则存在红色K3，这意味着有3个人相互认识; 若v1v2，v2v3，v1v3都是蓝色，则存在蓝色K3，这意味着有3个人相互不认识. 结论成立.

第3次作业

[论述题]第3次作业 参考答案：第3次作业

一、1.{1, 3, {1, 2}, {3}}；{{2, 3}, {1}}；{1, 3, {1, 2}, {3}, {2, 3}, {1}}.

2.0，1，0.

3. ??x(Z(x)?O(x)). 4. pn, p为素数，n为正整数.

第 6 页 共 12 页

本文来源：https://www.bwwdw.com/article/lgc7.html