吉林大学离散数学课后习题答案

第二章 命题逻辑

§2.2 主要解题方法

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

主要有如下方法：

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

18

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

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

例2.2.1 说明 G= (P?Q?R)?(P?Q)?(P?R)是恒真、恒假还是可满足。

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

P Q R P?QP?(P?QP?R G ?R Q ?R)?(P?Q) 0 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 表2.2.1

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

19

1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 G恒真。

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

例2.2.2 说明 G= ((P?R) ?? R)? (? (Q?P) ? P)是恒真、恒假还是可满足。

解：由(P?R) ?? R=?P? R?? R=1，以及

? (Q?P) ? P= ?（?Q? P）? P = Q?? P? P=0 知，((P?R) ?? R)? (? (Q?P) ? P)=0，故G恒

假。

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

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

20

恒假，若最终结果有1，有0，则是可满足的。例子参见书中例2.4.3。

方法五. 注意到公式G蕴涵公式H的充要条件是：公式G?H是恒真的；公式G，H等价的充要条件是：公式G?H是恒真的，因此，如果待考查公式是G?H型的，可将证明G?H是恒真的转化为证明G蕴涵H；如果待考查公式是G?H型的，可将证明G?H是恒真的转化为证明G和H彼此相蕴涵。

例2.2.3 证明 G= (P?R) ? ( (Q? R) ?(( P?Q) ? R))恒真。

证明：要证明(P?R) ? ( (Q? R) ?(( P?Q) ? R))恒真，只需证明(P?R) ?( (Q? R) ?(( P?Q) ? R))。我们使用形式演绎法。

（1）P?R 规则1 （2）Q? R 附加前提

（3）?P? R 规则2，根据（1） （4）?Q? R 规则2，根据（2） （5）（?P? R）?（?Q? R） 规则2，根据（3）、（4）

（6）（?P??Q）? R 规则2，根据（5） （7）?（P? Q）? R 规则2，根据（6）

21

（8）（P?Q）? R 规则2，根据（7） （9）(Q? R) ?(( P?Q) ? R) 规则3，根据（2）、（8）

2.2.2 公式蕴涵的证明方法

主要有如下方法：给出两个公式A，B，证明A蕴涵B，我们有如下几种方法：

方法一. 真值表法。将公式A和公式B同列在一张真值表中，扫描公式A所对应的列，验证该列真值为1的每一项，它所在行上相应公式B所对应列上的每一项必为1（真），则公式A蕴涵B。

例2.2.4 设A= (P?Q?R)?(P?Q)，B=(P?R)，证明：A?B。 证明：

P Q R P?QP??R Q 0 0 0 0

A B 0 0 1 1 0 1 0 1 22

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 0 0 1 1 0 1 0 1 1 1 0 1 表2.2.2

0 0 1 1 0 0 0 1 1 1 0 1

由表2.2.2可以看出，使A为真的解释均使B亦为真，因此，A?B。

方法二. 证明A?B是恒真公式。

由例2.2.1知，(P?Q?R)?(P?Q)?(P?R)恒真，因此，立即可得到例2.2.4中的结论：(P?Q?R)?(P?Q)? (P?R)，即A?B。

例2.2.5 设A、B和C为命题公式，且A?B。请分别阐述（肯定或否定）下列关系式的正确性。 （1）(A?C) ? (B?C)； （2）(A?C) ?( B?C)。

解：由A?B知，A?B是恒真公式，故A=1时，B不可能为0。 真值表如下： A

B C 23

A?B (A?C) (A?C) ? (B?C) 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 表2.2.3

1 1 1 1 1 1 ? ( B?C) 1 1 0 1 1 1 从真值表可以看出，(A?C) ? (B?C)是恒真公式，所以，(A?C) ?( B?C) (A?C) ? (B?C)正确；(A?C) ? ( B?C)不是恒真公式，所以，(A?C) ?( B?C)不正确。

例2.2.6 设A=(R? P) ? Q，B= P? Q，证明A蕴涵B。 证明：我们来证明A?B恒真。

