離散數(shù)學屈婉玲版第一章部分習題匯總

《離散數(shù)學屈婉玲版第一章部分習題匯總》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學屈婉玲版第一章部分習題匯總（19頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

3、題,簡單命題.p: 藍色和黃色可以調(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當且僅當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)pq,真值為1.(6)pq,真值為0.(7)pq,真值為0.(8)pq,真值為1

4、.14將下列命題符號化，并討論其真值。 （1）如果今天是1號，則明天是2號。 p:今天是1號。 q:明天是2號。 符號化為：pq 真值為：1 （2）如果今天是1號，則明天是3號。 p:今天是1號。 q:明天是3號。 符號化為：pq 真值為：01.5將下列命題符號化。（1）2是偶數(shù)又是素數(shù)。（2）小王不但聰明而且用功。（3）雖然天氣很冷，老王還是來了。（4）他一邊吃飯，一邊看電視。（5）如果天下雨，他就乘公共汽車上班。（6）只有天下雨，他才乘公共汽車上班。（7）除非天下雨，否則他不乘公共汽車上班。(意思為：如果他乘公共汽車上班，則天下雨或如果不是天下雨，那么他就不乘公共汽車上班)（8）不經(jīng)一事，

5、不長一智。答案：（1）設p：2是偶數(shù)，q：2是素數(shù)。符號化為：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或qp（8）設p：經(jīng)一事，q：長一智。符號化為：pq1.6設p,q的真值為0；r,s的真值為1，求下列各命題公式的真值。（1）p(qr)（2）(pr)(ps)（3）(p(qr)(pq)(rs)（4）(p(q(rp

6、) (rs) 解：（1） p(qr)pqrqrp(qr) 00100(2) (pr)(ps) pqrsprpps(pr)(ps)00110110(3)(p(qr)(pq)(rs)pqrsqrp(qr)pqrs(pq)(rs)(p(qr)(pq)(rs)0011100101 (4) (p(q(rp) (rs)pqrsprpq(rp)(p(q(rp)(rs)(p(q(rp) (rs)001111111117 判斷下列命題公式的類型。（1）p(pqr) 解：pqrpqpqrp(pqr)000001001011010111011111100111101111110111111111由真值表可知，該命題

7、公式為重言式。（2）（p p） p ppp p（p p） p01111001由真值知命題公式的類型是：重言式（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

8、（pp）(qq) r)00010100001100000101010001110000100101001011000011010101111000結(jié)論：此命題為矛盾式1.7(8) (p q)(pq).p q(pq)(pq)(pq)(p q)(pq)0 010110 101011 001011 11100由此可以知道，上式為非重言式的可滿足式.(9) ()()() 解:p（）（）A0001111100111111010100110111111110001001101010111101000111111111該命題為永真式（10）（pq）r）s解：pqrspq（pq）r（pq）r）s0000010

9、000101100100100011011010010101011000110110011111111111111110110110110011001011001100101011010111111000101 結(jié)論：此命題為非重言式可滿足式1.8 用等值演算法證明下列等值式（1）（pq）(pq) p證明：（pq）(pq) （分配律）p(qq) （排中律）p1 (同一律)p （3）（p q） ( ( p q ) ( p q ) ) 證明：（p q） ( ( p q ) (q p ) ) ( ( p q ) ( q p ) ) ( p q ) ( q p ) ( p q ) ( q p ) (

10、( p q ) q ) ( (p q ) p ) ( ( p q ) ( q q ) ) ( ( p p ) ( q p) ) ( p q ) 1) (1 ( q p) ) ( p q ) ( q p) ( p q ) ( p q ) 1.9 用等值演算法判斷下列公式的類型。 （1）（pq）p）.解：（1）（pq）p）（pq）p） 蘊含等值式（pq）p 德摩根律pqp 雙重否定律 ppq 交換律0q 矛盾律0 零律即原式為矛盾式.(2) (pq) (qp)(pq)解：(pq) (qp)(pq)(pq) (pq)(pq) (pq) (pq) (pq)(Pq) (pq)(pq) (pq) 1即(p

11、q) (qp)(pq)是重言式。 (3) (pq)(qp). 解：(pq)(qp) (pq) (qp) (pq) (qp) (p(pq) (q(qp) ( (pp)q) (qq)p (pq) (pq) (pq)或 (pq)(qp) (pq) (qp) (pq) (qp)（ (pq) q）p結(jié)合律 pq 吸收律結(jié)論：該公式為可滿足式。1.12(1)求下面命題公式的主析取范式、主合取范式、成真賦值、成假賦值。 (p(qr)（pqr）(p(qr)(pqr) (p(qr) (pqr) (pq) (pr)(pqr) (pq)(rr) (pr)(qq) (pqr) (pqr)(pqr)(pqr) (pqr

12、) (pqr) (pqr)(pqr) (pqr) (pqr) (pqr) (pqr)(pqr) (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)由主析取范式和主合取范式的關(guān)系即可知道 主合取范式為 (p(qr)（pqr）(3,4,5,6)（3）（pq）q r解：（pq）q r（pq）qrpqqr0既（pq）q r是矛盾式。（pq）q r的主合取范式為M0 M1 M2 M3 M4

13、 M5 M6 M7， 成假賦值為：000，001，010，011，100，101，11113.通過求主析取范式判斷下列各組命題公式是否等值。 （1）p(qr); q(pr). 解：p(qr) p (qr) p (qr) pqr (p(qq)(rr)(pp)q(rr)(pp)(qq) r) (pqr) (pqr) (pqr) (pqr) (pqr) (pqr) (pq r) (0,1,2,3,4,5,7)q(pr) q (pr) pqr (0,1,2,3,4,5,7) 所以兩式等值。（2） pq(pq) (p(qq)(q(pp) (pq)(pq) (qp) (pq) (pq) (pq) (pq)

14、m1m0m2(0,1,2)(pq)處原為(qp)，不是極小項 令A = pqB= (pq)C=(pq) (pq) (pq)D = pq則B*=(pq) ? pq=D且A?B?C所以D?A*?C*C* = (pq)(pq)(pq)?（0，1，2）?(3)所以!?1.15某勘探隊有3名隊員，有一天取得一塊礦樣，3人判斷如下：甲說：這不是鐵，也不是銅；乙說：這不是鐵，是錫；丙說：這不是錫，是鐵；經(jīng)實驗室鑒定后發(fā)現(xiàn)，其中一人兩個判斷都正確，一個人判對一半，另一個人全錯了。根據(jù)以上情況判斷礦樣的種類。解：p：是鐵 q：是銅 r：是錫 由題意可得共有6種情況：1)甲全對，乙對一半，丙全錯：(pq) (pr

15、)(pr) (rp) 2)甲全對，丙對一半，乙全錯：(pq) （rp）(rp)）(pr) 3)乙全對，甲對一半，丙全錯：（pr）(pq) (qp) (rp) 4)乙全對，丙對一半，甲全錯：（pr）(rp) (rp) (pq) 5)丙全對，甲對一半，乙全錯：(rp) ( (pq) (pq) (pr) 6)丙全對，乙對一半，甲全錯：(rp) (pr)(pr) (pq) 則1(pqprrp) (pqprrp) 000(pqrppr)(pqrppr) 000(prpqrp) （prqprp） (pqr) 0pqr（prrppq）（prrppq） 000(rppqpr) (rppqpr)0(pqr) p

16、qr(rpprpq) (rp prpq)000所以（pqr）（pqr）而這塊礦石不可能既是銅又是錫，所以只能是1.16判斷下列推理是否正確，先將命題符號化，再寫出前提和結(jié)論，讓后進行判斷。3 如果今天是1號，則明天是5號。今天是1號，所以明天是5號。 p：今天是1號 q：明天是5號 解：前提：pq ,p 結(jié)論：q 推理的形式結(jié)構(gòu)為：(pq)p)q 證明：pq 前提引入 p 前提引入 q 假言推理此命題是正確命題1.16（2）判斷下列推理是否正確，先將命題符號化再寫出前提和結(jié)論，然后進行判斷 如果今天是1號，則明天是5號。明天是5號，所以今天是1號。 解 設p: 今天是1號,q: 明天是5號,則

17、該推理可以寫為( (pq)q)p 前提 pq，q結(jié)論 p判斷 證明 ( (pq)q)p ( (pq)q)p ( pq)qp ( pq) qp (pq) qp qp此式子為非重言式的可滿足式，故不可以判斷其正確性所以此推理不正確1.16（3）如果今天是1號，則明天是5號，明天不是5號，所以今天不是1號。解：p:今天1號.q:明天是5號.(pq)q)p前提:pq,q.結(jié)論: p.證明:pq 前提引入q 前提引入p 拒取式推理正確1.17(1)前提：（pq）,qr,r結(jié)論：p.證明：qr 前提引入 r 前提引入 q 析取三段論 (pq) 前提引入 pq 置換 p 析取三段論即推理正確。（2）前提：p

18、(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）前提：qp,qs,st,tr. 結(jié)論：pqsr.證明：1) tr；前提引入2) t ；1)的化簡3) st；前提引入4)（st）(ts); 3)的置換5) ts 4)的化簡6) s； 2),5)的假言推理7) qs；前提引入8) (qs)(sq)；7)置換9) sq 8)的

