《离散数学》期末试题及答案-离散数学期末

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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4