7、设集合为
A、RB、RA?{1,2,3}，下列关系R中不是等价关系的是_____。
?{?1,1?,?2,2?,?3,3?}
?{?1,1?,?2,2?,?3,3?,?3,2?,?2,3?}
C、R?{?1,1?,?2,2?,?1,2?,?2,1?,?1,3?,?3,3?}
D、R?{?1,1?,?2,2?,?1,2?,?2,1?,?1,3?,?3,1?,?3,3?,?3,2?,?2,3?} 8、设集合_____。
A、自反性 B、传递性 C、对称性 D、反对称性 9、设T是由n个顶点的完全二元树，则T的叶子数为_____。
A、n?1 B、2n?1 C、(n?1)/2 D、(n?2)/3
10、设无向图G有12条边，已知G中3度顶点有6个，其余顶点度数均小于3，则G中顶点数最多有_____。
A、6 B、8 C、9 D、12 11、设I是如下一个解释，D?{a,b}，其中解释I下取真值的公式是______。
A、?x?yp(x,y) B、?x?yp(x,y) C、?xp(x,x) D、?x?yp(x,y) 12、设R和S是非空集合A上的等价关系，下列各式是A上等价关系的是_____。
A、
A?{1,2,3}，A上的关系R?{?1,1?,?2,2?,?2,3?,?3,3?,?3,2?}，则R不具备
p(a,a)，p(b,a)为真，p(a,b)，p(b,b)为假，则在
A?A?R B、R?S C、R?S D、R?S的对称闭包
13、下面编码____不是前缀码。
A、11，00，10，01 B、01，11，011，1001 C、101，11，001，011，010
D、010，11，011，1011，1001，10101 14、由0、1、2、3这四个数字能构成_____个3位数
A、64 B、48 C、24 D、18 15、在下列选项中，不是群的是_____。
A、(Q,?)，Q为有理数，+为加法运算 B、(R?,?)，R?为非零实数集，?为乘法运算
C、全体实对称矩阵集合，对于矩阵的加法运算 D、(Q,?)，Q为有理数，*为乘法运算
6
三、计算题（5分+5分+8分，共18分）
1、已知：有向图
D??V,E?，
V?{1,2,3,4,5}，E={
?1,2?,?1,4?,?2,3?，
?3,4?,?3,5?,?5,1?}，求有向图D的邻接矩阵和可达矩阵。
2、求叶的权值分别为2，4，6，8，10，12，14的最优二元树及其权值。
3、试画出集合 (1)集合
A?{1,2,3,4,5,6}，在偏序关系整除下的哈斯图，并分别求出：
A的最大元，最小元，极大元，极小元；
?{2,3,6}的上界，下界，最小上界，最小下界。
(2)集合B四、证明题（5分+5分+6分，共16分） 1、证明：利用命题演绎法证明
((P?(Q?R))?(?S?P)?Q)?(S?R)
2、设R和S是A上的二元关系，证明：(R?S)
3、证明：设??1?R?1?S?1
R,??是一个代数系统，*是R上的二元运算，?a,b?R,a?b?a?b?a?b，则0
（R为实数集合）。 R,??是含幺半群。
是单位元，且?
五、应用题（共6分）
p,q,r的意义如下：p：张群是大学生，q：张群心情愉快，r：张群唱歌
试用日常语言说明下列复合命题：
（1）（2）
p?(q?r) p??(q?r)
（3）?p?(q2008a v1.1
?r)
一、填空（每空2分，共30分）
1、设P：1+1=2，Q：2是偶数，将命题“1+1=2，仅当2是偶数”符号化 (1)___，其真值为 (2)___。 2、在公式?x(F(x,y,z)?G(x,y))中，约束出现的变元为 (3)___。
7
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?}，
则其中满足对称性的关系是 (4)___；满足自反性的关系是 (5)___。 4、非空集合A上的自反、 (6)___和传递的关系称为A上的偏序关系。 5、后缀表达式 3 5 2 － * 7 + 4 / 的值是 (7)___。
6、设无向图G有11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (8)___个悬挂顶点。
7、设G为连通的平面图，有5个面，总度数为14，则G有 (9)___条边，有 (10)___个顶点。 8、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树叶，则T有 (11)___个树叶。
9、设集合S?{a,b,c,d,e}，S上的运算?定义为：
*abcde则代数系统?aabcdebbdaadccabcbddcadceedbce S,??中单位元是 (12)___，b的右逆元是 (13)___，无右逆元的元素是 (14)___。
10、设运算?的运算表如下所示，则运算?满足交换律、幂等律、结合律中的 (15)___。
* a b c a c a b
二、选择题（每题2分，共30分） 1、下面语句是真命题的为_____。
A、我正在说谎。
8
b a b c c b c 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、
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)
6、设集合
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、以上都不对 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中删去_____条边后可以使之成为树。
9
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?2ab15、在下列选项中，不是群的是_____。
A、(Q,?)，Q为有理数，+为加法运算 B、(R?,?)，R?为非零实数集，?为乘法运算
C、(R,?)，R为实数集，+为加法运算 D、(Q,?)，Q为有理数，*为乘法运算
三、计算题（5分+6分+8分，共19分） 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元树．
10
D、a?b?|a?b|