一、单项选择题（每题2分） 16 %
1. 设P： ，Q： ，则命题“只有 ，才有 ”符号化为 ( )
2 设F(x)：x是运动员，G(y)：y是世界，H(x,y)：x游玩过y，那么命题“某些运动员游玩过整个世界”符号化为 ( )
(A) (B)
(C) (D)
3. 命题公式 是 ( )
(A) 矛盾式 (B) 重言式 (C) 可满足式 (D) 蕴涵式
4. 若A-B=Ф，则下列结论不可能正确的是 ( )
(A) (B) (C) (D)
5. 设A={a,b,c}，A上的关系R={<a,a>,<c,a>,<b,b>,<b,c>}，则R是 ( )
（A）自反的 （B）传递的 （C）对称的 （D）反对称的
6. 设函数 且 ，则 是 ( )
(A) 单射，非满射 (B) 满射，非单射
(C) 双射 (D) 非单射，非满射
7. 设G是由5个顶点组成的完全图，则从图G中删去（ ）条边可以得到树。
(A) 4 (B) 5 (C) 6 (D) 8
8. 无向图 是连通图且没有奇度顶点是欧拉图的（ ）条件。
（A）充分必要条件 （B）充分条件（C）必要条件（D）都不是
二、填空题（每空2分） 18 %
9. 设 是汽车， 是火车，H(x,y)：x比y快，则命题“说凡是火车就比汽车快是不对的”符号化是 ，
其另一种等值形式为 。
10. 设个体域D={a,b,c},公式 的消去量词后等值式为
。
11. 一棵树有3个2度顶点，2个3度顶点，1个4度顶点，其余都是树叶，则其树叶数为 。
12. 命题“整数列（2,2,3,3,5,5）可图化”的真值为 。
13. 设D＝<V,E>为4阶有向图， ，邻接矩阵为A(D)= ，那么D中顶点 的入度为 。
14. 在1到400的整数中（包含1和400）满足各条件整除个数：可以被3整除,但不能被5整除的是 ；可以被5整除,但不能被3整除的是 。
15. 设集合A={a,b,c}，R为A上的关系，R={<a,b>,<b,a>,<c,a>}，则R的传递闭包 是 。
三、计算题 46 %
16. （5 分）设 是 子集，其中 ， ，用列元素法表示集合 。
17. （10分）用等值演算法求公式 的主析取范式，并求成真赋值。
18. （8分）画出偏序集 的哈斯图，并指出A的极大元、极小元、最大元和最小元。其中： 和
19. （13分）右图所示无向图G中，实线边所示子图为G的一棵生成树T，求G对应T的基本回路系统和基本割集系统。
20. （10分）已知有向图D如右图所示，求（1）邻接矩阵A (D)；（2）D中长度是2的回路数；（3）D中从v2到v3长度是3的通路数；（4）D是哪类连通图, 为什么?
四、证明题 20 %
21. （5分）证明对任意集合A,B,C，有 。
22. （7分）在自然推理系统P中构造推理证明：
前提： ，结论：
23. （8分）在自然推理系统P中构造推理证明：
前提： ，结论：
其它题：
（8分）右图是偏序集 的哈斯图，分别写出集合A和偏序关系 的集合表达式，并指出A的极大元、极小元、最大元和最小元。
（10分）设代数系统(Z, )，其中Z是整数集合，
二元运算为：x,yZ, x y= x+y+xy,+为普通加法
试问是否满足交换律、结合律，并求单位元、零元以及所有可逆元素的逆元。