((R? P) ? Q) ?( P? Q)= ? (? ( ?R?P) ?Q) ?(?P?Q)

=((?R?P) ?? Q) ?(?P?Q) =(?R?? Q) ?( P ?? Q) ??( P ?? Q)

=1

24

方法三. 利用一些基本等价式及蕴涵式进行推导。 对于例2.2.6，由基本等价式可得：

A=(R? P) ? Q =? ( ?R?P) ?Q = (R?? P) ?Q =( R?Q) ?(? P?Q) =( R?Q) ?( P? Q)

由教材中基本蕴涵式2. P?Q?Q可知，( R?Q) ?( P? Q) ?(P? Q)，即A蕴涵B。

方法四. 任取解释I，若I满足A，往证I满足B。

例2.2.7 设A= P? Q，B=(R?Q) ?（（P?R）? Q），证明A蕴涵B。

证明：任取解释I，若I满足A，则有如下两种情况： （1）在解释I下，P为假，这时，B等价于(R?Q) ?（R? Q），因此，I亦满足B。

（2）在解释I下，P为真，Q为真，所以，P?R? Q为真，故B为真，即，I满足B。 综上，I满足B，因此，A蕴涵B。

25

方法五. 反证法，设结论假，往证前提假。

对于例2.2.6，证明(R? P) ? Q蕴涵 P? Q，若使用方法三，是很烦琐的，而使用方法四，就很简单。假设存在解释I使P? Q为假，则只有一种情形，P在I下为真，且Q在I下为假，这时R? P在I下为真，故I弄假(R? P) ? Q。因此，(R? P) ? Q蕴涵 P? Q。

方法六. 分别将公式A和公式B转化为它们各自的主析取范式或主合取范式。若公式A的主析取范式所包含的所有极小项也包含在公式B的主析取范式中；或者，公式B的主合取范式中所包含的极大项均包含在公式A的主合取范式中，则公式A蕴涵公式B。

使用这种方法需要注意，当公式A和公式B中包含的原子不完全相同时，在求两公式的极小项或极大项时，要考虑该两公式包含命题原子的并集中的所有原子。 在例2.2.6中，A和B的主析取范式分别为：

A= (? P?? Q?R) ?(? P?Q??R) ?

(? P?Q?R) ? (P?Q??R) ? ( P?Q?R)， B= (? P?? Q??R) ? (? P?? Q?R) ? (? P?Q??R) ?

(? P?Q?R) ? (P?Q??R) ? ( P?Q?R)，

可见，A?B。

A和B的主合取范式分别为：

26

A=(P?Q?R) ?(? P?Q?R) ?(? P?Q??R) ,

B=(? P?Q?R) ?(? P?Q??R)

可见，A?B。

另外若给出前提集合S={G1 ，…，Gk }，公式G，证明S?G有如下两种方法： 1. G1 ? …? Gk ?G

2. 形式演绎法：根据一些基本等价式和基本蕴涵式，从S出发，演绎出G。

教材中已经给出了这方面的例子，在此不再赘述。

2.2.3 求主合取范式和主析取范式

1. 极小项与极大项的性质

以3个原子为例，则对应极小项和极大项的表为： P 0 0 0 0

Q 0 0 1 1 R 0 1 0 1 极小项 m0=? P?? Q??R m1=? P?? Q?R m2=? P? Q??R m3=? P? Q?R 27

极大项 M0=P?Q?R M1=P?Q??R M2=P??Q?R M3=P??Q??R

1 1 1 1 0 0 1 1 0 1 0 1 m4= P?? Q??R m5=P?? Q?R m6= P?Q??R m7= P? Q?R 表2.2.4

M4=?P?Q?R M5=?P?Q??R M6=?P??Q?R M7=?P??Q??R

由表2.2.4可知，对n个命题原子P1，…，Pn，极小项有如下性质：

（1）n个命题原子P1，…，Pn有2n个不同的解释，每个解释对应P1，…，Pn的一个极小项。

（2）对P1，…，Pn的任意一个极小项m，有且只有一个解释使m取1值，若使极小项取1的解释对应的二进制数为i，则m记为mi，于是关于P1，…，Pn的全部极小项为m0，m1，…，m2?1。

