第二章 命题逻辑

§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）