离散数学(屈婉玲版)第一章部分习题分解

1、第一章习题1.1&1.2 判断下列语句是否为命题 ,若是命题请指出是简单命题还是复合命题 .并将命题符号化 ,并讨论它们的真值 .(1) 2是无理数 .是命题 ,简单命题 .p:2是无理数 .真值 :1(2) 5能被 2整除 .是命题 ,简单命题 .p:5能被 2整除 .真值 :0(3) 现在在开会吗 ? 不是命题 .(4) x+5>0.不是命题 .(5) 这朵花真好看呀 ! 不是命题 .(6) 2是素数当且仅当三角形有 3条边 .是命题 ,复合命题 .p:2 是素数 .q:三角形有 3条边 .pq真值:1(7) 雪是黑色的当且仅当太阳从东方升起 .是命题 , 复合命题 .p:

2、雪是黑色的 .q: 太阳从东方升起 .p q真值 :0(8) 2008年10月 1日天气晴好 .是命题 , 简单命题 .p:2008 年 10月 1日天气晴好 . 真值唯一 .(9) 太阳系以外的星球上有生物 .是命题 , 简单命题 .p: 太阳系以外的星球上有生物. 真值唯一 .(10) 小李在宿舍里 .是命题 , 简单命题 .P: 小李在宿舍里 . 真值唯一 .(11) 全体起立 ! 不是命题 .(12) 4是2的倍数或是 3的倍数 .是命题 , 复合命题 .p:4 是 2的倍数 .q:4 是3的倍数 .p q真值 :1(13) 4是偶数且是奇数 .是命题 , 复合命题 .P:4 是偶数

3、.q:4 是奇数 .p q真值 :0(14) 李明与王华是同学 .是命题 , 简单命题 .p: 李明与王华是同学 . 真值唯一 .(15) 蓝色和黄色可以调配成绿色 .是命题 , 简单命题 .p: 蓝色和黄色可以调配成绿色 . 真值:11.3判断下列各命题的真值.(1) 若 2+2=4, 则 3+3=6.(2) 若 2+2=4, 则 3+3 6.(3) 若 2+2 4, 则 3+3=6.(4) 若 2+2 4, 则 3+3 6.(5)2+2=4 当且仅当 3+3=6.(6)2+2=4 当且仅当 3+36.(7)2+2 4当且仅当 3+3=6.(8)2+2 4当且仅当 3+36.答案 :设p:2

4、+2=4,q:3+3=6, 则p,q 都是真命题 .(1)p q, 真值为 1.(2)p q, 真值为 0.(3) p q, 真值为 1.(4) p q, 真值为 1.(5)p q, 真值为 1.(6)p q, 真值为 0.(7) p q, 真值为 0.(8) p q, 真值为 1.14将下列命题符号化，并讨论其真值。（ 1）如果今天是 1号，则明天是 2号。p:今天是 1号。q:明天是 2号。符号化为： p q真值为： 1（ 2）如果今天是 1号，则明天是 3号。p:今天是 1号。q:明天是 3号。符号化为： pq真值为： 01.5将下列命题符号化。（ 1）2是偶数又是素数。（ 2）小王不但

5、聪明而且用功。（ 3）虽然天气很冷，老王还是来了。（ 4）他一边吃饭，一边看电视。（ 5）如果天下雨，他就乘公共汽车上班。（ 6）只有天下雨，他才乘公共汽车上班。（ 7）除非天下雨，否则他不乘公共汽车上班。 (意思为：如果他乘公共汽车上班，则天下雨或如果不是天下雨，那么他就不乘公共汽车上班 )（ 8）不经一事，不长一智。答案：（1）设 p：2是偶数， q：2是素数。符号化为：pq（ 2）设 p：小王聪明， q：小王用功。符号化为： p q（ 3）设 p：天气很冷， q：老王来了。符号化为： p q（ 4）设 p：他吃饭 ,q：他看电视。符号化为： pq（ 5）设 p：天下雨， q：他乘公共汽车

