一阶逻辑等值与前束范式

离散数学(第6讲)章静E-mail:2.2一阶逻辑合式公式及解释同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，必须给出一阶逻辑中公式的抽象定义，以及它们的分类及解释。一阶语言是用于一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系，一阶语言本身不具备任何意义，但可以根据需要被解释成具有某种含义。一阶语言的形式是多种多样的，本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为F。一阶语言中的字母表定义2.1一阶语言F的字母表定义如下:(1)个体常项：a,b,c,…,ai

,bi

,ci

,…,i

1(2)个体变项：x,y,z,…,xi

,yi

,zi

,…,i

1(3)函数符号：f,g,h,…,fi

,gi

,hi

,…,i

1(4)谓词符号：F,G,H,…,Fi

,Gi

,Hi

,…,i

1(5)量词符号:，(6)联结词符号:┐,∧,∨,→,(7)括号与逗号:(,),，定义2.2项的递归定义如下:(1)个体常项和个体变项是项。(2)若f(x1,x2,…,xn)是任意n元函数，t1,t2,…,tn是项，则f(t1,t2,…,tn)也是项。(3)只有有限次地使用(1)，(2)生成的符号串才是项。看书P42例子定义2.3设R(x1,x2,…,xn)是的任意n元谓词，t1,t2,…,tn是项，则称R(t1,t2,…,tn)为原子公式。定义2.4合式公式定义如下:

合式公式也称为谓词公式，简称公式。1.原子公式是合式公式；2.若A，B是合式公式，则(┐A)、(┐B)、(A∨B)、(A∧B)、(A→B)、(AB)也是合适公式；3.若A是合式公式，x是个体变量，则(x)A、(x)A也是合式公式；4.只有有限次地应用1-3构成的符号串才是合式公式。

在定义2.4中出现的字母A，B是代表任意公式的元语言符号。为方便起见，公式(┐A)，(A∧B)，…中的最外层括号可以省去，使其变成┐A，A∧B，…。定义2.5在公式xA和xA中，称x为指导变项，A为相应量词的辖域。在x和x的辖域中，x的所有出现都称为约束出现。A中不是约束出现的其他变项均称为是自由出现的。例2.6

指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。

(1)x(F(x,y)→G(x,z))

(2)x(F(x)→G(y))→y(H(x)∧L(x,y,z))解答(1)x是指导变项。量词的辖域A=(F(x,y)→G(x,z))。在A中，x的两次出现均是约束出现。y和z均为自由出现。(2)前件上量词的指导变项为x，量词的辖域A=(F(x)→G(y))，x在A中是约束出现的，y在A中是自由出现的。后件中量词的指导变项为y，量词的辖域为B=(H(x)∧L(x,y,z))，y在B中是约束出现的，x、z在B中均为自由出现的。再看书P43例2.6注意用A(x1,x2,…,xn)表示含x1,x2,…,xn自由出现的公式。用Δ表示任意的量词或，则Δx1A(x1,x2,…,xn)是含有x2,x3,…,xn自由出现的公式，可记为A1(x2,x3,…,xn)。类似的，Δx2Δx1A(x1,x2,…,xn)可记为A2(x3,x4,…,xn)Δxn-1Δxn-2…Δx1A(x1,x2,…,xn)中只含有xn是自由出现的个体变项，可以记为An-1(xn)。Δxn…Δx1A(x1,x2,…,xn)没有自由出现的个体变项。将x(F(x,y)→G(x,z))简记为A(y,z)，表明公式含有自由出现的个体变项y，z。而yA(y,z)中只含有z为自由出现的公式，zyA(y,z)中已经没有自由出现的个体变项了，定义2.6设A是任意的公式，若A中不含有自由出现的个体变项，则称A为封闭的公式，简称闭式。要想使含r（r1）个自由出现个体变项的公式变成闭式至少要加r个量词。如x(F(x)→G(x))是闭式，

x(F(x)→G(x,y))不是闭式换名规则P43例2.6（2）

