离散数学期末考试含答案.doc

离散数学综合练习题一 一、单项选择题（每题2分 ）16 % 设P：王强是南方人，Q：他怕热．命题“王强不怕热是因为他是南方人”符号化为 ( ) 2 设F(x)：x是熊猫，G(y)：y是竹子，H(x,y)：x喜欢y. 那么命题“有些熊猫喜欢各种的竹子”符号化为 ( ) (A) (B) (C) (D) 3. 命题公式是 ( ) (A) 重言式 (B) 矛盾式 (C) 可满足式 (D) 以上3种都不是 4. 设集合A＝{a,b,{c,d,e}}则下列各式为真的是 ( ) (A) ?∈A (B) c∈A (C) {c,d,e}? A (D) {a,b}?A 5. 设函数且，则是 ( ) (A) 单射，非满射 (B) 满射,非单射 (C) 双射 (D) 非单射，非满射 6. 设E为全集, A, B为非空集，且B?A，则空集为（ ） (A) (B) (C) (D) 7. 设A={0,1,2,3}，A上的关系R={0,1,0,2,1,1,1,2,2,1,2,2,3,3}，则R是 ( ) （A）自反的 （B）对称的 （C）反对称的 （D）可传递的 8. 无向图K3,3是（ ） （A）哈密顿图 （B）欧拉图 （C）完全图 （D）平面图 二、填空题（每空2分）18 % 1. 设是火车，是汽车，H(x,y)：x比y快，则命题“说所有火车比有的汽车快是不对的”符号化是 ， 其另一种等值形式为 。 2. 设个体域D={a,b},公式 的消去量词后为 。 3. 设有向图D＝V,E的邻接矩阵为A(D)=，那么|E|= 。 4. n阶m条边的无向连通图G，要确定G的一棵生成树T必须删去G中的边数是 。 5. 设集合A={a,b,c}，R为A上的关系，R={a,b,b,a,c,c}，则R的传递闭包是 。 6.设G是n阶无向简单哈密顿图,则对于任意不相邻的顶点,均有, 此结论正确吗? 答 ?。 7. 设，则“是从 到的函数”的真值为 。 8. 命题“整数列（2,2,3,3,4,4）可简单图化”的真值为 。 三、化简计算题 56 % 1. （12分）用等值演算法求公式的主合取范式，并求成假赋值。 2. （6分）一棵无向树T有8片树叶，2个3度支点，其余的分支点都是小于4度顶点，问T至少有几个顶点。 3. （8分）对于集合A＝{2,3,4,5,6,9,10,12,18,20,60}与整除关系R，画出偏序集A,R的哈斯图，并求A的极大元、极小元、最大元、最小元。 4. （10分）已知有向图D如右图所示，求（1）邻接矩阵A (D)；（2）D是哪类连通图, 为什么?（2）D中从v3到v2长度是2的通路数；（3）D中从v2到v2长度是3的回路数。 5. （10分）右图所示无向图G中，实线边所示子图为G的一棵生成树T，求G对应T的基本割集系统。 6. （10分）求在1和1000之间(包含1和1000在内)不能被5或6整除, 也不能被8整除的数的个数。 (必须写出解题过程) 四、证明题 10 % （10分）在自然推理系统中构造下面推理的证明: 若张超和李志都是计算机系学生，则王红是中文系学生；若王红是中文系学生，则她爱看小说；可是王红不爱看小说；张超是计算机系学生；所以李志不是计算机系的学生。 离散数学综合练习题一（答案） 一、 单项选择题（每题2分，共16分） （1）B （2）C （3）C （4）D （5）A （6）B （7）D （8）A 二、 填空题 （每空2分，共18分） 1．， 2． 3． 7 4．m-n+1 5． 6．不正确 7． 0 （或假） 8． 1