离散数学期末考试和答案-6.doc

厦门大学《离散数学》课程试卷软件学院2008年级主考教师：金贤安 试卷类型：（A卷） 厦门大学《离散数学》课程试卷 软件学院2008年级 主考教师：金贤安 试卷类型：（A卷） 选择题（共10题，每题3分，共30分）CDDAC DCADD 1、下列语句为命题的是（ ）。 A．勿踏草地；。 B．你去图书馆吗？； C．月球上有水； D．本命题为假。 下列推理中，（ ）是错误的。 如果x是有理数，则它为整数。1/2是有理数。所以1/2是整数。 若周末气温超过30度，小红就去游泳。小红周末没去游泳。所以周末气温没超过30度。 下午小明或者去看电影，或者去打篮球。下午小明没去打篮球。因此下午小明去看电影了。 若a能被4整除，则a能被2整除。a能被2整除。因此a能被4整除。 3．谓词公式中的x(?? ???)。A．只是约束变元B．只是自由变元C．既非约束变元又非自由变元D．既是约束变元又是自由变元 4. 下列关系中，（ ）不是等价关系。 非空集合的幂集的元素间包含关系； 集合之间的等势关系； 公式之间的等值关系； 图之间的同构关系。 5. 下面等值式中，（ ）是不正确的。 6．下列关于集合的势的叙述中，（ ）是错误的。 A. 实数集比自然数集优势；B. 任一无限集合都存在与自己等势的真子集； C. 集合之间的优势关系是偏序关系；D. 有理数集比整数集优势。 7．设A,B,C是集合，F是关系，，则下列式子中不正确的是（ ）。A． B. C. D. 8. 以下序列中，（ ）是简单可图的。 (4,4,3,3,2,2)； B. (3,3,3,1)； C. (5,4,3,2,2)； D. (6,6,3,2,2,2,1)。 9. 下列叙述中错误的是( )。 n(n≥2)阶竞赛图都具有哈密顿通路； 非平凡树不是欧拉图，也不是哈密顿图； n(n≥3且为奇数)阶的二部图一定不是哈密顿图； 欧拉回路包含图的所有顶点，哈密顿回路包含图的所有边。 10．下列关于图的连通性的叙述中正确的是( )。 有向图是连通的是指它是强连通的； 任一无向图的点连通度都不超过它的边连通度； 在一n阶圈Cn(n≥4)上任意去掉两个顶点得到得图都有2个连通分支； n阶无向完全图的点连通度为n； 二、填空题（共8题，每题3分，共24分） 令F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快。则命题“不存在比所有火车都快的汽车”符号化形式为_________________。 公式的主析取范式为______________。 集合A={a,b,c,d}上的等价关系共有___15___个。 自对偶图的顶点数n和边数m之间满足关系式为m =_______ m=2n-2________。 5．设T是有t片树叶的2叉正则树，则T应该有_______个顶点。 6．P({Φ,{Φ}}) = _{Φ,{Φ},{Φ,{Φ}},{{Φ}}}____。 7．在1到100之间（包含1和100）即不能被2，也不能被3，还不能被5整除的自然数有___26____个。 8．“p仅当q”，“只有q才p”，“除非q才p”这三个命题的符号化分别为___ __ , ____ 和 _____ 。（请按顺序填写） 三、应用、计算和证明题（共6题，46分） 1．(6分) 在命题逻辑的自然推理系统中构造下面推理的证明。 前提：┒(P∧┒Q)，┒Q∨R，┒R 结论：┒P 1 （1） 前提引入 （2） 前提引入 （3） （1）（2）析取三段论 （4） 前提引入 （5） 置换 (6) (3)(5)析取三段论 2．（8分）设集合A={a，b，c，d}，A上的关系R={a，a,a，b,b，a,c，d,b，c} 求：（1）画出R的关系图。(2分) （2）R的自反闭包、对称闭包和传递闭包的关系图。（2分，2分和2分） （1） 如图1 （2） 3．（8分）设A,R为一偏序集，其中A={1，2，…，12}，R是A上的整除关系。（1）画出A,R的哈斯图；（4分）（2）求A的所有极大元和极小元（2分）（3）求B={2,3,6}的最小上界和最大下界（2分）。 (1)如图2 （2）A的极大元有：7，8，9，10，11，12 A的极小元有：1 （3）B的上界是{6,12},最小上界是6 B的下界是1，最小下界是1 4.（8分） 判断左图是否为欧拉图，若是