离散数学2-3.pptVIP

前束范式 谓词演算的推理理论 应注意的几个问题 在命题演算中，常常要将公式化成规范形式，对于谓词演算，也有类似情况，一个谓词演算公式，可以化为与它等价的范式。 定义2-6、1 一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的未尾，则该公式叫做前束范式。 前束范式可记为下述形式： （□v1）(□v2)…(□vn)A，其中□可能是量词?或量词?，vi(i=1,2,…,n)是客体变元，A是没有量词的谓词公式。 定理2-6、1 任意一个谓词公式，均和一个前束范式等价。 证明：首先利用量词转化公式，把否定深入到命题变元和谓词公式前面，其次利用（?x）(A?B(x))?A?(?x)B(x)和（?x）（A?B(x)）?A?(?x)B(x)把量词移到全式的最前面，这样便得到前束范式。 定义2-6、2 一个wffA如果具有如下形式称为前束合取范式（□v1）(□v2)…(□vn)[(A11?A12?…?A1l2)?(A21?A22?…?A2l2)?…?(Am1?Am2?…?Amlm)]其中□可能是量词?或?，vi(I=1,2,…,n)是客体变元，Aij是原子公式或其否定。 定理2-6、2 每一个wffA都可转化为与其等价的前束合取范式。 定义2-6、3 一个wffA如果具有如下形式称为前束析取范式。？？？（□v1）(□v2)…(□vn)[(A11?A12?…?A1l2)?(A21?A22?…?A2l2)?…?(Am1?Am2?…?Amlm)] 其中□可能是量词?或?，vi(I=1,2,…,n)是客体变元，Aij是原子公式或其否定。 定理2-6、3 每一个wffA都可转化为与其等价的前束析取范式。 下面将举例说明以上定理、定义 例题1 把公式（?x）P(x)→(?x)Q(x)转化为前束范式。 解 （?x）P(x)→(?x)Q(x) ?(?x)┒P(x)?(?x)Q(x) ?(?x)(┒P(x)?Q(x)) 例题2 化公式 （?x）(?y)((?z)(P(x,z)?P(y,z))→(?u)Q(x,y,u))为前束范式。 解：原式?(?x)(?y)(┒(?z) (P(x,z)?P(y,z))?(?u)Q(x,y,u)) ?(?x)(?y)((?z) (┒P(x,z)?┒P(y,z))?(?u)Q(x,y,u)) ?(?x)(?y)(?z)(?u) (┒P(x,z)?┒P(x,z)?Q(x,y,u)) 例题3 把公式 ┒(?x){(?y)A(x,y)→(?x)(?y)[B(x,y)?(?y)(A(y,x)→B(x,y))]}化为前束范式。 例题3 解：第一步否定深入 原式?(?x)┒{┒(?y)A(x,y)?(?x)(?y) [B(x,y)?(?y)(A(y,x)→B(x,y))]} ?(?x){(?y)A(x,y)?(?x)(?y) [┒B(x,y)?(?y)┒(A(y,x)→B(x,y))]} 第二步改名，以便把量词提到前面。 ?(?x){(?y)A(x,y)?(?u)(?R)[┒B(u,R)? (?z)┒(A(z,u)→B(u,z))]} (?x)(?y)(?u)(?R)(?z){A(x,y)∧[┒B(u,R) ∨┒(A(z,u)→B(u,z))]} 谓词演算的推理方法,可看作是命题演算推理方法的扩张。因为谓词演算的很多等价式和蕴含式，是命题演算有关公式的推广，所以命题演算中的推理规则，如P、T和CP规则等亦可在谓词的推理中应用，但是在谓词推理中，某些前提与结论可能是受量词限制的，为使用这些等价式和蕴含式，必须在推理过程中有消去和添加量词的规则，以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。 现介绍如下规则： (1)全称指定规则，它表示为US (?x)P(x) ∴ P(c) US有两种形式可以用： 1）（?x）P（x）?P（y） y是任意的不在P（x）中出现的个体变项 2）（?x）P（x）?P（y） y是任意个体常项 (2)全称推广规则，它表示为UG P(c)