下载文档原格式
谓 词 逻 辑《应用离散数学》第2章21世纪高等教育计算机规划教材目录2.1 个体词、谓词与量词2.2 谓词公式及其解释2.3 谓词公式的等价演算2.4 谓词公式的推理演算在命题逻辑中，命题是最基本的单位，对原子命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。
因而命题逻辑具有局限性，甚至无法判断一些简单而常见的推理。
例如，考虑下面著名的苏格拉底三段论：● 所有的人都是要死的。
● 苏格拉底是人。
● 所以，苏格拉底是要死的。
这个推理是公认的真理，但在命题逻辑中却无法判断它的正确性。
因为在命题逻辑中只能将推理中出现的三个原子命题依次符号化为p ， q ， r ，将推理的形式结构符号化为由于上式不是永真式，所以不能由它判断推理的正确性。
命题逻辑无法准确描述这个推理过程，原因在于命题逻辑本身未对各原子命题之间的内部成分的逻辑关系加以研究。
为了更准确地对命题进行符号化，我们需要把一个逻辑判断的对象和谓语分离并细化，分析出其中的个体词、谓词和量词，研究它们的形式结构和逻辑关系、推理规则和推理形式，这就是本章的基本内容。
2.1.1 个体词与谓词定义2.1 在原子命题中，表示对象的词称为个体词；表示对象所具有的性质或多个对象之间关系的词称为谓词。
个体词一般是原子命题中的主语或宾语。
个体词可以是具体事物，也可以是抽象的概念，例如，小王，夏天，偶数，思想等都可以作为个体词。
特定的个体词称为个体常元，用小写字母 a ， b， c ， L 或 表示；不确定的个体词称为个体变元，用小写字母 x ， y ， z ， L或 表示。
谓词一般是原子命题中的谓语，通常用大写字母 或 表示。
含有n 个 个体变元的谓词称为n元谓词，也称为n元简单命题函数，通常记为 。
它实际上是 到{0，1}的一个函数，其中D i是个体变元x i的个体域。
所谓个体域就是个体变元遍历的非空集合。
一般地，个体域应事先给定，如果没有给定，则约定个体域是全体事物构成的集合，称为全总个体域。
§2.2 谓词公式及其解释习题2.21. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。
（1）))()((y x Q x P x ，→∀ （2）)()(y x yQ y x xP ，，∃→∀（3）)())()((z y x xR z y Q y x P y x ，，，，∃∨∧∃∀解 （1）x ∀中的x 是指导变元；量词x ∀的辖域是),()(y x Q x P →；x 是约束变元，y 是自由变元。
（2）x ∀中的x ，y ∃中的y 都是指导变元；x ∀的辖域是)(y x P ，，y ∃的辖域是)(y x Q ，；)(y x P ，中的x 是x ∀的约束变元，y 是自由变元；)(y x Q ，中的x 是自由变元，y 是y ∃的约束变元。
（3）x ∀中的x ，y ∃中的y 以及x ∃中的x 都是指导变元；x ∀的辖域是))()((z y Q y x P y ，，∧∃，y ∃的辖域是)()(z y Q y x P ，，∧，x ∃的辖域是)(z y x R ，，；)(y x P ，中的x ，y 都是约束变元；)(z y Q ，中的y 是约束变元；z 是自由变元，)(z y x R ，，中的x 为约束变元，y ，z 是自由变元。
2. 设个体域}21{，=D ，请给出两种不同的解释1I 和2I ，使得下面谓词公式在1I 下都是真命题，而在2I 下都是假命题。
（1）))()((x Q x P x →∀（2）))()((x Q x P x ∧∃解（1）解释1I ：个体域}21{，=D ，0:)(,0:)(>>x x Q x x P 。
（2）解释2I ：个体域}21{，=D ，2:)(,0:)(>>x x Q x x P 。
3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。
（1）)))()(()((y x R y Q y x P x ，∧∃→∀ （2）)),()()((y x R y Q x P y x →∧∀∀解 （1）成真解释：个体域D ＝{1,2,3},0:)(<x x P ,2:)(>y y Q ,3:),(>+y x y x R 。
§2.2 谓词公式及其解释
习题2.2
1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。
（1）))()((y x Q x P x ，→∀ （2）)()(y x yQ y x xP ，，∃→∀
（3）)())()((z y x xR z y Q y x P y x ，，，，∃∨∧∃∀
解 （1）x ∀中的x 是指导变元；量词x ∀的辖域是),()(y x Q x P →；x 是约束变元，y 是自由变元。
（2）x ∀中的x ，y ∃中的y 都是指导变元；x ∀的辖域是)(y x P ，，y ∃的辖域是
)(y x Q ，；)(y x P ，中的x 是x ∀的约束变元，y 是自由变元；)(y x Q ，中的x 是自由变元，
y 是y ∃的约束变元。
（3）x ∀中的x ，y ∃中的y 以及x ∃中的x 都是指导变元；x ∀的辖域是
))()((z y Q y x P y ，，∧∃，y ∃的辖域是)()(z y Q y x P ，，∧，x ∃的辖域是)(z y x R ，，；)(y x P ，中的x ，y 都是约束变元；)(z y Q ，中的y 是约束变元；z 是自由变元，
)(z y x R ，，中的x 为约束变元，y ，z 是自由变元。
2. 设个体域}21{，=D ，请给出两种不同的解释1I 和2I ，使得下面谓词公式在1I 下都是真命题，而在2I 下都是假命题。
（1）))()((x Q x P x →∀
（2）))()((x Q x P x ∧∃
解（1）解释1I ：个体域}21{，=D ，0:)(,0:)(>>x x Q x x P 。
（2）解释2I ：个体域}21{，=D ，2:)(,0:)(>>x x Q x x P 。
3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。
（1）)))()(()((y x R y Q y x P x ，∧∃→∀ （2）)),()()((y x R y Q x P y x →∧∀∀
解 （1）成真解释：个体域D ＝{1,2,3},0:)(<x x P ,2:)(>y y Q ,3:),(>+y x y x R 。
成假解释：个体域D ＝{1,2,3},0:)(>x x P ，2:)(>y y Q ，1:),(<+y x y x R 。
（2）成真解释：个体域D ＝{1,2,3}，0:)(<x x P ，2:)(>y y Q ，3:),(>+y x y x R 。
成假解释：个体域D ＝{1,2,3},0:)(>x x P ，0:)(>y y Q ，1:),(<+y x y x R 。
4. 给定解释I 如下： 个体域R =D （这里R 为实数集合）。
个体常元0=a 。
二元函数y x y x f -=)(，。
二元谓词y x y x P =：，)(，y x y x Q <：，)(。
在解释I 下，下列公式的含义是什么？哪些成为命题哪些不成为？成为命题的其真值又如何？ （1）))()((y x P y x Q y x ，，⌝→∀∀ （2）))())(((y x Q a y x f P y x ，，，→∀∀ （3）)))(()((a y x f P y x Q y x ，，，⌝→∀∀
（4）))())(((y x P a y x f Q y x ，，，→∀∀
解（1）公式被解释成“)(y x y x y x ≠→<∀∀”，为真命题。
（2）公式被解释成“)0(y x y x y x <→=-∀∀”，为假命题。
（3）公式被解释成“)0(≠-→<∀∀y x y x y x ”，为真命题。
（4）公式被解释成“)0(y x y x y x =→<-∀∀”，为假命题。
5. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。
（1）)()(x xP x P ∃→ （2）)()(x P x xP →∃ （3）)()(x xP x P ∀→
（4）)()(x P x xP →∀
（5）))()((x P x P x ⌝→∀
（6）)()(y x xP y y x yP x ，，∀∀→∀∀ （7）)()(x y yP x y x yP x ，，∀∀→∀∀ （8）)()(y x yP x y x yP x ，，∀∃→∃∀
（9）)()(y x xP y y x yP x ，，∃∀→∀∃
（10）))()((x y P y x P y x ，，→∀∀
解（1）因为当存在某个x 使)(x P 取1时)(x xP ∃一定取1，所以公式是为永真式。
（3）取解释1I ：个体域为自然数集合，0)(2
≥x x P ：。
在1I 下公式的前件与后件均为真，所以公式为真，即不是永假式。
取解释2I ：个体域仍为自然数集合，但)(x P 取为0>x 。
在2I 下公式不成为命题，即不是永真式。
综合知公式为可满足式。
（5）取解释1I ：个体域为自然数集合，0)(2
≥x x P ：。
在1I 下，对任意的x ，)(x P 为真而)(x P ⌝为假，所以公式为假，即不是永真式。
取解释2I ：个体域仍为自然数集合，但)(x P 取为02
<x 。
在2I 下，对任意的x ，)(x P 为假而)(x P ⌝为真，所以公式为真，即
不是永假式。
综合知公式为可满足式。
（7）公式为永真式，用非形式化的反证法证明如下：若公式非永真，则存在一个解释，使得)(y x yP x ，∀∀取1而)(x y yP x ，∀∀取0。
)(x y yP x ，∀∀取0表明存在某对00,y x 使得)(00x y P ，取0，从而)(y x yP x ，∀∀也应取0。
这与前面说)(y x yP x ，∀∀取1矛盾。
故公式是永真式。
（9）
设I 为任意一个解释，个体域为D 。
若)(y x yP x ，∀∃取1，即存在D x ∈0，
使得)(0y x yP ，∀为真，从而)(y x xP y ，∃∀为真，故)()(y x xP y y x yP x ，，∃∀→∀∃为真。
所以在解释I 下公式为真，由I 的任意性可知，公式为永真式。
（2）、（4）、（6）、（8）、（10）略。
6. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。
（1）))()(())()((y yQ x xP x Q x P x ∀∧∀→∧∀ （2）))()(())()((y yQ x xP x Q x P x ∀∨∀→∨∀ （3）)())()((y yQ y yQ x xP ∃∧∃→∀⌝ （4）))()(())()((x xQ y P x Q y P x ∀→→→∀ （5）))()(())()((x xQ x P x Q x P x ∀→→→∀ （6）)))()(()((x P y x yQ x P →∀→⌝， （7）))()(()(y x P y x Q y x P ，，，→→ 解 略 7. 给出一个非闭式的永真式，给出一个非闭式的永假式，给出一个非闭式的可满足式。
解 略。