6、。符号化为： pq（ 6）设 p：天下雨， q：他乘公共汽上班。符号化为： qp（ 7）设 p：天下雨， q：他乘公共汽车上班。符号化为： qp 或 q p（ 8）设 p：经一事， q：长一智。符号化为： p q1.6设 p,q的真值为 0； r,s的真值为 1，求下列各命题公式的真值。（ 1） p(q r)（ 2） (p? r) (? ps)（ 3） (p(qr) (pq) (rs)（ 4） ?(p(q(r ?p) (r ?s)解：（1） p(qr)pqrqrp(qr)00100(2) (p? r) (?ps)pqrsp?p(p r)(?pr?pss)00110110(3)(p (qr) (

7、p q) (r s)pqrsq rp r)(qp qr s(p q) (r s)(p (q r) (p q) (r s)0011100101(4) ?(p(q (r?p) (r ?s)pq rs?r q (r (p (q (r(r ?(p (q (rp?p?p) ?p)?s) ?p) (r?s)00 111111111 7 判断下列命题公式的类型。（ 1）p (p q r)解：pqrp qp qp (p qrr)000001001011010111011111100111101111110111111111由真值表可知，该命题公式为重言式。（2）（p p） pppp p （p p） p0111

8、1001由真值知命题公式的类型是：重言式（ 3）(q p)ppqqp（ qp）(qp) p00100010101010011100此命题公式是矛盾式。(4)( pq) (q p)解:其真值表为 :p q q p qq(pq)( qp p p)0011111011011110010011100111由真值表观察 ,此命题为重言式 .(5)(pq) (q p)解:其真值表为 :p qpq (p q)( qpqp p)001011011111100111110100由真值表观察 ,此命题为 非重言式的可满足式 .（7）（pp） (q q) r)解：p qr p pq qr(q （ p p）q)(q

9、q) rr)00010100001100000101010001110000100101001011000011010101111000结论： 此命题为矛盾式1.7(8)(pq) (p q).pq (pq)(p q) (p q)(pq) (pq)001011010101100101111100由此可以知道，上式为非重言式的可满足式.(9) ( )( ) ( ) 解:p （） A（）000111110011111101010011011111100010101010110100111111该命题为永真式（10）（ pq） r ）s解：p q rsp （pq）rq00000100010100100

10、1001101010010010110011011011111111111111011110110110010100110101011101111100010结论：此命题为非重言式可满足式1.8用等值演算法证明下列等值式1101110111（ pq） r ）s0101100110010011（1）（p q） (p q)p证明：（p q） (p q)p(q q)p1(（分配律）（排中律）同一律 )p（3）（ pq）( ( pq )( pq ) )证明：（pq）( ( pq )(q( (pq )(pq )(p ) )qp ) )qp )( pq )( q( ( pq )q )( ( pq )(q(

11、 pq )1)(1( pq )(q( pq )( pp )( (pq )q ) )( ( p(qp) )p)q )p )p )(qp) )1.9 用等值演算法判断下列公式的类型。（ 1） （ p q） p） .解：（1） （p q） p）（ p q）p）（ p q）pp qppp q0 q0蕴含等值式德·摩根律双重否定律交换律矛盾律零律即原式为矛盾式.(2) (pq)(qp)解： (pq)(q(pp)q)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(P(pq)q)(p(pq)q)1即(pq)(qp)(pq)是重言式。(3) ( pq) (q p). 解： ( pq) (q

12、 p)(pq) (pq) ( p(pqp)qp)q) (q (qp) )( (pp) (pq) (pq)q) ( (qpq)q)p或( pq) (q p)(pq) (pq) (qp)qp)（(pq) q）p结合律pq 吸收律结论：该公式为可满足式。1.12(1)求下面命题公式的主析取范式、主合取范式、成真赋值、成假赋值。(p (q r)（ pqr）(p (q r) (p qr)(?p(?q?r ) (p qr)(?p?q)(? p?r )(p qr)(?p?q) (r ?r) ) (? p?r )(q?q) (p qr)(?p ?qr) (?p ?q?r) ( ?p ?q?r) (?p q ?

13、r ) (p qr)(?p?q r) (?p ?q?r) (? pq?r ) (p qr) (?p?q?r) (? p?q r) (?p q?r ) (p q r) m0m1m2m7 (0,1,2,7)故 其主析取范式为(p(q r)（ pqr）(0,1,2,7)由最小项定义可知道原命题的成真赋值为(0,0,0) (0,1,0) (0,0,1) (1,1,1)成假赋值为 (0,1,1)(1,0,0)(1,0,1)(1,1,0)由主析取范式和主合取范式的关系即可知道主合取范式为(p(qr) （ pqr） (3,4,5,6)（ 3） （p q） q r解： （p q） q r（ p q） q r

14、p q q r0既（ pq）qr 是矛盾式。（pq） qr 的主合取范式为M0 M1 M2 M3 M4 M5 M6 M7， 成假赋值为： 000，001，010，011，100，101，11113.通过求主析取范式判断下列各组命题公式是否等值。（ 1） p(q r); q (p r).解： p (q r)p(q r) p ( q r) p q r( p (qq)(rr) )p)(qq)r )( (p p)q (r r) )( (p( p q r)(pq r)( p q r)(pq r)( p q r) p qr)(pq r) (0,1,2,3,4,5,7)q (p r)q( p r) p q

15、r (0,1,2,3,4,5,7)所以两式等值。（2）pq(p q)(p (q q) (q (pp)(pq) (pq)(qp)(pq)(pq)(pq) (p q)m1m0m2 (0,1,2)(p q) 处原为(q p) ，不是极小项令 A = pqB=(p q)C=(pq)(pq) (p q)D = pq则B*=(p q)p q=D且ABC所以DA* C*C* = (pq) (pq) (p q)（ 0， 1， 2） (3)所以! 1.15某勘探队有 3名队员，有一天取得一块矿样，3人判断如下：甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，是铁；经实验室鉴定后发现， 其中一人两

16、个判断都正确， 一个人判对一半，另一个人全错了。根据以上情况判断矿样的种类。解： p：是铁q：是铜r：是锡由题意可得共有 6种情况：1)甲全对，乙对一半，丙全错：(p q) r)(r p)(p r)(p2) 甲全对，丙对一半，乙全错： (p q) （ r p）(r p) ） (p r)3) 乙全对，甲对一半，丙全错： （ p r ） ( p q) ( q p) (r p) 4) 乙全对，丙对一半，甲全错： （ p r ） ( r p) (r p) (p q) 5) 丙全对，甲对一半，乙全错： ( r p) ( (pq) (p q)(p r)6) 丙全对，乙对一半，甲全错：( r p)( p r

17、) (p r) (p q)则1 (p q p r r p) (p qp rr p) 00 0 (p q r pp r) (p q r ppr) 00 0 ( pr pq r p) （ pr qpr p）( p qr ) 0pq r（ p r r ppq）（ pr r pp q）0 0 0 ( r p pq p r) ( r pp q pr)0(p q r)p q r( r p p r pq) ( r p pr pq)000所以 （ pqr ）（ p q r ）而这块矿石不可能既是铜又是锡，所以只能是1.16判断下列推理是否正确， 先将命题符号化， 再写出前提和结论，让后进行判断。3 如果今天是

18、 1号，则明天是 5号。今天是 1号，所以明天是 5 号。p：今天是 1号q：明天是 5号解：前提： pq ,p结论： q推理的形式结构为：(pq) p)q证明：p q前提引入p前提引入q假言推理此命题是正确命题1.16（2）判断下列推理是否正确，先将命题符号化再写出前提和结论，然后进行判断如果今天是 1号，则明天是 5号。明天是 5号，所以今天是 1号。解设p: 今天是 1号,q: 明天是 5号,则该推理可以写为( (pq) q) p前提 p q，q结论 p判断证明( (pq)q) p( (pq) q)p( p q) qp(pq)qp(pq) q pqp此式子为非重言式的可满足式，故不可以判

19、断其正确性所以此推理不正确1.16（ 3）如果今天是 1号，则明天是 5号，明天不是 5号，所以今天不是 1号。解： p:今天 1号.q:明天是 5号.(pq) ?q) ?p前提 :pq, ?q.结论 :?p.证明 : p q前提引入?q前提引入?p拒取式推理正确1.17(1)前提：（ p q） , qr, r结论： p.证明： q r前提引入 r前提引入 q析取三段论 (p q)前提引入 pq置换 p析取三段论即推理正确。（ 2）前提： p(q s),q, p r结论： r s.证明：p r前提引入 r附加前提引入 p析取三段论 p (q s)前提引入 q s假言推理 q前提引入 s假言推理

20、由附加前提证明法可知，结论正确。(3): 前提 : p q.结论 : p (pq).证明 : p q.前提引入 p附加前提引入 q假言推理p q合取引入规则（4）前提： qp,qs,st,t r.结论： p q s r.证明： 1)t r；前提引入2)t ；1)的化简3)st；前提引入4)（st）(ts); 3)的置换5) t s 4)的化简6) s； 2),5)的假言推理7) q s；前提引入8) (q s) (s q)；7)置换9) s q 8)的化简10) q；6),9)的假言推理11) q p；前提引入12) p；10),11)的假言推理13） r 1)的化简14) p q s r 6

