解：

（1）S(x)：x是学生。w：小王。┐S(w)

（2）C(x)：x聪明。S(x)：x好学。w：小王。C(w)∧S(w) （3）F(x，y)：x和y是好朋友。w：小王。z：小张。F(w，z)

（4）S(x)：x是田径运动员。B(x)：x是球类运动员。h：他。S(h)∨B(h) （5）O(x)：x是奇数。O(m)→┐O(2m)。

（6）Q(x)：x是有理数。R(x)：x是实数。(?x)(Q(x)→R(x)) （7）Q(x)：x是有理数。R(x)：x是实数。(?x)(R(x)∧Q(x)) （8）Q(x)：x是有理数。R(x)：x是实数。┐(?x)( R(x)→Q(x))

←（9）N(x)：x是自然数。O(x)：x是奇数。E(x)：x是偶数。(?x)(N(x)→(O(x) E(x))) ∣→（10）B(x)：x是黑猫。W(x)：x是白猫。G(x)：x是好猫。Z(x)：x抓住老鼠。论域为{猫}。

(?x)((B(x)∨W(x))∧Z(x)→G(x))

（11）M(x)：x是机器人。T(x)：x会说话。(?x)(M (x)∧T(x))

（12）M(x)：x是人。E(x)：x吃萝卜。D(x)：x喝水。(?x)(M(x)∧┐E(x))∧(?x)(M(x)→D(x)) 2. 用谓词表达式符号化下列命题。

（1）并非所有大学生都能成为科学家。

（2）直线A平行于直线B，当且仅当直线A不相交于直线B。 （3）某些运动员是大学生。

（4）某些教练员是年老的，但是很健壮。 （5）王教练既不年老，也不健壮。 （6）某些大学生运动员是国家对选手。 （7）所有运动员都钦佩某些教练。 （8）有些大学生不钦佩教练。

（9）并不是所有的汽车都比火车快。 （10）男人一定比女人高，是不对的。

（11）某些汽车慢于所有的火车，但至少有一火车快于每一汽车。 （12）两个不相等的实数间，必存在第三个实数。 解：

（1）S(x)：x是大学生。K(x)：x是科学家。┐(?x)(S(x)→K(x))

┐C(a,b) （2）P(x,y)：x平行于y。C(x,y)：x与y相交。a：直线A。b：直线B。P(a,b)←→（3）S(x)：x是大学生。A(x)：x是运动员。(?x)(A(x)∧S(x))

（4）T(x)：x是教练员。O(x)：x是年老的。J(x)：x是健壮的。(?x)(T(x)∧O(x)∧J(x)) （5）O(x)：x是年老的。J(x)：x是健壮的。w：王教练。┐O(w)∧┐J(w)

（6）S(x)：x是大学生。A(x)：x是运动员。G(x)：x是国家对选手。(?x)(A(x)∧S(x)∧G(x)) （7）A(x)：x是运动员。T(x)：x是教练员。P(x,y)：x钦佩y。(?x)(A(x)→(?y)(T(y)∧P(x,y))) （8）S(x)：x是大学生。T(x)：x是教练员。P(x,y)：x钦佩y。(?x)(S (x)∧(?y)(T(y)→┐P(x,y))) （9）C(x)：x是汽车。T(x)：x是火车。K(x,y)：x比y快。┐(?x)(C(x)→(?y)(T(y)→K(x,y))) （10）M(x)：x是男人。W(x)：x是女人。T(x,y)：x比y高。┐(?x)(M(x)→(?y)(W(y)→T(x,y))) （11）C(x)：x是汽车。T(x)：x是火车。K(x,y)：x比y快。

(?x)(C(x)∧(?y)(T(y)→┐K(x,y)))∧(?y)(T(y)∧(?x)(C(x)→K(y,x)))

（12）R(x)：x是实数。E(x,y)：x等于y。

