证明永真可满足性的方法.ppt

第八章 证明永真可满足性的方法2 现在我们给出一个证明公式的另一种方法，以前讲述的是，给了一个公式A，如何判断它的永真性及可满足性，如何求出所有的成真指派，当然最直接的办法就是使用真值表。但当命题变元很多时，指派总数很大，非常麻烦，为了简化可使用逐次指派法，我们采用如下方法：,我们通过例子来说明这种方法该给定公式：A=（PQ）R）（PQ）（PR）1)将P用T代入作为左分支有：（TQ）R）（TQ）（TR）2)将P用F代入作为右分支有：（FQ）R）（FQ）（FR）3)形如,A P=T P=F（TQ）R）（TQ）（TR）（FQ）R）（FQ）（FR）,利用如下公式：TP=PT=T TP=TP=P FP=P FP=F FP=T（PF）=P（TP）=P（FP）=P（PP）=(PP)=P（PP）=T（PP）=T P=P,5）利用上述公式则有 A P=T P=F（QR）Q）R T 6）当得到T或F时便终止，因此右分支终止，而左分 之继续这个过程，既：分别用T与F代替Q，也就 是给Q指派，一般地我们构造了一个公式的二叉 树。它的根是给定的公式如果最后所有终极公式 都是T，那么原公式是永真公式，如果最后所有终 极公式都是F，原公式便是永假公式。否则便是可 满足公式。,7）上述给定的A的完全的二叉树如下：（PQR）（PQ）（PR）P=T P=F（QR）Q）R T Q=T Q=F RR T R=T R=F T T 所以公式永真,8）为了书写方便，也可以将上述方法改写为下列形 式，（并可作一些修改，即：可对出现次数最多 的命题变元或者马上可给出结果的一个先指定 值）。方法用例子说明：例如:设A=（PR）（PQ）（Q（PR）先令：P=T 有：A=（TR）（TQ）（Q（TR）=T（Q（QR）=（Q（QR）,再令：Q=T 有 A=（T（TR）=R=R 所以成真指派TTT，成假指派TTF又令：Q=F 有 A=（F（FR）=（FF）=F,所以成假指派还有TFX 再令：P=F 有 A=（FR）（FQ）（Q（FR）=R（Q（QF）=R（QF）=RQ 此时，成真指派为FTT，FFF，成假指派为 FTF，FFT。总之：A的成真指派为TTT，TFX，FFF，而成假指派 为TTF，FTF，FFT。,