二、选择题（本大题共15小题，每小题2分，共30分）
得分 1、下面语句是真命题的为_____。
A、我正在说谎。
B、如果1＋1＝2，则太阳从西边升起来。 C、如果1＋1＝3，则太阳从西边升起来。 D、吃饭了吗？
2、命题公式P→(Q→P)为_____。
A、重言式 B、可满足式 C、矛盾式 D、等值式 3、下面联结词不具有交换律的是_____。
A、∧ B、∨ C、→ D、?
4、设I是如下一个解释，D?{a,b}，其中解释I下取真值的公式是______
A、?x?yp(x,y) B、?x?yp(x,y) C、?xp(x,x) D、?x?yp(x,y) 5、下列哪个表达式错误_____。。
A、 B、 C、 D、
6、设集合
p(a,a)，p(b,a)为真，p(a,b)，p(b,b)为假，则在
?x(P(x)?Q(x))??xP(x)??xQ(x)
?xP(x)??xQ(x)??x(P(x)?Q(x)) ?x(P(x)?Q(x))??xP(x)??xQ(x) ?x(P(x)?Q(x))??xP(x)??xQ(x)
A?{1,2,3,4}上的两个关系R?{?1,1?,?2,3?,?2,4?,?3,4?}，则R具有____。
A、自反性 B、传递性 C、对称性 D、反自反性 7、下述结论错误的是____。
A、存在这样的关系，它可以既满足对称性，又满足反对称性。 B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。 C、存在这样的关系，它可以既满足自反性，又满足反自反性。 D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。 8、设偏序集（?A,??）关系R的哈斯图如右所示，若A的子集B?{2,3,4,5}，则元素6为B的_____。
A、下界 B、上界 C、最小上界 D、以上都不对
26
9、以下整数序列，能成为一个简单图的顶点度数序列的是_____。
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
10、设图G是有6个顶点的连通图，总度数为16，则从G中删去_____条边后可以使之成为树。
A、10 B、5 C、3 D、2 11、在下列关于图论的命题中，正确的是_____。
A、哈密顿图一定是欧拉图
B、无向完全图Kn(n?3)都是欧拉图
C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出 D、哈密顿图是平面图 12、下面编码_____不是前缀码。
A、11，00，10，01 B、01，11，011，1001 C、101，11，001，011，010
D、010，11，011，1011，1001，10101 13、6阶非同构的无向树有_____棵。
A、5 B、6 C、7 D、8 14、实数集R关于下列二元运算?满足结合律和交换律的是_____。
A、a?b?a?2b B、a?b?b C、a?b?a?b?2ab D、a?b?|a?b|15、在下列选项中，不是群的是_____。
A、(Q,?)，Q为有理数，+为加法运算 B、(R?,?)，R?为非零实数集，?为乘法运算
C、(R,?)，R为实数集，+为加法运算 D、(Q,?)，Q为有理数，*为乘法运算
三、填空题（本大题共10小题，每小题2分，共20分）
1、设P：1+1=2，Q：2是偶数，将命题“1+1=2，仅当2是偶数”符号化 (1)___。
27
CM
2、在公式?x(F(x,y,z)?G(x,y))中，约束出现的变元为 (2)___。
3、给定集合
A?{1,2,3}上的3个关系如下：
R1?{?2,2?,?2,3?,?2,1?,?1,1?}，R2?{?2,2?,?2,3?,?2,1?,?3,3?,?1,1?}，
R3?{?2,3?,?2,2?,?3,2?,?1,1?}，
则其中满足对称性的关系是 (3)___；
4、非空集合A上的自反、 (4)___和传递的关系称为A上的偏序关系。 5、后缀表达式 3 5 2 － * 7 + 4 / 的值是 (5)___。
6、设无向图G有11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (6)___个悬挂顶点。
7、设G为连通的平面图，有5个面，总度数为14，则G有 (7)___个顶点。
8、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树叶，则T有 (8)___个树叶。9、设集合S?{a,b,c,d,e}，S上的运算?定义为：
*abcdeaabcdebbdacdccababddacdceedbce 则代数系统?S,??中单位元是 (9)___。
10、设运算?的运算表如下所示，则运算?满足交换律、幂等律、结合律中的 (10)___。
* a b c a c a b b a b c c b c a
四、计算题（本大题共2小题，每小题6分，共12分）
28
CM
1、求下图中的最小生成树，并计算它的权。
V2 5 V3 1 8 V1 2 4 7 V4 3 V6 6 V5 9
2、设有7个字母在通信中出现的频率(%)如下：
a: 35% b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5% (1)以频率(或乘100)为权，求最优2元树． (2)利用所求最优2元树找出每个字母的前缀码．
(3)求传输10000个按上述比例出现的字母需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字?节约多少个二进制位？
五、应用题（本大题共2小题，每小题8分，共16分）
1、设集合
X?{a,b,c,d}，X上的关系R如图所示，试求：
a b c d
（1）写出关系R的关系矩阵MR
（2）求关系R的自反闭包r(R)的关系矩阵Mr(R), (r(R)?R?R0?R?IX) （3）求关系R的对称闭包s(R)的关系矩阵Ms(R), (s(R)?R?R?1)
（4）求关系R的传递闭包t(R)的关系矩阵Mt(R), (t(R)?R?R2?R3?R4)
2、如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就能按时完成作业。
(1) 将命题中的4个简单命题依次符号化为p,q,r,s； (2) 将命题符号化，即将命题的前提和结论符号化； (3) 在自然推理系统P中构造命题的推理证明。
29
CM
CM
六、证明题（本大题共2小题，每小题6分，共12分）
得分 1、设
A?Z??Z?,在A上定义二元关系R如下：
??x,y?,?u,v??R??xv?yu,其中x,y,u,v?Z?，证明：R是A上的等价关系。
2、设n阶m条边的无向图G中，m=n+1，证明G中存在顶点v：d(v)≥3。 2010
一、选择题（本大题共 15 小题，每小题 2 分，共 30 分）
1、给定语句如下，则______是复合命题。
A、15是素数 B、2x+2>3
C、小王和小李是好朋友。 D、小王和小李成绩都好。
2、给定下列语句中，是真命题的是______。
A、这个男孩真勇敢呀。 B、明年5月1日是晴天。 C、如果2+2=6，则3是奇数。 D、2x+2>3
3、下列哪个表达式错误_____。
A、 B、 C、 D、
?x(P(x)?Q(x))??xP(x)??xQ(x)
?xP(x)??xQ(x)??x(P(x)?Q(x)) ?x(P(x)?Q(x))??xP(x)??xQ(x) ?x(P(x)?Q(x))??xP(x)??xQ(x)
4、斯科特先生、他的妹妹、儿子、女儿都是网球选手，关于这四个人，有如的情况：最佳选手的孪生同胞与最差选手性别不同；最佳选手与最差选手年龄相同。则_______是最佳选手。 A、斯科特 B、斯科特妹妹 C、斯科特儿子 D、斯科特女儿
30