发布时间 : 星期一 文章第2章谓词逻辑习题及答案更新完毕开始阅读caa890b9551810a6f52486ff
谓词逻辑习题
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)??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规则，然而，对
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?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++。
假设个体域为全总个体域，谓词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的个体域都是全世界所有人的集合。用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))?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的辖域是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. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。
（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?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 是永假式，所以公式是永假式。
（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)?Q(x))??x(P(x)??Q(x))