离散数学谓词公式与解释.ppt

符号体系：个体常元符号：a,b,c,a1,a2,a3,个体变元:x,y,z,x1,x2,x3,函数符号:f,g,h,f1,f2,f3,谓词符号:F,G,H,量词符号:联结词:项的定义个体变元、个体常元是项；若是任意n元函数，t1,t2,tn是项，则是项；有限次的应用1，2得到项。,2.2一阶逻辑合式公式及解释,原子公式：为n元谓词符号，t1,t2,tn是项，则是原子公式；合式公式的归纳定义：1、任意的原子公式是公式2、若A是公式，则xA、xA是公式；3、若A、B是公式，则A、AB、AB、AB、AB是公式；有限次地应用前三条，得到公式。,判断下列符号串是否为合式公式：x(P(x)Q(x)xy(P(x)Q(y)yxP(x)xf(x)x(g(x,y)f(x),一、合式公式的定义：,在谓词公式中，形如xP(x)或xP(x)以及xP(x，y)的部分中x称为指导变元，在辖域中,x的所有出现称为约束变元（约束出现）；y是自由变元（自由出现）。量词的辖域(x)P(x)或(x)P(x)中的公式P(x)，通称为量词的辖域。换言之，量词的辖域是邻接其后的公式，除非辖域是原子公式，否则应在所辖公式的两侧插入圆括号。,二、约束部分,量词辖域举例,例如：xF(x)G(x,y)解：x的辖域仅F(x),x是指导变元，变元x第一次出现是约束出现，第二次出现是自由出现，y的出现是自由出现。所以第一个x是约束变元，第二个x是自由变元，本质上这两个x的含义是不同的；而y仅是自由变元。,换名规则,可以看出,在谓词公式中一个变元可能既是约束出现,同时又有自由出现,则该变元既是自由变元又是约束变元,本质上这两种出现,用的是一个符号,实质上是不同的含义。为避免混淆,需要改名。改名要采用以下规则,使谓词公式的含义不改变。1、换名规则：对约束变元进行换名。将量词辖域内出现的某个约束变元及其相应量词中的指导变元，可以换成一个其他变元，改变元不能与本辖域内的其他变元同名，公式中的其他部分不改变。2、代替规则：对自由变元进行代入。整个谓词公式中同一个字母的自由变元是指同一个个体名词。因此可以用整个公式中没有的变元符号来代替，且要求整个公式中该变元同时用同一个符号代替。,换名规则举例,xF(x,y)xG(x,y)改为：xF(x,y)uG(u,y)或者为：zF(z,y)xG(x,y)对x(F(x,y)yG(x,y)F(x,y)改为：x(F(x,t)yG(x,y)F(s,t)或者为：t(F(t,y)yG(t,y)F(x,y),谓词公式的解释,谓词逻辑中的解释(赋值)在命题逻辑对每个命题符号作个真值指定可以得一个公式的一个指派,又称赋值,又称解释。如公式中共出现n个不同的命题符号,则共有2n个解释,因而可以列出公式的真值表。而谓词逻辑中公式的赋值解释是怎样的呢？例如公式：xF(x,a)xG(f(x),a),三、谓词公式的赋值(解释),一个解释由4部分组成：（1）非空个体域D；（2）D中特定元素；（3）D上特定函数；（4）D上特定谓词。公式xF(x,a)xG(f(x),a)指定：D=实数集合；a=0；f(x):3x;F(x,y):xy；G(x,y):x=y。则x(x0)x(3x=0)假命题。,解释举例1,给定解释I如下：,x(F(x)G(x,2)(F(2)G(2,2)(F(3)G(3,2)011,yL(2,y)yL(3,y)(L(2,2)L(2,3)(L(3,2)L(3,3)(10)(01)1,解释举例2,例2：已知指定一个解释N如下：(1)个体域为自然数集合DN(2)指定常项a=0(3)DN上的指定函数f(x,y)=x+y,g(x,y)=x*y(4)指定谓词F(x,y)为x=y在以上指定的解释N下,说明下列公式的真值(1)xF(g(x,a),x)即x(x*0=x)该命题假的(2)xy(F(f(x,a),y)F(f(y,a),x)在解释N下此公式：xy(x+0=yy+0=x)此命题为真(3)F(f(x,y),f(y,z)在解释N下该公式x+y=y+z此时,x,y,z均为自由变元,解释不对自由变元进行指定。因而该公式是命题函数,不是命题,真值不能确定。,解释的说明,(1)一个谓词公式如果不含自由变元,则在一个解释下,可以得到确定的真值,不同的解释下可能得到不同的真值。(2)公式的解释并不对变元进行指定,如果公式中含有自由变元,即使对公式进行了一个指派,也得不到确定的真值,其仅是个命题函数,但约束变元不受此限制。3）有公式的解释定义可以看出,公式的解释有许多的解释,当D为无限集时,公式有无限多个解释,根本不可能将其一一列出,因而谓词逻辑的公式不可能有真值表可列。,四、谓词公式的类型,设A是公式。如果A在任何的解释下都是真的，则A是永真式；如果A在任何的解释下都是假的，则A是永假式；如果A在一些解释下为假，一些解释下为真，则A是非永真的可满足式。,例如：xA(x)xA(x)是永真式；xA(x)xA(x）是永假式。,代换实例,设A0是含命题变元p1,p2,pn的命题逻辑公式，A1,A2,An是一阶逻辑公式，用Ai(1in)替换A0中的pi的处处出现所得到的一阶逻辑公式A称为命题逻辑公式A0的替换实例。定理：命题逻辑中的永真式的任意替换实例在一阶逻辑中都是永真式；命题逻辑中的矛盾式的任意替换实例在一阶逻辑中都是矛盾式。,1、永真式和永假式的代入实例是永真、永假式；2.对于某些简单的公式，特别对于简单的闭式，可在假定给定任意解释的前提下该公式的真值都为真（或者为假）来证明该公式是永真式（或矛盾式）。3.要证明一个公式是可满足式，只要找到一个解释，使得该公式的真值为真即可。同时为了证明它不是永真式，只要找一个解释，使得该公式的真值为假即可。,公式类型举例,判断下列公式的类型：1)xF(x)(xyG(x,y)xF(x)2)xF(x)xF(x)3)xyF(x,y)yxF(x,y),xF(x)(xyG(x,y)xF(x),解：显然该公式是：P(QP)的替换实例。容易知道P(QP)是永真式，从而xF(x)(xyG(x,y)xF(x)是永真式。,2)xF(x)xF(x),设在任意的解释I下，1）xF(x)为真，则a，使得F(a)为真，使得xF(x)为真，在这种情况下，xF(x)xF(x)为真；2）xF(x)为假，xF(x)xF(x)为真。从而，在蕴涵式的前件xF(x)为1或0的情况，蕴涵式都为真。又由解释I的任意性，知公式xF(x)xF(x)永真。,3)xyF(x,y)yxF(x,y),1）取解释I1为：D=R,F(x,y):xy则公式为：xy(xy)yx(xy)=10=0，从而公式不是永真式；2)取解释I2为：D=R,F(x,y):x.y=0则公式为：xy(xy=0)yx(xy=0)=1