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

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