谓词逻辑习题及答案

1、谓词逻辑习题1 .将下列命题用谓词符号化。(2) 2大于3仅当2大于4。(4) 2或3是质数。(1)小王学过英语和法语。(3) 3不是偶数。(5)除非李键是东北人，否则他一定怕冷。解：(1)令P(x)： x学过英语，Q(x) ： x学过法语，c：小王，命题符号化为P(c) Q(c)(2)令P(x, y)： x大于y,命题符号化为 P(2,4)P(2,3)(3)令P(x)： x是偶数，命题符号化为P(3)(4)令P(x) ： x是质数，命题符号化为P(2) P(3)(5)令P(x)： x是北方人；Q(x) ： x怕冷；c：李键；命题符号化为Q(c) P(x)2 .设个体域D a, b, c,消去

2、下列各式的量词。(1) x y(P(x) Q(y)(2)x y(P(x) Q(y)(3) xP(x) yQ(y)(4)x(P(x, y) yQ(y)解：中A(x) y( P(x) Q(y),显然A(x)对y是自由的，故可使用 UE规则，得到A(y) y(P(y) Q(y),因此 x y(P(x) Q(y) y(P(y) Q(y),再用 ES规贝U, y(P(y) Q(y) P(z) Q(z), z D ,所以 x y(P(x) Q( y) P(z) Q(z) (2)中A(x) y(P(x) Q(y),它对y不是自由的，故不能用UI规则，然而，对A(x)中约束变元y改名z,得到 z(P(x) Q

3、(z),这时用UI规则，可得:x y(P(x) Q(y)x z(P(x) Q(z) z(P(x) Q(z)(4)略3.设谓词P(x,(3)略y)表示“ x等于y ”，个体变元x和y的个体域都是 D 1, 2, 3。求下列各式的真值。(1)xP(x, 3)(2)yP(1, y)(3)x yP(x, y)(4)x yP(x, y)(5)x yP(x, y)(6)y xP(x, y)解：(2)当x 3时可使式子成立，所以为 Ture。(3)当y 1时就不成立，所以为 False 。(4)任意的x,y使彳导x y ,显然有x y的情况出现，所以为 False。(4)存在x,y使得x y ,显然当x 1

4、, y 1时是一种情况，所以为 Ture。(5)存在x,任意的y使得x y成立，显然不成立，所以为 False。(6)任意的y ,存在x ,使得x y成立，显然不成立，所以为 False。4.令谓词P(x)表示“ x说德语”，Q(x)表示“ x 了解计算机语言 C+”，个体域为杭电全体学生 的集合。用P(x)、Q(x)、量词和逻辑联接词符号化下列语句。(1)杭电有个学生既会说德语又了解C+。(2)杭电有个学生会说德语，但不了解C+。(3)杭电所有学生或会说德语，或了解 C+。(4)杭电没有学生会说德语或了解C+。假设个体域为全总个体域，谓词M(x)表示“ x是杭电学生”。用P(x)、Q(x)、

5、M(x)、量词和逻辑联接词再次符号化上面的4条语句。解：(i)个体域为杭电全体学生的集合时：(1) x(P(x) Q(x)(2) x(P(x) Q(x)(3) x(P(x) Q(x)(4) x (P(x) Q(x)(1) x(M (x)(2) x(M (x) x(M (x)(4) x(M (x)(5) 谓词P(x,量词和逻辑联接词符号化下列语句。(1)每个人都爱王平。(3)有个人人都爱的人。(5)有个张键不爱的人。(7)恰有一个人人都爱的人。(9)每个人都爱自己。P(x) Q(x)P(x) Q(x)(P(x) Q(x)(P(x) Q(x)y)表示“ x爱y ”，其中x和y的个体域都是全世界所有

6、人的集合。(ii)假设个体域为全总个体域，谓词 M (x)表示“ x是杭电学生”时:用 P(x, y)(2)每个人都爱某个人。(4)没有人爱所有的人。(6)有个人人都不爱的人。(8)成龙爱的人恰有两个。解：a ：王平b :张键c :张龙(1)xP(x, a)(2)(3)y xP(x, y)(4)(5)x P(b, x)(6)(7)x( yP(y,x)z( P( , z)(10)有人除自己以外谁都不爱。x yP(x, y)x y P(x, y)x y P(x, y)z x)(8) x y(x y P(c,x) P(c) z(P(c, z) (z x z y)(9) xP(x,x)§谓词

7、公式及其解释(10)x y(P(x, y) x y)习题1 .指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。(1) x(P(x) Q(x, y)(2) xP(x, y) yQ(x, y)(3) x y(P(x, y) Q(y, z)xR(x, y, z)解：(1) x是指导变元，x的辖域是P(x) Q(x, y),对于 x的辖域而言，x是约束变元，y是自由变元。(2)x,y都为指导变元，x的辖域是P(x, y) yQ(x, y) , y的辖域是Q(x, y);对于 x的辖域而言，x,y都为约束变元，对于y的辖域而言，x是自由变元，y是约束变元。(4) x,y为指导变元，x的辖域是y

8、(P(x, y) Q(y, z)xR(x, y, z) , y的辖域是(P(x, y) Q(y, z)xR(x, y, z) , x的辖域是R(x, y, z)；对于 x的辖域而言，x,y为约束变元，z为自由变元，对于 y的辖域而言，z为自由变元，y为约束变元，x即为约束变元也为自由 变元，对于 x的辖域而言，x为约束变元，y,z是自由变元。在整个公式中，x,y即为约束变元又为自由变元，z为自由变元。2 .判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。(1) x(P(x)Q(x)( xP(x)yQ(y)(2) x(P(x)Q(x)( xP(x)yQ(y)(3) ( x

9、P(x) yQ(y) yQ(y)(4) x(P(y)Q(x)(P(y)xQ(x)(5) x(P(x)Q(x)(P(x)xQ(x)(6 )(P(x)( yQ(x, y) P(x)(7 ) P(x, y) (Q(x, y)解：(1)易知公式是(p q)(p q) (p是永真式，所以公式是永真式。(2)易知公式是(p q)( p q) (p是永真式，所以公式是永真式。P(x, y)(p q)的代换实例，而q)(pq)(pq)1(p q)的代换实例，而q)(pq)(pq)1(3)易知公式是 (p q) q的代换实例，而(p q) q ( p q) q p q q 0是永假式，所以公式是永假式。(4)易

10、知公式是(p q) (p q) (p 是永真式，所以公式是永真式。(5)易知公式是(p q)(p q) (p 是永真式，所以公式是永真式。(6)易知公式是 (p(p (q 是永假式，所以公式是永假式。(7)易知公式是p q p q p(pq)的代换实例，而q)(pq)(pq)1(pq)的代换实例，而q)(pq)(pq)1(q p)的代换实例，而p)( p ( q p) p q p op的代换实例，而(p q) p (p q) p是可满足式，所以公式是可满足式。 谓词公式的等价演算与范式习题i.将下列命题符号化，要求用两种不同的等价形式。(1)没有小于负数的正数。(2)相等的两个角未必都是对顶角

11、。R(x, y) : x小于y ,命题可符号化为:2.设 P(x)、Q(x)和 R(x,y)都是谓词，证明下列各等价式(1)x(P(x) Q(x)x(P(x)x(P(x) Q(x)x(P(x)(3) x y(P(x) Q(y)R(x, y)(4) x y(P(x) Q(y) R(x, y)Q(x)Q(x)x y(P(x) Q(y)R(x, y)x y(P(x) Q(y)R(x, y)解：(1) P(x) ： x为负数，Q(x) : x是正数, x y(R(P(x),Q(y)或 x y ( R(P(x),Q(y)(2)略证明：(1)左边= x (P(x) Q(x)=x( P(x)Q(x)=x(P

12、(x)Q(x)=右边(2)左边=x (P(x)Q(x)=x ( P(x) Q(x)=x(P(x) Q(x)=右边(3)左边=x y (P(x) Q(y) R(x, y)=x y ( (P(x) Q(y) R(x, y)=x y(P(x) Q(y)R(x, y)=右边(4)左边=x y (P(x) Q(y) R(x, y)x y (P(x) Q(y) R(x, y)=x y(P(x) Q(y) R(x, y)=右边3.求下列谓词公式的前束析取范式和前束合取范式。(1)xP(x)yQ(x, y)(2)x(P(x, y)yQ(x, y, z)(3)x yP(x, y) ( zQ(z) R(x)(4)

13、解：(1)x(P(x)原式Q(x, y)( y(R(y) zS(y, z)x yP(x) Q(z, y) xy( P(x) Q(z,y)前束析取范式(2)原式x y (P(x)t(P(x,y)Q(z,y)Q(x,t,z)前束合取范式(3)原式原式(P(x,y)Q(x,t,z)z( P(x,y) (Q(z)z(P(x, y) Q(z)z ( P(x, y) Q(z)x t( P(x, y) Q(x,t,z)前束析取范式前束合取范式R(t)R(t)R(t)x(P(x) Q(x, y)( t(R(t)zS(t, z)前束析取范式前束合取范式x t z(P(x) Q(x, y)(R(t)S(t,z)z

14、( ( P(x) Q(x,y) ( R(t)S(t,z)z( P( x)Q(x, y)R(t)(P(x) Q(x, y) S(t, z)z(P(x)(R(t)S(t,z)(Q(x, y)R(t) S(t,z)§谓词公式的推理演算习题1.证明： x(A(x)B(x)x(A(x)B(x)证明：(1)左边x(A(x) B(x)(A(x)B(x)(A(x)B(x)= x(A(x)B(x)2.指出下面演绎推理中的错误，并给出正确的推导过程。(1) xP(x) Q(x)P规则 P(y)(2) x(P(x)Q(y)Q(x)US规则：p规则 P(a)Q(b)US规则：(3) P(x)xQ(x)P规则

15、 P(a)Q(a)ES规则：(4) P(a)G(a)P规则 x(P(x) G(x)UGB则： x(P(x) G(x)EG规则：(6)P(y) Q(y)P规则 x(P(c) Q(x)EG规则：解：(1)错，使用US,UG,ES,EG规则应对前束范式，而中公式不是前束范式，所以不能用 US 规则。(2)错，中公式为 xA(x)，这时，A(x) P(x) Q(x)，因而使用US规则时，应得A(a)(或A(y),故应有 P(a) Q(a),而不能为 P(a) Q(b)。3.用演绎法证明下列推理式xP(x) y(P(y) Q(y)R(y), xP(x) xR(x)证明：xP(x)前提引入P(a)ES前提

16、引入xP(x) y(P(y) Q(y)R(y)y(P(y) Q(y)R(y) t (P(a) Q(a) R(a) US P(a) Q(a) T R(a)T xR(x)EG 4.将下列命题符号化，并用演绎推理法证明其结论是有效的。(1)有理数、无理数都是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。(个体域取全总个体域)(2)所有的舞蹈者都很有风度；万英是个学生并且是个舞蹈者。因此，有些学生很有风度。(个体域取人类全体组成的集合)(3)每个喜欢步行的人都不喜欢骑自行车；每个人或者喜欢骑自行车或者喜欢乘汽车；有的人不喜欢乘汽车。所以有的人不喜欢步行。(个体域取人类全体组成的集合)(4)

17、每个旅客或者坐头等舱或者坐经济舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此有些旅客坐经济舱。(个体域取全体旅客组成的集合)解：(2)证明：设P(x) : x是个舞蹈者；Q(x) : x很有风度；S(x) : x是个学生；a :王华结论：x(S(x) Q(x)上述句子符号化为:前提：x(P(x) Q(x)、S(a) P(a)(1) S(a) P(a) P(3) P(a) Q(a)US (2)T (1) IT (3) (4) IT (1) IT (5) (6) I(4) P(a)(5) Q(a).(6) S(a)(7) S(a) Q(a)(8) x(S(x) Q(

18、x)EG (7)(3)命题符号化为：F(x) : x喜欢步行,G(x) : x喜欢骑自行车，H(x) : x喜欢坐汽车。前提： x(F(x) G(x), x(G(x) H(x), x( H(x)结论：x( F(x).证明：(1)x( H(x) P(2) H (c)ES(1)(3) x(G(x) H(x) P(4) G(c) H (c)US(3)(5) G(c)T(2)(4) I(6) x(F(x) G(x) P(7) F(c) G(c) US(6)(8) F (c)T(5)(7) I(9) x( F(x)EG(8)命题符号化为：F(x) : x坐头等舱，G(x) : x坐经济舱，H(x) : x富裕。前提：x(F(x) G(x)，