xF(x)∧G(x,y)换名为zF(z)∧G(x,y)让公式中不会有既约束出现又自由出现的变项。P43换名规则:将一个指导变项及其在辖域中所有约束出现替换成公式中没有出现的个体变项符号。P43例2.6（3）

x(R(x,y,z)∧yH(x,y,z))换名为x(R(x,y,z)∧tH(x,t,z))例2.7

将下列两个公式中的变项指定成常项使其成为命题: (1)x(F(x)→G(x))

(2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))(1)指定个体变项的变化范围，并且指定谓词F，G的含义，下面给出两种指定法:

(a)令个体域D1为全总个体域，

F(x)为x是人，

G(x)为x是黄种人， 则命题为“所有人都是黄种人”，这是假命题。(b)令个体域D2为实数集合R，

F(x)为x是自然数，

G(x)为x是整数， 则命题为“自然数都是整数”，这是真命题。(2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))

含有两个2元函数变项，两个1元谓词变项，两个2元谓词变项。 指定个体域为全总个体域，

F(x)为x是实数， G(x,y)为x≠y，

H(x,y)为x>y， f(x,y)=x2+y2，

g(x,y)=2xy， 则表达的命题为“对于任意的x，y，若x与y都是实数，且x≠y，则x2+y2>2xy”，这是真命题。 如果H(x,y)改为x<y， 则所得命题为假命题。定义2.7一个解释I由下面4部分组成:(a)非空个体域D；(b)给论及的每一个个体常项符号指定一个D中的元素；

(c)给论及的每一个函数变项符号指定一个D中的函数；(d)给论及的每一个谓词变项符号指定一个D中的谓词。例2.8

给定解释I如下:(a)个体域D=N(N为自然数集合，即N={0,1,2,…})(b)元素a=0(c)函数f(x,y)=x+y,g(x,y)=x•y。(d)谓词F(x,y)为x=y。在I下，下列哪些公式为真?哪些为假?哪些的真值还不能确定?(1)F(f(x,y),g(x,y))(2)F(f(x,a),y)→F(g(x,y),z)(3)┐F(g(x,y),g(y,z))(4)xF(g(x,y),z)(5)xF(g(x,a),x)→F(x,y)(6)xF(g(x,a),x)(7)xy(F(f(x,a),y)→F(f(y,a),x))(8)xyzF(f(x,y),z)

(9)xF(f(x,x),g(x,x))

(1)F(f(x,y),g(x,y))

公式被解释成“x+y=x·y”，这不是命题。

(2)F(f(x,a),y)→F(g(x,y),z)

公式被解释成“(x+0=y)→(x·y=z)”，这也不是命题。

(3)┐F(g(x,y),g(y,z))

公式被解释成“x·y≠y·z”，同样不是命题。

(4)xF(g(x,y),z)

公式被解释成“x(x·y=z)”，不是命题。例2.8

给定解释I如下:(a)个体域D=N(N为自然数集合，即N={0,1,2,…})(b)元素a=0(c)函数f(x,y)=x+y,g(x,y)=x•y。(d)谓词F(x,y)为x=y。(5)xF(g(x,a),x)→F(x,y)

公式被解释成“x(x·0=x)→(x=y)”，由于前件为假，所以被解释的公式为真。

(6)xF(g(x,a),x)

公式被解释成“x(x·0=x)”，为假命题。(7)xy(F(f(x,a),y)→F(f(y,a),x))

公式被解释成“xy((x+0=y)→(y+0=x))”，为真命题。

例2.8

给定解释I如下:(a)个体域D=N(N为自然数集合，即N={0,1,2,…})(b)元素a=0(c)函数f(x,y)=x+y,g(x,y)=x•y。(d)谓词F(x,y)为x=y。(8)xyzF(f(x,y),z)

公式被解释成“xyz(x+y=z)”，这也为真命题。(9)xF(f(x,x),g(x,x))

公式被解释成“x(x+x=x·x)”，为真命题。例2.8

