谓词演算的推理理论课件

第6讲§2—7谓词演算的推理理论

要求：熟练掌握谓词的推理理论与推理方法，会用谓词的推理理论与推理方法进行推理。

重点：应用谓词的推理理论与推理方法进行推理。

难点：正确理解和运用有关量词规则。

谓词逻辑是命题逻辑的进一步深化和发展，谓词演算的推理方法，可以看作是命题演算推理方法的扩张。因此命题逻辑的推理理论在谓词逻辑中几乎可以完全照搬，只不过这时涉及的公式是谓词逻辑的公式罢了。在谓词逻辑中，某些前提和结论可能受到量词的约束，为确立前提和结论之间的内部联系，有必要消去量词和添加量词，因此正确理解和运用有关量词规则是谓词逻辑推理理论中十分重要的关键所在。一、有关量词消去和添加规则量词消去规则（证前去量词）：(1)

全称量词消去规则(称为全称指定规则，简称US规则)(x)A(x)A(c)：其中c为论域中任意个体常元（举例说明）(2)

存在量词消去规则(称为存在指定规则，简称ES规则)(x)A(x)A(c)：其中c为论域中的某些特定的个体常元，它不是任意的。c不得在前提中或者居先推导公式中出现或自由出现。（举例说明：存在一些人是男生，存在一些人是女生）量词产生规则（证后加量词）：(3)

存在量词产生规则(称为存在推广规则，简称EG规则)A(c)(y)A(y)其中c为论域中特定个体常元

(4)

全称量词产生规则(称为全称推广规则，简称UG规则)A(c)(y)A(y)若能证明对论域中每一个客体c断言A(c)都成立，则全称推广规则可得到结论(y)A(y)成立。二、Lp中推理实例：

Lp的推理方法是Ls推理方法的扩展，因此在Lp中利用的推理规则：（1）T规则、P规则和CP规则（2）已知的等价式，蕴含式（3）有关量词的消去和产生规则。使用的推理方法是：直接构造法和间接证法（不能用真值表）。

所有谓词的推理，均可先忽略量词，按命题逻辑中分析基本思路及所用方法，然后再注意证前去量词，证后加量词，并注意次序即可例题1

证明苏格拉底论证：所有的人都是要死的。苏格拉底是人。所以苏格拉底是要死的。解设H(x)：x是一个人。

M(x)：x是要死的。

s：苏格拉底。故苏格拉底论证可符号化为：(x)(H(x)→M(x))∧H(s)M(s)证明(1)(x)(H(x)→M(x))P(2)H(s)→M(s)

US(1)(3)H(s) P(4)M(s) T(2)(3)I例题2

证明证明(x)(C(x)→W(x)∧R(x))∧(x)(C(x)∧Q(x))(x)(Q(x)∧R(x))(1)(x)(C(x)→W(x)∧R(x))P(2)(x)(C(x)∧Q(x))P(4)C(a)→W(a)∧R(a)US(1)(3)C(a)∧Q(a)ES(2)(5)C(a)T(3)I(6)W(a)∧R(a)T(4)(5)I(7)Q(a)T(3)I(8)R(a)T(6)I(9)Q(a)∧R(a)T(7)(8)I(10)(x)(Q(x)∧R(x))EG（9）注意（3）（4）两条次序不能颠倒。（1）原来的作用变元相同：若先用ES后用US，可用同一常元也可用不同常元（按需决定）； 若先用US后用ES，必用不同常元; 若几个ES在一起，必用不同常元． 若几个US在一起，可用相同常元也可用不同常元（按需决定）（2）原来作用变元不同： 无论顺序如何，ＥＳ或ＵＳ后，常元必不同例题3

证明(x)(P(x)∨Q(x))(x)P(x)∨(x)Q(x)方法（１）：用反证法（假定┐C为T，推出矛盾）(1)┐((x)P(x)∨(x)Q(x))P(附加前提)(2)(x)┐P(x)∧(x)┐Q(x)T(1)E(3)(x)┐P(x)

T(2)I(4)(x)┐Q(x)T(2)I(5)┐P(c)

ES(3)(6)┐Q(c)US(4)(7)┐P(c)∧┐Q(c)T(5)(6)I(8)┐(P(c)∨Q(c))T(7)E(9)(x)(P(x)∨Q(x))P(10)P(c)∨Q(c)US(9)(11)┐(P(c)∨Q(c))∧(P(c)∨Q(c))(矛盾)T(8)(10)I方法（２）：用CP规则原题可转为：(x)(P(x)∨Q(x))┐(x)P(x)(x)Q(x)(要证SRC

，也就是证明(S∧R)C。)(1)┐(x)P(x)

P（附加前提）(2)(x)┐P(x)

T（1）E(3)┐P(c)

