326《离散数学》期末考试题(B)

一、填空题(每小题3分，共15分)

1.设A?{{a,b},a,b,?}，则A?? = ( )，A?{?} = ( )，P(A)中的元素个数|P(A)|?( ).

2.设集合A中有3个元素，则A上的二元关系有( )个，其中有( )个是A到A的函数.

3.谓词公式?x(P(x)?Q(x))??y(Q(y)??P(y))中量词?x的辖域为( ), 量词?y的辖域为( ).

4.设D24?{1,2,3,4,6,8,12,24}，对于其上的整除关系“|”，元素( )不存在补元. 5.当n( )时，n阶完全无向图Kn是平面图，当当n为( )时，Kn是欧拉图. 二．1. 若|A|?m,|B|?n，则|A?B|?( )，A到B的2元关系共有( )个，A上的2元关系共有( )个.

2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射.

3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)p?(p?q)?q； (2)p?(p?q)； (3)p?(p?q)； (4)?p?(p?q)?q； (5)(p?q)?q.

4. 设D24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).

5. 设G是(7, 15)简单平面图，则G一定是( )图，且其每个面恰由( )条边围成，G的面数为( ).

三．1.设A?{{a,b},{c}}，B?{{a},{b,c},{c}}，则A?B?()，

A?B?()，P(A)?().

2.集合A?{a,b,c}，其上可定义( )个封闭的1元运算，( )个封闭的2元运算，( )个封闭的3元运算.

3.命题公式(p?q)?1的对偶式为( ). 4.所有6的因数组成的集合为( ). 5.不同构的5阶根树有( )棵.

四、(10分)设f:A?B且g:B?C，若f?g是单射，证明f是单射，并举例说明g不一定是单射.

五、(15分)设A?{a,b,c,d},A上的关系

R?{(a,a),(a,b),(a,c),(c,a),(c,b),(c,c),(d,a),(d,b),(d,c)},

1.画出R的关系图GR. 2.判断R所具有的性质. 3.求出R的关系矩阵MR.

六、(10分)利用真值表求命题公式A?(p?(q?r))?(r?(q?p))的主析取范式

和主合取范式.

七、(10分) 边数m?30的简单平面图G，必存在节点v使得deg(v)?4. 八、(10分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.

《离散数学》期末考试题(B)参考答案

一、1. {{a, b}, a, b, ?}， {{a, b}, a, b}，16.

2.2, 27.

3.P(x)?Q(x), Q(y)??P(y). 4. 2, 4, 6, 12. 5.?4，奇数. 二、1.mn,2mn,2m.

2.g, g, g.

293.1,2,4.

4.8，不存在，不存在. 5.连通，3，10.

三、1. A?B?{{a},{a,b},{b,c},{c}}，A?B?{{c}}，P(A)?{?, {{a, b}}, {{c}}, {{a, b}, {c}}}.

2.33,39,327. 3.(p?q)?0.

4.{-1，-2，-3，-6，1，2，3，6}. 5.9.

四、证 对于任意x,y?A，若f(x)?f(y)，则g(f(x))?g(f(y))，(f?g)(x)?(f?g)(y). 由于f?g是单射，因此x?y，于是f是单射.

例

如

取

A?{a,b},B?(1,2,3},C?{?,?,?}，令f?{(a,1),(b,2)}g?{(1,?),(2,?),(3,?)}，这时f?g?{(a,?),(b,?)}是单射，而g不是单射.

五、解 1. R的关系图GR如下：

a c b d

2.(1)由于(b,b)?R，所以R不是自反的. (2)由于(a,a)?R，所以R不是反自反的.

(3)因为(d,b)?R，而(b,d)?R，因此R不是对称的. (4)因(a,c),(c,a)?R，于是R不是反对称的.

即

，

(5)经计算知R?R?{(a,a),(a,b),(a,c),(c,a),(c,b),(c,c),(d,a),(d,c)}?R，进而R是传递的.

综上所述，所给R是传递的.

?1??03.R的关系矩阵MR??1??1?101110110??0?. 0??0??六、解 命题公式A?(p?(q?r))?(r?(q?p))的真值表如下:

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?(p?(q?r))?(r?(q?p))的主析取范式为

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

?(?p??q?r)?(?p??q??r).A的主合取范式为A?(?p??q?r)?(p??q??r).

七、证 不妨设G的阶数n?3，否则结论是显然的. 根据推论1知，m?3n?6. 若G的任意节点v的度数均有deg(v)?5，由握手定理知

2m??deg(v)?5n.

v于是n?22m，进而m?3n?6?3?m?6. 因此m?30，与已知矛盾. 所以必存在55节点v使得deg(v)?4.

八、解 设满足要求的r位数的个数有ar种，r = 0，1，2，…，则排列计数生成函数

?x2x3??x2?E(x)???1?x?2!?3!????1?x?2!???1?x?

?????1?3x?4x2?因而a4?1931941516x?x?x?x, 61221219?4!?38. 12