给定解释I如下:(a)个体域D=N(N为自然数集合，即N={0,1,2,…})(b)元素a=0(c)函数f(x,y)=x+y,g(x,y)=x•y。(d)谓词F(x,y)为x=y。书P44例题2.7，2.8闭式在给定的解释中都变成了命题。如(6)(8)。不是闭式的公式在某些解释下也可能变为命题。如(5)。结论定理2.1封闭的公式在任何解释下都变成命题。P45在给定的解释和赋值下，任何公式都是命题。一阶公式的分类定义2.8永真式、永假式、可满足式设A为一个公式，若A在任何解释下均为真，则称A为永真式(或称逻辑有效式)。设A为一个公式，若A在任何解释下均为假，则称A为矛盾式(或永假式)。设A为一个公式，若至少存在一个解释使A为真，则称A为可满足式。永真式一定是可满足式，但可满足式不一定是永真式。在一阶逻辑中，到目前为止，还没有找到一种可行的算法，用来判断任意一个公式是否是可满足的，这与命题逻辑的情况是完全不同的。但对某些特殊的公式还是可以判断的。说明例2.9

判断下列公式中，哪些是逻辑有效式，哪些是矛盾式？（1）x(F(x)G(x))（2）x(F(x)G(x))（3）xF(x)(xyG(x,y)xF(x))（4）(xF(x)yG(y))yG(y)解:(1)x(F(x)G(x))

解释1：个体域为实数集合R，F(x)：x是整数，G(x)：x是有理数，因此公式真值为真。解释2：个体域为实数集合R，F(x)：x是无理数，G(x)：x能表示成分数，因此公式真值为假。所以公式为非永真式的可满足式。（2）x(F(x)G(x))

公式为非永真式的可满足式。（3）xF(x)(xyG(x,y)xF(x))

为p(qp)（重言式）的代换实例，故为永真式。（4）(xF(x)yG(y))yG(y)

为(pq)q（矛盾式）的代换实例，故为永假式。代换实例定义2.9设A0是含有命题变项p1,p2,…,pn的命题公式，A1,A2,…,An是n个谓词公式，用Ai(1≤i≤n)处处代替A0中的pi，所得公式A称为A0的代换实例。例如，F(x)G(x),xF(x)yG(y)等都是pq的代换实例，而x(F(x)G(x))不是pq的代换实例。定理2.2重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。例2.10

判断下列公式的类型。

(1)xF(x)→xF(x)

(2)xyF(x,y)→xyF(x,y)

(3)x(F(x)∧G(x))→yG(y)解记(1)，(2)，(3)中的公式分别为A,B,C。(1)设I为任意一个解释，个体域为D。 若存在x0∈D，使得F(x0)为假，则xF(x)为假，所以A的前件为假，故A为真。 若对于任意x∈D，F(x)均为真，则xF(x)，xF(x)都为真，从而A为真。 所以在I下A为真。由I的任意性可知，A是永真式。(2)xyF(x,y)→xyF(x,y)

取解释I：个体域为自然数集合N，F(x,y)为x≤y。 在I下B的前件与后件均为真，所以B为真。这说明B不是矛盾式。（在xyF(x,y)中，x＝0） 再取I‘：个体域仍然为N，F(x,y)为x=y。 在I’下，B的前件真而后件假，所以B为假。这说明B不是永真式。 故B是非永真式的可满足式。(3)x(F(x)∧G(x))→yG(y)

C也是非永真式的可满足式。书P45例2.9课后练习P532.4-2.82.3一阶逻辑等值式与置换规则在一阶逻辑中，有些命题可以有不同的符号化形式。例如：没有不犯错误的人 令M(x):x是人。F(x):x犯错误。 则将上述命题的符号化有以下两种正确形式：

(1)┐x(M(x)∧┐F(x)) (2)

x(M(x)→F(x))我们称(1)和(2)是等值的。说明等值式的定义定义2.10

设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值的。

记做AB，称AB是等值式。例如：判断公式A与B是否等值，等价于判断公式

