四、计算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，*]是阿贝尔群。