2.6 谓词逻辑的推理

2.6.1 推理理论

谓词逻辑的推理形式同命题逻辑一样，若（ A ₁ ∧ A ₂ ∧…∧ A _n ）→ B 是永真式，则称由前提 A ₁ ， A ₂ ，…， A _n 可推出结论 B ，可表示为（ A ₁ ∧ A ₂ ∧…∧ A _n ）⇒ B 。但谓词逻辑的推理要更为复杂。在命题逻辑的推理中使用的等价关系、蕴涵关系和推理规则在谓词逻辑的推理中同样适用，另外还有谓词演算特有的关于量词的规则。

1.全称量词消去规则 （ UI ）

全称量词消去规则为

∀ xA （ x ）⇒ A （ y ）

成立的条件为：

1） x 是 A （ x ）中自由出现的个体变元；

2） y 是任意的不在 A （ x ）中约束出现的个体变元。

由于 y 具有任意性， y 可以是个体域中的任意个体 c ，因此这个规则还可表示为∀ xA （ x ）⇒ A （ c ）。在推理过程中，两种形式可根据需要选用。

使用时，要注意规则成立条件。例如，若 A （ x ）⇔∃ yF （ x ， y ），则∀ xA （ x ）⇔∀ x ∃ yF （ x ， y ），利用UI规则∀ xA （ x ）⇒ A （ y ），于是∀ x ∃ yF （ x ， y ）⇒∃ yF （ y ， y ），如假设在实数集上 F （ x ， y ）： x ＞ y ，∀ x ∃ yF （ x ， y ）是真命题，而∃ yF （ y ， y ）是假命题，这个蕴含式不成立，原因是使用UI规则时违背了条件2）。

2.存在量词消去规则 （ EI ）

存在量词消去规则为

∃ xA （ x ）⇒ A （ c ）

成立的条件为：

1） c 是个体域中使 A 成立的特定的个体常元；

2） c 不曾在 A （ x ）中出现过；

3） A （ x ）中除 x 外还有其他自由出现的个体变元时，不能用此规则。

注意这里的 c 是使 A 成立的特定的个体常元，不要和公式中或推理证明过程中前面步骤的其他常元和变元名称相同。

例如在实数集上 F （ x ， y ）： x ＞ y ，若 A （ x ）⇔ F （ x ， c ）， c 是实数集上的一个常数，则∃ xA （ x ）为真，利用EI规则，消去量词，用 c 取代 x ，得 F （ c ， c ），这是假命题，原因是违背了条件2）。

3.全称量词引入规则 （ UG ）

全称量词引入规则为

A （ y ）⇒∀ xA （ x ）

成立的条件为：

1） y 是 A （ y ）中自由出现的个体变元， y 取个体域中的任何值 A 都为真；

2）取代 y 的 x 不能在 A （ x ）中约束出现。

例如，在实数集上 F （ x ， y ）： x ＞ y ，若 A （ y ）⇔∃ xF （ x ， y ），则对任意的 y ， A （ y ）为真，用UG规则，用 x 取代 y ，得∀ x ∃ xF （ x ， x ），显然这是假命题，原因是违背了条件2）。

当能够证明个体域中的任一个体都使 A （ x ）为真时，才能应用此规则引入全称量词。

4.存在量词引入规则（EG）

存在量词引入规则为

A （ c ）⇒∃ xA （ x ）

成立的条件为：

1） c 是特定的个体常元；

2）取代 c 的 x 不能在 A （ c ）中出现过。

例如，在实数集上 F （ x ， y ）： x ＞ y ，若 A （2）⇔∃ xF （ x ，2），则 A （2）为真，利用EG规则，用 x 取代2，得∃ xF （ x ， x ），显然这是假命题，原因是违背了条件2）。

注意上述4条规则仅对谓词公式的前束范式适用。应用上述规则和命题逻辑中的推理规则，可以证明谓词逻辑的推理问题。

2.6.2 推理问题的证明

谓词逻辑的推理问题的证明本质上和命题逻辑的推理问题的证明相同。

例2.6.1 证明 。

证明 利用CP规则，证明 。

例2.6.1主要利用了谓词公式的等价式、命题逻辑等价式和蕴含式的代换实例进行推演。在有些谓词逻辑推理时，可用量词消去规则先把量词去掉，变为命题逻辑的推理推出结论；若推出的结论带有量词，可利用量词引入规则把量词附加上去。

例2.6.2 证明“所有计算机专业的学生都喜欢编程，小明是计算机专业的学生，所以小明喜欢编程”是正确的推理。

证明 设 M （ x ）表示 x 是计算机专业的学生， P （ x ）表示 x 喜欢编程， a 表示小明。

上述推理问题的前提符号化为∀ x （ M （ x ）→ P （ x ））、 M （ a ）。结论可符号化为 P （ a ）。因此，需要证明 P （ a ）是∀ x （ M （ x ）→ P （ x ））和 M （ a ）的结论。

证明过程如下：

例2.6.3 证明“所有的舞蹈者都很有风度，有些学生是舞蹈者，因此有些学生很有风度”是正确的推理。

证明 设 P （ x ）表示 x 是个舞蹈者， Q （ x ）表示 x 很有风度， S （ x ）表示 x 是个学生。

上述推理问题的前提符号化为∀ x （ P （ x ）→ Q （ x ））、∃ x （ S （ x ）∧ P （ x ））。结论可符号化为∃ x （ S （ x ）∧ Q （ x ））。

证明过程如下：

例2.6.4 说明下面推理中的错误，并指出错误的原因。

解 错误在4）用EI规则时，用 c 取代 x ， c 在前面步骤已用于特指使 P 为真的个体，在这里不一定能使 Q 为真。

正确的推理步骤是：

蕴含式∃ xP （ x ）∧∃ xQ （ x ）⇒∃ x （ P （ x ）∧ Q （ x ））不成立。例如，假设 P （ x ）表示 x 是正数， Q （ x ）表示 x 是负数，在实数集的个体域中，∃ xP （ x ）和∃ xQ （ x ）都是真命题，∃ x （ P （ x ）∧ Q （ x ））是假命题。

◀

例2.6.5 说明下面推理中的错误，并指出错误的原因。

解 推理的错误是2）使用全称指定规则时引入了常量 c ，在4）使用存在指定规则时又引入了常量 c 。正确的推理步骤是：

注意，在推理过程中，应先使用EI规则，后使用UI规则。

例2.6.6 下面的推理是否正确？为什么？

解 不正确。错在3），因为∃ yF （ z ， y ）中 z 是自由变元，不能使用EI规则。

例如，假设在实数集上 F （ x ， y ）： x ＞ y ，∀ x ∃ yF （ x ， y ）表示所有的实数都有比它小的实数，是真命题；∀ xF （ x ， b ）表示所有实数都大于某个确定的实数 b ，是假命题。因此这个推理不正确，违反了EI规则的使用条件3），∃ y 的辖域 F （ z ， y ）有自由变元 z 。

◀

例2.6.7 用演绎法证明推理式：∀ x （ P （ x ）∨ Q （ x ））， 。

证明 证明步骤如下： IKOmj4vin5rWEJJW6oMcyXphl0Cwo/0Q52S35co2hnV+uClyGDLT+VwmBCv2Fdo1