AB是否为永真式。谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。说明一阶逻辑中的一些基本而重要等值式代换实例消去量词等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式代换实例由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而P9的24组等值式模式给出的代换实例都是一阶逻辑的等值式的模式。例如：

(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)

（蕴涵等值式）定理2.1量词否定等值式设A(x)是任意的含自由出现个体变项x的公式，则（1）┐xA(x)x┐A(x)（2）┐xA(x)x┐A(x)否定内移，量词互换。任意变存在，存在变任意。说明“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。”不存在有性质A的x”与”所有X都没有性质A”是一回事。消去量词等值式设个体域为有限集D={a1,a2,…,an},则有（1）xA(x)A(a1)∧A(a2)∧…∧A(an)（2）xA(x)A(a1)∨A(a2)∨…∨A(an)

P47（1）┐xA(x)x┐A(x)

（2）┐xA(x)x┐A(x)┐xA(x)┐(A(a1)∧A(a2)∧…∧A(an))┐

A(a1)∨┐A(a2)∨…∨┐A(an)

x┐A(x)┐xA(x)┐(A(a1)∨A(a2)∨…∨A(an)

)┐

A(a1)∧┐A(a2)∧…∧┐A(an)

x┐A(x)定理2.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)（P47）定理2.2量词辖域收缩与扩张等值式设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则（1）x(A(x)∨B)xA(x)∨B

（P47）x(A(x)∨B)(A(a1)∨B)∧(A(a2)∨B)∧…∧(A(an)∨B)(A(a1)∧A(a2)∧…∧A(an))

∨B

xA(x)∨B证明:(2)3:

x(A(x)→B)xA(x)→Bx(A(x)→B)x(┐A(x)∨B)x┐A(x)∨B┐xA(x)∨BxA(x)→B证明:(1)3:

x(A(x)→B)xA(x)→B

x(A(x)→B)

x(┐A(x)∨B)x┐A(x)∨B┐xA(x)∨BxA(x)→B定理2.3量词分配等值式设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)（P47）例如，“联欢会上所有人既唱歌又跳舞”和“联欢会上所有人唱歌且所有人跳舞”，这两个语句意义相同。故有(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)例2.10

证明 （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)为假命题。 两边不等值。证明(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)∧BP48定理2.4xyA(x,y)yxA(x,y)xyA(x,y)yxA(x,y)2.一阶逻辑等值演算的三条原则置换规则：设Φ(A)是含公式A的公式，Φ(B)是用公式B取代Φ(A)中所有的A之后的公式，若AB，则Φ(A)Φ(B)。换名规则：设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A'，则A'A。代替规则：设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A'，则A'A。说明一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B是一阶逻辑公式。例将下面公式化成与之等值的公式，使其没有既是约束出现又是自由出现的个体变项。

(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)(代替规则)解答(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))(换名规则)解答例—消去量词如P54练习2.12例设个体域为D＝{a,b,c}，将下面各公式的量词消去：

(1)x(F(x)→G(x)) (2)x(F(x)∨yG(y)) (3)xyF(x,y)说明如果不用量词的辖域缩小，演算过程较长。注意，此时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)

(F(a)∧F(b)∧F(c))∨(G(a)∨G(b)∨G(c))例—消去量词(3)xyF(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))

在演算中先消去存在量词也可以，得到结果是等值的。xyF(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))例给定解释I如下： （a）个体域D＝{2,3}

（b）D中特定元素

（c）D上的特定函数(x)为：

（d）D的特定谓词在解释I下求下列各式的值： （1）x(F(x)∧G(x,a))

（2）x(F(f(x))∧G(x,f(x))

（3）xyL(x,y)

（4）yxL(x,y)（1）x(F(x)∧G(x,a))

(F(2)∧G(2,2))∧(F(3)∧G(3,2)) (0∧1)∧(1∧1) 0例给定解释I如下： （a）个体域D＝{2,3}

（b）D中特定元素

（c）D上的特定函数(x)为：

（d）D的特定谓词（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) 1例给定解释I如下： （a）个体域D＝{2,3}

