2.3-一阶逻辑等值式与前束范式.ppt

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(a1)A(a2)A(an) 2) xA(x)A(a1)A(a2)A(an)2. 量词否定等值式 3) xA(x) xA(x) 4) xA(x) xA(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 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, 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) )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, y)： x与y完全一样. xy(F(x)F(y)G(x, y)H(x, y) ) xy(F(x)F(y)G(x, y) H(x, y) ) 11前束范式 例如，xy( 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 (1ik)为或，B为不含量词的公式.12公式的前束范式 定理（前束范式存在定理）一阶逻辑中的任何 公式都存在与之等值的前束范式. 1. 公式的前束范式不惟一；2. 求公式的前束范式的方法: 利用重要等值式、置换规则、换名规则、代替规则进行等值演算. 注意:13例2.13 求下列公式的前束范式: (1) x(M(x)F(x)解： x(M(x)F(x) x(M(x)F(x) (量词否定等值式) x(M(x)F(x)两步结果都是前束范式，说明前束范式不惟一.14(2) xF(x) xG(x)解: xF(x) xG(x) xF(x) xG(x) (量词否定等值式) x(F(x) G(x) (量词分配等值式)(3) xF(x) xG(x) 解: xF(x) xG(x) xF(x) xG(x) (量词否定等值式) x(F(x) G(x) (量词分配等值式) x(G(x) F(x) 15 (4) xF(x)y(G(x, y)H(y) 解: xF(x)y(G(x, y)H(y) zF(z)y(G(x, y)H(y) (换名规则) zy(F(z)(G(x, y)H(y) (为什么？)或 xF(x)y(G(z, y)H(y) (代替规则) xy(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) (代替规则)xy(F(x, u)G(x, y)H(x, z) (辖域扩张)注意：x与y不能颠倒! 17(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) (代替规则) xy 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) (换名规则)xt (F(x, y) G(t) ) wH(w, y) (辖域扩张等值式)xt ( (F(x, y) G(t) wH(w, y) ) (辖域扩张等值式)xtw( (F(x, y) G(t) ) H(w, y) ) (辖域扩张等值式)19注意: 求出的某公式的前束范式中，各指导变项是不同的，原公式中的自由出现的变项还应该是自由出现的，而且出现的次数不变。

20作业:P61 9(2)(3)，10。