《第五章 一阶逻辑等值演算》由会员分享，可在线阅读，更多相关《第五章 一阶逻辑等值演算（39页珍藏版）》请在金锄头文库上搜索。
1、第五章一阶逻辑等值演算与推理,1. 等值式与基本的等值式 在有限个体域中消去量词等值式量词否定等值式 量词辖域收缩与扩张等值式量词分配等值式 2. 基本规则 置换规则换名规则代替规则 3. 前束范式 4. 推理理论 推理的形式结构推理正确 构造证明新的推理规则 全称量词消去规则, 记为UI 全称量词引入规则, 记为UG 存在量词消去规则, 记为EI 存在量词引入规则, 记为EG,5.1 一阶逻辑等值式与置换规则,一、基本等值式定义5.1 设A, B是一阶逻辑中任意两个公式, 若AB是永真式, 则称A与B是等值的. 记做AB, 称AB是等值式. 谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式
2、类似. 下面主要讨论关于量词的等值式. 第一组 代换实例 由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式, 因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式. 例如：xy(F(x,y)G(x,y) xy(F(x,y)G(x,y) 是A A(2.1)式的代换实例. 又如： x(F(x)G(y)zH(z)x(F(x)G(y)zH(z) 是AB AB(2.12)式的代换实例.,第二组 消去量词等值式 设个体域为有限域D=a1,a2,an, 则有 (1) xA(x) A(a1)A(a2)A(an) (2) xA(x) A(a1)A(a2)A(an) (5.1),第三组 量词否定
3、等值式 设A(x)是任意的含有自由出现个体变项x的公式, 则 (1)xA(x) xA(x) (2)xA(x) xA(x) (5.2),第四组 量词辖域收缩与扩张等值式 设A(x)是任意的含自由出现个体变项x的公式, B中不含x的出现, 则 (1) 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) (5.3) (2) 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) (5.4) 注意：这些等值式的条件.,第五组 量词分配等值式 设A(x), B(
4、x)是任意的含自由出现个体变项x的公式, 则 (1) x(A(x)B(x) xA(x)xB(x) (2) x(A(x)B(x) xA(x)xB(x) (5.5),二、基本规则1置换规则 设(A)是含公式A的公式, (B)是用公式B取代(A)中所有的A之后的公式, 若A B, 则(A) (B). 2换名规则 设A为一公式, 将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号, 公式的其余部分不变, 设所得公式为A, 则A A. 3代替规则 设A为一公式, 将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替, A中其余部分不变,
5、设所得公式为A, 则A A.,三、等值演算,例5.1 将下面公式化成与之等值的公式, 使其没有既是约束出现又是自由出现的个体变项. (1)xF(x,y,z)yG(x,y,z) (2)x(F(x,y)yG(x,y,z)解 (1) xF(x,y,z) yG(x,y,z) tF(t,y,z) yG(x,y,z) (换名规则) tF(t,y,z) wG(x,w,z) (换名规则) 原公式中, x,y都是既约束出现又有自由出现的个体变项, 只有z仅自由出现. 而在最后得到的公式中, x, y, z, t, w中再无既是约束出现又有自由出现个体变项了. 或： xF(x,y,z) yG(x,y,z) xF(
6、x,t,z) yG(x,y,z) (代替规则) xF(x,t,z) yG(w,y,z) (代替规则),例5.2 证明 (1) x(A(x)B(x) xA(x)xB(x) (2) x(A(x)B(x) xA(x) xB(x)其中A(x), B(x)为含x自由出现的公式. 证 (1)只要证明在某个解释下两边的式子不等值. 取解释I：个体域为自然数集合N；取F(x)：x是奇数, 代替A(x)；取G(x)：x是偶数, 代替B(x). 则x(F(x)G(x)为真命题, 而 xF(x)xG(x)为假命题. 两边不等值.对于(2)可以类似证明. 说明, 全称量词 对无分配律. 同样的, 存在量词 对无分配律
7、. 但当B(x)换成没有x出现的B时, 则有 x(A(x)B) xA(x)B x(A(x)B) xA(x)B,例5.3 设个体域为Da,b,c,将下面各公式的量词消去： (1)x(F(x)G(x) (2)x(F(x)yG(y) (3)xyF(x,y) 解 (1) x(F(x)G(x) (F(a)G(a)(F(b)G(b)(F(c)G(c) (2) x(F(x) yG(y) xF(x) yG(y) (公式5.3) (F(a)F(b)F(c)(G(a)G(b)G(c) (3) x yF(x,y) x(F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c)(F(b,a)F(b,
8、b)F(b,c)(F(c,a)F(c,b)F(c,c),例5.4 给定解释I如下： （a）个体域 D2,3. （b）D中特定元素 =2 （c）D上的特定函数 (x)为： (2)=3, (3)=2 . （d）D上的特定谓词 (x,y)为： (2,2)= (2,3)= (3,2)=1, (3,3)=0. (x,y)为： (2,2)= (3,3)=1, (2,3)= (3,2)=0. (x)为： (2)=0, (3)=1. 在I下求下列各式的真值. (1) x(F(x)G(x,a) (2) x(F(f(x)G(x,f(x) (3) x yL(x,y) (4) y xL(x,y),例5.5 证明下列等
9、值式. (1) x(M(x)F(x) x(M(x)F(x) (2) x(F(x)G(x) x(F(x)G(x) (3) x y(F(x)G(y)H(x,y) x y (F(x)G(y)H(x,y) (4) x y(F(x)G(y)L(x,y) x y (F(x)G(y)L(x,y),证 (1) x(M(x)F(x) x(M(x)F(x) (公式(5.2) x(M(x)F(x) (置换规则) x(M(x)F(x) (置换规则) 由此说明例4.4中(3)有两种等值的符号化形式.,(2) x(F(x)G(x) x(F(x)G(x) (公式(5.2) x(F(x)G(x) (置换规则) x(F(x)G
10、(x) (置换规则) 由此说明例4.4中(4)有两种等值的符号化形式.,(3) x y(F(x)G(y)H(x,y) x(y(F(x)G(y)H(x,y) x y(F(x)G(y)H(x,y) x y(F(x)G(y)H(x,y) 由(3)可知, 例4.5中(3)的两个符号化形式是等值的.,5.2 一阶逻辑公式前束范式,一、一阶逻辑公式的标准形前束范式定义5.2 设A为一个一阶逻辑公式, 若A具有如下形式 Q1x1Q2x2QkxkB 则称A为前束范式, 其中Qi(1ik)为或, B为不含量词的公式. 可证明每个一阶逻辑公式都能找到与之等价的前束范式. 定理5.1 (前束范式存在定理)一阶逻辑中
11、的任何公式都存在与之等值的前束范式.,例5.6 求下面公式的前束范式： (1) xF(x) xG(x) (2) xF(x) xG(x) 解 (1) xF(x)xG(x) xF(x)yG(y) (换名规则) xF(x)yG(y) (5.2)第二式) x(F(x)yG(y) (5.3)第二式) x y(F(x)G(y) (5.3)第二式) 或者 xF(x)xG(x) xF(x)xG(x) (5.2)第二式) x(F(x)G(x) (5.5)第一式) 由此可知, (1)中公式的前束范式是不唯一的.,(2) xF(x)xG(x) xF(x) xG(x) (5.2)第二式) xF(x) yG(y) (换名规则) x(F(x) yG(y) (5.3)第一式) xy(F(x)G(x) (5.3)第一式) 问：(2)的下述求法是否正确？ xF(x)xG(x) xF(x)xG(x) x(F(x)G(y),
