326《离散数学》期末考试题(B )
一、填空题(每小题3分，共15分)
1.设,,},,{{b a b a A }，则A
= ( )，A {} = ( )，)(A P 中的元素个数|)(|A P (
). 2.设集合A 中有3个元素，则
A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式
))()(())()((y P y Q y x Q x P x 中量词x 的辖域为( ), 量词y 的辖域为(
). 4.设}24,12,8,6,4,3,2,1{24D ，对于其上的整除关系“
|”，元素( )不存在补元.5.当n (
)时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ||,||
，则||B A ( )，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)
q q p p )(；(2))(q p p
；(3))(q p p
；(4)q q p p
)(；(5)
q q p )(. 4. 设D 24是24的所有正因数组成的集合，
“|”是其上的整除关系，则3的补元( )，4的补元( )，
6的补元( ). 5. 设G 是(7, 15)简单平面图，则
G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为(
). 三．1.设}}{},,{{c b a A ，}}{},,{},{{c c b a B
，则)(B A ，)(B A ，)(
)(A P .
2.集合},,{c b a A ，其上可定义( )个封闭的1元运算，( )个封闭的2元运算，( )个封闭的3元运算.
3.命题公式1)(q p 的对偶式为(
). 4.所有6的因数组成的集合为(
).5.不同构的5阶根树有(
)棵. 四、(10分)设B A
f :且C B
g :，若g f 是单射，证明f 是单射，并举例说明g 不一定是单射.五、(15分)设},,,{d c b a A ,A 上的关系
)},(),,(),,(),,(),,(),,(),,(),,(),,{(c d b d a d c c b c a c c a b a a a R ,
1.画出
R 的关系图R G . 2.判断
R 所具有的性质. 3.求出R 的关系矩阵R M .
六、(10分)利用真值表求命题公式))(())((p q r r q p A 的主析取范式和主合取范式
.七、(10分)边数30m 的简单平面图G ，必存在节点v 使得4)deg(v .
八、(10分)有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数
.《离散数学》期末考试题(B)参考答案
一、1. {{a, b}, a, b, }，{{a, b}, a, b}，16.
2.
92, 27. 3.)()(x Q x P , )()(y P y Q .
4. 2, 4, 6, 12.
5.4，奇数
. 二、1.22,2,m mn mn .
2.g, g, g.
3.1,2,
4.
4.8，不存在，不存在
. 5.连通，3，10.
三、1. }}{},,{},,{},{{c c b b a a B A ，}}{{c B A ，{)(A P , {{a, b}}, {{c}}, {{a, b}, {c}}}.
2.27933,3,3
. 3.0)(q p
. 4.{-1，-2，-3，-6，1，2，3，6}.
5.9.
四、证对于任意A y x,，若)()(y f x f ，则))(())((y f g x f g ，即))(())((y g f x g f . 由于g f 是单射，因此y x ，于是f 是单射.
例如取},,{},3,2,1(},,{C B b a A ，令)}2,(),1,{(b a f ，)},
3(),,2(),,1{(g ，这
时)},(),,{(b a g f 是单射，而g 不是单射.
五、解 1. R 的关系图R G 如下：
2.(1)由于R b b ),(，所以R 不是自反的.
(2)由于R a a ),(，所以R 不是反自反的.
(3)因为R b d ),(，而R d b ),(，因此R 不是对称的.
(4)因R a c c a ),(),,(，于是R 不是反对称的.
(5)经计算知R c d a d c c b c a c c a b a a a R R )},(),,(),,(),,(),,(),,(),,(),,{(，进而R 是传递的.
综上所述，所给R 是传递的.
3.R 的关系矩阵0
11101110
0000
111R M .
六、解命题公式))(())((p q r r q p A 的真值表如下:
p, q, r A
1, 1, 1 1 1 1 a b c
d
