lecture 5 一阶逻辑等值式与置换规则.pptVIP

* 定义5.1 设A，B是一阶逻辑中任意两个公式，若A ? B是永真式，则称A与B是等值的。记做A=B，称A = B是等值式。 一、基本等值式 ???第一组 代换实例 ???由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。 例如：?xF(x) =┐┐?xF(x) ???????? F(x)→G(y) =┐F(x)∨G(y) ????第二组 消去量词等值式 ???设个体域为有限域D={a1,a2,…,an}，则有 ????(1) ?xA(x)=A(a1)∧A(a2)∧…∧A(an)? ??(2) ?xA(x) = ??第三组 量词否定等值式 ???设A(x)是任意的含有自由出现个体变项x的公式，则 ????(1)┐?xA(x) = ?x┐A(x)????(2)┐?xA(x) = ?A(a1)∨A(a2)∨…∨A(an)???? (5.1) ?x┐A(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(B→A(x))= B→ ?xA(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(B→A(x))= B→xA(x)??????????? (5.4) ????第五组 量词分配等值式 ???设A(x)，B(x)是任意的含自由出现个体变项x的公式，则 ????(1) ?x(A(x)∧B(x)）=????(2) ?x(A(x)∨B(x)）= ?xA(x)∧xB(x) ?xA(x)∨xB(x)?? (5.5) 问： ?x(A(x)∨B(x)）= ?xA(x)∨xB(x) ? ╳ 二、基本规则 ????1．置换规则 ????设Φ(A)是含公式A的公式，Φ(B)是用公式B取代Φ(A)中所有的A之后的公式，若A=B，则Φ(A)=Φ(B). ????2．换名规则 ????设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A，则A=A. ????3．代替规则 ????设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A，则A=A. 三、等值演算 例5.1 将下面公式化成与之等值的公式，使其没有既是约束出现又是自由出现的个体变项。 ???? ?xF(x,y,z)→ ?yG(x,y,z) ???解 2. ?xF(x,y,z)→ ?yG(x,y,z) ??? =?xF(x,t,z)→?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)??(换名规则) ?????? =?xF(x,t,z)→?yG(w,y,z)??? (代替规则) 四、一阶逻辑公式的标准形——前束范式 定义5.2 设A为一个一阶逻辑公式，若A具有如下形式????????????????????????? ?Q1x1Q2x2…QkxkB 则称A为前束范式，其中Qi(1≤i≤k)为?或?，B为不含量词的公式。 定理5.1 (前束范式存在定理)一阶逻辑中的任何公式都存在与之等值的前束范式。 例5.6 求下面公式的前束范式： ???? ?xF(x)∧┐?xG(x) ????解 1. ?xF(x)∧┐?xG(x) ???????? =?xF(x)∧┐?yG(y) ??(换名规则) ????? 或者 ??? ??解 2. ?xF(x)∧┐?xG(x) ??? ??? =?xF(x)∧?x┐G(x) ???((5.2)第二式) ??? ???? =?xF(x)∧?y┐G(y) ??((5.2)第二式) ???? ??? ???? =?x(F(x)∧?y┐G(y)) ((5.3)第二式) ??? ???? =?x?y(F(x)∧┐G(y)) ((5.3)第二式) ??? ? ????