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

谓词逻辑习题
1. 将下列命题用谓词符号化。
（1）小王学过英语和法语。 （2）2大于3仅当2大于4。
（3）3不是偶数。 （4）2或3是质数。
（5）除非李键是东北人，否则他一定怕冷。
解：
(1) 令：x学过英语，Q(x)：x学过法语，c：小王，命题符号化为
(2) 令：x大于y, 命题符号化为
(3) 令：x是偶数，命题符号化为
(4) 令：x是质数，命题符号化为
(5) 令：x是北方人；：x怕冷；：李键；命题符号化为
2. 设个体域，消去下列各式的量词。
（1） （2）
（3） （4）
解：
(1) 中，显然对y是自由的，故可使用规则，得到
，因此，再用规则，
，，所以
（2）中，它对y不是自由的，故不能用规则，然而，对
中约束变元y改名z，得到，这时用规则，可得：

（3）略
（4）略
3. 设谓词表示“等于”，个体变元和的个体域都是。求下列各式的真值。
（1） （2）
（3） （4）
（5） （6）
解：
(2) 当时可使式子成立，所以为。
(3) 当时就不成立，所以为。
(4) 任意的使得，显然有的情况出现，所以为。
(4)存在使得，显然当时是一种情况，所以为。 (5)存在x，任意的y使得成立，显然不成立，所以为。
(6)任意的y ，存在x ，使得成立，显然不成立，所以为。
4. 令谓词表示“说德语”，表示“了解计算机语言”，个体域为杭电全体学生的集合。用、、量词和逻辑联接词符号化下列语句。
（1）杭电有个学生既会说德语又了解。
（2）杭电有个学生会说德语，但不了解。
（3）杭电所有学生或会说德语，或了解。
（4）杭电没有学生会说德语或了解。
假设个体域为全总个体域，谓词表示“是杭电学生”。用、、、量词和逻辑联接词再次符号化上面的4条语句。
解：（ⅰ）个体域为杭电全体学生的集合时：
（1）
（2）
（3）
（4）
（ⅱ）假设个体域为全总个体域，谓词表示“是杭电学生”时：
（1）
（2）
（3）
（4）
5. 令谓词表示“爱”，其中和的个体域都是全世界所有人的集合。用、量词和逻辑联接词符号化下列语句。
（1）每个人都爱王平。 （2）每个人都爱某个人。
（3）有个人人都爱的人。 （4）没有人爱所有的人。
（5）有个张键不爱的人。 （6）有个人人都不爱的人。
（7）恰有一个人人都爱的人。 （8）成龙爱的人恰有两个。
（9）每个人都爱自己。 （10）有人除自己以外谁都不爱。
解：：王平 ：张键 ：张龙
(1) (2)
(3) (4)
(5) (6)
(7)
(8)
(9) (10)
§2.2 谓词公式及其解释
习题2.2
1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。
（1）
（2）
（3）
解： （1）x是指导变元，的辖域是，对于的辖域而言，x是约束变元，y是自由变元。
（2）都为指导变元，的辖域是，的辖域是；对于的辖域而言，都为约束变元，对于的辖域而言，x是自由变元，y是约束变元。
（3）为指导变元，的辖域是，的辖域是，的辖域是；对于的辖域而言，为约束变元，z为自由变元，对于的辖域而言，z为自由变元，y为约束变元，x即为约束变元也为自由变元，对于的辖域而言，x为约束变元，是自由变元。在整个公式中，即为约束变元又为自由变元，z为自由变元。
2. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。
（1）
（2）
（3）
（4）
（5）
（6）
（7）
解：（1）易知公式是的代换实例，而

是永真式，所以公式是永真式。
（2）易知公式是的代换实例，而

是永真式，所以公式是永真式。
（3）易知公式是的代换实例，而

是永假式，所以公式是永假式。
（4）易知公式是的代换实例，而

是永真式，所以公式是永真式。
（5）易知公式是的代换实例，而

是永真式，所以公式是永真式。
（6）易知公式是的代换实例，而

是永假式，所以公式是永假式。
（7）易知公式是的代换实例，而