19、化簡10) q；6),9)的假言推理11) qp；前提引入12) p；10),11)的假言推理13）r 1)的化簡14) pqsr 6),10),12),13)的合取所以推理正確。118 如果他是理科學生，他必學好數(shù)學。如果他不是文科學生，他必是理科學生。他沒學好數(shù)學。所以它是文科學生。判斷上面推理是否正確，并證明你的結(jié)論。解：p:他是理科學生 q:他學好數(shù)學 r:他是文科學生 前提：pq ，rp ，q結(jié)論：r p 前提引入 pq 前提引入 p 拒取式 rp 前提引入 r 拒取式1.19 給定命題公式如下：p(qr)。 求命題公式的主析取范式、主合取范式、成真賦值、成假賦值。解： p(qr)

20、( p(qq)(rr)(qr)(pp) (pqr)(pqr)(pqr)(pqr)(pqr)(pqr) m7m6m5vm4m6m2 m7m6m5vm4m2 (2、4、5、6、7) p(qr) (0、1、3) 既010、100、101、110、111是成真賦值， 000、001、011是成假賦值1.20 給定命題公式如下：（pq）r。 求命題公式的主析取范式、主合取范式、成真賦值、成假賦值。解： （pq）r (pq)r(pq)(rr)(pp)(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m7m6m7m5m3m1 m7m6 m5m3m1(1、3、5、6、7)（pq）r (0

21、、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）

22、 (pq)q解： (pq)q(pq)q (pq)qp(qq) p00由上使等值演算結(jié)果可知：此式為矛盾式。(4) (pp)q0q(0q)(q0)(0q)(q0)1qq由此結(jié)果可得此式為：非重言式的可滿足式 （5）p(pq);解：p(pq)p( pq)（p p）q 1q1所以該命題公式是重言式。（6）（pp）(qq)r)1（0r）10100所以為矛盾式 (7)(pq)p)?p解: (pq)p) ?p ?(（pq）p) ?p ?(pq) p) ?p?(pq) p?p?p?p?(pp)(pp) 等價等值式?pp 等冪律?pp 蘊涵等值式?1所以該式為重言式例1.25 第（8）題 （pq）(pq)(pq)p)(（pq）q) (pp)(qp)(pq)(qq)p(pq)(pq)p(pq)p或（pq）(pq)p(qq) p1p為可滿足式 (9) (pqr) ?(pqr)?(pq) r) ?(pqr)?(pq)r) ?(pqr) ?(pqr) ?(pqr)?(pqr)(pqr)(pqr)(pqr)?(pqr)(pqr)?(pqr)(pqr)?1 所以該式為重言式（10）（pq）r解： 是非重言式的可滿足式，因為000是其成假賦值，111是其成真賦值。