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

第5章一阶逻辑等值演算与推理离散数学2本章说明本章的主要内容–一阶逻辑等值式与基本等值式–置换规则、换名规则、代替规则–前束范式–一阶逻辑推理理论本章与其他各章的关系–本章先行基础是前四章–本章是集合论各章的先行基础3本章主要内容5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式5.3一阶逻辑的推理理论45.1一阶逻辑等值式与置换规则在一阶逻辑中，有些命题可以有不同的符号化形式。例如：没有不犯错误的人令M(x):x是人。F(x):x犯错误。则将上述命题的符号化有以下两种正确形式：(1)┐x(M(x)∧┐F(x))(2)x(M(x)→F(x))我们称(1)和(2)是等值的。说明5等值式的定义定义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是否为永真式。谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。说明6一阶逻辑中的一些基本而重要等值式代换实例消去量词等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式7代换实例由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的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)（蕴涵等值式）8消去量词等值式设个体域为有限集D={a1,a2,…,an},则有（1）xA(x)A(a1)∧A(a2)∧…∧A(an)（2）xA(x)A(a1)∨A(a2)∨…∨A(an)（5.1）9量词否定等值式设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）10量词否定等值式(举例)Nn(nN→|an-a|)a1,a2,a3,…,aN,aN+1,aN+2,…,an,…?aannlimaannlima11量词否定等值式(举例、续)Nn(nN→|an-a|)Nn(nN→|an-a|)Nn(nN→|an-a|)Nn(nN→|an-a|)Nn(nN∨|an-a|)Nn(nN∧|an-a|)Nn(nN∧|an-a|)aannlimaannlim12量词辖域收缩与扩张等值式设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）13量词辖域收缩与扩张(、续)x(A(x)→B)xA(x)→B证明:x(A(x)→B)x(A(x)∨B)xA(x)∨BxA(x)∨BxA(x)→Bx(B→A(x))B→xA(x)证明:x(B→A(x))x(B∨A(x))B∨xA(x)B∨xA(x)B→xA(x)14量词辖域收缩与扩张(、续)x(A(x)→B)xA(x)→B证明:x(A(x)→B)x(A(x)∨B)xA(x)∨BxA(x)∨BxA(x)→Bx(B→A(x))B→xA(x)证明:x(B→A(x))x(B∨A(x))B∨xA(x)B∨xA(x)B→xA(x)15量词分配等值式设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)式。由(1)式推导(2)式x(A(x)∧B(x))xA(x)∧xB(x)x(┐A(x)∧┐B(x))x┐A(x)∧x┐B(x)┐x(A(x)∨B(x))┐(xA(x)∨xB(x))x(A(x)∨B(x))xA(x)∨xB(x)16量词分配等值式–①x(A(x)B(x))xA(x)xB(x)–②x(A(x)B(x))xA(x)xB(x)注意:对无分配律,对无分配律17量词分配(反例)x(A(x)∨B(x))xA(x)∨xB(x)x(A(x)∨B(x))xA(x)∨xB(x)个体域为全体自然数;A(x):x是偶数B(x):x是奇数;左1,右0x(A(x)∧B(x))xA(x)∧xB(x)x(A(x)∧B(x))xA(x)∧xB(x)个体域为全体自然数;A(x):x是偶数B(x):x是奇数;左0,右118量词的次序xyA(x,y)yxA(x,y)xyA(x,y)yxA(x,y)yxA(x,y)xyA(x,y)xyA(x,y)yxA(x,y)xyA(x,y)yxA(x,y)–相邻的同名量词的次序无关紧要,不同名量词的次序是不可随意变更的19一阶逻辑等值演算的三条原则置换规则：设Φ(A)是含公式A的公式，Φ(B)是用公式B取代Φ(A)中所有的A之后的公式，若AB，则Φ(A)Φ(B)。换名规则：设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A'，则A'A。代替规则：设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A'，则A'A。说明一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B是一阶逻辑公式。20例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)(代替规则)解答21例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))(换名规则)解答22例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)为假命题。两边不等值。证明23例5.2(2)x(A(x)∧B(x))≠xA(x)∧xB(x)x(F(x)∧G(x))：有些x既是奇数又是偶数为假命题；而xF(x)∧xG(x)：有些x是奇数并且有些x是偶数为真命题。两边不等值。证明说明全称量词“”对“∨”无分配律。存在量词“”对“∧”无分配律。当B(x)换成没有x出现的B时，则有x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧B24例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))25例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))26例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下求下列各式的值：（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)27例5.4的解答（1）x(F(x)∧G(x,a))(F(2)∧G(2,2))∧(F(3)∧G(3,2))(0∧1)∧(1∧1)0（2）x(F(f(x))∧G(x,f(x))(F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3)))(F(3)∧G(2,3))∨(F(2))∧G(3,2))(1∧1)∨(0∧1)128例5.4的解答（3）xyL(x,y)(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))(1∨0)∧(0∨1)1（4）yxL(x,y)y(L(2,y)∧L(3,y))(L(2,2)∧L(3,2))∨(L(2,3)∧L(3,3))(1∧0)∨(0∧1)0说明由(3)，(4)的结果进一步可以说明量词的次序不能随意颠倒。29例5.5例5.5证明下列等值式。（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))30例5.5的证明（1）┐x(M(x)∧F(x))x(M(x)→┐F(x))┐x(M(x)∧F(x))x┐(M(x)∧F(x))x(┐M(x)∨┐F(x))x(M(x)→┐F(x))（2）┐x(F(x)→G(x))x(F(x)∧┐G(x))┐x(F(x)→G(x)