请按以下三个步骤筛选可能的选派方案： (1)符号化命题；
(2)求命题的主析取范式； (3)列出可行的选派方案。
3、请在自然推理系统P中构造下面的证明：
如果数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数，因此a是无理数。
(1) 将命题中的4个简单命题依次符号化为p,q,r,s； (2) 将命题符号化，即将命题的前提与结论符号化； (3) 在自然推理系统P中构造命题的推理证明。 2008-2-B
一、填空（每空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)___。
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上的运算?定义为：
16
*abcde则代数系统?aabcdebbdaadccabcbddcadceedbce S,??中单位元是 (12)___，b的右逆元是 (13)___，无右逆元的元素是 (14)___。
10、设运算?的运算表如下所示，则运算?满足交换律、幂等律、结合律中的 (15)___。
* a b c a c a b
二、选择题（每题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 a b c c b c a p(a,a)，p(b,a)为真，p(a,b)，p(b,b)为假，则在
?x(P(x)?Q(x))??xP(x)??xQ(x)
17
B、 C、 D、
?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具有____。
6、设集合
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中删去_____条边后可以使之成为树。
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阶非同构的无向树有_____棵。
18
A、5 B、6 C、7 D、8 14、实数集R关于下列二元运算?满足结合律和交换律的是_____。
A、a?b?|a?b| a?b?a?2b B、a?b?b C、a?b?a?b?2ab D、15、在下列选项中，不是群的是_____。
A、(Q,?)，Q为有理数，+为加法运算 B、(R?,?)，R?为非零实数集，?为乘法运算
C、(R,?)，R为实数集，+为加法运算 D、(Q,?)，Q为有理数，*为乘法运算
三、计算题（5分+6分+8分，共19分） 1、求下图中的最小生成树，并计算它的权。
1 V1 3 V2 2 V6 4 5 V3 7 8 V4 9
6 V5 2、设有7个字母在通信中出现的频率(%)如下：
a: 35% b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5% (1)以频率(或乘100)为权，求最优2元树． (2)利用所求最优2元树找出每个字母的前缀码．
(3)求传输10000个按上述比例出现的字母需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字?节约多少个二进制位？
3、设集合
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)
19
（3）求关系R的对称闭包s(R)的关系矩阵Ms(R), (s(R)?（4）求关系R的传递闭包t(R)的关系矩阵Mt(R), (t(R)?
四、证明题（5分+5分+5分，共15分） 1
、
设
R?R?1)
R?R2?R3?R4)
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。
3、设G为群，a?G，令H?{ak|k?Z}，证明：H是G的子群。
五、应用题（共6分）
1. 如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就能按时完成作业。
(1) 将命题中的4个简单命题依次符号化为p,q,r,s； (2) 将命题符号化，即将命题的前提和结论符号化； (3) 在自然推理系统P中构造命题的推理证明。 2009-2-A
一、判断题（本大题共10小题，每小题1分，共10分） 1、“如果天气好，那么我去散步”是命题。 2、“我正在说谎话”是命题。 3、
p?q既是合取范式也是析取范式。
4、?xF(x)?G(x)是前束范式。
5、A，B，C都是集合，如果A∪B=A∪C，则B=C。 6、R1和R2是集合A上的具有自反性的关系，则R1?R2也一定具有自反性。
7、顶点数目相同，边数也相同的两个无向图一定同构。
20