是可满足式，所以公式是可满足式。
§2.3 谓词公式的等价演算和范式
习题2.3
1. 将下列命题符号化，要求用两种不同的等价形式。
（1）没有小于负数的正数。 （2）相等的两个角未必都是对顶角。
解：（1）：x为负数，：x是正数，：x小于y，命题可符号化为：或
（2）略
2.设、和都是谓词，证明下列各等价式
（1）
（2）
（3）
（4）
证明：（1）左边＝
＝
＝＝右边
（2）左边 ＝
＝
＝＝右边
（3）左边＝
＝
＝＝右边
（4）左边＝
＝
＝＝右边
3. 求下列谓词公式的前束析取范式和前束合取范式。
（1）
（2）
（3）
（4）
解：（1） 前束析取范式
前束合取范式
（2）原式前束析取范式
前束合取范式
（3）原式
前束析取范式
前束合取范式
（4）原式

§2.4 谓词公式的推理演算
习题2.4
1.证明：
证明：（1）左边
＝
2. 指出下面演绎推理中的错误，并给出正确的推导过程。
（1） ① P规则
② 规则：①
（2） ① P规则
② 规则：①
（3） ① P规则
② 规则：①
（4） ① P规则
② 规则：①
（5） ① P规则
② 规则：①
（6） ① P规则
② 规则：①
解：（1）②错，使用规则应对前束范式，而①中公式不是前束范式，所以不能用规则。
(2)②错，①中公式为，这时，，因而使用规则时，应得A(a)(或A(y)),故应有，而不能为。
3.用演绎法证明下列推理式

证明：① 前提引入
② ①
③ 前提引入
④ T①③
⑤ ④
⑥ T②
⑦ T⑤⑥
⑧ ⑦
4. 将下列命题符号化，并用演绎推理法证明其结论是有效的。
（1）有理数、无理数都是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。（个体域取全总个体域）
（2）所有的舞蹈者都很有风度；万英是个学生并且是个舞蹈者。因此，有些学生很有风度。（个体域取人类全体组成的集合）
（3）每个喜欢步行的人都不喜欢骑自行车；每个人或者喜欢骑自行车或者喜欢乘汽车；有的人不喜欢乘汽车。所以有的人不喜欢步行。（个体域取人类全体组成的集合）
（4）每个旅客或者坐头等舱或者坐经济舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此有些旅客坐经济舱。（个体域取全体旅客组成的集合）
解：(2)证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华
上述句子符号化为：
前提：、 结论：
（1） P
（2） P
（3） （2）
（4） T（1）I
（5） T（3）（4）I
（6） T（1）I
（7） T（5）（6）I
（8） （7）

]（3）命题符号化为：F(x)：x喜欢步行(x)：x喜欢骑自行车，H(x)：x喜欢坐汽车。
前提：，，
结论：.
证明：(1) P
(2) (1)
(3) P
(4) (3)
(5) T(2)(4) I
(6) P
(7) (6)
(8) T(5)(7) I
(9) (8)

（4）命题符号化为：F(x)：x坐头等舱, G(x)：x坐经济舱，H(x)：x富裕。
前提：，，，
结论：.
证明：(1) P
(2) (1)
(3) P
(4) (3)
(5) T(2)(4)I
(6) P
(7) (6)
(8) T(5)(7)I
(9) (8)

5. 令谓词、、和分别表示“是婴儿”，表示“的行为符合逻辑”、“能管理鳄鱼”和“被人轻视”，个体域为所有人的集合。用、、、、量词和逻辑联接词符号化下列语句。
（1）婴儿行为不合逻辑。
（2）能管理鳄鱼的人不被人轻视。
（3）行为不合逻辑的人被人轻视。
（4）婴儿不能管理鳄鱼。
请问，能从（1）、（2）和（3）推出（4）吗？若不能，请写出（1）、（2）和（3）的一个有效结论，并用演绎推理法证明之。
解：（1）
（2）
（3）
（4）
能从（1）（2）（3）推出（4）。
证明：（1） P(x) 前提假设
（2） 前提引入
（3） T 规则：(1)，(2)
（4） P规则
（5） T 规则：(3)，(4)
（6） P规则
（7） 拒取式
（8） 规则