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

更新时间:2023-11-17 04:50:01 阅读量: 教育文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

第二章 命题逻辑

§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

Top