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

[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 页