離散數(shù)學(xué)屈婉玲部分習(xí)題

1、第一章習(xí)題1.1&1.2 判斷下列語句是否為命題,若是命題請(qǐng)指出是簡單命題還是復(fù)合命題.并將命題符號(hào)化,并討論它們的真值.(1) 2是無理數(shù).是命題,簡單命題.p:2是無理數(shù).真值:1(2) 5能被2整除. 是命題,簡單命題.p:5能被2整除.真值:0(3) 現(xiàn)在在開會(huì)嗎?不是命題.(4) x+5>0.不是命題.(5) 這朵花真好看呀!不是命題. (6) 2是素?cái)?shù)當(dāng)且僅當(dāng)三角形有3條邊. 是命題,復(fù)合命題.p:2是素?cái)?shù).q:三角形有3條邊.p«q真值:1 (7) 雪是黑色的當(dāng)且僅當(dāng)太陽從東方升起. 是命題,復(fù)合命題.p:雪是黑色的.q:太陽從東方升起. p«q

2、真值:0 (8) 2008年10月1日天氣晴好. 是命題,簡單命題.p:2008年10月1日天氣晴好.真值唯一. (9) 太陽系以外的星球上有生物. 是命題,簡單命題.p:太陽系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命題,簡單命題.P:小李在宿舍里.真值唯一. (11) 全體起立! 不是命題. (12) 4是2的倍數(shù)或是3的倍數(shù). 是命題,復(fù)合命題.p:4是2的倍數(shù).q:4是3的倍數(shù).pq真值:1 (13) 4是偶數(shù)且是奇數(shù). 是命題,復(fù)合命題.P:4是偶數(shù).q:4是奇數(shù).pq真值:0 (14) 李明與王華是同學(xué). 是命題,簡單命題.p: 李明與王華是同學(xué).真值唯一. (

3、15) 藍(lán)色和黃色可以調(diào)配成綠色. 是命題,簡單命題.p: 藍(lán)色和黃色可以調(diào)配成綠色.真值: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當(dāng)且僅當(dāng)3+3=6.(6)2+2=4當(dāng)且僅當(dāng)3+36.(7)2+24當(dāng)且僅當(dāng)3+3=6.(8)2+24當(dāng)且僅當(dāng)3+36.答案: 設(shè)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將下列命題符號(hào)化，并討論其真值。 （1）如果今天是1號(hào)，則明天是2號(hào)。 p:今天是1號(hào)。 q:明天是2號(hào)。 符號(hào)化為：p®q 真值為：1 （2）如果今天是1號(hào)，則明天是3號(hào)。 p:今天是1號(hào)。 q:明天是3號(hào)。 符號(hào)化為：p®q 真值為：01.5將下列命題符號(hào)化。（1）2是偶數(shù)又是素?cái)?shù)。（2）小王不但聰明而且用功。（3）雖然天氣很冷，老王還是來了。（4）他一邊吃飯，一邊看電視。（5）如果天下雨，他就乘公共汽車上班。（6）只有天下雨，他才乘公共汽車上班。（7）除非天下雨，否則他不乘公

5、共汽車上班。(意思為：如果他乘公共汽車上班，則天下雨或如果不是天下雨，那么他就不乘公共汽車上班)（8）不經(jīng)一事，不長一智。答案：（1）設(shè)p：2是偶數(shù)，q：2是素?cái)?shù)。符號(hào)化為：pq （2）設(shè)p：小王聰明，q：小王用功。符號(hào)化為：pq （3）設(shè)p：天氣很冷，q：老王來了。符號(hào)化為：pq （4）設(shè)p：他吃飯,q：他看電視。符號(hào)化為：pq （5）設(shè)p：天下雨，q：他乘公共汽車。符號(hào)化為：pq （6）設(shè)p：天下雨，q：他乘公共汽上班。符號(hào)化為：qp （7）設(shè)p：天下雨，q：他乘公共汽車上班。符號(hào)化為：qp或ØqØp（8）設(shè)p：經(jīng)一事，q：長一智。符號(hào)化為：ØpØq

6、1.6設(shè)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結(jié)論：此命題為矛盾式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 結(jié)論：此命題為非重言式可滿足式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） 蘊(yùn)含等值式ÛØ（Ø（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結(jié)合律Û ØpØq 吸收律結(jié)論：該公式為可滿足式。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)由最小項(xiàng)定義可知道原命題的成真賦值為(0,0,0) (0,1,0) (0,0,1) (1,1,1)成假賦值為(0,1,1)(1,0,0)(1,0,1)(1,1,0)由主析取范式和主合取范式的關(guān)系即可知道 主合取范式為 (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)，不是極小項(xiàng) 令A(yù) = 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某勘探隊(duì)有3名

