离散数学课后习题答案 .doc
《离散数学课后习题答案 .doc》由会员分享,可在线阅读,更多相关《离散数学课后习题答案 .doc(69页珍藏版)》请在沃文网上搜索。
1、第1章 习题解答11 除(3),( 4),( 5),( 11)外全是命题,其中,(1),( 2),( 8),( 9),(10),( 14),( 15)是简单命题,(6),( 7),( 12),( 13)是复合命题。分析首先应注意到,命题是陈述句,因而不是陈述句的句子都不是命题。本题中,(3)为疑问句,(5)为感叹句,(11)为祈使句,它们都不是陈述句,所以它们都不是命题。其次,( 4)这个句子是陈述句,但它表示的判断结果是不确定。又因为(1),(2),( 8),( 9),( 10),( 14),( 15)都是简单的陈述句,因而作为命题,它们都是简单命题。(6)和(7)各为由联结词“当且仅当”联
2、结起来的复合命题,(12)是由联结词“或”联结的复合命题,而(13)是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中,合取联结词有许多表述法,例如,“虽然,但是 ”、“不仅,而且 ”、“一面,一面 ”、“和 ”、“与”等。但要注意,有时“和”或“与”联结的是主语,构成简单命题。例如,(14)、( 15)中的“与”与“和”是联结的主语,这两个命题均为简单命题,而不是复合命题,希望读者在遇到“和”或“与”出现的命题时,要根据命题所陈述的含义加以区分。12 (1)p : 2是无理数,p 为真命题。(2)p : 5能被2 整除,p 为假命题。(6)p q 。其中,p :
3、2是素数,q:三角形有三条边。由于p 与q 都是真命题,因而p q 为假命题。(7)p q ,其中,p:雪是黑色的,q:太阳从东方升起。由于p 为假命题,q 为真命题,因而p q 为假命题。(8)p : 2000年10 月1 日天气晴好,今日(1999 年2 月13 日)我们还不知道p 的真假,但p 的真值是确定的(客观存在的),只是现在不知道而已。(9)p:太阳系外的星球上的生物。它的真值情况而定,是确定的。(10)p:小李在宿舍里. p 的真值则具体情况而定,是确定的。(12) p q ,其中,p : 4是偶数,q : 4是奇数。由于q 是假命题,所以,q为假命题,p q为真命题。(13)
4、p q,其中,p : 4是偶数,q : 4是奇数,由于q 是假命题,所以,p q 为假命题。(14) p:李明与王华是同学,真值由具体情况而定(是确定的)。(15) p:蓝色和黄色可以调配成绿色。这是真命题。分析命题的真值是唯一确定的,有些命题的真值我们立即可知,有些则不能马上知道,但它们的真值不会变化,是客观存在的。13 令p : 2 + 2 = 4,q : 3 + 3 = 6,则以下命题分别符号化为(1)p q(2)p q(3)p q(4)p q(5) p q(6)p q(7)p q(8) p q以上命题中,( 1),( 3),( 4),( 5),( 8)为真命题,其余均为假命题。分析本题
5、要求读者记住p q 及p q 的真值情况。p q 为假当且仅当p 为真,q 为假,而p q为真当且仅当p 与q 真值相同.由于p 与q 都是真命题,在4 个蕴含式中,只有(2)p r,其中,p 同(1), r:明天为3 号。在这里,当p 为真时,r 一定为假,p r为假,当p 为假时,无论r 为真还是为假,p r为真。15 (1)p q,其中,p:2 是偶数,q:2 是素数。此命题为真命题。(2)p q ,其中,p:小王聪明,q:小王用功(3)p q ,其中,p:天气冷,q:老王来了(4)p q,其中,p:他吃饭,q:他看电视(5)p q ,其中,p:天下大雨,q:他乘公共汽车上班(6)p q
6、 ,其中,p,q 的含义同(5)(7)p q ,其中,p,q 的含义同(5)(8)p q ,其中,p:经一事,q:长一智分析1在前4 个复合命题中,都使用了合取联结词,都符号化为合取式,这正说明合取联结词在使用时是很灵活的。在符号化时,应该注意,不要将联结词部分放入简单命题中。例如,在(2)中,不能这样写简单命题:p:小王不但聪明,q:小王而且用功。在(4)中不能这样写:p:他一边吃饭, q:他一边看电视。2 后4 个复合命题中,都使用了蕴含联结词,符号化为蕴含式,在这里,关键问题是要分清蕴含式的前件和后件。p q 所表达的基本逻辑关系为,p 是q 的充公条件,或者说q 是p 的必要条件,这种
7、逻辑关系在叙述上也是很灵活的。例如,“因为p,所以q”,“只要p,就q”“ p 仅当q”“ 只有q 才p”“除非q,否则p ”“ 没有q,就没有p”等都表达了q 是p 的必要条件,因而都符号化为p q 或p q 的蕴含式。在(5)中,q 是p 的必要条件,因而符号化为p q,而在(6)( 7)中,p成了q 的必要条件,因而符号化为q p。在(8)中,虽然没有出现联结词,但因两个命题的因果关系可知,应该符号化为蕴含式。16 (1),( 2)的真值为0,( 3),( 4)的真值为1。分析1 (1)中公式含3 个命题变项,因而它应该有23 = 8个赋值:000,001 , , 111 题中指派p,
8、q 为0, r 为1 ,于是就是考查001 是该公式p (q r)的成真赋值,还是成假赋值,易知001 是它的成假赋值。2 在公式(2),( 3),( 4)中均含4 个命题就项,因而共有24 = 16个赋值:0000,0001,1111。现在考查0011 是它的成假赋值。1.7 (1),( 2),( 4),( 9)均为重言式,( 3),( 7)为矛盾式,(5),( 6),(8),( 10)为非重言式的可满足式。一般说来,可用真值表法、等值演算法、主析取范式(主合取范式法等判断公式的类型。(1)对(1)采用两种方法判断它是重言式。真值表法表1.2 给出了(1)中公式的真值表,由于真值表的最后一列
9、全为1,所以,(1)为重言式。等值演算法p ( p q r ) p ( p p r ) (蕴含等值式) (p p ) p r (结合律)p q r p q r p(p q r)0 0 0 0 10 0 1 1 10 1 0 1 10 1 1 1 11 0 0 1 11 0 1 1 11 1 0 1 11 1 1 1 11q r (排中律) 1 (零律)由最后一步可知,(1)为重言式。(2)用等值演算法判(2)为重言式。( p p ) p (p ) p (蕴含等值式) p p (等幂律) p p (蕴含等值式) 1 (排中律)(3)用等值演算法判(3)为矛盾式( p q ) q (pq ) q
10、(蕴含等值式) p q q (德摩根律) p (q q ) (结合律) p 0 (矛盾律) 0 (零律)由最后一步可知,(3)为矛盾式。(5)用两种方法判(5)为非重言式的可满足式。真值表法由表1.3 可知(5)为非重言式的可满足式。p q p p q q p (p q ) (q p )0 0 1 0 1 10 1 1 1 1 11 0 0 1 1 11 1 0 1 0 0主析取范式法(p q ) (q p )(p q) (q p) (p q) (q p) (p q ) q p p q(p 1) (1q) (p (q q ) (p p) q ) (p q ) (p q ) (p q ) ( p
11、 q ) (p q ) (p q ) (p q ). 0 1 2 m m m在(3)的主析取范式中不含全部(4 个)极小项,所以(3)为非重言式的可满足式,请读者在以上演算每一步的后面,填上所用基本的等值式。其余各式的类型,请读者自己验证。分析1D 真值表法判断公式的类别是万能。公式A 为重言式当且仅当A 的真值表的最后一旬全为1;A 为矛盾式当且仅当A 的真值表的最后一列全为0;A为非重言式的可满足式当且仅当A 的真值表最后一列至少有一个1,又至少有一个0。真值表法不易出错,但当命题变项较多时,真值表的行数较多。2D 用等值演算法判断重言式与矛盾式比较方例,A 为重言式当且仅当A 与1 等值
12、;A 为矛盾式当且仅当A 与0 等值,当A 为非重言式的可满足式时,经过等值演算可将A 化简,然后用观察法找到一个成真赋值,再找到一个成假赋值,就可判断A 为非重言式的可满足式了。例如,对(6)用等值演算判断它的类型。(p p)q 0q (矛盾律)(p q) (q 0) (等价等值式)(0q) (q 0) (蕴含等值式) (1q ) q (同一律)1q (零律) q (同一律)到最后一步已将公式化得很简单。由此可知,无论p 取0 或1 值,只要q取0 值,原公式取值为1,即00 或10 都为原公式的成真赋值,而01,11 为成假赋值,于是公式为非重言式的可满足式。用主析取范式判断公式的类型也是
13、万能的。A 为重言式当且仅当A 的主析取范式含2n(n为A 中所含命题变项的个数)个极小项;A 为矛盾式当且仅当A 的主析取范式中不含任何极小项,记它的主析取范式为0;A 为非重言式的可满足式当且仅当A 的主析取范式中含极小项,但不是完全的。当命题变项较多时,用主析取范式法判公式的类型,运算量是很大的。用主合取范式判断公式的类型也是万能的。A 为重言式当且仅当A 的主合取范式中不含任何极大项,此时记A 的主合取范式为1;A 为矛盾式当且仅当A 的主合取范式含2n个极大项(n 为A 中含的命题变项的个数);A 为非重言式的可满足式当且仅当A 的主析取范式中含含极大项,但不是全部的。1.8 (1)
14、从左边开始演算( p q ) ( p q) p (q q ) (分配律) p 1 (排中律) p. (同一律)(2)从右边开始演算p (q r ) p (q r ) (蕴含等值式)(p q) (p r) (分配律)(p q) (p r). (蕴含等值式)(3)从左边开始演算(p q) ( p q) (q p) (p q) (p q) (p q ) ( p q ) ( p q ) ( p q ).请读者填上每步所用的基本等值式。本题也可以从右边开始演算( p q ) ( p q ) ( p q ) ( p q )(p q)(p q) (p q ) ( p q ) (p q) (p q ) (q
15、p) (q q) (1 p q ) (q p) 1 ( p q) (q p)(p q).读者填上每步所用的基本的等值式。1.9 (1)(p q)p) ( p q ) p (蕴含等值式)(p q) p) (德摩根律) (p q ) (p) (q q ) ( p q) p q p (结合律、交换律) ( p p) q (矛盾式) 0. (零律)由最后一步可知该公式为矛盾式。(2)( p q) (q p) ( p q )(p q) p) (蕴含等值式)由于较高层次等价号两边的公式相同,因而此公式无成假赋值,所以,它为重言式。(3)(p q)(q p) ( p q) (q p ) (蕴含等值式) (
16、p q) (q p ) (蕴含等值式)(p q)q p (德摩根律) q p (吸收律) p q. (交换律)由最后一步容易观察到,11 为该公式成假赋值,因而它不是重言式,又00,01,10 为成真赋值,因而它不是矛盾式,它是非重言式的可满足式。1.10 题中给出的F,G,H,R 都是2 元真值函数。给出的5 个联结词集都是全功能集,可以用观察法或等值演算法寻找与真值函数等值的公式。首先寻找在各联结词集中与F 等值的公式。(1)设A = ( p q ),易知A 是,中公式且与F 等值,即F A.(2)设B = p q ,易知B 是,中公式且与F 等值,即F B.(3)设C = (p q),易
17、知C 是,中公式,且F C.(4)设D = ( p (q q) ( p (q q),易知D 为中公式,且F D.(5)设E = ( p p) q ,易知E 为中公式,且F E.分析1 只要找到一个联结词集中与F 等值的公式,经过等值演算就可以找出其他联结词集中与F 等值的公式。例如,已知A =(p q)是,公式,且F A。进行以下演算,就可以找到F 等值的其他联结词集中的公式。对A进行等值演算,消去联结词,用,取代,得A = ( p q )(p q) p q记为B.则B 为,中公式,且F B 。再对A 进行等值演算,消去,用,取代,得A =(p q) (p q)记为C.则C 为,中公式,且F
18、C 。再对B 进行演算,消去,用取代,在演算中,注意,对于任意的公式A,有A (A A) A A.B = p q p (q q ) ( p (q q) ( p (q q) ( p (q q) (p (q q )记为D.则D 为中公式,且F D.再对C 进行演算,消去,用取代,在演算中注意,对于任意的公式AA (A A) A A.C = (p q) p q ( p p ) q记为E.则E 为中公式,且F E.2 开始找一个与某真值函数等值的公式的方法,除观察法外,就是根据该真值函数的真值表,求它的主析取范式,而后进行等值演算即可。例如,由G的真值表可知G 的主析取范式为,于是1 3 m m1 3
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 课后 习题 答案