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

§2.2 一阶逻辑合式公式及解释 原子公式： 为n元谓词符号，t1,t2,…,tn 是项，则 是原子公式； 合式公式的归纳定义： 1、任意的原子公式是公式 2、若A是公式，则?xA、?xA是公式； 3、若A、B是公式，则? A、A∧ B、A∨B、A → B、A ?B是公式； 有限次地应用前三条，得到公式。 二、约束部分 在谓词公式中，形如?xP(x)或?xP(x)以及 ?xP(x，y)的部分中x称为指导变元，在辖域中,x的所有出现称为约束变元（约束出现）；y是自由变元（自由出现）。量词的辖域 ?(x)P(x)或?(x)P(x)中的公式P(x)，通称为量词的辖域。换言之，量词的辖域是邻接其后的公式，除非辖域是原子公式，否则应在所辖公式的两侧插入圆括号。 量词辖域举例 例如：?x F(x)?G(x,y) 解：?x的辖域仅F(x),x是指导变元，变元x第一次出现是约束出现，第二次出现是自由出现，y的出现是自由出现。所以第一个x是约束变元，第二个x是自由变元，本质上这两个x的含义是不同的；而y仅是自由变元。 换名规则 可以看出,在谓词公式中一个变元可能既是约束出现,同时又有自由出现,则该变元既是自由变元又是约束变元,本质上这两种出现,用的是一个符号,实质上是不同的含义。为避免混淆,需要改名。改名要采用以下规则,使谓词公式的含义不改变。 1、 换名规则：对约束变元进行换名。 将量词辖域内出现的某个约束变元及其相应量词中的指导变元，可以换成一个其他变元，改变元不能与本辖域内的其他变元同名，公式中的其他部分不改变。 2、 代替规则：对自由变元进行代入。 整个谓词公式中同一个字母的自由变元是指同一个个体名词。因此可以用整个公式中没有的变元符号来代替，且要求整个公式中该变元同时用同一个符号代替。 换名规则举例 ?x F(x,y)∧?x G(x,y) 改为：?x F(x,y)∧?u G(u,y) 或者为： ?z F(z,y)∧?x G(x,y) 对?x (F(x,y)∧?y G(x,y)) ?F(x,y) 改为： ?x (F(x,t)∧?y G(x,y)) ?F(s,t) 或者为：?t (F(t,y)∧?y G(t,y)) ?F(x,y) 谓词公式的解释 谓词逻辑中的解释(赋值) 在命题逻辑对每个命题符号作个真值指定可以得一个公式的一个指派,又称赋值,又称解释。如公式中共出现n个不同的命题符号,则共有2n个解释,因而可以列出公式的真值表。而谓词逻辑中公式的赋值解释是怎样的呢？ 例如公式：?x F(x,a)∧?x G(f(x),a) 三、谓词公式的赋值(解释) 一个解释由4部分组成： （1） 非空个体域D； （2）D中特定元素； （3）D上特定函数； （4）D上特定谓词。 公式?x F(x,a)∧?x G(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如下： 解释举例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)) 在解释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为无限集时,公式有无限多个解释,根