23、隊(duì)員，有一天取得一塊礦樣，3人判斷如下：甲說：這不是鐵，也不是銅；乙說：這不是鐵，是錫；丙說：這不是錫，是鐵；經(jīng)實(shí)驗(yàn)室鑒定后發(fā)現(xiàn)，其中一人兩個(gè)判斷都正確，一個(gè)人判對(duì)一半，另一個(gè)人全錯(cuò)了。根據(jù)以上情況判斷礦樣的種類。解：p：是鐵 q：是銅 r：是錫 由題意可得共有6種情況：1)甲全對(duì)，乙對(duì)一半，丙全錯(cuò)：(pq) (pr)(pr) (rp) 2)甲全對(duì)，丙對(duì)一半，乙全錯(cuò)：(pq) （rp）(rp)）(pr) 3)乙全對(duì)，甲對(duì)一半，丙全錯(cuò)：（pr）(pq) (qp) (rp) 4)乙全對(duì)，丙對(duì)一半，甲全錯(cuò)：（pr）(rp) (rp) (pq) 5)丙全對(duì)，甲對(duì)一半，乙全錯(cuò)：(rp) ( (pq) (

24、pq) (pr) 6)丙全對(duì)，乙對(duì)一半，甲全錯(cuò)：(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判斷下列推理是否正確，先將命題符號(hào)化，再寫出前提和結(jié)論，讓后進(jìn)行判斷。3 如果今天是1號(hào)，則明天是5號(hào)。今天是1號(hào)，所以明天是5號(hào)。 p：今天是1號(hào) q：明天是5號(hào) 解：前提：pq ,p 結(jié)論：q 推理的形式結(jié)構(gòu)為：(pq)p)q 證明：pq 前提引入 p 前提引入 q 假言推理此命題是正確命題1.16（2）判斷下列推理是否正確，先將命題符號(hào)化再寫出前提和結(jié)論，然后進(jìn)行判斷 如果今天是1號(hào)，則明天是5號(hào)。明天是5號(hào)，所以今天是1號(hào)。 解 設(shè)p: 今天是1號(hào),q: 明天是5號(hào),則該推理可以寫為( (pq)q)p 前提 p

26、q，q結(jié)論 p判斷 證明 ( (pq)q)p Û¬ ( (pq)q)p Û¬( pq)¬qp Û ¬( ¬pq) ¬qpÛ (p¬q) ¬qp Û¬qp此式子為非重言式的可滿足式，故不可以判斷其正確性所以此推理不正確1.16（3）如果今天是1號(hào)，則明天是5號(hào)，明天不是5號(hào)，所以今天不是1號(hào)。解：p:今天1號(hào).q:明天是5號(hào).(pq)¬q)¬p前提:pq,¬q.結(jié)論: ¬p.證明:pq 前提引入¬q 前提引入

27、¬p 拒取式推理正確1.17(1)前提：（pq）,qr,r結(jié)論：p.證明：qr 前提引入 r 前提引入 q 析取三段論 (pq) 前提引入 pq 置換 p 析取三段論即推理正確。（2）前提：p(qs),q, pr 結(jié)論：r s. 證明： pr 前提引入 r 附加前提引入 p 析取三段論 p(qs) 前提引入 qs 假言推理 q 前提引入 s 假言推理 由附加前提證明法可知，結(jié)論正確。 (3): 前提: pq. 結(jié)論: p(pq). 證明: pq. 前提引入 p 附加前提引入 q 假言推理pq 合取引入規(guī)則 （4）前提：q®p,q«s,s«t,tÙ

28、;r. 結(jié)論：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 如果他是理科學(xué)生，他必學(xué)好數(shù)學(xué)。如果他不是文科學(xué)生，他必是理科學(xué)生。他沒學(xué)好數(shù)學(xué)。所以它是文科學(xué)生。判斷上面推理是否正確，并證明你的結(jié)論。解：p:他是理科學(xué)生 q:他學(xué)好數(shù)學(xué) r:他是文科學(xué)生 前提：pq ，rp ，q結(jié)論：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ÛØ(&#