离散数学（本）2015年10月份试题
一、单项选择题（每小题3分，本题共15分） 1．若集合A＝{1,2,3}，则下列表述正确的是 ( )． A．{1}?A B．{1}?A
C．{1, 2, 3}?A D．??A
2．设A={1, 2, 3｝，B ={1, 2, 3, 4}，A到B的关系R ={
4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．v + e - r=2 B．v + e - r=4 C．r + v - e =2 D．v + e – r = – 4
5．设个体域D是整数集合，则命题?x?y (x?y = y)的真值是（ ）． A．不确定 B．由y的取值确定 C．F D．T
二、填空题（每小题3分，本题共15分）
6．设集合A={a, b, c}，B={b, c}，C={c, d}，则A∩(B∪C)等于 ． 7．设A={2，3}，B={1，2}，C={3，4}，从A到B的函数f={<2, 2>, <3, 1>}，从B到C的函数g={<1，3>, <2，4>}，则Dom(g? f)等于 ．
8．若图G=
9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为4，则在G -S中的连通分支数不超过 ．
10．设个体域D＝{1,2, 3, 4}，A(x)为“x大于5”，则谓词公式(?x)A(x)的真值为 ．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“雪是白色的，但天是蓝色的．”翻译成命题公式． 12．将语句“如果下雨，则活动取消．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．集合的元素可以是集合．
14．(?x)(P(x)→Q(y)∧R(z))中的自由变元为x．
五．计算题（每小题12分，本题共36分）
15．设A={1，2，3}，R={ 1 试求R，S，R-1，s(S)． 16．图G= （1）画出G的图形； （2）写出G的邻接矩阵； （3）求出G权最小的生成树及其权值． 17．试画一棵带权为1, 1, 3, 4, 4的最优二叉树,并计算该最优二叉树的权． 六、证明题（本题共8分） 18．试证明：?P∨Q ? P→（? (?P∨?Q)） 2 ．离散数学（本）2015年10月份试题 参考解答 一、单项选择题（每小题3分，本题共15分） 1．B 2．A 3．D 4．C 5．D 二、填空题（每小题3分，本题共15分） 6．{b，c } 7．{2，3} （或A） 8．b 9．4 10．假（或F，或0） 三、逻辑公式翻译（每小题6分，本题共12分） 11．设P：雪是白色的，Q：天是蓝色的． 则命题公式为： P∧Q． 12．设P：下雨，Q：活动取消． 则命题公式为：P→Q． 四、判断说明题（每小题7分，本题共14分） 13．正确． 例：集合{{1}}中的元素{1}是集合． 14．错误． (?x)(P(x)→Q(y)∧R(z))中的约束变元为x，自由变元为y与z． 五．计算题（每小题12分，本题共36分） 15． R={<2, 3>, <3, 2>, <3, 3>} S={<1, 2>, <1, 3>, <2, 3>} R-1={<2, 3>, <3, 2>, <3, 3>} s(S)={ <1, 2>, <1, 3>, <2, 3>, <2, 1>, <3, 1>, <3, 2>} ．（1）G的图形表示为： a ? 4 ? d 2 3 7 6 b ? 5 ? c 3 （2分） （6分） （2分） （6分） （3分） （7分） （3分） （7分） （3分） （6分） （9分） （12分）3分） 16 （ ?0?1（2）邻接矩阵： ??1??1 1011a ? 11014 1?1?? （6分） 1??0?? d （3）粗线与结点表示的是最小生成树， 3 2 7 （10分） 6 b ? ? c 5 权值为9 （12分） 17． 13 ? 5 ? 2 ? ? 8 ? ? ? 4 3 4 ? 1 ? （10分） 1 权为1?3+1?3+3?2+4?2+4?2=28 （12分） 六、证明题（本题共8分） 18．证明： （1）?P∨Q P （1分） （2）P P（附加前提） （3分） （3）Q T（1）（2）I （5分） （4）P∧Q T（2）（3）I （6分） （5）? (?P∨?Q) T（4）E （7分） （6）P→? (?P∨?Q) CP规则 （8分） 说明：1、因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分． 另，可以用真值表验证．采用反证法可参照给分． 4