第11讲 谓词公式的等值,前束范式及推理 1.谓词公式的等值. 2.谓词公式的前束范式. 3.谓词逻辑中的推理.

4.4 逻辑等值的谓词公式 1.谓词公式等值的定义 与两个命题公式等值完全类似,有 4.4 逻辑等值的谓词公式 1.谓词公式等值的定义 与两个命题公式等值完全类似,有 Def 4-3(P125) 设A和B是谓词公式, 若A和B在任何解释下的取值都相同, 则称A和B是等值的,记为 A = B. 显然, A = B的充要条件是谓词公式A  B永真.

根据命题逻辑中的等值式容易得到一些谓词逻辑中的等值式. 例如,对于命题变元p 和q,有p  q = p  q,因为p  q  p  q永真, 所以对于谓词公式A和B, 有A  B  A  B, 进而有A  B = A  B. 照这种方式, 可以得到很多的谓词逻辑中的等值式.

2.基本等值式(remember) 10个与量词有关谓词逻辑中的基本等值式. I. 量词转换 (1)xA(x) = xA(x). (2)xA(x) = xA(x). 例举例说明I(1)(2)成立. Solution 令D是全班所有同学组成的集合, A(x): x今天来上课, 则“并非每位同学今天都来上课”逻辑等价于“有同学今天没有来上课”, “并非有同学今天来上课”逻辑等价于“每位同学今天都没有来上课”.

II. 量词辖域的收缩与扩张 设B中不含自由变元x,则有 (1) x(A(x)  B) = xA(x)  B. (2) x(A(x)  B) = xA(x)  B. (3) x(A(x)  B) = xA(x)  B. (4) x(A(x)  B) = xA(x)  B. 首先要说明的是, A(x){单独看A(x)!}含自由变元x, 而B中不含自由变元x,但A(x)和B都可能含其他自由变元.

就(1)来说, 左边x的辖域为A(x)  B, 右边x的辖域为A(x), 从左边到右边量词的辖域收缩了, 而从右边到左边量词的辖域扩张了. (1)的证明? 对于任意的个体域D上的解释I,假定x(A(x)  B)真,则对于任意dD, A(d)  B真,于是A(d)和B都为真,所以xA(x)和B取真,因此xA(x)  B真. 反过来亦成立.

例4-13(P126) 证明下列与蕴涵联结词有关的4个等值式,其中B中不含自由变元x. (1) x(A(x)  B) =  xA(x)  B. (2) x(B  A(x) ) = B  xA(x). (3) x(A(x)  B) = xA(x)  B. (4) x(B  A(x) ) = B  xA(x) . Proof (3)

(1)x(A(x)  B(x)) = xA(x)  xB(x). III. 量词分配(?)律 (1)x(A(x)  B(x)) = xA(x)  xB(x). (2)x(A(x)  B(x)) = xA(x)  xB(x). Remark (1)x(A(x)  B(x))  xA(x)  xB(x). (2)x(A(x)  B(x))  xA(x)  xB(x). 在给定解释I: D = Z, A(x): x是偶数, B(x): x是奇数. How to understand? D = {班上同学}, A(x): x会唱歌, B(x): x会跳舞.

Proof (2)任意给定个体域D上的解释I, 若x(A(x)  B(x))在I下取真, 则存在dD, 使得A(d)  B(d), 于是A(d)或B(d)为真,因此xA(x) 或xB(x)取真,进而xA(x)  xB(x)真. 反过来亦成立(?).

IV. 双重量词 (1) xyA(x, y) = yxA(x, y). (2) xyA(x, y) = yxA(x, y). Remark xyA(x, y)  yxA(x, y). D = R. A(x, y): x > y.

例4-14 xy(A(x)  B(y)) = xA(x)  yB(y). Proof 最后要说明的是, 等值置换定理在谓词逻辑中仍然成立.

