《一阶逻辑等值式与前束范式》由会员分享，可在线阅读，更多相关《一阶逻辑等值式与前束范式（20页珍藏版）》请在金锄头文库上搜索。
1、12.3 一阶逻辑等值式与前束范式一阶逻辑等值式与前束范式 等值式等值式基本等值式基本等值式前束范式前束范式 2等值式与基本等值式等值式与基本等值式 命题逻辑中命题逻辑中24个基本等值式的代换实例，个基本等值式的代换实例，如，如， xF(x)yG(y) xF(x)yG(y) ( xF(x)yG(y) xF(x)yG(y) 等等 定义定义 若若AB为永真式（逻辑有效式），则称为永真式（逻辑有效式），则称A与与B是是等值等值的，记作的，记作 AB，并称并称AB为为等值式等值式. 3基本等值式基本等值式:1. 消去量词等值式消去量词等值式 设设D = a1, a2, , an 1) xA(x)A(a
2、1) A(a2) A(an) 2) xA(x)A(a1) A(a2) A(an)2. 量词否定等值式量词否定等值式 3) xA(x) x A(x) 4) xA(x) x A(x)43. 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 设设A(x)是含是含x自由出现的公式，自由出现的公式，B中不含中不含x的出现的出现 5)关于全称量词的：关于全称量词的： x(A(x) B)x A(x) B x(A(x) B)x A(x) B x(A(x)B)x A(x)B x(BA(x)Bx A(x) 5 6)关于存在量词的关于存在量词的: x(A(x) B)xA(x) B x(A(x) B)xA(x) B
3、x(A(x)B)xA(x)B x(BA(x)BxA(x)4. 量词分配等值式量词分配等值式 7) x(A(x) B(x)xA(x)xB(x) 8) x(A(x) B(x)xA(x)xB(x)注意：注意： 对对 无分配律，无分配律， 对对 无分配律无分配律! 6注意：注意： 对对 无分配律，无分配律， 对对 无分配律无分配律!(1) x(A(x) B(x) xA(x) xB(x) (2) x(A(x) B(x) xA(x) xB(x) 取取 解释解释I1: 个体域：自然数集个体域：自然数集N, A(x): x是奇数是奇数, B(x): x是偶数是偶数.7例例2.11 设设个个体体域域为为D =a
4、, b, c, 将将下下列列公公式式中中的的量词消去量词消去: (1) x(F(x)G(x)(F(a)G(a) (F(b)G(b) (F(c)G(c) (2) x(F(x) G(y) (F(a) G(y) (F(b) G(y) (F(c) G(y) (F(a) F(b) F(c) G(y)8(3) x(F(x) yG(y) x( F(x) (G(a) G(b) G(c) ) ( F(a) (G(a) G(b) G(c) ) ( F(b) (G(a) G(b) G(c) ) ( F(c) (G(a) G(b) G(c) ) ( F(a) F(b) F(c) ) ( G(a) G(b) G(c)
5、)9例例2.12 将将下下面面命命题题用用两两种种形形式式符符号号化化, 给给出出演演算过程，并说明理由算过程，并说明理由. (1) 没有不犯错误的人没有不犯错误的人;解解: 令令F(x)：x是人，是人，G(x)：x犯错误犯错误. x( F(x)G(x) ) x( F(x)G(x) ) (2) 不是所有的人都爱看电影不是所有的人都爱看电影.解解: 令令F(x)：x是人，是人，G(x)：爱看电影：爱看电影. x( F(x)G(x) ) x( F(x)G(x) )10 (3) 没有两片完全一样的树叶没有两片完全一样的树叶.解解: 令令F(x)：x是树叶，是树叶，G(x, y)：x y， H(x,
6、y)： x与与y完全一样完全一样. x y(F(x) F(y) G(x, y) H(x, y) ) x y(F(x) F(y) G(x, y) H(x, y) ) 11前束范式前束范式 例如，例如， x y( F(x)( G(y) H(x, y) ) ) x ( F(x) G(x) ) 是前束范式是前束范式, 而而 x( F(x)y( G(y) H(x, y) ) ) x( F(x) G(x) ) 不是前束范式，不是前束范式，定义定义 设设A为一个一阶逻辑公式为一个一阶逻辑公式, 若若A具有如下形具有如下形式式Q1x1Q2x2QkxkB, 则称则称A为为前束范式前束范式, 其中其中Qi (1
7、i k)为为 或或 ，B为不含量词的公式为不含量词的公式.12公式的前束范式公式的前束范式 定理（前束范式存在定理）定理（前束范式存在定理）一阶逻辑中的任何一阶逻辑中的任何 公式都存在与之等值的前束范式公式都存在与之等值的前束范式. 1. 公式的前束范式不惟一；公式的前束范式不惟一；2. 求公式的前束范式的方法求公式的前束范式的方法: 利用利用重要等值式重要等值式、置换规则置换规则、换名规则换名规则、代替规则代替规则进行等值演算进行等值演算. 注意注意:13例例2.13 求下列公式的前束范式求下列公式的前束范式: (1) x(M(x) F(x)解：解： x(M(x) F(x) x( M(x)F
8、(x) (量词否定等值式量词否定等值式) x(M(x)F(x)两步结果都是前束范式，说明前束范式不惟一两步结果都是前束范式，说明前束范式不惟一.14(2) xF(x) xG(x)解解: xF(x) xG(x) xF(x) x G(x) (量词否定等值式量词否定等值式) x(F(x) G(x) (量词分配等值式量词分配等值式)(3) xF(x) xG(x) 解解: xF(x) xG(x) xF(x) x G(x) (量词否定等值式量词否定等值式) x(F(x) G(x) (量词分配等值式量词分配等值式) x(G(x) F(x) 15 (4) xF(x)y(G(x, y)H(y) 解解: xF(x
9、)y(G(x, y)H(y) zF(z)y(G(x, y)H(y) (换名规则换名规则) z y(F(z)(G(x, y)H(y) (为什么？为什么？)或或 xF(x)y(G(z, y)H(y) (代替规则代替规则) x y(F(x)(G(z, y)H(y) (辖域扩张辖域扩张)16(5) x(F(x, y)y(G(x, y) H(x, z)解解: x(F(x, y)y(G(x, y) H(x, z)x(F(x, u)y(G(x, y) H(x, z) (代代替替规规则则)x y(F(x, u)G(x, y) H(x, z) (辖域扩张辖域扩张)注意：注意： x与与 y不能颠倒不能颠倒! 17
10、(6) ( xF(x, y)yG(x, y) zH(x, y, z)解：解：( xF(x, y)yG(x, y) zH(x, y, z) ( xF(x, t)yG(x, y) zH(x, t, z) (代替规则代替规则) ( xF(x, t)yG(w, y) zH(w, t, z) (代替规则代替规则) x y z ( (F(x, t) G(w, y) H(w, t, z) ) (辖域扩张等值式辖域扩张等值式)18(7) ( xF(x, y) yG(y) ) xH(x, y)解：解：( xF(x, y) yG(y) ) xH(x, y) ( xF(x, y) tG(t) ) wH(w, y) (换名规则换名规则)x t (F(x, y) G(t) ) wH(w, y) (辖域扩张等值式辖域扩张等值式)x t ( (F(x, y) G(t) wH(w, y) ) (辖域扩张等值式辖域扩张等值式)x t w( (F(x, y) G(t) ) H(w, y) ) (辖域扩张等值式辖域扩张等值式)19注意注意: 求出的某公式的前束范式中，各指导求出的某公式的前束范式中，各指导变项是不同的，原公式中的自由出现的变项是不同的，原公式中的自由出现的变项还应该是自由出现的，而且出现的变项还应该是自由出现的，而且出现的次数不变。次数不变。20作业作业:P61 9(2)(3)，10
