《离散数学第五版前3章课后习题答案.docx》由会员分享，可在线阅读，更多相关《离散数学第五版前3章课后习题答案.docx（12页珍藏版）》请在三一文库上搜索。
1、第 1章习题1.1(2) 简单命题（3），（ 4），（ 5）不是命题(6) 复合命题1.5（ 1） p q ，其中， p： 2 是偶数， q： 2 是素数。（ 5） pq ，其中， p：天下大雨， q：他乘公共汽车上班（ 6） qp ，其中， p， q 的含义同（ 5）（ 7） qp ，其中， p， q 的含义同（ 5）1.7（ 1）对（ 1）采用两种方法判断它是重言式。真值表法表 1.2给出了（ 1）中公式的真值表，由于真值表的最后一列全为1，所以，（ 1）为重言式。pqrp q rp ( p q r )0000100111010110111110011101111101111111等值演算
2、法p( pqr )p( pqr )（蕴含等值式）(pp)qr（结合律）1qr（排中律）1（零律）由最后一步可知， （ 1）为重言式。（3）用等值演算法判（3）为矛盾式( pq)q(pq)qp q qp ( q q)（蕴含等值式）（德·摩根律）（结合律）p 0（矛盾律）0（零律）由最后一步可知， （ 3）为矛盾式。（10）非重言式的可满足式1.8 （ 1）从左边开始演算( pq)( pq)p(qq)（分配律）p1（排中律）p.（同一律）（2）从右边开始演算p( qr )p(qr )(pq)(pr )( pq)( pr ).1.9 （ 1）（蕴含等值式）（分配律）（蕴含等值式）( pq)
3、p)( pq)p)（蕴含等值式）pqp（德·摩根律）( pp)q（结合律、交换律）0q（矛盾式）0.（零律）由最后一步可知该公式为矛盾式。（2） ( pq) (qp)( p q)( pq)( p q)（等价等值式）由于较高层次等价号两边的公式相同，因而此公式无成假赋值，所以，它为重言式。1.12 (1)设 (1) 中公式为A.A( p(qr )( pqr )A( p(qr )( pqr )Ap ( qr ) ( p q r )A( pq) ( pr ) ( p q r )A( pq ( rr ) ( p (qq)r ) ( p q r )A( pqr ) ( pq r ) ( pqr
4、 ) ( p qr ) ( p q r )A(pqr )(pqr )(pqr )( pqr )Am0m1m2m7于是 , 公式 A 的主析取范式为m0m1m2m7易知 ,A 的主合取范式为M3M4M5M6A 的成真赋值为000, 001, 010, 111A 的成假赋值为011,100,101,110(2) 设 (2) 中公式为 BB(pq)(qp)(pq)( qp)( pq)(qp)( pq) (qp)(pq)qp(pq)( pp)q)( p ( qq)( pq) ( pq) ( pq) ( pq) ( p q)(pq)( pq)( pq)m0m2m3所以 ,B 的主析取范式为m0m2m3
5、.B 的主合取范式为M 1B 的成真赋值为00,10,11.B 的成假赋值为01.1.14设 p:A 输入 ;设 q:B 输入 ; 设 r:C 输入 ;由题的条件 , 容易写出 FA , FB , FC 的真值表 , 见表 1.5 所示 . 由真值表分别写出它们的主析范邓范式 , 而后 , 将它们都化成与之等值的 中的公式即可 .表 1.5pqrF AFBFC000000001001010010011010100100101100110100111100FA( pqr )( pqr )( pqr )( pqr )( pq)(rr )( pq)(rr )( pq)( pq)p(qq)pFB(pq
6、r )(pqr )(pq)(rr )(pq)(pq)( pq)pqp(qq) .FC(pqr )( pq)r( pq)r( pq)r )( pq)r )( pq)r( pq)( pq)(rr )1 19 (1)证明qr前提引入r前提引入q析取三段论( pq)前提引入pq置换p析取三段论(2)附加前提证明法：证明r pr p p(qs) qs q s(5) 归缪法：证明 q r s s r ( pq)r附加前提引入前提引入析取三段论前提引入假言推理前提引入假言推理结论的否定引入前提引入前提引入析取三段论前提引入( pq)拒取式pq置换 p qqq前提引入析取三段论合取? 01.20设置换p：他是
7、理科生q：他是文科生r：他学好数学前提pr ,qp,r结论 q通过对前提和结论的观察，知道推理是正确的，下面用构造证明法给以证明。证明p r前提引入r前提引入p拒取式qp前提引入q拒邓式 q置理补充作业：例某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件：(1) 若赵去，钱也去；(2) 李、周两人中至少有一人去；(3) 钱、孙两人中有一人去且仅去一人；(4) 孙、李两人同去或同不去；(5) 若周去，则赵、钱也去 .试用主析取范式法分析该公司如何选派他们出国？解 设 p：派赵去， q：派钱去， r ：派孙去，s ：派李去， u：派周去 .解此类问题的步骤
8、为： 将简单命题符号化 写出各复合命题 写出由中复合命题组成的合取式 求中所得公式的主析取范式解 设 p：派赵去， q：派钱去， r ：派孙去，s ：派李去， u：派周去 . (1) (pq)(2)(su)(3)(qr)(q r)(4)(rs)( rs)(5)(u(pq) (1) (5) 构成的合取式为A=(p(rq)(ss)u)(r(qs)r)(uq r)(pq)A 的演算过程如下 :A=(pq)(su)(qr)(q r)(rs)(rs)(uA(p q)(qr)(q r)(s(rs)(rs)B1= (p q)(qr)(q r)(p qr)(pq r)(qB2= (su)(u (pq)(su)
9、(pq s)(pq u)B1B2(p qrsu)(p(qrsu)(p再令 B3 = (rs)(rs)(pu)(r)q rqq)u (pq)（交换律 )（分配律）（分配律）su)rs)(pqru)得AB1 B2B3(pq rsu)(pqrs u)注意：在以上演算中多次用矛盾律要求：自己演算一遍A(pq rsu)(pqrs u)结论：由可知，A的成真赋值为00110 与 11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.第 2章习题2.1本题没有给出个体域, 因而使用全总个体域.(1) 令 F ( x) : x 是鸟G( x) : x 会飞翔 .命题符号化为x(F ( x
10、)G (x) .(2) 令 F (x) : x 为人 .G (x) : x 爱吃糖命题符号化为x( F (x)G ( x)或者x(F ( x)G (x)(3) 令 F (x) : x 为人 .G (x) : x 爱看小说 .命题符号化为x(F ( x)G ( x) .(4) F ( x) : x 为人 .G (x) : x 爱看电影 .命题符号化为x(F ( x)G ( x) .或者x( F ( x)G( x)2.2 （ 2） 在 (a), (b), (c) 中均符号化为xG( x)其中 G ( x) : x20 ，此命题在（ a）中为假命题，在(b)(c)中均为真命题。23 因题目中未给出个
11、体域，因而应采用全总个体域。（ 1） 令： F ( x) : x 是大学生， G ( x) : x 是文科生，H (x) : x 是理科生，命题符号化为x( F ( x)(G (x)H (x)（ 2）令 F ( x) : x 是人， G ( y) : y 是花， H (x, y) :x 喜欢 y，命题符号化为x(F ( x)y(G ( y)H (x, y)（ 4）令 F ( x) : x 在北京工作，G ( x) : x 是北京人，命题符号化为x( F (x)G( x),或x( F ( x)G (x),（ 5）令 F ( x) : x 是金属， G ( y) : y 是液体， H ( x, y
12、) : x 溶解在 y 中，命题符号化为x( F ( x)y(G ( y)H (x, y).2.5（1）取解释I 1 为：个体域DR （实数集合），F (x) : x 为有理数，G (x) : x能表示成分数，在I 1下，x( F (x)G( x)的含义为“对于任何实数x 而言，若x 为有理数，则x 能表示成分数” ，简言之为“有理数都能表示成分数。 ”在此蕴含式中， 当前件 F ( x)为真时， 后件 G (x) 也为真， 不会出现前件为真，后件为假的情况，所以在I 1 下， x( F ( x)G ( x) 为真命题。在在 I 1 下， x( F (x) G ( x) 的含义为“对于任何实数
13、 x,x 既为有理数，又能表示成分数。”取 x2，则 F(2 ) g( 2) 显然为假，所以，在I 1 下， x(F ( x)G( x) 为假命题.26 在解释 R 和赋值下各式分别化为（ 1） x( x 0);（ 2）x( x1x)y(0y2);2.11 （ 2）令 F ( x) : x 是北京人G (x) : x 去过香山。命题直接符号化为x( F (x)G( x)而x(F ( x)G ( x)x( F (x)G ( x)（双重否定律）x(F ( x)G( x)（量词否定等值式）x(F ( x)G ( x)（德·摩根律）x(F ( x)G( x)（蕴含等值式）最后得到的公式满足要
14、求（只含全称量词），将它翻译成自然语言，即为“并不是北京人都去过香山。”可见，“有的北京人没过过香山。 ”与“并不是北京人都去过香山。 ”是同一命题不同的叙述方法。2.12 （ 2）x(F ( x)yG( y)xF (x)yG( y)（量词辖域收缩扩张等值式）( F (a)F (b) F (c)(G( a) G(b) (c).214 （1）xF ( x)yG (x, y)xF ( x)yG( x, y)zF (z)yG (x, y)z y(F ( z)G( x, y)（量词否定等值式）（换名规则）（量词辖域收缩扩张等值式）zy( F ( z)G( x, y)（ 2）(xF ( x, y)yG
15、(x, y)xF (x, y)yG( x, y)（德·摩根律、量词否定等值式）z1 F (z1 , y)z2G( x, z2 )（换名规则）z1 z2 (F ( z1 , y)G(x, z2 )（量词辖域收缩扩张等值式）2.15 （ 2）x( F (x)yG( x, y, z)zH ( x, y, z)u(F (u)vG(u,v, z)wH ( x, y, w)uv( F (u)G (u,v, z)wH ( x, y, w)u v w( F (u)G (u,v, z)H (x, y, w)在以上演算中分别使用了换名规则和量词辖域收缩扩张等值式。第 3章习题3.1A：； B ：； C
16、：； D ：； E：3.4E： (h) 图3.5A：； B：； C ：； D ：； E ：3.13(1)A B a, b, c, d, A B c.AB a, b,AB a, b, d.3.14(2)P( A), 1, 1, 1, 1.3 16 （ 1），（ 2），（3）为真。分析如果给出的是集合恒等式，可以用两种方法验证。一是分别对等式两边的集合画出文氏图， 然后检查两个图中的阴影区域是否一致。二是利用集合恒等式的代入不断对等式两边的集合公式进行化简或者变形，直到两边相等或者一边是另一边的子集为止。例如， 题（1）中的等式左边经恒等变形后可得到等式右边，即（1）(AB)C(AB)C(AC)(
17、BC)(AC)(BC)证明过程用到了书上P62 页的 3.27 公式（2）A(BC)A(BC)A(BC)(AB)(AC)(AB)(AC)证明过程用到了书上P62 页的3.27 公式及德·摩根律（ 3）A( AA(B(BB)C )CAC )( A B)( B ( A CC )B ) C证明过程用到了书上P62 页的3.27公式及德·摩根律3.17（2）由于CD D C ,又 由AB可 得A DB C,即ADBC成立。（ 3）由于A( BA)AB ，故有BA( BA)BABAB 。这里用到 A（ 4）易见，当B 的充要条件为BA=B成立时，必有AB或AAB或ABA-B=B-A 。反之，由A-B=B-A 得.( AB)B(BA)BBA化简后得BA，即BA ，同理，由(AB)AABA-B=B-A 得(BA)A可证出AB ，由 BA及AB 可知A=B。3 19令 S x | xN1x1000000.A x | xSx 是完全平方数 ，B x | xSx 是完全立方数 ，从而有 | S | 1000000,| A | 1000, | B |100, | AB | 10. 代入包含排斥原理得|AB| |S| (|A|B|) |AB|1000000(1000100)10=998910