解:
(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)