离散数学期末考试及答案.docVIP

沈阳师范大学离散考试预测题 选择题谓词公式中的x(?? ???)。只是约束变元B只是自由变元C既非约束变元又非自由变元D既是约束变元又是自由变元 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； 二、题_________________。的主析取范式为______________。 集合A={a,b,c,d}上的等价关系共有___15___个。 自对偶图的顶点数n和边数m之间满足关系式为m =_______ m=2n-2________。应该有_____个顶点。 6．P({Φ,{Φ}}) = _{Φ,{Φ},{Φ,{Φ}},{{Φ}}}____。 7．在1到100之间（包含1和100）即不能被2，也不能被3，还不能被5整除的自然数有_______个。 8．“p仅当q只有q才除非q才p___ __ , ____ 和 _____ 。（请按顺序填写） 三、计算题在命题逻辑的自然推理系统中下面推理的证明前提：┒(P∧┒Q)，┒Q∨R，┒R结论：┒P  （2）R的自反闭包、对称闭包和传递闭包的关系图。（2分，2分和2分） 3．（8分）设A,R为一偏序集，其中A={1，2，…}，R是A上的整除关系。（1）画出A,R的哈斯图；（2）求A的所有极大元和极小元（2分）（）求B={}的最小上界和最大下界。设G是无向简单图δ(G)≥k≥2，试证明G中存在长度大于等于的。在一棵有3个2度顶点，2个4度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？画出非同构无向树。 二 1. 或者 2. 3. 15 4. m=2n-2 5. 2t-1 6. 7. 26 8. (该小题每空1分) 三 1 （1） 前提引入 （2） 前提引入 （3） （1）（2）析取三段论 （4） 前提引入 （5） 置换 (6) (3)(5)析取三段论 若未注明推理规则,或标注有错,扣1分. 2 （1） 如图1 （2） 该题要求画出三个闭包的关系图. 每个关系图2分,共6分. 边少画或多画一律判错. 3 (1)如图2 （2）A的极大元有：7，8，9，10，11，12 A的极小元有：1 （3）B的上界是{6,12},最小上界是6 B的下界是1，最小下界是1 哈斯图中若出现水平的边,扣1分. 4．（８分） （１）判断下图是否为欧拉图，若是，请给出一欧拉回路（用阿拉伯数字在边上标明顺序即可）；若不是，请说明原因；（4分） 答：因为该图是连通图且图中没有奇度顶点，所以该图是欧拉图(只要判断正确给2分)。欧拉回路标序如下图： 找的欧拉回路正确再2分 （2）判断下图是否为哈密顿图，若是，请给出一哈密顿回路（用阿拉伯数字在顶点上标明顺序即可）；若不是，请说明原因（4分） 答：该图不是哈密顿图(2分)。取Ｖ＝｛４，６，８｝，从图中删除Ｖ，得五个连通分支，如下图所示，所以该图不是哈密顿图。(2分) 另一证明:反证若有哈密顿圈,由于点5,7,9都是二度点,因此该哈密顿圈必包含边(4,5)(5,6)(6,7)(7,8)(8,9)(9,4),这6条边构成一个圈,矛盾. 　　　　　　　　　 ５．（8分）设G是无向简单图δ(G)≥k≥2，试证明G中存在长度大于等于的。…vt,则t≥k，事实上若存在“极大路径” Γs=v0v1…vs且sk，则v0只能