21、),10),12),13) 的合取所以推理正确。118 如果他是理科学生，他必学好数学。如果他不是文科学生，他必是理科学生。他没学好数学。所以它是文科学生。判断上面推理是否正确，并证明你的结论。解： p: 他是理科学生q:他学好数学r:他是文科学生前提： pq ， r p ， q结论： r p前提引入 p q前提引入 p拒取式 r p前提引入 r拒取式1.19给定命题公式如下：p (qr) 。求命题公式的主析取范式、主合取范式、成真赋值、成假赋值。解：p (qr)( pqq)(rr)(qr)(pp)pqr)pqr)(pqr)(pqr)(pqm7m 7r)( p qr)m6m5vm 4m 6 m

22、2m6m5vm 4m22、4、5、6、7p (q r)0、1、3既010 、100 、101 、 110 、111 是成真赋值， 000 、001 、011 是成假赋值1.20给定命题公式如下：（pq）r 。求命题公式的主析取范式、主合取范式、成真赋值、成假赋值。解：（p q）r(pq)r( (pq)(rr) ) ( (pp)(qq)r )(pqr)(pqr) (pqr)(pq r) ( p q r) ( p qr)m m m m mm767531mmm m m765311、3、5、6、7 （ p q） r0、2、4既001、011、 101、 110、111是成真赋值， 000 、 010、100是成假赋值。例题例1.25给定命题公式如下，用等值演算判断公式类型(1)(p q)(p q)解：(p q) (p q) p q p q( p p)( q q)1 11所以为重言式（ 2）(p? q) ? (pq)(q p) 解： (p? q