离散数学第2版,刘爱民习题解答.doc

附录2 习题答案习题一答案1.1下列各语句中哪些是命题?1) 不是； 2) 是； 3) 不是； 4) 不是；5) 不是； 6) 是；7) 是； 8) 不是 9) 不是；10)是； 11)不是；12)是。1.2 将下列命题符号化。 1) p q, p:太阳明亮,q:湿度高； 2) q p, p:明天你看到我，q:我要去深圳。 3) pq, p:我出校，q:我去图书城； 4) qp , p:你去,q:我去； 5) 5.1) pq；5.2) pq; 5.3) pq；5.4) pq；6) 6.1) pq 6.2) (p q) 6.3) pq 6.4) (pr)6.5) (pq) r6.6) (r (pq) 7) p:蓝色和黄色可以调配成绿色； 8) (pq), p:李兰现在在宿舍, q:李兰在图书馆里； 9) p q, p:一个人经一事，q:一个人长一智；10) (pq) (r s), p:晚上小王做完了做业, q: 晚上小王没有其他事情，r: 晚上小王看电视, s: 晚上小王看电影。11) (r s), r:小飞在睡觉, s:小飞在游泳；12) pqr, p:这个星期天我看电视，q: 这个星期天我外出，r:这个星期天我在睡觉。13) pq , p:卫星上天了，q:国家强大了；14) pq, p:今天没有课，q:我呆在图书馆里；15) pq,p:我去图书城，q:我有时间；16) pq , p:人们辛劳，p: 人们收获1.3 1) 小李家住北大西门外, 他现在坐在公共汽车里看书，没有考虑问题； 2) 小李在思考问题, 他没有乘坐公共汽车，也没有看书； 3) 小李只要乘坐公共汽车，他就看书或考虑问题； 4) 小李乘坐公共汽车，要么看书不考虑问题，要么考虑问题不看书， 5) 同4); 6) 如果小李家住北大西门外,则他现在没有乘坐公共汽车，没有看书，也没有考虑问题。1.4 1) 是2) 不是，因为联结词后没有字母3) 是4) 是5) 不是，因为pq之间缺联结词6) 不是，因为 不能构成公式7) 是*1.5 1) q是0层公式，q是1层公式，(p q)是2层公式，原公式是3层公式; 2) p是0层公式，p是1层公式，(pq) 是2层公式，(qr) 是1层公式，(pq) (qr)是3层公式，(pr)是1层公式，原公式是4层公式；3) r，s是0层公式，r s是1层公式，(q r s)是2层公式， (p (q r s)是3层公式，(p (q r s)是4层公式，(pq) s是2层公式，原公式是5层公式。4) p，q是0层公式，(p q)是1层公式，(p q)r是2层公式，(rs) 是1层公式，原公式是3层公式.1.6 p q r s，q p q1) (q r s) ( pq)r ;2) (q r s)( pq) (pq)r)( (q r s)r)；3) (q r s) ( pq) r s) (q r s) ( pq) s； 4) (q r s) ( pq)r (rs).1.7 AB, A的成真赋值或B的成真赋值，故为000,011,100,110,111, 101; AB, AB: A的成真赋值或B的成真赋值，001,010,101, 000,110; AB: 同时是A和B的成真赋值，000,110；AB: 同时是A和B的成真赋值，001, 010；AB: 同时是A和B的成真赋值或成假赋值，000,110, 001, 010；1.8 1) ( p q ) q 2) (p q) ppqp q( p q ) qpqp q(p q) p00010010010101101001100011111111这是重言式。这是可满足式。 3) (pp) p 4) p (p q)pqppp(pp) ppqp qp (p q)001110001011110111100011011110011111这是重言式。这是重言式。 5) (pq) q 6) (qp) (p q)pq(pq) qpq(qp)(p q)000100011111010100101111101001010010110101101011这是矛盾式这是重言式。 7) (pr) (pr) (pq)r) 8) (pq) p rpqr(pr)(pr)(pq)r)pqr(pq)pr00011110100001000011111010010100010101010010010001111111101101001000101101001010101111111101101111001011011001001111111111110100 这是可满足式 这是可满足式1.9 这里仅仅是无数个命题形式中的两个，读者可以另外给出F：矛盾式，用一个矛盾式与任何一个公式合取即可，即(pp) AF1=(pp) (qr), F2=p qr (qr)G：重言式，简单的可以是一个重言式与任何一个公式析取，(pp) A如：G1=(pp) (qr), G2= p (pq) p r，重言式拆分在不同的位置H：前四行可看成蕴涵式的否定，后四行与p相同，两种情况相或。所以H1= p (q r) ; p (r q)还是分成前后四行分析，如果以p作为蕴涵式的后件：Ap，后四行总成立，想法构成前件，使得前四行的第三行为0，其它行为1，正是蕴涵式q r。所以可写成H2=q r pR：只有全0的才为0，所以最简单的是用析取式，R1=pqr这个公式再与其它的确保p,q,r三个为0时一定为0的公式相析取即可；R2= pqr (p q)， pqr (pr)S：类似H的分析，前四行和后四行情况相或，S1=p (qr)如果以p作为蕴涵式的后件：Ap，后四行总成立，想法构成前件，使得前四行的第三行为0，其它行为1，正是蕴涵式q r。所以可写成S2=q r p习题二答案2.1 1) 不能。C1时，两边总是等值； 2) 不能。C0时，两边总是等值； 3) 能。由否定之否定可得。2.2 1) 证明下列等值式：(1) p(qr) p(qr) (2) (p q) (pq)(qp) pqr (pq)(qp) qpr (pq) (qp) q(pr) (pq)(pq) q (p r) (pq)(pq)(3) p(qp) p (q p)(4) (pr) (q r) (pr) (q r) p (p q) (重言式) (p q) r p (p q) (p q) r p (p q) (p q) r(5) (pq) (p r) (p q) (p r) p (qr) p q r 2) 判定命题形式类型：(1) (pq)(pp)(pq) (2) (q(p q) p) (pq) (pq) q (p q) p) (pq) (qp) q (q p) (pq) (qp) 0 (pq)这是矛盾式 (pq) (qp) (pq) (pq) 1 1这是重言式(3) (pq)(qp) p (4) (qp)(pq) (pq)(qp) p (qp)(pq)(p p) q) p (q q) p q p p 这是可满足式这是可满足式(5) (p q) p) (6) (p q r) (r(p q) ( (p q) p)(p q r) (r (p q) ( (pp) q)p (q r) r p q 1p r q 0这是可满足式 这是矛盾式2.3 提示：对偶式是将与互换、0与1互换。但要注意括号省略问题。1) (pq) (pq) (p q)(pq) p( q q) p对偶式是： (pq) (pq) p2) q (pq) p) q (q p) q q p 1对偶式是：q (pq) p) 03) (pq) (pq) (pq) (pq) (p p)q) (pq) q (pq) q p q (pq)对偶式是：(pq) (pq) (pq) (pq)2.4 香农定理：A(p1, p2, , pn, 0, 1, , , ) A(p1, p2, , pn, 1, 0, , , )对偶式的定义为：A*(p1, p2, , pn, 0, 1, , , ) A(p1, p2, , pn, 1, 0, , , )对偶式定义是重言式，其任何的替换实例仍然是重言式，以pi替换pi，所以A*(p1, p2, , pn, 0, 1, , , ) A(p1, p2, , pn, 0, 1, , , )从而A(p1, p2, , pn, 0, 1, , , ) A*(p1, p2, , pn, 0, 1, , , )这就是香农定理的对偶式表示式，简写成 A(p1, p2, , pn) A*(p1, p2, , pn)。 显然1) 若A是重言式，则A*是矛盾式； 2)若A是矛盾式，则A*是重言式； 都成立。*2.5 已知 , , 是全功能集。p p；p q (p q) ( p q)p q p q) p q即, , 可有, 表示，所以, 是全功能集。实际上p p0，可用表示，是冗余联结词，所以, 不是极小全功能集。*2.6 找出下式的等值的尽可能简单的由,和, 生成的公式:1) p(q (rp) p (q r) , (p(q r) ,2) p (q p) p p , (重言式) (p p) , 3) (p q) r (p r) p p ,(重言式) (p p) , 4) p(q rp) pq r , ( pq r) , 5) (p q q) p q (pq) , p q ,*2.7 1) ,: (p q)r 2) ,: ( (p q) r) 3) ,: (p q) r 4) ；(pp) (qq) (rr) 5) : (pq) r) (pq) r)2.8 1) (pq) (pq) r) 2) (pqr) (q(pr) *3) (pq) (pqr) *4) (p q) (pq)2.9 1) p r q 2) rp (pq) (p r) q (rp ) (pq) (pq) p r q (p r) (pq) (pq) M5 (pqr) (pqr) (pq r)主合取范式，仅含有一个极大项， (pq r) (pqr)所以是可满足式 m6m4m5m3m2 含有5个极小项，是可满足式 3) (p q r) (p q r) 4) p q (pq) (p q r) (p q r) (p q p) (p q q) (p q r) (p q r) 0 m7m0 主析取范式，含有两个极小项主析取范式不含有任何极大项， 所以是可满足式是矛盾式。2.10 1) (a) (pq)(pqr) (b) (p(qr)(q(pr) (pqr)(pqr)(pqr) (p q)(qr)(pqr) m7m6m3(p q r)(p qr)(pqr) M5M4M2M1M0 (pqr)(pqr) m7m6m3 M5M4M2M1M0主范式都相同，两者等值。 2) (a) p(qr) (b) q(pr) p (qr) p (qr) M6 M6 m0m1m2m3m4m5m7 m0m1m2m3m4m5m7主范式都相同，两者等值。 3) (a) p (pq) (b) (pq) p q p q m2 m2 M0M1M3 M0M1M3主范式都相同，两者等值。 4) (a) (pq) p q (b) (pp) (rp) (pq) p q (p p) (rp) (pq) p q p (pq r) (pqr) (pq r) (pqr) (p q r) (p qr)(p q r) (p qr) m5m4m7m6 m5m4m7m6 M0M1M2M3 M0M1M2M3 主范式都相同，两者等值。2.11 指派需要同时满足1), 2), 3)条件，以及只派两个人的条件。条件1)： A(CD) A (CD) (CD) A (CD) (CD) (A CD) (ACD) (ABCD) (ABCD) (ABCD) (ABCD) M11M15M8M12条件2)： (BC) BC (ABCD) (ABCD) (ABCD) (ABCD) M6M7M14M15条件3)： CD CD (ABCD) (ABCD) (ABCD) (ABCD) M3M7M11M15这三个条件同时满足，是合取关系。即为M11M15M8M12M6M7M14M3而指派的情况是各种可能的情况，是析取关系，为此得到析取范式，为m0m1m2m4m5m9m10m13这就是可能的情况，其中下标的二进制数对应位置为1的就是要指派的人。如1：0001，只指派D条件只指派两人，就是5：0101，9：1001，10：1010；即可以指派的情况有三种：B和D，A和D，或A和C2.12 解：按照题意，三个推测只有一个是对的。推测1：(b c)；推测2：ab；推测3：(b d)推测正确为肯定，推测错误为否定。推测1正确：(b c) (ab) (b d)abcd 推测2正确：(b c) (ab) (b d) abcd推测3正确：(b c) (ab) (b d) (abc) (abc)( acd)可以看到，只有推测3正确时(abc)中含有一个肯定的b。所以该生没有说谎，他是从b地直接返校的。*111110BC001110AACAC2.14 提示：设开关向上为肯定，向下为否定，四种情况分别是：1) 搬键C向上, A、B同向下时： pq r 2) 搬键A向上, B、C同向下时：pq r3) 搬键B、C向上, A同向下时：pq r4) 搬键A、B向上, C同向下时：pq r各种情况都可以成立，所以是析取关系，可采用卡诺图化简，得到 pq r pq r pq r pq r p r pr即只要A或C中的一个但又不同时控制电灯即可。*2.15 按照题意：只要A有信号，FA就有信号，此时不管B，C是否有信号设A，B，C有信号分别表示为p，q，r。 只要A有信号的情况就是：100，101，110，111 即：FAm4m5m6m7 p (pp) (pp)类似A无信号，但是B有信号，C不管有无信号，FB输出信号。此时情况是：010，011FBm2m3pq p qp (qq)FC输出信号必须是只有C有信号，只有001一种情况，所以FCm1 pq r (pq) r ( (pq) r) (pq) r (pq) r (pq) (pq) (rr)习题三答案3.1判断前提是否一致，即判断他们的的合取是否不为矛盾式：下面用主范式判断： 1) (p q) (s r) (s r) (p q s) (p qr) (s r) (p q r s) (p qrs)这是可满足式，所以前提一致。2) p1 (p1 p2) (p1 p2 p3) (p1 p2 pn-1 pn) p1 p2 (p2 p3) (p2 pn-1 pn) p1 p2 p3 (p3 pn-1 pn) p1 p2 p3 pnn个命题变项的合取，这是可满足式，前提一致。3) (p q) (p q) (p q) (p q) (p q) (p q) (p q) p 0 诸前提矛盾，不一致；3.2构造下列推理的证明：1) 前提q p, q s, s t, t r; 结论p q s r。证明 s t 前提引入P (ts) (st)置换TE ts 化简TI t r 前提引入P t 化简TI s 假言推理TI q s 前提引入P (qs) (sq)置换TE sq 化简TI q 假言推理TI q p 前提引入P p 假言推理TI p q s r 合取TI2)前提p(qs),rp,q;结论rs。证明 p (q s) 前提引入P q (p s) 置换TE q 前提引入P p s 假言推理TI r p 前提引入P r p 置换TE r s 假言三段论TI3)前提( pq),qr, r; 结论p。证明 q r 前提引入P r 前提引入P q 析取三段论TI ( p q) 前提引入P p q 置换TE p 析取三段论TI3.3 用相应证明方法证明：1) 归谬法： 前提p q, q r, r s； 结论p。证明 p 否定结论作为前提P p q 前提引入P q 假言推理TI q r 前提引入P r 析取三段论TI r s 前提引入P r r s 合取TI 0 置换TI推出矛盾，所以原结论正确。2) 附加前提法：前提(p q) (r s), (s t) u; 结论p u。证明 p 附加前提引入P p q 附加TI (p q) (r s)前提引入P r s 假言推理TI s 化简TI s t 附加TI (s t) u 前提引入P u 假言推理TI p uCP规则CP3) 反证法： 前提p q, 结论 (p q)证明 p q 否定结论作为前提引入P p 化简TI p q 附加TI (p q) 置换TE得到否定的前提，原推理正确。3.4 反证法。否定结论推出否定的前提。否定结论，即如果2不能整除a，即a=2m+1；则a2=(2m+1)2=4m2+2m+1所以2不能整除a2。这正是否定的前提。原推理正确。*3.5 甲在最后，丙在最前，甲先推测自己戴的帽子。设甲乙丙戴红帽子分别为p，q，r甲看到乙和丙戴的帽子推测自己带的，乙根据看到丙所戴及甲所判断的来确定自己所戴帽子，根据可能的情况是：(1) 乙和丙戴黑帽子，甲确定自己戴红帽子，即pqr。三个前提成立，丙能确定自己为r，即戴黑帽子；(2) 乙和丙中并非都戴黑帽子，甲不能确定自己戴什么帽子，可能的情况是(2.1) 乙和丙都戴红帽子：qr，(2.2) 乙和丙一个戴红帽子：(qr) (qr)综合即为(qr)(qr) (qr) r (qr) 一种情况就是：r，则q，q可能都成立，乙无法判断自己所戴帽子，而丙一旦听到乙无法判断自己所戴帽子，即可确定自己带红帽子； 另一种情况是：(qr)，乙看到丙带黑帽子，确定自己带红帽子；丙一旦听到乙说自己带红帽子，可确定自己带黑帽子；总结就是：甲确定自己戴红帽子，丙可确定自己戴黑帽子； 甲不能确定所戴帽子：乙可确定自己戴红帽子，丙能确定自己戴黑帽子； 乙不能确定自己所带帽子，丙能确定自己戴红帽子；所以丙总能判断出自己所戴帽子。*3.6 针对其中一个人，是哥哥(p)是弟弟(p)，是说真话 (q)还是说谎(q)，都必居其一。 可能的情况是：pq，pq，pq，pq， 询问只能就这几种情况询问，并根据答复情况确定结果。而答复可能是说真话的答复，或者说假话的答复。两种答复都要能判断。 如果只询问一种情况，如pq，则肯定答复结果是(pq) q) (pq) q)pqq pq，无法得到确定的结果；不必再讨论否定答复结果。 如果只询问两种的情况，有共同点时，如pq，pq，则肯定答复结果是(pq pq) q (pq pq) q pq pq，无法确定结果，不必再讨论否定答复结果。 无共同点时，如pq，pq，则肯定答复结果是(pq pq) q (pq pq) q p，能确定被询问的人是哥哥；否定答复结果是(pq pq) q (pq pq) q p；能确定被询问的人是弟弟。问话为： “你是哥哥且你说了真话，或你是弟弟且你说了假话”对吗？。肯定者是哥哥，否定者是弟弟。如果另外一对无共同点的情况，如pq，pq，则肯定答复结果是(pqpq) q (pqpq) q p，能确定被询问的人是弟弟；否定答复结果是(pqpq) q (pqpq) q p；能确定被询问的人是哥哥。问话也可为： “你是哥哥且你说了假话，或你是弟弟且你说了真话”对吗？。肯定者为弟弟，否定者是哥哥。3.7证明下列各推理是否正确.提示：也可以直接利用等值演算方法，获得原蕴涵式是可满足式，则推理不正确。1) p：我是一年级学生；q：我要学习高等数学，r：我要学习集合论；s：我是二年级学生；t：我要学习数学逻辑，u：我要学习图论；前提：p ( qr)，s(tu)，qs结论：qrtu证明 qs 前提引入P q 化简TI s化简TI p ( qr) 前提引入P到此无法继续往下推理，所以无法证明，即原推理是错误的。2) p：我复习完功课；q：我打篮球，r：我打乒乓球；前提：q p，qr，p结论：qr证明 q p 前提引入P p 前提引入P q 拒取式TI qr 前提引入P到此无法继续往下推理，所以无法证明，即原推理是错误的。3) p：我的程序通过了；q：我高兴，r：我生活愉快；前提：p q，rq，p结论：r证明 p q 前提引入P p 前提引入P q 假言推理TI rq 前提引入P到此无法继续往下推理，所以无法证明得到r，即原推理是错误的。3.8 解：符号化：p：甲获胜；q：乙获胜；r：丙获胜；s：丁获胜；前提：pq，rq，ps，结论：rs rq 前提引入P pq 前提引入P qp 置换TE rp假言三段论TI ps前提引入P rs 假言推理TI3.9 解：符号化：p：今天天晴；q：今天下雨；r：我去看电影；s：我看书；前提：p q，pr， rs，结论：sq pr 前提引入P rs 前提引入P ps假言三段论TI p qs q前后件附加TI p q 前提引入P s q假言推理TI sq 置换TIE提示：3.8、3.9可用CP规则。*3.10 机器证明是：归谬法，并利用转换成合取范式，以便得到各简单析取式，各简单析取式之间消解。1) 前提q p, q s, s t, t r; 结论p q s r。证明 (p q s r) 否定结论引入得合取范式p q s r，也是简单析取式 q p前提引入得合取范式q p，也是简单析取式 q s 前提引入得合取范式(q s) (q s)，再得q s q s 得到的第二个简单析取式 s t 前提引入得合取范式(t s) (t s)，再得t s t s得到的第二个简单析取式 t r 前提引入为合取范式，得到t r得到的第二个简单析取式 q s r 消解TI p q r消解TI p s r 消解TI p q t r消解TI p q s 消解TI p s 消解TI q t 消解TI q t消解TI s消解TI q消解TI p q消解TI q消解TI(21) 空消解TI得空，所以原推理正确。注：机器证明中有许多过程是机器的，得到的结果在后续可能并没用，如上面得到，。2)前提p(qs),rp,q; 结论rs。证明 (rs) 否定结论得合取范式rs，得简单析取式r和 s 得到第二个简单析取式 p(qs)前提引入得合取范式p q s r p 前提引入P q 前提引入P p 消解TI p q 消解TI p消解TI 空消解TI得空，所以原推理正确。3)前提( pq),qr, r; 结论p。证明 p 否定结论引入P ( p q) 前提引入得p qP，E qr 前提引入P r 前提引入P q 消解TI pr 消解TI q 消解TI 空消解TI得空，所以原推理正确。习题四答案4.1 将下列命题用0元谓词符号化： 1) P(x): x是素数, Q(x): x是偶数；a:2; P(a) Q(a) 2) P(x,y): x大于y, a:2, b:3, c:4；P(a,b) P(a,c); 3) P(x,y): x比y高, a:张明, b: 李民, c: 赵亮; P(a,b) P(b,c) P(a,c)； 4) P(x): x是素数, a:3; P(a)； 5) P(x): x是素数, a:2,b:3; P(a) P(b)； 6) P(x,y): x能被y整除,a:16,b:4,c:8；P(a,b) P(a,c) 7) P(x,y): x能整除y, a:7,b:100,c:3, P(a,b) P(c,b); 8) P(x,y): x能整除y , Q(x): x是偶数,b:2; P(2,a) Q(a)。4.2 解：个体域全部为全总个体域： 1) P(x): x是火车，Q(x):x是轮船，R(x,y):x比y快； x(P(x) y(Q(y) R(x,y