2.2谓词公式与解释

《2.2谓词公式与解释》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、符号体系：个体常元符号：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、A∧B、A∨B、A→B、AB是公式

2、；有限次地应用前三条，得到公式。判断下列符号串是否为合式公式：x(P(x)∧Q(x))xy(P(x)Q(y))yx∧P(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(

3、x)G(x,y)解：x的辖域仅F(x),x是指导变元，变元x第一次出现是约束出现，第二次出现是自由出现，y的出现是自由出现。所以第一个x是约束变元，第二个x是自由变元，本质上这两个x的含义是不同的；而y仅是自由变元。换名规则可以看出,在谓词公式中一个变元可能既是约束出现,同时又有自由出现,则该变元既是自由变元又是约束变元,本质上这两种出现,用的是一个符号,实质上是不同的含义。为避免混淆,需要改名。改名要采用以下规则,使谓词公式的含义不改变。1、换名规则：对约束变元进行换名。将量词辖域内出现的某个约束变元及其相应量词中的指导变元，可以换成一个其他变元，改变元不能与

4、本辖域内的其他变元同名，公式中的其他部分不改变。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)谓词公式的解释谓词逻辑中的解释(赋值)在命题逻辑对

5、每个命题符号作个真值指定可以得一个公式的一个指派,又称赋值,又称解释。如公式中共出现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):x≥y；G(x,y):x=y。则x(x≥0)∧x(3x=0)假命题。解释举例1给定解释I如下：x(F

6、(x)∧G(x,2))(F(2)∧G(2,2))∧(F(3)∧G(3,2))0∧11yL(2,y)∧yL(3,y)(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))(1∨0)∧(0∨1)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)xy(F(f(x,a),y)F(f(y,a),x))在解释

7、N下此公式：xy(x+0=yy+0=x)此命题为真(3)F(f(x,y),f(y,z))在解释N下该公式x+y=y+z此时,x,y,z均为自由变元,解释不对自由变元进行指定。因而该公式是命题函数,不是命题,真值不能确定。解释的说明(1)一个谓词公式如果不含自由变元,则在一个解释下,可以得到确定的真值,不同的解释下可能得到不同的真值。(2)公式的解释并不对变元进行指定,如果公式中含有自由变元,即使对公式进行了一个指派,也得不到确定的真值,其仅是个命题函数,但约束变元不受此限制。3）有公式的解释定义可以看出,公式的解释有许多的解释,当D为无限集时,公式有无