ES(2)(4)(x)(P(x)∨Q(x))P(5)P(c)∨Q(c)US(3)(6)Q(c)T(3)(5)I(7)(x)Q(x)

EG(6)(8)┐(x)P(x)(x)Q(x)CP例题4

构造下面推理的证明：每个学术会的成员都是专家并且是工人，有些成员是青年人，所以有些成员是青年专家。证明设P(x)：x是学术会的成员。Q(x)：x是专家。R(x)：x是工人。S(x)：x是青年人。证明过程如下：则本题要证明：(x)(P(x)→Q(x)∧R(x))，(x)(P(x)∧S(x))(x)(P(x)∧Q(x)∧S(x))(1)(x)(P(x)∧S(x))P(2)P(a)∧S(a)ES(1)(3)P(a)T(2)I(4)S(a)T(2)I(5)(x)(P(x)→Q(x)∧R(x))P(6)P(a)→Q(a)∧R(a)US(5)(7)Q(a)∧R(a)T(3)(6)I(8)Q(a)T(7)I(9)P(a)∧Q(a)∧S(a)T(3)(4)(8)I(10)(x)(P(x)∧Q(x)∧S(x))EG(9)例5

任何人违反了交通规则都要处以罚款，如果没有罚款，就没有人违反交通规则。解：S(x,y)：x违反了y（x的论域是人）Ｍ(y)：y是交通规则，

P(z)：z是罚款

R(x,z)：x受到z。则问题符号化为：Ｈ：(

x)((y)(S(x,y)∧M(y))→(z)(P(z)∧R(x,z)))

Ｃ：┐(

z)P(z)→(x)(

y)(S(x,y)→┐

M(y))（可改为存在量词，并把非提前，与陈述更接近，更好理解）由于结论为条件式，故用CP规则推理。(1)(x)((y)(S(x,y)∧M(y))→(z)(P(z)∧R(x,z)))P(2)(y)(S(b,y)∧M(y))→(z)(P(z)∧R(b,z))

US(1) (3)┐(

z)P(z) P（附加前提）(4)(z)┐

P(z)

T(3)E(5)┐

P(a) US(4)(6)

┐

P(a)

∨┐R(b,a)

T(5)I(7) (

z)(

┐

P(z)∨

┐

R(b,z))

UG(6)(8)

┐(z)(

P(z)∧

R(b,z))

T(7)E(9) ┐(y)(S(b,y)∧M(y))

T(2)(8)I(10)(y)(┐

S(b,y)∨

┐

M(y))

T(9)E(11)

(y)(S(b,y)→┐

M(y))

T(10)E(12)

（

x)

(y)(S(x,y)→┐

M(y))

UG(11)┐(

z)P(z)→(x)(y)(S(x,y)→┐M(y)) CP例中（7）（8），（9）（10），（10）（11）都是错误步骤。其中（7）（8），（9）（10）还犯了省略步骤的错误。在推理过程中，谓词公式只能用表２－１所列的蕴含式与等价式；除表中所列的带量词的公式外，一般的不能在量词后面的辖域内进行蕴含推证或等价变换，因此必须消除量词后，才能对谓词公式进行蕴含或等价推证；在作了适当的推演后，再恢复约束关系，以完成带量词公式的逻辑推证．(1)(x)((y)(S(x,y)∧M(y))→(z)(P(z)∧R(x,z)))P(2)(y)(S(b,y)∧M(y))→(z)(P(z)∧R(b,z))

US(1) (3)┐(

z)P(z) P（附加前提）(4)(z)┐

P(z)

T(3)E(5)┐

P(a) US(4)(6)

┐

P(a)

∨┐R(b,a)

T(5)I(7)┐(

P(a)∧

R(b,a))

T(6)E

(8)(z)┐(

P(z)∧

R(b,z))

UG(7)(9)┐(z)(

P(z)∧

R(b,z))

T(8)E(10)

┐(y)(S(b,y)∧M(y))

T(2)(9)I(11)(y)┐(S(b,y)∧M(y))T(10)I(12)

┐(S(b,

c)∧M(c))

US(11)

(13)

┐S(b,c)∨

┐

M(c)

T(12)E(14)

S(b,c)→┐

M(c)

T(13)E(15)(

y)(S(b,y)→┐

M(y))

UG(14)(16)(

x)

(y)(S(x,y)

→┐

M(y))

UG(15)

(17)┐(z)P(z)→(x)(y)(S(x,y)→┐M(y))CP数理逻辑在计算机科学中的用途：(1)作为知识表示的手段，因为日常生活中的或数学领域中的命题，大多能用谓词逻辑的符号表达式，便于计算机处理；(2)

研究形式推理，为计算机进行自动推理提供方法和理论。

第二个用途过于专门和复杂，已超过本课程教学大纲的要求。但是，第