4.5 谓词公式的前束范式 讨论谓词公式的标准形式是很有意义的. 4.5 谓词公式的前束范式 讨论谓词公式的标准形式是很有意义的. 我们仅讨论谓词公式的前束范式. 实际上, 在前束范式的基础上, 可以进一步得出谓词公式的Skolem范式, 进而得出一个谓词公式永真(假)在有限步内可判定的著名结论(Church & Turing).

1.谓词公式的(前+束)范式的定义 Def 设A是谓词公式, 若 直观地理解, 谓词公式的前束范式是将所有量词放在最前面, 去作用整个B.

2.谓词公式的前束范式的计算 前束范式的计算步骤如下: Step1 将逻辑联结词归约到只含, , 的谓词公式. 因为在要求记住的谓词逻辑等值式中,没有出现除, , 外的其他联结词. Step2 使用以下两个等值式将否定联结词往里面移: (1)xA(x)=xA(x). (2)xA(x)=xA(x). Step3 使用等值式将所有量词移到最前面, 必要时使用改名技巧.

例4-15 求xA(x)  xB(x)的前束范式. Solution xA(x)  xB(x) = x(A(x)  B(x)). 例4-16 求xA(x) xB(x)的前束范式. xA(x) xB(x) = xA(x) xB(x) =xA(x) xB(x) =x(A(x)  B(x)).

例4-17 求xA(x)  xB(x)的前束范式. Solution xA(x)  xB(x) = xA(x)  yB(y) =x(A(x)  yB(y)) = xy(A(x)  B(y)) 采用改名的技巧总可以利用等值式得出前束范式, 但要求前束范式中的量词要尽可能地少.

例4-18 求xF(y, x)  yG(y)的前束范式. Solution xF(y, x)  yG(y) = xF(y, x)  yG(y) = xF(y, x)  yG(y) =x(F(y, x)  yG(y)) = x(F(t, x)  yG(y)) = xy (F(t, x)  G(y)).

4.6 谓词逻辑中的推理 1.逻辑蕴涵式 首先,根据命题逻辑中的逻辑蕴涵式可以产生谓词逻辑的逻辑蕴涵式. 如在命题逻辑中有p  q, p  q,则(p  q)  p  q永真,对于谓词公式A和B, (A  B)  A  B永真,从而有A  B, A  B.

其次,可以得出与量词有关的一些逻辑蕴涵式. 例4-19 证明xA(x)  A(t). Proof 因为由4.3节例2知, xA(x)  A(t)永真. 例4-20 证明xyA(x, y)  yxA(x, y). Proof 任意给定个体域D上的解释I, 假定在该解释下xyA(x, y)取1, 则存在d0  D, 对于任意d D,有A(d0, d)为1, 所以yxA(x, y)为1. 因此,xyA(x, y)  yxA(x, y)永真. 故之.

例4-21 证明yxA(x, y)不是xyA(x, y)的有效结论. Proof D = R, A(x, y): x > y +3. yxA(x, y)? xyA(x, y)? xyA(x, y)  yxA(x, y)?

命题逻辑中的基本推理规则可以很方便地推广到谓词逻辑, 参见上章3.7节. 谓词逻辑中有两个非常重要与量词有关的逻辑蕴涵式. 2.基本推理规则 命题逻辑中的基本推理规则可以很方便地推广到谓词逻辑, 参见上章3.7节. 谓词逻辑中有两个非常重要与量词有关的逻辑蕴涵式. Theorem 4-1 下列逻辑蕴涵式成立: (1)xA(x)  xB(x)  x(A(x)  B(x)). (2)x(A(x)  B(x))  xA(x)  xB(x). How to understand? D = {班上同学}, A(x): x会唱歌, B(x): x会跳舞.

例4-22(P130) 证明或反驳下列结论. (1)xA(x)  xA(x). (2)x(A(x)  B(x))  xA(x)  xB(x). Solution (1)D = Z, A(x): x是偶数. (2)D = {1, 2}, x(A(x)  B(x)) = 1? xA(x)  xB(x) = 0?

