第2章谓词逻辑习题及答案

《第2章谓词逻辑习题及答案》由会员分享，可在线阅读，更多相关《第2章谓词逻辑习题及答案（9页珍藏版）》请在装配图网上搜索。

1、第2章谓词逻辑习题及答案 - 教育文库 谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （3）3不是偶数。 （2）2大于3仅当2大于4。 （4）2或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

2、)?P(x) b，c，消去下列各式的量词。 2. 设个体域D?a，（1）?x?y(P(x)?Q(y) （3）?xP(x)?yQ(y) （2）?x?y(P(x)?Q(y) （4）?x(P(x，y)?yQ(y) 解： (1) 中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规则， ?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规则

3、，然而，对 A(x)中约束变元y改名z，得到?z(P(x)?Q(z)，这时用UI规则，可得： ?x?y(P(x)?Q(y) ?x?z(P(x)?Q(z) ?z(P(x)?Q(z) （3）略 （4）略 ，2，3。求下列各式3. 设谓词P(x，y)表示“x等于y”，个体变元x和y的个体域都是D?1（1）?xP(x，3) 的真值。 ，y) （2）?yP(1y) （4）?x?yP(x，y) （6）?y?xP(x， y) （3）?x?yP(x，y) （5）?x?yP(x， 解： (2) 当x?3时可使式子成立，所以为Ture。 (3) 当y?1时就不成立，所以为False。 (4) 任意的x,y使得x?

4、y，显然有x?y的情况出现，所以为False。 (4)存在x,y使得x?y，显然当x?1,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+

5、。 假设个体域为全总个体域，谓词M(x)表示“x是杭电学生”。用P(x)、Q(x)、M(x)、量词和逻辑联接词再次符号化上面的4条语句。 解：（）个体域为杭电全体学生的集合时： （1）?x(P(x)?Q(x) （2）?x(P(x)?Q(x) （3）?x(P(x)?Q(x) （4）?x?(P(x)?Q(x) （）假设个体域为全总个体域，谓词M(x)表示“x是杭电学生”时： （1）?x(M(x)?P(x)?Q(x) （2）?x(M(x)?P(x)?Q(x) （3）?x(M(x)?(P(x)?Q(x) （4）?x(M(x)?(P(x)?Q(x) 5. 令谓词P(x，y)表示“x爱y”，其中x和y的个

6、体域都是全世界所有人的集合。用P(x，y)、量词和逻辑联接词符号化下列语句。 （1）每个人都爱王平。 （2）每个人都爱某个人。 （4）没有人爱所有的人。 （6）有个人人都不爱的人。 （8）成龙爱的人恰有两个。 （3）有个人人都爱的人。 （5）有个张键不爱的人。 （7）恰有一个人人都爱的人。 （9）每个人都爱自己。 （10）有人除自己以外谁都不爱。 解：a：王平 b：张键 c：张龙 (1) ?xP(x,a） (2)?x?yP(x,y) (3)?y?xP(x,y) (4)?x?y?P(x,y) (5)?x?P(b，x) (6)?x?y?P(x,y) (7)?x(?yP(y,x)?z(?P(?,z)

7、?z?x) (8)?x?y(x?y?P(c,x)?P(c)?z(P(c，z)?(z?x?z?y) (9)?xP(x,x) (10)?x?y(P(x,y)?x?y) 2.2 谓词公式及其解释 习题2.2 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的辖域是

8、Q(x，y)；对于?x的辖域而言，x,y都为约束变元，对于?y的辖域而言，x是自由变元，y是约束变元。 （3）x,y为指导变元，?x的辖域是?y(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. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明

9、理由。 （1）?x(P(x)?Q(x)?(?xP(x)?yQ(y) （2）?x(P(x)?Q(x)?(?xP(x)?yQ(y) （3）?(?xP(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)?P(x，y) 解：（1）易知公式是(p?q)?(p?q)的代换实例，而 (p?q)?(p?q)?(p?q)?(p?q)?1 是永真式，所以公式是永真式。 （2）易知公式是(p?q)?(p?q)的代换实例，而 (p?q)?(p?

10、q)?(p?q)?(p?q)?1 是永真式，所以公式是永真式。 （3）易知公式是?(p?q)?q的代换实例，而 ?(p?q)?q?(?p?q)?q?p?q?q?0 是永假式，所以公式是永假式。 （4）易知公式是(p?q)?(p?q)的代换实例，而 (p?q)?(p?q)?(p?q)?(p?q)?1 是永真式，所以公式是永真式。 （5）易知公式是(p?q)?(p?q)的代换实例，而 (p?q)?(p?q)?(p?q)?(p?q)?1 是永真式，所以公式是永真式。 （6）易知公式是?(p?(q?p)的代换实例，而 ?(p?(q?p)?(?p?(?q?p)?p?q?p?0 是永假式，所以公式是永假式

11、。 （7）易知公式是p?q?p的代换实例，而 p?q?p?(?p?q)?p?(p?q)?p 是可满足式，所以公式是可满足式。 2.3 谓词公式的等价演算与范式 习题2.3 1. 将下列命题符号化，要求用两种不同的等价形式。 （1）没有小于负数的正数。 （2）相等的两个角未必都是对顶角。 解：（1）P(x)：x为负数，Q(x)：x是正数，R(x,y)：x小于y，命题可符号化为：?x?y(R(P(x),Q(y)或?x?y?(?R(P(x),Q(y) （2）略 2.设P(x)、Q(x)和R(x，y)都是谓词，证明下列各等价式 （1）?x(P(x)?Q(x)?x(P(x)?Q(x) （2）?x(P(x

12、)?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) （4）?x?y(P(x)?Q(y)?R(x，y)?x?y(P(x)?Q(y)?R(x，y) 证明：（1）左边?x?(P(x)?Q(x) ?x(?P(x)?Q(x) ?x(P(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?(

13、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）?x(P(x)?Q(x，y)?(?y(R(y)?zS(y，z) 解：（1）原式?x?yP(x)?Q(z,y)?x?y(?P(x)?Q(z,y) 前束析取范式 ?x?y?(P(x)?Q(z,y) 前束合取范式 （2）原式?x?t(P(x,y)?Q(x,t,z)?x?t(?P(x,

14、y)?Q(x,t,z)前束析取范式 ?x?t?(P(x,y)?Q(x,t,z) 前束合取范式 （3）原式?x?y?z(?P(x,y)?(Q(z)?R(t) ?x?y?z(P(x,y)?Q(z)?R(t) 前束析取范式 ?x?y?z?(?P(x,y)?Q(z)?R(t) 前束合取范式 （4）原式?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) ?x?t?z(?(?P(x)?Q(x,y)?(?R(t)?S(t,z) ?x?t?z(P(x)?Q(x,y)?R(t)?(P(x)?Q(x,y)?S(t,z) ?x?t?z(P(x)?(?R(t)?S(t,z)?(Q(x,y)?R(t)?S(t,z) 第 9 页 共 9 页