2013秋西南大学《离散数学》第2次作业

《离散数学》第2次作业

一、填空题

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

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

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

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

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

二、单选题

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

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

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

(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, *)中，( D )是群.

(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 ） (A)3 (B)4 (C)5 (D)2

?1三、设A和B是集合，使A?B?B成立的充要条件是什么，并给出理由.

证 A?B?B?A?B??. (?)显然.

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

四、设R和S是集合A上的对称关系，证明R?S对称的充要条件是R?S?S?R.

解 由于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)等值演算法和(2)真值表求命题公式

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

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

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

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

= (?r?(?q?p))?(?p?(q?r)) = ?(?r?(?q?p))?(?p?q?r) = (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是(n, m)无向图，若m?n，证明G中必存在圈.

证(反证) 假设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毕.