第五章-一阶逻辑等值演算与推理

复习变元的约束(Boundofvariable)在x和x的辖域中，x的所有出现都称为约束出现，相应的x称为约束变元;P(x)中除约束变元以外出现的变元称为是自由变元。例1：1、x(H(x,y)y(W(y)∧L(x,y,z)))2、x(H(x)W(y))y(F(x)∧L(x,y,z))注意：(1)n元谓词公式A(x1，x2...xn)中有n个自由变元,若对其中的k(k≤n)个进行约束,则构成了n-k元谓词;如果一个公式中没有自由变元出现,则该公式就变成了一个命题(2)一个公式的约束变元所使用的名称符号是无关紧要的,如(x)M(x)与(y)M(y)意义相同.约束变元的换名与自由变元的代入规则换名规则:(对约束变元而言）对约束变元进行换名,使得一个变元在一个公式中只呈一种形式出现.(1)约束变元可以换名,其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的该变元,公式的其余部分不变.(2)换名时一定要更改为作用域中没有出现的变元名称.例1:x(P(x)R(x,y))∧L(x,y)换名为t(P(t)R(t,y))∧L(x,y)x(H(x,y)y(W(y)∧L(x,y,z)))换名为x(H(x,y)s(W(s)∧L(x,s,z)))代入规则（对自由变元而言）对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入,代入时需要对公式中出现该自由变元的每一处进行;(2)用以代入的变元与原公式中所有变元的名称不能相同.例如对例1中的公式x(P(x)R(x,y))∧L(x,y)自由变元y用z来代入,得x(P(x)R(x,z))∧L(x,z)习题1、在一阶逻辑中将下列命题符号化。（1）大熊猫都可爱。（2）有人爱发脾气。（3）说所有人都爱吃面包是不对的。（4）没有不爱吃糖的人。（5）一切人都不一样高。（6）并不是所有的汽车都比火车快。解：由于没指出个体域，故用全总个体域（1）大熊猫都可爱。设F(x):x为大熊猫，G(x):x可爱，命题符号化为x(F(x)G(x))（2）有人爱发脾气。设F(x):x是人，G(x):x爱发脾气，命题符号化为x(F(x)G(x))（3）说所有人都爱吃面包是不对的。设F(x):x是人，G(x):x爱吃面包，命题符号化为x(F(x)G(x))或x(F(x)G(x))（4）没有不爱吃糖的人。设F(x):x是人，G(x):x爱吃糖，命题符号化为x(F(x)G(x))或x(F(x)G(x))（5）一切人都不一样高。设F(x):x是人,H(x,y)：x与y相同,L(x,y):x与y一样高，命题符号化为xy(F(x)F(y)H(x,y)L(x,y))或x(F(x)y(F(y)H(x,y)L(x,y)))（6）并不是所有的汽车都比火车快。设F(x):x是汽车,G(y):y是火车,H(x,y):x比y快，命题符号化为xy(F(x)G(y)H(x,y))或xy(F(x)G(y)H(x,y))2、在一阶逻辑中将下列命题符号化。（1）没有一个自然数大于等于任何自然数。（2）有唯一的偶素数。解：（1）N(x):x是自然数，G(x,y):xyx(N(x)y(N(y)G(x,y)))（2）Q(x):x是偶数，P(x):x是素数，E(x,y):x＝yx(Q(x)P(x)y(Q(y)P(y)E(x,y)))3、判断公式是否为永真公式。(xA(x)xB(x))x(A(x)B(x))解：不是永真公式。设个体域为{a,b}，令A(a)=1,B(a)=0,A(b)=0,B(b)=1。小节结束第5章一阶逻辑等值演算与推理离散数学山东师范大学本科生课程信息科学与工程学院2008专升本本章说明本章的主要内容–一阶逻辑等值式与基本等值式–置换规则、换名规则、代替规则–前束范式–一阶逻辑推理理论本章与其他各章的关系–本章先行基础是前四章–本章是集合论各章的先行基础本章主要内容5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式5.3一阶逻辑的推理理论主要内容作业5.1一阶逻辑等值式与置换规则在一阶逻辑中，有些命题可以有不同的符号化形式。例如：没有不犯错误的人令M(x):x是人。F(x):x犯错误。则将上述命题的符号化有以下两种正确形式：(1)┐x(M(x)∧┐F(x))(2)x(M(x)→F(x))我们称(1)和(2)是等值的。说明等值式的定义定义5.1设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值的。记做AB，称AB是等值式。G(x))x(F(x)G(x))x(F(x)例如：判断公式A与B是否等值，等价于判断公式AB是否为永真式。谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。说明一阶逻辑中的一些基本而重要等值式代换实例消去量词等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式代换实例---命题公式的推广由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式模式给出的代换实例都是一阶逻辑的等值式的模式。例如：(1)xF(x)┐┐xF(x)（双重否定律）(2)F(x)→G(y)┐F(x)∨G(y)（蕴涵等值式）(3)x(F(x)→G(y))→zH(z)┐x(F(x)→G(y))∨zH(z)（蕴涵等值式）消去量词等值式设个体域为有限集D={a1,a2,…,an},则有（1）xA(x)A(a1)∧A(a2)∧…∧A(an)（2）xA(x)A(a1)∨A(a2)∨…∨A(an)（5.1）量词否定等值式设A(x)是任意的含自由出现个体变项x的公式，则（1）┐xA(x)x┐A(x)（2）┐xA(x)x┐A(x)说明“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。”不存在有性质A的x”与”所有X都没有性质A”是一回事。（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)（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.3）（5.4）量词辖域中如果有合取或析取项，且其中有一个是命题，则可将该命题移至量词辖域之外证明:xA(x)→Bx(A(x)→B)xA(x)→B┐xA(x)∨Bx┐A(x)∨Bx(┐A(x)∨B)x(A(x)→B)量词分配等值式设A(x)，B(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)式。以下两式注意x(A(x)∨B(x))xA(x)∨xB(x)x(A(x)∧B(x))xA(x)∧xB(x)谓词演算蕴含式xA(x)∨xB(x)x(A(x)∨B(x))x(A(x)∧B(x))xA(x)∧xB(x)多个量词间的次序排列等值式。多个量词同时出现时,其顺序是至关重要的.(1)(,)(,)xyAxyyxAxy(2)(,)(,)xyAxyyxAxyxyP(x,y)yxP(x,y)yxP(x,y)xyP(x,y)xyP(x,y)yxP(x,y)yxP(x,y)xyP(x,y)多个量词间的次序排列等值式。一阶逻辑等值演算的三条原则置换规则：设Φ(A)是含公式A的公式，Φ(B)是用公式B取代Φ(A)中所有的A之后的公式，若AB，则Φ(A)Φ(B)。一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B是一阶逻辑公式。换名规则：设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A'，则A'A。代替规则：设A为一公式，将A中某个自由出现的个体变项的所有出现，用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A'，则A'A。例5.1例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)(换名规则)或xF(x,y,z)→yG(x,y,z)xF(x,t,z)→yG(x,y,z)(代替规则)xF(x,t,z)→yG(w,y,z)(代替规则)解答例5.1的解答(2)x（F(x,y)→yG(x,y,z))x(F(x,t)→yG(x,y,z))(代替规则)或x(F(x,y)→yG(x,y,z))x(F(x,y)→tG(x,t,z))(换名规则)解答例5.2例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自由出现的公式。只要证明在某个解释下两边的式子不等值。取解释I：个体域为自然数集合N；(1)取F(x)：x是奇数，代替A(x)；取G(x)：x是偶数，代替B(x)。则x(F(x)∨G(x))为真命题，而xF(x)∨xG(x)为假命题。两边不等值。证明例5.2(2)x(A(x)∧B(x))≠xA(x)∧xB(x)x(F(x)∧G(x))：有些x既是奇数又是偶数为假命题；而xF(x)∧xG(x)：有些x是奇数并且有些x是偶数为真命题。两边不等值。证明说明全称量词“”对“∨”无分配律。存在量词“”对“∧”无分配律。例5.3—消去量词例5.3设个体域为D＝{a,b,c}，将下面各公式的量词消去：(1)x(F(x)→G(x))(2)x(F(x)∨yG(y))(3)xyF(x,y)说明如果不用公式(5.3)将量词的辖域缩小，演算过程较长。注意，此时yG(y)是与x无关的公式B。解答(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))例5.3—消去量词(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))在演算中先消去存在量词也可以，得到结果是等值的。xyF(x,y)yF(a,y)∨yF(b,y)∨yF(c,y)(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))例5.4例5.4给定解释I如下：（a）个体域D＝{2,3}（b）D中特定元素（c）D上的特定函数(x)为：（d）D的特定谓词2a。，23(3)(2)ff。，为：0(3,3)1(3,2)(2,3)(2,2)y)(x,GGGGG。，为：01(3,2)(2,3)(3,3)(2,2)y)(x,LLLLL。，为：10(3)(2)(x)FFF在解释I下