(?x)(?y)((R(x)∧R(y)∧┐E(x,y))→(?z)(R(z)∧┐E(x,z)∧┐E(y,z)))

3. 试表示出“A是B的外祖父”，只允许用以下谓词：P(x)表示“x是人”，F(x，y)表示“x是y的父亲”，M(x，y)表示“x是y的母亲”。

解：P(A)∧P(B)∧P(C)∧F(A，C)∧M(C，B) 4. 利用谓词公式翻译下列命题。

（1）如果有限个数的乘积为零，那么至少有一个因子等于零。 （2）对于每一个实数x，存在一个更大的实数y。

（3）存在实数x，y和z，使得x与y之和大于x与z之积。 解：

（1）N(x)：x是有限个数的乘积。Z(y)：y为零。P(x)：x的乘积为零。F(y)：y是乘积中的一个因子。(?x)(N(x)∧P(x)→(?y)(F(y)∧Z(y)))

（2）R(x)：x是实数。Q(x,y)：y大于x。(?x)(R(x)→(?y)(R(y)∧Q(x,y)))

（3）R(x)：x是实数。G(x,y)：x大于y。(?x)(?y)(?z)(R(x)∧R(y)∧R(z)∧G(x+y,x·z)) 5. 自然数一共有3条公理。

（1）每个数都有惟一的一个数是它的后继数。 （2）没有一个数使数1是它的后继数。

（3）每个不等于1的数都有惟一的一个数是它的直接先行者。 用两个谓词表达上述3条公理。

解：N(x)：x是自然数。S(x,y)：y是x的后继数。 （1）(?x)(N(x)→(?!y)(N(y)∧S(x,y))) （2）┐(?x)( N(x)∧S(x,1))

（3）(?x)(N(x)∧┐S(x,2)→(?!y)(N(y)∧S(y,x))) 6. 对下面的每个公式指出约束变元和自由变元。 （1）(?x)P(x)→P(y)

（2）(?x)(P(x)∧Q(x))∧(?x)S(x) （3）(?x)(?y)(P(x)∧Q(y))→(?x)R(x) （4）(?x)(?y)(P(x，y)∧Q(z)) 解：

（1）x为约束变元，受(?x) 约束，y为自由变元。

（2）(P(x)∧Q(x))的x为约束变元，受(?x) 约束，S(x)的x为约束变元，受(?x)约束。

（3）(P(x)∧Q(y)) 的x和y为约束变元，分别受(?x)和(?y)约束，R(x)的x为约束变元，受(?x) 约束。

（4）(P(x，y)∧Q(z))的x和y为约束变元，分别受(?x)和(?y)约束，Q(z)中的z为自由变元。 7. 如果论域是集合{a，b，c}，试消去下面公式中的量词。 （1）(?x)P(x)

