吉林大学离散数学课后习题答案
更新时间: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
正在阅读:
吉林大学离散数学课后习题答案11-17
xx年上半年安全工作总结与分析06-14
一年级语文《自己去吧》教案设计优秀7篇03-22
湖南省长沙市第一中学2022届高三上学期第四次月考化学试题04-08
心理学作业《爱德华大夫》06-01
网站制作课程设计_06-13
期待长大作文600字06-23
系统遗传学03-11
文学,舞蹈学,试题,盛哥版03-08
上市公司经营水务产业的模式05-06
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 吉林大学
- 离散
- 课后
- 习题
- 答案
- 数学
- 2013年湖北高考美术联考《书法基础理论》试卷
- 三期B15、B16、B17、B18栋厂房施工安全与进度推进会议纪要
- 塔罗牌关键字以及牌阵大全 - 图文
- 2017普通高校招生录取办法及考试违规处理办法调查问卷(参考答案修正后)
- 东师民法16秋在线作业2
- excel练习
- 经典时空观与相对论时空观
- 当代大学生恋爱观调查研究报告
- 公司财务学作业标准答案
- 自杀或企图自杀处理应急预案
- 工业锅炉能效测试中的术语和定义
- 化学品安全技术说明书2016年 最新版
- 无机非金属材料的主角 - 硅习题及答案
- 西师版四年级下册数学上半期教案
- 推销实务期末考试试卷(B卷)(附答案)
- 湖南大学数字信号处理试题
- 北大幼教落户南山集团幼儿园,家长很放心 - 图文
- 第一讲 认识运动负荷
- 02多项选择题
- 红军将领汤慕禹