四、计算10%
1、 设命题A1，A2的真值为1，A3，A4真值为0，求命题
(A1?(A2?(A3??A1)))?(A2??A4)的真值。（5分）
2、 利用主析取范式，求公式?(P?Q)?Q?R的类型。（5分）
五、谓词逻辑推理 15%
符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。
六、证明：（10%）
设论域D={a , b , c}，求证：?xA(x)??xB(x)??x(A(x)?B(x))。 答案：
十、 填空 10%（每小题2分）
1、P真值为1，Q的真值为0；2、?x(F(x)?L(x,0)??y(F(y)?L(y,x))；3、
?x(?P(x)?Q(x))；4、约束变元；5、?xA(x)?A(y)，y为D的某些元素。
十一、 选择 25%（每小题2.5分） 题目 答案
十二、 逻辑判断 30% 1、（1）等值演算法
1 A,C 2 A,D 3 C,D 4 A,D 5 B,C 6 A,B,C,D,E 7 C 8 A 9 B 10 (4) A?((P?Q)?(Q?P))?(P?Q)?(P?Q)?(P?Q)?T
（2）真值表法
P Q 1 1 1 0 0 1 0 0 所以A为重言式。 2、（1）不成立。
P?Q 1 0 1 1 Q?P 1 1 0 1 (P?Q)?(Q?P) 1 0 0 1 P?Q 1 0 0 1 A 1 1 1 1 若取C?T则A?T?TB?T?T有A?C?B?C?T
但A与B不一定等价，可为任意不等价的公式。 （2）成立。 证明：?A??B充要条件?A??B?T
T?(?A??B)?(?B??A)?(A??B)?(B??A)即：?(?B?A)?(?A?B)?(A?B)?(B?A)?A?B
所以A?B?T故 A?B。
3、解：设P：厂方拒绝增加工资；Q：罢工停止；R罢工超壶过一年；R：撤换厂长 前提：P?(?(R?S)??Q),①P?(?(R?S)??Q) ②P
③?(R?S)??Q ④?R ⑤?R??S ⑥?(R?S) ⑦?Q
罢工不会停止是有效结论。 四、计算 10%
P,?R 结论：?Q
P P T①②I P T④I T⑤E T③⑥I
(1?(1?0?0)))?(1?1)?(1?(1?0)?1（1） 解：?(1?0)?1?1?1?1
（2）
?(P?Q)?Q?R??(?P?Q)?(Q?R)?(P??Q)?(Q?R)?P??Q?Q?R?F
它无成真赋值，所以为矛盾式。
五、谓词逻辑推理 15%
解：M(x):x是人;F(x):x是花;G(x):x是杂草;H(x,y):x喜欢y
?x(M(x)??y(F(y)?H(x,y))) ?x(M(x)??y(G(y)??H(x,y))) ??x(F(x)??G(x))
证明：
⑴?x(M(x)??y(F(y)?H(x,y)))
P
⑵M(a)??y(F(y)?H(a,y)) ⑶M(a)
⑷?y(F(y)?H(a,y))
⑸?x(M(x)??y(G(y)??H(x,y))) ⑹M(a)??y(G(y)??H(a,y)) ⑺?y(G(y)??H(a,y)) ⑻?y(H(a,y)??G(y)) ⑼F(z)?H(a,z) ⑽H(a,z)??G(z) ⑾F(z)??G(z) ⑿?x(F(x)??G(x))
十三、
证明10%
ES⑴ T⑵I T⑵I P US⑸ T⑶⑹I T⑺E US⑷ US⑻ T⑼⑽I UG⑾
?xA(x)??xB(x)?(A(a)?A(b)?A(c)?(B(a)?B(b)?B(c)?(A(a)?B(a))?(A(a)?B(b))?(A(a)?B(c))?(A(b)?B(a))?(A(b)?B(b))?(A(b)?B(c))?(A(c)?B(a))?(A(c)?B(b))?(A(c)?B(c))?(A(a)?B(a))?(A(b)?B(b))?(A(c)?B(c) ??x(A(x)?B(x))
试卷五试题与答案
一、填空15%（每空3分）
1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 个5度结点。 2、n阶完全图，Kn的点数X (Kn) = 。
3、有向图 中从v1到v2长度为2的通路有 条。
4、设[R，+，·]是代数系统，如果①[R，+]是交换群 ②[R，·]是半群
③ 则称[R，+，·]为环。 5、设[L,?,?]是代数系统，则[L,?,?]满足幂等律，即对?a?L有 。
二、选择15%（每小题3分）
1、 下面四组数能构成无向简单图的度数列的有（ ）。 A、（2，2，2，2，2）； B、（1，1，2，2，3）； C、（1，1，2，2，2）； D、（0，1，3，3，3）。 2、 下图中是哈密顿图的为（ ）。
3、 如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（ ）
A、真； B、假。
4、 下列偏序集（ ）能构成格。
5、 设
s?{1,111,2,,3,,4}234，*为普通乘法，则[S，*]是（）。
A、代数系统； B、半群； C、群； D、都不是。
三、证明 48%
1、（10%）在至少有2个人的人群中，至少有2 个人，他们有相同的朋友数。 2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。
3、（8%）证明在6个结点12条边的连通平面简单图中， 每个面的面数都是3。 4、（10%）证明循环群的同态像必是循环群。 5、（12%）设[B,?,?,?,0,1]是布尔代数，定义运算*为a*b?(a?b)?(a?b)，
求证[B，*]是阿贝尔群。