（2）(?x)P(x)∧(?x)Q(x) （3）(?x)(P(x) →Q(x)) （4）(?x)┐(P(x)∨(?x) (P(x) 解：

（1）P(a)∧P(b)∧P(c)

（2）(P(a)∧P(b)∧P(c))∧(Q(a)∧Q(b)∧Q(c)) （3）(P(a) →Q(a))∧(P(b) →Q(b))∧(P(c) →Q(c)) （4）(┐P(a)∧┐P(b)∧┐P(c))∨(P(a)∧P(b)∧P(c)) 8. 试求下列各式的真值。 （1）(?x)(P(x)∨Q(x))，其中P(x)：x=1，Q(x)：x=2，论域是{1，2}。 （2）(?x) (P→Q(x))∨R(a)，其中P：2>1，Q(x)：x≤3，R(x)：x>5，a：5，论域是{-2，3，6}。

解：

（1）(?x)(P(x)∨Q(x)) ? (P(1)∨Q(1)) ∧(P(2)∨Q(2)) ?(T∨F) ∧(F∨T) ?T ∧T?T （2）(?x) (P→Q(x))∨R(a)?(P→Q(-2))∧(P→Q(3))∧(P→Q(6))∨R(a)

? (T→T)∧(T→T)∧(T→F)∨F? T∧T∧F∨F?F 9. 对下列谓词公式中的约束变元进行换名。

S(x，y) （1）(?x)(?y)(P(x，z)→Q(y)) ←→

（2）((?x)(P(x)→(R(x)∨Q(x)))∧(?x)R(x))→(?z)S(x，z) 解：

S(x，y) （1）(?u)(?v)(P(u，z)→Q(v)) ←→

（2）((?u)(P(u)→(R(u)∨Q(u)))∧(?v)R(v))→(?z)S(x，z)

10. 对下列谓词公式中的自由变元进行代入。

（1）((?y)A(x，y)→(?x)B(x，z))∧(?x)(?z)C(x，y，z) （2）((?y)P(x，y)∧(?z)Q(x，z))∨(?x)R(x，y) 解：

（1）((?y)A(u，y)→(?x)B(x，v))∧(?x)(?z)C(x，w，z) （2）((?y)P(u，y)∧(?z)Q(v，z))∨(?x)R(x，w) 11. 考虑以下赋值。 论域 D={1，2}

指定常数a：1，b：2

指定函数f：f (1)=2，f (2)=1

指定谓词P：P(1，1)?T，P(1，2)?T，P(2，1)?F，P(2，2)?F 求以下各式的真值。

（1）P(a，f(a))∧P(b，f(b)) （2）(?x)(?y)P(y，x)

（3）(?x)( ?y)(P(x，y)→P(f (x)，f (y))) 解：

（1）P(a，f(a))∧P(b，f(b)) ? P(1，f(1))∧P(2，f(2)) ? P(1，2)∧P(2，1) ? T∧F?F （2）(?x)(?y)P(y，x) ?(?x)(P(1，x)∨P(2，x))?(P(1，1)∨P(2，1))∧(P(1，2)∨P(2，2)) ?( T∨F)∧(T∨F) ?T∧T?T

（3）(?x)(?y)(P(x，y)→P(f (x)，f (y)))?(?x)((P(x，1)→P(f (x)，f (1)))∧(P(x，2)→P(f (x)，f (2)))) ?((P(1，1)→P(f (1)，f (1)))∧(P(1，2)→P(f (1)，f (2))))∧((P(2，1)→P(f (2)，f (1)))∧(P(2，2)→P(f (2)，f (2))))? ((T→F)∧(T→F))∧((F→F)∧(F→T))?(F∧F)∧(T∧T)?F∧T?F 12. 将下面各式翻译成自然语言，然后在不同的个体域中确定它们的真值。 （1）(?x) (?y)(x·y=0) （2）(?x) (?y)( x·y=0) （3）(?x) (?y)( x·y=1) （4）(?x) (?y)( x·y=1) （5）(?x) (?y)( x·y=x) （6）(?x) (?y)( x·y=x) （7）(?x) (?y) (?z)(x-y=z) 个体域分为

（a）实数集合R （b）整数集合Z （c）正整数集合Z+

（d）非零实数集合R-{0} 解：（1）对于任意的x，存在y，使得x·y=0。 （2）存在x，对于任意的y，都有x·y=0。 （3）对于任意的x，存在y，使得x·y=1。 （4）存在x，对于任意的y，都有x·y=1。 （5）对于任意的x，存在y，使得x·y=x。 （6）存在x，对于任意的y，都有x·y=x。

（7）对于任意的x，任意的y，存在z，使得x-y=z。 个体域分为

（a）实数集合R

（1）真（2）真（3）假（4）假（5）真（6）真（7）真 （b）整数集合Z

（1）真（2）真（3）假（4）假（5）真（6）真（7）真 （c）正整数集合Z+

（1）假（2）假（3）假（4）假（5）真（6）假（7）假 （d）非零实数集合R-{0}

（1）假（2）假（3）真（4）假（5）真（6）假（7）假

13. 判断下面公式的真假，如果是真，请证明之；如果为假，请给出P和Q的解释，以说明公式为假

（1）(?x)(P(x)→Q(x)) ?(?x)P(x)→(?x)Q(x) （2）(?x)P(x)→(?x)Q(x) ?(?x)(P(x)→Q(x)) 解：（1）(?x)(P(x)→Q(x))?(?x)(┐P(x)∨Q(x))?(?x)┐(P(x)∧┐Q(x))?┐(?x)(P(x)∧┐Q(x)) ?┐((?x)P(x)∧(?x)┐Q(x))?┐(?x)P(x)∨┐(?x)┐Q(x))?(?x)┐P(x)∨(?x)Q(x)) ? (?x)┐P(x)∨(?x)Q(x))? ┐(?x)P(x)∨(?x)Q(x)) ?(?x)P(x)→(?x)Q(x) （2）(?x)P(x)→(?x)Q(x) ?(?x)(P(x)→Q(x))不成立。