（b）D中特定元素

（c）D上的特定函数(x)为：

（d）D的特定谓词（3）xyL(x,y) (L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3)) (1∨0)∧(0∨1) 1例给定解释I如下： （a）个体域D＝{2,3}

（b）D中特定元素

（c）D上的特定函数(x)为：

（d）D的特定谓词（4）yxL(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)的结果进一步可以说明量词的次序不能随意颠倒。例给定解释I如下： （a）个体域D＝{2,3}

（b）D中特定元素

（c）D上的特定函数(x)为：

（d）D的特定谓词2.3一阶逻辑前束范式定义2.11

设A为一个一阶逻辑公式，若A具有如下形式

Q1x1Q2x2…QkxkB

则称A为前束范式，其中Qi(1≤i≤k)为或，B为不含量词的公式。前束范式的例子：

xy(F(x)∧G(y)→H(x，y))

xyz(F(x)∧G(y)∧H(z)→L(x，y，z))

不是前束范式的例子：

x(F(x)→y(G(y)∧H(x，y)))

x(F(x)∧y(G(y)→H(x，y)))前束范式存在定理定理

一阶逻辑中的任何公式都存在与之等值的前束范式。说明求前束范式的过程，就是制造量词辖域可以扩大的条件，进行量词辖域扩大。任何公式的前束范式都是存在的，但一般说来，并不唯一。利用一阶逻辑等值式以及三条变换规则（置换规则、换名规则、代替规则）就可以求出与公式等值的前束范式，或所谓公式的前束范式。(1)利用量词转化公式，把否定深入到指导变元的后面。

┐xA(x)x┐A(x)

┐xA(x)x┐A(x)(2)利用x(A(x)∨B)xA(x)∨B和x(A(x)∧B)xA(x)∧B把量词移到全式的最前面，这样便得到前束范式。例2.11求公式的前束范式（1）xF(x)∧┐xG(x)

xF(x)∧┐yG(y) (换名规则)

xF(x)∧y┐G(y) (定理2.1第二式)

x(F(x)∧y┐G(y)) (定理2.1第二式)

xy(F(x)∧┐G(y)) (定理2.2第二式)

（

yx(F(x)∧┐G(y))）或者 xF(x)∧┐xG(x)

xF(x)∧x┐G(x) (定理2.1第二式)

x(F(x)∧┐G(x)) (定理2.3第一式)例2.11求公式的前束范式（2）xF(x)∨┐xG(x)

xF(x)∨x┐G(x) (定理2.1第二式)

xF(x)∨y┐G(y) (换名规则)

x(F(x)∨y┐G(y)) (定理2.2第一式)

xy(F(x)∨┐G(y)) (定理2.2第一式)说明公式的前束范式是不唯一的。例2.11求前束范式(3)xF(x)∧xG(x)

yF(y)∧xG(x) yx(F(y)∧G(x))(4)xF(x)→xG(x)

yF(y)→xG(x) yx(F(y)→G(x))(5)xF(x)→xG(x)

yF(y)→xG(x) yx(F(y)→G(x))(6)xF(x)→yG(y) xy(F(x)→G(x))例2.11求公式的前束范式(7)xF(x,y)→yG(x,y)

tF(t,y)→wG(x,w)(换名规则)

tw(F(t,y)→G(x,w))(定理2.2)或者 xF(x,y)→yG(x,y)

xF(x,t)→yG(w,y)(代替规则)

xy(F(x,t)→G(w,y))(定理2.2)说明解本题时一定注意，哪些个体变项是约束出现，哪些是自由出现，特别要注意那些既是约束出现又是自由出现的个体变项。不能混淆。例2.11求公式的前束范式(8)(x1F(x1,x2)→x2G(x2))→x1H(x1,x2,x3) (x4F(x4,x2)→x5G(x5))→x1H(x1,x2,x3)

x4x5(F(x4,x2)→G(x5))→x1H(x1,x2,x3)

x4x5x1((F(x4,x2)→G(x5))→H