n（3）任意两个不同的极小项的合取式恒假：mi? mj=0，i≠j。 （4）所有极小项的析取式恒真：?mi=1。

i?02n?1极大项有如下性质：

（1）n个命题原子P1，…，Pn有2n个不同的解释，每个解释对应P1，…，Pn的一个极大项。

（2）对P1，…，Pn的任意一个极大项M，有且只有一个解释使M取0值，若使极大项取0的解释对应的二进制数

28

为i，则M记为Mi，于是关于P1，…，Pn的全部极大项为M0，M1，…，M2?1。

n（3）任意两个不同的极大项的析取式恒真：Mi ? Mj=1，i≠j。

（4）所有极大项的合取式恒假：?Mi=0。

i?02n?1

2. 主合取范式与主析取范式之间的关系

由极小项和极大项的定义可知，二者有如下关系：

mi=? Mi ，Mi=?mi

由此可知，若P?Q?R为一公式G的主合取范式，则

G =??G

=?? M0

= ? (M1? M2?…? M6) = ?M1??M2?…??M6 = m1? m2?…? m6 为G的主析取范式。

若（?P? Q）?（? P?? Q）?（ P? Q）为一公式H的主析取范式，则

H=??H

=??（(?P? Q）?（? P?? Q）

29

?（ P? Q）)

=?（?（m0? m1? m3））

= ? (m2) =M2

= ?P?Q 为H的主合取范式。

一般地，若公式A中含n个命题原子，且A的主析取范式中含有k个极小项：mi,...,mi，则?A的主析取范式中必含

1k有其余的2n-k个极小项，不妨设为：mj,...,mj，即

12n?k?A=mj因此，

1?...?mjn2?k。

A=??A = ?（mj1?...?mjn12?k）

2?k =?mj =Mj1?...??mjn2?k

?...?Mjn。

由此可知，从一公式A的主析取范式求其主合取范式的步骤如下：

（1）求出A的主析取范式中没有包含的所有极小项。 （2）求出与（1）中极小项下标相同的极大项。

（3）将（2）求出的所有极大项合取起来，即得A的主合取范式。

类似地，从一公式A的主合取范式求其主析取范式的步骤为：

30

（1）求出A的主合取范式中没有包含的所有极大项。 （2）求出与（1）中极大项下标相同的极小项。

（3）将（2）求出的所有极小项析取起来，即得A的主析取范式。

3. 求主合取范式和主析取范式的方法

方法一. 真值表法。主析取范式恰好是使得公式为真的解释所对应的极小项的析取组成，主合取范式恰好是使得公式为假的解释所对应的极大项的合取组成。

方法二. 公式推导法。设命题公式G中所有不同原子为P1，…，Pn，则G的主析取范式的求法如下： (a) 将公式G化为析取范式。

(b) 删去析取范式中所有恒假的短语。

(c) 用等幂律将短语中重复出现的同一文字化简为一次出现，如，P?P=P。

(d) 对于所有不是关于P1，…，Pn的极小项的短语使用同一律，补进短语中未出现的所有命题原子，并使用分配律展开，即，如果短语Gi’不是关于P1，…，Pn的极小项，则Gi’中必然缺少原子，不妨设为P j1，…，Pjk，于是 Gi’= Gi’?(Pj1?? Pj1)?…?( Pjk?? Pjk)

31

=mi1?...?mik

2这样，就将非极小项Gi’化成了一些极小项之析取。将相同的短语的多次出现化为一次出现，就得到了给定公式的主析取范式。

主合取范式的求法类似，留给读者作为练习。

由上面讨论可知，只要求出一种范式，可立即得到另外一种范式。

例2.2.8 求公式G= P→(Q→R)的主析取范式与主合取范式。

解：（1）使用真值表法。见表2.2.5。 P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 表2.2.5

32

R 0 1 0 1 0 1 0 1 P→(Q→R) 1 1 1 1 1 1 0 1

本文来源：https://www.bwwdw.com/article/k5fv.html