8、每个顶点的度数都是偶数的无向图一定是欧拉图。 9、五阶完全图K5既是欧拉图，也是哈密顿图。 10、设无向图T是树，则T中一定没有简单回路。
二、选择题（本大题共15小题，每小题2分，共30分） 1、下面语句是简单命题的为_____。
A、3不是偶数。 B、李平既聪明又用功。 C、李平学过英语或日语。 D、李平和张三是同学。
2、下列命题公式中是矛盾式的有_____。
A、(p??p)??p B、?(q?p)?p C、(?p?q)?(q??p) D、(p?q)?r
3、下列集合不是连接词极小全功能集的为_____。
A、{?,∧,∨} B、{?,→} C、{↓} D、{↑}
4、下列谓词公式不是命题公式P→Q的代换实例的是______
A、F(x)?G(y) B、?xF(x,y)??yG(x,y) C、?x(F(x)?G(x))
D、?xF(x)?G(x)
5、设个体域为整数集，下列公式中其值为1的是_____。
A、?x?y(x?y?0) B、?y?x(x?y?0) C、?x?y(x?y?0) D、??x?y(x?y?0)
6、下列哪个表达式错误_____。
A、 ?x(A(x)?B)??xA(x)?B
B、 ?x(A(x)?B)??xA(x)?B C、 ?x(B?A(x))?B??xA(x) D、
?x(A(x)?B)??xA(x)?B
21
得分 1.5CM
7、设集合A＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是____。
A、1?A B、{{4,5}}?A C、{1,2,3}?A D、??A 8、设集合
A?{2,4,6,8,10,12}，集合B?{3,6,9,12,15,18}，则B?A? ____。
{2,4,8,10} D、{6,9}
A、{1,2,3,4,5,6} B、{3,9,15,18} C、
9、设集合
A?{1,2,3,4}上的两个关系R?{?1,1?,?2,3?,?2,4?,?3,4?}，则R具有____。
A、对称性 B、传递性 C、自反性 D、反自反性 10、下述结论错误的是____。
A、存在这样的关系，它可以既满足对称性，又满足反对称性。 B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。 C、存在这样的关系，它可以既满足自反性，又满足反自反性。 D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。 11、集合A上的关系R为一个等价关系，当且仅当R具有_____。
A、自反性、对称性和传递性 B、自反性、反对称性和传递性 C、反自反性、对称性和传递性 D、反自反性、反对称性和传递性 12、以下整数序列，能成为一个简单图的顶点度数序列的是_____。
A、1，2，2，3，4，5 B、2，3，3，4，4，5 C、2，2，3，4，5，6 D、1，2，2，3，3，5
?1?13、设无向图G的关联矩阵为?0?1??0(A)4, 5 (B)4, 10
1100?1110??，则G的顶点数与边数分别为_____。 0012??0000?(D)5, 10
(C)5, 4
14、以下无向图中，不是二部图的是_____。
A、
B、
22
C、 D、
15、设G 是由 5 个顶点组成的无向完全图，则从 G 中删去_____条边可以得到 树。
A、4
B、5
C、6
D、10
三、填空题（本大题共10小题，每小题2分，共20分） 得分
1、设 p:天冷，q:小王穿羽绒服，将命题“除非天冷，小王才穿羽绒服”符号化 (1)___。 2、命题公式?p?(q?r)的对偶式是 (2)___。 3、p→q 的主合取范式是 (3)___。
4、设G(x)：x爱美，F(x)：x为人，在全总个体域中将命题“人都爱美”符号化 (4)___。
5、设F(x)：x是兔子， G(y)：y是乌龟，H(x,y)：x比y跑得快，在全总个体域中将命题“有的兔子比所有的乌龟跑得快”符号化 (5)___。 6、设集合A?{6,8,10,12}，集合B?{3,6,9,12}，则B?A? (6)___。 7、设集合
A?{a}，则P(P(A))? (7)___。
8、设集合A={1, 2, 3, 4}，R=={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}和S={<1,2>, <1,4>, <2,2>, <2,3>}是集合A上关系，则R○S= (8)___。
9、设无向图G有12条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (9)___个悬挂顶点。
10、写出波兰符号表达式 ÷＋×＋a×bcde×fg对应的算术表达式 (10)___。
四、计算题（本大题共2小题，每小题6分，共12分） 得分
1、求1到1000之间的整数（包含1和1000在内）既不能被 6 和7 整除，也不能被 8 整除的数有多少
23
CM
CM
个？
2、有向图D如图4-1所示，试求： (1) 写出有向图D邻接矩阵A； (2) 判断有向图D的连通性。
v1
v4
v2
v3
图4-1
五、应用题（本大题共2小题，每小题8分，共16分）
1、给出集合
A?{1,2,3,4,5,6,7,8,9,10,11,12}，分别求出：
(1)画出集合
A的整除偏序关系的哈斯图；
(2)集合
A的最大元，最小元，极大元，极小元；
(3)集合B?{2,4,6}的上界，下界，最小上界，最大下界。
2、设集合
X?{a,b,c,d,e}，X上的关系R如图5-1所示，试求：
a b c d e 图5-1
（1）写出关系R的关系矩阵MR； （2）画出关系R的自反闭包r(R)的关系图； （3）画出关系R的对称闭包s(R)的关系图；
24
得分
CM
（4）画出关系R的传递闭包t(R)的关系图。
CM
1.5CM
六、证明题（本大题共2小题，每小题6分，共12分） 得分 1、公安人员审查一件盗窃案，已知的事实如下：
① 甲或乙盗窃了录音机；
② 若甲盗窃了录音机，则作案时间不能发生在午夜前； ③ 若乙的证词正确，则午夜时屋里灯光未灭； ④ 若乙的证词不正确，则作案时间发生在午夜之前； ⑤ 午夜时屋里灯光灭了。
试问谁盗窃了录音机？将命题符号化，即将命题的前提符号化；然后在自然推理系统中构造命题的推理证明过程。
2、求下列谓词公式的前束范式，要求使用自由变项换名规则，请写出推理过程： ?x(F(x)??yG(x,y,z))??zH(x,y,z)
2009-2-B
一、判断题（本大题共10小题，每小题1分，共10分） 1、奇数阶完全图K2n?1(n?0)一定是欧拉图。 2、二阶以上连通没有回路的无向图是二部图。 3、“如果天气好，那么我去散步”是命题。 4、“我正在说谎话”是命题。 5、
p?q既是合取范式也是析取范式。
6、?xF(x)?G(x)是前束范式。
7、A，B，C都是集合，如果A∪B=A∪C，则B=C。 8、R1和R2是集合A上的具有自反性的关系，则R1?R2也一定具有自反性。
9、顶点数目相同，边数也相同的两个无向图一定同构。 10、每个顶点的度数都是偶数的无向图一定是欧拉图。
25