3.谓词逻辑的自然推理系统 谓词逻辑的自然推理系统是命题逻辑的自然推理系统的一种推广. 初始符号增加了函词、谓词、量词；谓词公式的形成规则参见4.2节谓词公式的定义；没有公理；基本推理规则增加定理4-1中两个逻辑蕴涵式,以及下述4个与量词有关的基本推理规则. 我们以最简洁的方式加以介绍.

I. US(Universal quantifier Specification)规则: 全称量词消去规则 (1)xA(x) (2)A(c) (其中c为个体域中任意个体) II.UG(Universal quantifier Generalization)规则: 全称量词产生规则 (1)A(c) (其中为个体域中任意个体) (2)xA(x)

III.ES(Existential quantifier Specification)规则: 存在量词消去规则 (1)xA(x) (2)A(c) (其中c为个体域中某个体) Remark 由xA(x)推出A(c), 要确保c与其他自由变元无关. IV.EG(Existential quantifier Generalization)规则: 存在量词产生规则 (1)A(c) (其中c为个体域中某个体) (2)xA(x)

例4-23 证明苏格拉底三段论推理的有效性. Proof 用s:苏格拉底, P(x): x是人, D(x): x是要死的, (1)P(s) P (2)x(P(x)  D(x)) P (3)P(s)  D(s) US(2) (4)D(s) T(1)(3)

例4-24 用构造法证明以下推理: x(F(x)  G(x)), xF(x)  xG(x). Proof (1)xF(x) P (2)F(c) ES(1) (3)x(F(x)  G(x)) P (4)F(c)  G(c) US(3) (5)G(c) T(2)(4)I (6)xG(x) EG(5)

Remark (1)(2)与(3)(4)的顺序不能颠倒 Remark (1)(2)与(3)(4)的顺序不能颠倒. (2)中F(c)中的c是某个体, (4)中F(c)  G(c)中的c本来是任意个体, 现取为(2)中出现的c, 这是可以的. 但反过来就不行. 避免这种错误的最好方法是象上面的证明过程一样, 先消去存在量词, 再消去全称量词.

例4-25(P131) 用构造法证明以下推理: x(F(x)  H(x)), x(G(x)  H(x))  x(G(x)  F(x)). Proof (1)x(F(x)  H(x)) P (2)  x(F(x)  H(x)) T(1)E (3)F(c)  H(c) US(2) (4) H(c)  F(c) T(3)E (5) x(G(x)  H(x)) P (6) G(c)  H(c) US(5) (7) G(c)  F(c) T(4)(6)I (8) x(G(x)  F(x)) UG(7)

例4-26 设个体域D为所有人组成的集合,在谓词逻辑中符号化下列各命题,并用构造法证明以下推理: 每位科学家都是勤奋的,每个勤奋且身体健康的人在事业上都会获得成功,存在身体健康的科学家, 所以存在事业获得成功或事业半途而废的人. Solution 令Q(x): x是勤奋的, F(x): x是健康的, S(x): x是科学家, C(x): x是事业获得成功的人, F(x): x是事业半途而废的人,则

关于多重量词的推理,需要注意的问题比较多. 例4-27(P132) 指出下列推理步骤中的错误. (1)xy(x > y) P (2)y(c > y) US(1) (3)c > d ES(2) (4)x(x > d) UG(3) (5)yx(x > y) EG(4)

Solution (3)错. 在(2)中的c是个体域中任意个体,实际上是自由变元,当由(2)消去存在量词y时,不能利用ES规则 Solution (3)错. 在(2)中的c是个体域中任意个体,实际上是自由变元,当由(2)消去存在量词y时,不能利用ES规则. 换句话说,(3)中所得到的d与c密切相关. 已经有例子表明, xyA(x, y)  yxA(x, y)不是永真式.