P(x)：x成绩优秀。Q(x)：x获得奖学金。论域为所有学生。

(?x)P(x)→(?x)Q(x)表示：若所有学生成绩都优秀，则所有学生都获得奖学金。 (?x)(P(x)→Q(x))表示：任何一个学生，只要成绩优秀，他就获得奖学金。 显然“任何一个学生，只要成绩优秀，他就获得奖学金。”可以推出“若所有学生成绩都优秀，则所有学生都获得奖学金。”反之未必成立。 14. 求证：(?x)(P(x)→Q(x))?(?x)P(x)→(?x)Q(x) 证明：(?x)(P(x)→Q(x))? (?x)( ┐P(x)∨Q(x))? (?x)┐P(x)∨(?x)Q(x))? ┐(?x) P(x)∨(?x)Q(x)) ?(?x)P(x)→(?x)Q(x)

15. 求证：(?x)(?y)(P(x)→Q(y))?(?x)P(x)→(?y)Q(y) 证明：(?x)(?y)(P(x)→Q(y))? (?x)(?y)( ┐P(x)∨Q(y)) ? (?x) ┐P(x)∨(?y)Q(y) ? ┐(?x)P(x)∨(?y)Q(y)?(?x)P(x)→(?y)Q(y) 16. 下列推导过程中有何错误？ （1） (?x)(P(x)→Q(x)) P （2） P(a)→Q(a) US(1) （3） (?x)P(x) P （4） P(a) ES(3) （5） Q(a) T(2),(4) I （6） (?x)Q(x) EG(5) 解：应先消去存在量词。

17. 把以下各式化为前束范式。 （1）(?x)(P(x)→(?y)Q(x，y))

（2）(?x)(┐((?y)P(x，y))→((?z)Q(z)→R(x)))

（3）(?x)(?y)(((?z)P(x，y，z)∧(?u)Q(x，u))→(?v)Q(y，v)) 解：

（1）(?x)(P(x)→(?y)Q(x，y)) ? (?x)(┐P(x)∨(?y)Q(x，y)) ?(?x)(?y)(┐P(x)∨Q(x，y)) （2）(?x)(┐((?y)P(x，y))→((?z)Q(z)→R(x))) ?(?x)((?y)P(x，y)∨((?z)Q(z)→R(x))) ?(?x)((?y)P(x，y)∨(┐(?z)Q(z)∨R(x))) ?(?x)((?y)P(x，y)∨((?z) ┐Q(z)∨R(x))) ?(?x)(?y)(?z)(P(x，y)∨┐Q(z)∨R(x)) （3）(?x)(?y)(((?z)P(x，y，z)∧(?u)Q(x，u))→(?v)Q(y，v)) ?(?x)(?y)(┐((?z)P(x，y，z)∧(?u)Q(x，u))∨(?v)Q(y，v)) ?(?x)(?y)((?z) ┐P(x，y，z)∨(?u) ┐Q(x，u))∨(?v) Q(y，v)) ?(?x)(?y)(?z)(?u)(?v)(┐P(x，y，z)∨┐Q(x，u)∨Q(y，v)) 18. 求等价于下面各式的前束析取范式和前束合取范式。 （1）((?x)P(x)∨(?x)Q(x))→ (?x)(P(x)∨Q(x))

