第二章 命题逻辑
§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，故
全为1，则公式G恒真，若最终结果全为0，则公式G恒假，若最终结果有1，有0，则是可满足的。例子参见书中例2.4.3。 方法五. 注意到公式G蕴涵公式H的充要条件是：公式G
H是恒真的；公式G，H等价的充要条件是：公式G
H是H
恒真的，因此，如果待考查公式是GH型的，可将证明G
是恒真的转化为证明G蕴涵H；如果待考查公式是G可将证明G
例2.2.3 证明 G= (PR))恒真。 证明：要证明(P恒真，只需证明(P
R) R)
( (Q( (Q
R) R)
(( P(( P
R) ( (Q
R) (( P
H型的，
H是恒真的转化为证明G和H彼此相蕴涵。
Q)
Q) Q)
R)) R))。
我们使用形式演绎法。 （1）P（2）Q（3）（4）（5）（（4） （6）（（7）
P（PQ）
Q） Q）
R 规则2，根据（5） R 规则2，根据（6）
PQ
R 规则1 R 附加前提
R 规则2，根据（1） R 规则2，根据（2）
Q
R） 规则2，根据（3）、
P R）（
（8）（P R 规则2，根据（7）