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