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

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条边.p«q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p«q

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

3、15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:11.3 判断下列各命题的真值.(1)若 2+2=4,则 3+3=6.(2)若 2+2=4,则 3+36.(3)若 2+24,则 3+3=6.(4)若 2+24,则 3+36.(5)2+2=4当且仅当3+3=6.(6)2+2=4当且仅当3+36.(7)2+24当且仅当3+3=6.(8)2+24当且仅当3+36.答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题.(1)pq,真值为1.(2)pq,真值为0.(3)pq,真值为1.(4)pq,真值为1.(5)p«q,真值为1.(6)p&#

4、171;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号。 符号化为：p®q 真值为：01.5将下列命题符号化。（1）2是偶数又是素数。（2）小王不但聪明而且用功。（3）虽然天气很冷，老王还是来了。（4）他一边吃饭，一边看电视。（5）如果天下雨，他就乘公共汽车上班。（6）只有天下雨，他才乘公共汽车上班。（7）除非天下雨，否则他不乘公

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

6、1.6设p,q的真值为0；r,s的真值为1，求下列各命题公式的真值。（1）p(qr)（2）(pr)(¬ps)（3）(p(qr)(pq)(rs)（4）¬(p(q(r¬p) (r¬s) 解：（1） p(qr)pqrqrp(qr) 00100(2) (pr)(¬ps) pqrsp«r¬p¬ps(p«r)(¬ps)00110110(3)(p(qr)(pq)(rs)pqrsqrp(qr)pqrs(pq)(rs)(p(qr)(pq)(rs)0011100101 (4) ¬(p(q(r¬p

7、) (r¬s)pqrs¬pr¬pq(r¬p)(p(q(r¬p)(r¬s)¬(p(q(r¬p) (r¬s)001111111117 判断下列命题公式的类型。（1）p®(pÚqÚr) 解：pqrpÚqpÚqÚrp®(pÚqÚr)000001001011010111011111100111101111110111111111由真值表可知，该命题公式为重言式。（2）（p p） p ppp p（p p） p01111001由真

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

9、000100101001011000011010101111000结论：此命题为矛盾式1.7(8) (p «q)(pq).p q(p«q)(pq)(pq)(p «q)(pq)0 010110 101011 001011 11100由此可以知道，上式为非重言式的可满足式.(9) ()()() 解:p（）（）A0001111100111111010100110111111110001001101010111101000111111111该命题为永真式（10）（pq）r）s解：pqrspq（pq）r（pq）r）s00000100001011001001000110110

10、10010101011000110110011111111111111110110110110011001011001100101011010111111000101 结论：此命题为非重言式可满足式1.8 用等值演算法证明下列等值式（1）（pq）(pq) p证明：（pq）(pq) （分配律）p(qq) （排中律）p1 (同一律)p （3）Ø（p « q）Û ( ( p Ú q ) Ù Ø ( p Ù q ) ) 证明：Ø（p « q） Û Ø ( ( p ® q ) 

11、7; (q ® p ) ) Û Ø ( (Ø p Ú q ) Ù (Ø q Ú p ) ) Û Ø (Ø p Ú q ) Ú Ø ( Øq Ú p ) Û ( p Ù Ø q ) Ú ( q Ù Ø p ) Û ( ( p Ù Ø q ) Ú q ) Ù ( (p Ù Ø q ) Ú Ø

12、p ) Û ( ( p Ú q ) Ù ( Ø q Ú q ) ) Ù ( ( p Ú Ø p ) Ù ( Ø q Ú Ø p) )Û ( p Ú q ) Ù1) Ù (1 Ù ( Ø q Ú Ø p) )Û ( p Ú q ) Ù ( Ø q Ú Ø p) Û ( p Ú q ) Ù Ø ( p

13、Ù q ) 1.9 用等值演算法判断下列公式的类型。 （1）Ø（pÙq）®p）.解：（1）Ø（pÙq）®p）ÛØ（Ø（pÙq）Úp） 蕴含等值式ÛØ（Ø（pÙq）ÙØp 德·摩根律ÛpÙqÙØp 双重否定律Û pÙØpÙq 交换律Û0Ùq 矛盾律Û0 零律即原式为矛盾式.(2) (p®q)

14、Ù (q®p)«(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) Û1即(p®q)Ù (q®p)«(p

15、71;q)是重言式。 (3) (Øpq)(qØp). 解：(Øpq)(qØp) Û Ø (pq) (ØqØp)Û (ØpØq) (ØqØp)Û (Øp(ØpØq) (Øq(ØqØp)Û ( (ØpØp)Øq) (ØqØq)ØpÛ (ØpØq) (ØpØq)Û (

16、6;pØq)或 (Øpq)(qØp) Û Ø (pq) (ØqØp)Û (ØpØq) (ØqØp)Û（ (ØpØq) Øq）Øp结合律Û ØpØq 吸收律结论：该公式为可满足式。1.12(1)求下面命题公式的主析取范式、主合取范式、成真赋值、成假赋值。 (p(qr)（pqr）Û¬(p(qr)(pqr) Û (¬p(¬q¬r) (pqr)&

17、#219; (¬p¬q) (¬p¬r)(pqr)Û (¬p¬q)(r¬r) (¬p¬r)(q¬q) (pqr)Û (¬p¬qr)(¬p¬q¬r)(¬p¬q¬r) (¬pq¬r) (pqr)Û (¬p¬qr)(¬p¬q¬r) (¬pq¬r) (pqr)Û (¬p¬q

18、72;r) (¬p¬qr)(¬pq¬r) (pqr)Ûm0m1m2m7Û(0,1,2,7)故 其主析取范式为 (p(qr)（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）&#

19、217;qÙ rÛØ（ØpÚq）ÙqÙrÛpÙØqÙqÙrÛ0既Ø（p®q）ÙqÙ r是矛盾式。Ø（p®q）ÙqÙ r的主合取范式为M0 Ù M1 Ù M2Ù M3 Ù M4 Ù M5 Ù M6 Ù M7， 成假赋值为：000，001，010，011，100，101，11113.通过求主析取范式判断下列各组命题公式是否

20、等值。 Ú Ú Ù （1）p(qr); q(pr). 解：p(qr) ÛpÚ (qr)Û pÚ (qÚr)Û pÚqÚrÛ (pÙ(qÚq)Ù(rÚr)Ú(pÚp)ÙqÙ(rÚr)Ú(pÚp)Ù(qÚq) Ùr)Û (pÙqÙr)Ú (pÙqÙr)Ú (pÙq

21、Ùr)Ú (pÙqÙr)Ú (pÙqÙr)Ú (pÙqÙr)Ú (pÙq Ùr) Û(0,1,2,3,4,5,7)q(pr) ÛqÚ (pÚr) Û pÚqÚr Û(0,1,2,3,4,5,7) 所以两式等值。（2） p­qÛ¬(pq) Û(p(q¬q)(q(p¬p)Û (pq)(¬p¬q) (&#

22、172;qp) (¬p¬q)Û (¬pq) (¬p¬q) (p¬q)Ûm1m0m2Û(0,1,2)(p¬q)处原为(¬qp)，不是极小项 令A = p­qB= ¬(pq)C=(¬pq) (¬p¬q) (p¬q)D = pq则B*=¬(pq) ? pq=D且A?B?C所以D?A*?C*C* = (¬pq)(¬p¬q)(p¬q)?（0，1，2）?(3)所以!?1.15某勘探队有3名

23、队员，有一天取得一块矿样，3人判断如下：甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，是铁；经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一半，另一个人全错了。根据以上情况判断矿样的种类。解：p：是铁 q：是铜 r：是锡 由题意可得共有6种情况：1)甲全对，乙对一半，丙全错：(pq) (pr)(pr) (rp) 2)甲全对，丙对一半，乙全错：(pq) （rp）(rp)）(pr) 3)乙全对，甲对一半，丙全错：（pr）(pq) (qp) (rp) 4)乙全对，丙对一半，甲全错：（pr）(rp) (rp) (pq) 5)丙全对，甲对一半，乙全错：(rp) ( (pq) (

24、pq) (pr) 6)丙全对，乙对一半，甲全错：(rp) (pr)(pr) (pq) 则Û1Û(pqprrp) (pqprrp) Û00Û0Û(pqrppr)(pqrppr) Û00Û0Û(prpqrp) （prqprp）Û (pqr) 0ÛpqrÛ（prrppq）（prrppq） Û00Û0Û(rppqpr) (rppqpr)Û0(pqr)Û pqrÛ(rpprpq) (rp prpq)Û00Û0所以&#

25、219;（pqr）（pqr）而这块矿石不可能既是铜又是锡，所以只能是1.16判断下列推理是否正确，先将命题符号化，再写出前提和结论，让后进行判断。3 如果今天是1号，则明天是5号。今天是1号，所以明天是5号。 p：今天是1号 q：明天是5号 解：前提：pq ,p 结论：q 推理的形式结构为：(pq)p)q 证明：pq 前提引入 p 前提引入 q 假言推理此命题是正确命题1.16（2）判断下列推理是否正确，先将命题符号化再写出前提和结论，然后进行判断 如果今天是1号，则明天是5号。明天是5号，所以今天是1号。 解 设p: 今天是1号,q: 明天是5号,则该推理可以写为( (pq)q)p 前提 p

26、q，q结论 p判断 证明 ( (pq)q)p Û¬ ( (pq)q)p Û¬( pq)¬qp Û ¬( ¬pq) ¬qpÛ (p¬q) ¬qp Û¬qp此式子为非重言式的可满足式，故不可以判断其正确性所以此推理不正确1.16（3）如果今天是1号，则明天是5号，明天不是5号，所以今天不是1号。解：p:今天1号.q:明天是5号.(pq)¬q)¬p前提:pq,¬q.结论: ¬p.证明:pq 前提引入¬q 前提引入

27、¬p 拒取式推理正确1.17(1)前提：（pq）,qr,r结论：p.证明：qr 前提引入 r 前提引入 q 析取三段论 (pq) 前提引入 pq 置换 p 析取三段论即推理正确。（2）前提：p(qs),q, pr 结论：r s. 证明： pr 前提引入 r 附加前提引入 p 析取三段论 p(qs) 前提引入 qs 假言推理 q 前提引入 s 假言推理 由附加前提证明法可知，结论正确。 (3): 前提: pq. 结论: p(pq). 证明: pq. 前提引入 p 附加前提引入 q 假言推理pq 合取引入规则 （4）前提：q®p,q«s,s«t,tÙ

28、;r. 结论：pÙqÙsÙr.证明：1) tÙr；前提引入2) t ；1)的化简3) s«t；前提引入4)（s®t）Ù(t®s); 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

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

30、Ù(rÚØr)Ú(qÙØr)Ù(pÚØp) Û(pÙqÙr)Ú(pÙqÙØr)Ú(pÙØqÙr)Ú(pÙØqÙØr)Ú(pÙqÙØr)Ú(ØpÙqÙØr) Ûm7Úm6Úm5vm4Úm6Úm2 Ûm7

31、Úm6Úm5vm4Úm2 Ûå(2、4、5、6、7) pÚ(qÙØr) ÛÕ(0、1、3) 既010、100、101、110、111是成真赋值， 000、001、011是成假赋值1.20 给定命题公式如下：Ø（pÙq）®r。 求命题公式的主析取范式、主合取范式、成真赋值、成假赋值。解： Ø（pÙq）®r Û(pÙq)ÚrÛ(pÙq)Ù(rÚØr)Ú

32、(pÚØp)Ù(qÚØq)Ùr)Û(pÙqÙr)Ú(pÙqÙØr)Ú(pÙqÙr)Ú(pÙØqÙr)Ú(ØpÙqÙr)Ú(ØpÙØqÙr)Ûm7Úm6Úm7Úm5Úm3Úm1Û m7Úm6 Úm5Úm3

33、8;m1Ûå(1、3、5、6、7)Ø（pÙq）®r Û Õ(0、2、4)既001、011、101、110、111是成真赋值， 000、010、100是成假赋值。例题例1.25 给定命题公式如下，用等值演算判断公式类型(1)(pq) (pq) 解： Û (pq) (pq) Û pq pq Û (pp) (qq) Û 11 Û1 所以为重言式（2）(pq) (pq)(qp) 解：(pq) (pq)(qp) Û (pq) (q) Û (pq)(pq)(pq)(pq) Û (pq)(pq) Û¬(pq) (pq) Û¬(pq) (qp) (pq) (qp) Û (¬(pq) ¬ (qp) (pq) (¬(pq) ¬ (qp) (qp) Û (1¬ (qp)(1(qp) Û1 1 Û1 所以此式是重言式(红色字体部分可删去)（3）Ø (pq)q解： Ø (pq)qÛØ(&#