2012年4月离散数学试题2.doc

孝感学院新技术学院 2011 — 2012 学年度第 二 学期期中考核试卷 考核课程： 离散数学 考核类型： 考试 考核形式： 闭卷 学生所在院系： 信息工程系 年 级： 试 卷： A 题号 一 二 三 四 五 总分 得分 一、单项选择题（本大题共10小题，每小题2分，共20分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子是命题的是（　　　） A．我们要努力学习！ B．今天是星期天吗？ C．雪是黑色的 D．太好了！ 2．下列式子不是析取的性质的是（　　　） A．P∨P(P B．P∧┐P ( 0 C．P∨(P∧Q)P( P D．P∨(Q∧R) ((P∨Q) ∧(P∨R) 3．下列式子是命题公式的是（　　　） A．┐P∨Q∨ B．(┐P∨Q∨R) ∧（┐P∧┐Q） C．（┐P∧Q）→ D．P∨（Q∨R∨ 4．张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎，则说真话的是（ ） A．张三说真话 B．李四说真话 C．王五说真话 D．张三和王五都说真话 5．下列各式不是前束范式的是（ ） A．(x(y(z（P（x，y，z）→Q（x，y）） B．(x(y(z（P（x，y，z）→(x(y Q（x，y） C．(x(y（P（x，y，z）→Q（x，y）） D．(x(y（P（x，y）∧Q（x，y）） 命题教师 院系负责人签字 【第1页 共6页】 6．已知指定一个解释I如下： （1）个体域为自然数集合N； （2）指定常项a=0； （3）指定谓词F（x，y）为x=y； （4）N上的指定函数f（x，y）=x+y，g（x，y）=x*y。 在以上指定的解释I下，下列公式的真值为假的是（　　　） A．(x F（g（x，a），x） B．(x(y（F(f（x，a），y) →F(f（y，a），x) C．F(f（x，y），f（y，z）) D．F(g（x，y），f（y，x）) 7．下列有关图的概念不正确的是（　　　） A．规定顶点集和边集均为空的图为空图 B．规定含有平行边的图称为多重图 C．规定有自环和平行边的图称为简单图 D．规定顶点集和边集均不为有限集的图称为有限图 8．下列有关的命题等价式错位的是（　　　） A．幂等率：A∨A(A A∧A(A B．吸收率：A∧（A∨B）(B A∨（A∧B）(B C．互补率：A∨┐A(1 A∧┐A(0 D．假言易位：A→B(┐B→┐A 9．有题9图得出的如下结论错误的是（　　　） d g A．（g，h，c，d，a，b，c，e，f，g）是回路，但不是环 a c f B．（h，c，d，a，b，c，e，f）是通路，也是基本通路 C．（a，b，c，d，a）是环 b e D．（h，g，f）是h与f之间的短程 题9图 10．下列图是欧拉图的是（　　　） 二、填空题（本大题共5小题，每空2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．请写出表示德摩根律的两个命题公式等价定理___________， 17．请将下列命题符号化： P；李明是计算机系的学生。Q：李明是男生。R：李明是女生； ______________________ 18．置换规则：假设A为含公式X的命题公式，Y也为公式且___________如果用Y置换A中的X，得到新的公式为B，则___________。 【第2页 共5页】 19．由有限个最小项组成的析取范式称为______________，由有限个最大项组成的合取范式称为_____________。 20．（1）设G=(V，E)，若G的任意两个顶点都是可达的，则称G是________，否则，则称G是____________。 （2）（握手定理）设图G=(V，E)，则___________________。 三、计算题（本大题共4小题，每小题7分，共28分） 21．给定论域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在该赋值下，求式子(x(S( f(x))