第二章 命题逻辑

§2.2 主要解题方法

2.2.1 证明命题公式恒真或恒假

主要有如下方法：

方法一. 真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每

一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。

真值表法比较烦琐，但只要认真仔细，不会出错。

例2.2.1 说明 G= (P恒假还是可满足。

解：该公式的真值表如下：

P Q R PQPR Q (P0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 (PR)Q) 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 QPR G Q

R)

(P

Q)

(P

R)是恒真、

表2.2.1

由于表2.2.1中对应公式G所在列的每一取值全为1，故

G恒真。

方法二. 以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。

例2.2.2 说明 G= ((P

R)

R) (

(Q

P)

P)是恒真、恒假还是可满足。

解：由(P

(Q

P=0

知，((P

G恒假。

方法三. 设命题公式G含n个原子，若求得G的主析取范式包含所有2个极小项，则G是恒真的；若求得G的主合取范式包含所有2个极大项，则G是恒假的。

方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，Pn，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，Pn，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果

nn

R) R=P RQ

R=1，以及 P）

P = Q

P

P) P= （

R) R) ( (QP) P)=0，故