（2）(?x)(P(x)→(?y)((?z)Q(x，y)→┐(?z)R(y，x))) （3）(?x)P(x)→(?x)((?z)Q(x，z)∨(?z)R(x，y，z)) （4）(?x)(P(x)→Q(x，y))→((?y)P(y)∧(?z)Q(y，z)) 解：

（1）((?x)P(x)∨(?x)Q(x))→ (?x)(P(x)∨Q(x)) 因为((?x)P(x)∨(?x)Q(x)) ?(?x)(P(x)∨Q(x))，所以((?x)P(x)∨(?x)Q(x))→ (?x)(P(x)∨Q(x))为永真式，不写为前束范式的形式。

（2）(?x)(P(x)→(?y)((?z)Q(x，y)→┐(?z)R(y，x))) ?(?x)(┐P(x)∨(?y)(Q(x，y)→┐R(y，x))) ?(?x)(?y)(┐P(x)∨┐Q(x，y)∨┐R(y，x))) 前束合取范式 ?(?x)(?y)((┐P(x)∧Q(x，y)∧R(y，x))∨(┐P(x)∧Q(x，y)∧┐R(y，x))∨(┐P(x)∧┐Q(x，y)∧R(y，x))∨(┐P(x)∧┐Q(x，y)∧┐R(y，x))∨(P(x)∧┐Q(x，y)∧R(y，x))∨(P(x)∧┐Q(x，y)∧┐R(y，x))∨(P(x)∧Q(x，y)∧┐R(y，x))) 前束析取范式 （3）(?x)P(x)→(?x)((?z)Q(x，z)∨(?z)R(x，y，z)) ?┐(?x)P(x)∨(?x)((?z)Q(x，z)∨(?z)R(x，y，z)) ?(?x)┐P(x)∨(?x)((?z)Q(x，z)∨(?u)R(x，y，u)) ?(?x)( ┐P(x)∨(?z)Q(x，z)∨(?u)R(x，y，u)) ?(?x)(?z)(?u)( ┐P(x)∨Q(x，z)∨R(x，y，u)) 前束合取范式 ?(?x)(?z)(?u)((┐P(x) ∧Q(x，z) ∧R(x，y，u))∨(┐P(x) ∧Q(x，z) ∧┐R(x，y，u))∨(┐P(x) ∧┐Q(x，z) ∧R(x，y，u))∨(┐P(x) ∧┐Q(x，z) ∧┐R(x，y，u))∨(P(x) ∧Q(x，z) ∧R(x，y，u))∨(P(x) ∧Q(x，z) ∧┐R(x，y，u))∨(P(x) ∧┐Q(x，z) ∧R(x，y，u))) 前束析取范式 （4）(?x)(P(x)→Q(x，y))→((?y)P(y)∧(?z)Q(y，z)) ?┐(?x)(┐P(x)∨Q(x，y))∨((?y)P(y)∧(?z)Q(y，z)) ?(?x)(P(x)∧┐Q(x，y))∨((?u)P(u)∧(?z)Q(y，z)) ?(?x)(?u)(?z)((P(x)∧┐Q(x，y))∨(P(u)∧Q(y，z)) 前束析取范式 ?(?x)(?u)(?z)((P(x)∨P(u))∧(P(x)∨Q(y，z))∧(┐Q(x，y)∨P(u))∧(┐Q(x，y)∨Q(y，z))) 前束合取范式

19. 求下列各式的斯柯伦范式。 （1）(?x) P(x)∧┐(?x)Q(x)