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

* 说明： （1）公式的前束范式一般是不唯一的 （2）原公式中自由出现的个体变项在前束范式中还应是自由出现的。 精品课件资料分享 SL出品 精品课件资料分享 SL出品 精品课件资料分享 SL出品 * 第五章 一阶逻辑等值演算与推理5.1 一阶逻辑等值式与置换规则 * 定义5.1（等值式） 设A，B是一阶逻辑中任意两个公式，若A?B是永真式，则称A和B是等值的，记作A?B，称A?B是等值式。 下面给出一阶逻辑中的一些基本而重要的等值式： 由于命题逻辑的重言式的代换实例都是一阶逻辑的永真式，所以命题逻辑中24个等值式模式（p.24）给出的代换实例都是一阶逻辑的等值式模式。 例如：?xF（x）?┐┐?xF（x） ?x?y（F（x，y）→G（x，y）） ?┐┐?x?y（F（x，y）→G（x，y）） 等都是A?┐┐A的代换实例。 * 下面介绍一些一阶逻辑固有的等值式，这些等值式都与量词有关。 1、消去量词等值式 设个体域为有限集D={a1，a2，…，an}，则有 （1）?xA（x）? A（a1）∧A（a2）∧…∧A（an） （2）?xA（x）? A（a1）∨A（a2）∨…∨A（an） 2、量词否定等值式 对于任意的公式A（x）： （1）┐?xA（x）??x┐A（x） （2）┐?xA（x）??x┐A（x） * 3、量词辖域收缩与扩张等值式 设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） （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） * 4、量词分配等值式 对于任意的公式A（x）和B（x）： （1）?x（A（x）∧B（x））??xA（x）∧?x B（x） （2）?x（A（x）∨B（x））? ?xA（x）∨?x B（x） 说明：量词分配等值式中，只有?对∧的分配和?对∨的分配的等值式。而?对∨和?对∧无分配律。 * 5、同种量词顺序置换等值式 对于任意的公式A（x，y） (1)?x?yA（x，y）? ?y?xA（x，y） (2)?x?yA（x，y）? ?y?xA（x，y） * 一阶逻辑的等值演算 一阶逻辑的等值演算中三条重要的规则： 1、置换规则 设ф(A)是含公式A的公式，ф(B)是用公式B置换了ф(A)中所有的A后得到的公式，若A?B，则ф(A) ?ф(B)。 * 例 设个体域为D={a，b，c}，将下面公式的量词消去。 （1）?x（F（x）→G（x）） （2）?x（F（x）∨?yG（y）） （3）?x?yF（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） ?（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，b）∧F（b，c））∨ （F（c，a）∧F（c，b）∧F（c，c）） * 例 给定解释I如下： （a）个体域D={2，3}； （b）D中特定元素a=2 （c）D上特定函数f（x）为：f（2）=3，f（3）=2 （d）D上特定谓词 G（x，y）为：G（2，2）= G（2，3）= G（3，2）=1， G（3，3）=0。 L（x，y）为：L（2，2）= L（3，3）=1，