离散数学1套.doc

院： 专业： 班级： 姓名： 学号： -装-订-线- 20112012学年第二学期离散数学期末考试试卷 2009级软件工程专业离散数学期末考试试卷题号一二三四五总分核分人得分-得分阅卷人一、单项选择题（每小题1分，共15分）1设P:我将去镇上,Q:我有时间。命题“我将去镇上,仅当我有时间时”符号化为 （ ） APQ B QP C QP D QP2命题公式(P(PQ)Q 是 （ ）A 矛盾式 B 蕴含式 C重言式 D 等值式3下列命题联结词集合中,哪个是最小联结词组 （ ） A B C D4谓词公式中变元是; （ ）A自由变元 B约束变元 C既不是自由变元也不是约束变元 D既是自由变元也是约束变元5设:x是人, :x犯错误,命题“没有不犯错误的人”符号化为 （ ）A. B C D6对任意集合A、B、C，下述论断正确的是 （ ） A若AB，BC，则 AC B若AB，BC，则 AC C若AB，BC，则 AC D若AB，BC，则 AC7若f,g是满射，则复合函数必是 （ ）A映射 B单射 C满射 D双射8设上的关系如下，有传递关系的有 （ ）A BC D9R是A上的自反关系，则 （ ） A B C D10.设R是非空集A上的二元关系，则R的对称闭包s(R)是 （ ）ARIA BR CRIA DR11.无向树T有7片树叶, 3个3度顶点,其余的都是4度顶点，则T的4度顶点的个数是（ ）A1 B2 C3 D412. 中含3条边的不同构生成子图有 （ ）A1个 B2个 C3个 D4个13设为无向图，,若连通，则 （ ）A B C D14欧拉回路是 （ ）A路径 B简单回路 C既是基本回路也是简单回路 D既非基本回路也非简单回路155阶有向完全图的边数是 （ ）A5 B10 C15 D20得分阅卷人二、填空题（每空1分，共10分）1命题公式的成真赋值为 。2设T是各边带权均为1的n阶带权图的最小生成树，则W（T）= ,。3谓词公式的前束范式为 。4A=,R是A上的整除关系，那么A的极大元和极小元分别是（极大元） 、（极小元） 。5设R是集合上的模7同余关系，则. 。6设G=n,m是简单图,v是G中度数为k的结点，e是G中的一条边，则Gv中有 个结点， 条边。73个结点可构成 个不同构的简单无向图。8设N是自然数集合，和是N到N的函数，其中； 那么复合函数 ， 。得分阅卷人三、判断题（对的画，错的画，每题1分，共10分）1推理定律正确。 （ ）2在谓词演算中是的有效结论，其理论根据是全称量词引入规则。 （ ）3. 无向图G有生成树的充分必要条件是G是连通图。 （ ）4若ABAC 则BC （ ）5. 设，R是A上的二元关系，那么是传递的。 （ ）6. T是n阶非平凡的无向树，则T中至少有两片树叶。 （ ）7设A，B，C，D为任意集合，则ABAC B C。 （ ）8非负整数列（3，3，3，1）是可图化的。 （ ）9设为无向图，若对任意的（的真子集）,且，均有 ，则G为哈密顿图。 （ ）10设为n阶无向简单向哈密顿图，对任意的，均有。（ ） 得分阅卷人四、证明题（每题8分，共32分）1写出下面推理的形式证明：如果今天是星期一，则要进行英语或离散数学考试。如果今天英语老师有会，则不考英语。今天是星期一，英语老师有会。所以今天进行离散数学考试。 2设A，B，C为任意三个集合，证明A（BC）（AB）（AC） 得分阅卷人3设R为X上二元关系，证明：R是对称的当且仅当RR-1 4设G为n阶无向简单图，n5，证明G或必含圈。 五、计算题（第1、2、3题各8分，第4题9分，共计33分）1在1000名大学毕业生的调查中，有804人掌握了英语，205人掌握了日语，190人掌握了俄语，125人既掌握了英语又掌握了日语，57人既掌握了日语又掌握了俄语，85人既掌握了英语又掌握了俄语，求这1000名大学生中，英语、日语、俄语全掌握的有多少人。2（1）设集合A=,是集合A的幂集，画出（，）的Hasse图。 （2）设X=，R=，写出R的关系矩阵，画出关系图。 3求命题公式(pq)（pq）的主合取范式和主析取范式。 4有向图D如图所示: （1） D中V1到V4长度为1，2，3，4