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

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

第一章習(xí)題 1.1&1.2 判斷下列語句是否為命題,若是命題請指出是簡單命題還是復(fù)合命題.并將命題符號化,并討論它們的真值. (1) √2是無理數(shù). 是命題,簡單命題.p:√2是無理數(shù).真值:1 (2) 5能被2整除. 是命題,簡單命題.p:5能被2整除.真值:0 (3) 現(xiàn)在在開會嗎? 不是命題. (4) x+5>0. 不是命題. (5) 這朵花真好看呀! 不是命題. (6) 2是素數(shù)當(dāng)且僅當(dāng)三角形有3條邊. 是命題,復(fù)合命題.p:2是素數(shù).q:三角形有3條邊.pq真值:1 (7) 雪是黑色的當(dāng)且僅當(dāng)太陽從東方升起. 是命題,復(fù)合命題.p:雪是黑色的.q:太陽從東方升起. pq真值: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ù).p∨q真值:1 (13) 4是偶數(shù)且是奇數(shù). 是命題,復(fù)合命題.P:4是偶數(shù).q:4是奇數(shù).p∧q真值:0 (14) 李明與王華是同學(xué). 是命題,簡單命題.p: 李明與王華是同學(xué).真值唯一. (15) 藍(lán)色和黃色可以調(diào)配成綠色. 是命題,簡單命題.p: 藍(lán)色和黃色可以調(diào)配成綠色.真值:1 1.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當(dāng)且僅當(dāng)3+3=6. (6)2+2=4當(dāng)且僅當(dāng)3+3≠6. (7)2+2≠4當(dāng)且僅當(dāng)3+3=6. (8)2+2≠4當(dāng)且僅當(dāng)3+3≠6. 答案: 設(shè)p:2+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)pq,真值為1. (6)p┐q,真值為0. (7)┐pq,真值為0. (8)┐p┐q,真值為1. 1．4將下列命題符號化，并討論其真值。 （1）如果今天是1號，則明天是2號。 p:今天是1號。 q:明天是2號。 符號化為：pq 真值為：1 （2）如果今天是1號，則明天是3號。 p:今天是1號。 q:明天是3號。 符號化為：pq 真值為：0 1.5將下列命題符號化。 （1）2是偶數(shù)又是素數(shù)。 （2）小王不但聰明而且用功。 （3）雖然天氣很冷，老王還是來了。 （4）他一邊吃飯，一邊看電視。 （5）如果天下雨，他就乘公共汽車上班。 （6）只有天下雨，他才乘公共汽車上班。 （7）除非天下雨，否則他不乘公共汽車上班。(意思為：如果他乘公共汽車上班，則天下雨或如果不是天下雨，那么他就不乘公共汽車上班) （8）不經(jīng)一事，不長一智。 答案：（1）設(shè)p：2是偶數(shù)，q：2是素數(shù)。符號化為：p∧q （2）設(shè)p：小王聰明，q：小王用功。符號化為：p∧q （3）設(shè)p：天氣很冷，q：老王來了。符號化為：p∧q （4）設(shè)p：他吃飯,q：他看電視。符號化為：p∧q （5）設(shè)p：天下雨，q：他乘公共汽車。符號化為：p→q （6）設(shè)p：天下雨，q：他乘公共汽上班。符號化為：q→p （7）設(shè)p：天下雨，q：他乘公共汽車上班。符號化為：q→p或q→p （8）設(shè)p：經(jīng)一事，q：長一智。符號化為：p→q 1.6設(shè)p,q的真值為0；r,s的真值為1，求下列各命題公式的真值。 （1） p∨(q∧r) （2） (p?r)∧(p∨s) （3） (p∧(q∨r))→(p∨q)∧(r∧s) （4） (p∨(q→(r∧p)) → (r∨s) 解：（1） p∨(q∧r) p q r q∧r p∨(q∧r) 0 0 1 0 0 (2) (p?r)∧(p∨s) p q r s pr p p∨s (pr)∧(p∨s) 0 0 1 1 0 1 1 0 (3)(p∧(q∨r))→(p∨q)∧(r∧s) p q r s q∨r p∧(q∨r) p∨q r∧s (p∨q)∧(r∧s) (p∧(q∨r))→(p∨q)∧(r∧s) 0 0 1 1 1 0 0 1 0 1 (4) (p∨(q→(r∧p)) → (r∨s) p q r s p r∧p q→(r∧p) (p∨(q→(r∧p)) (r∨s) (p∨(q→(r∧p)) → (r∨s) 0 0 1 1 1 1 1 1 1 1 1．7 判斷下列命題公式的類型。 （1）p(pqr) 解： p q r pq pqr p(pqr) 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 由真值表可知，該命題公式為重言式。 （2）（p → ┑p）→ ┑ p p ┑p p → ┑p （p → ┑p）→ ┑p 0 1 1 1 1 0 0 1 由真值知命題公式的類型是：重言式 （3）┐(q→p)∧p p q q→p ┐（q→p） ┐(q→p)∧p 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 此命題公式是矛盾式。 (4)(p→q) →(﹁q→﹁p) 解: 其真值表為: p q ﹁p ﹁q p→q ﹁q→﹁p (p→q)→(﹁q→﹁p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1 由真值表觀察,此命題為重言式. (5)( ﹁p→q) →(q→﹁p) 解: 其真值表為: p q ﹁p ﹁p→q q→﹁p (﹁p→q)→(q→﹁p) 0 0 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 由真值表觀察,此命題為非重言式的可滿足式. （7）（p∨p）→((q∧q) ∧r) 解： p q r p∨p q∧q r (q∧q) ∧r （p∨p）→((q∧q) ∧r) 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 結(jié)論：此命題為矛盾式 1.7(8) (p q)→﹁(p∨q). p q (pq) (p∨q) ﹁(p∨q) (p q)→﹁(p∨q) 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 由此可以知道，上式為非重言式的可滿足式. (9) ((ｐ→ｑ)∧(ｑ→ｒ))→(ｐ→ｒ) 解: p ｑ ｒ ｐ→ｑ ｑ→ｒ （ｐ→ｑ）∧（ｑ→ｒ） ｐ→ｒ A 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 該命題為永真式 （10）（（p∨q）→r）s 解： p q r s p∨q （p∨q）→r （p∨q）→r）s 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 結(jié)論：此命題為非重言式可滿足式 1.8 用等值演算法證明下列等值式 （1）（p∧q）∨(p∧﹁q) p 證明： （p∧q）∨(p∧﹁q) （分配律） p∧(q∨﹁q) （排中律） p∧1 (同一律) 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 ) ( ( 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） 蘊(yùn)含等值式 （（pq））p 德摩根律 pqp 雙重否定律 ppq 交換律 0q 矛盾律 0 零律 即原式為矛盾式. (2) ((pq) (qp))(pq) 解：((pq) (qp))(pq) (pq) (pq) ((pq) (pq)) ((pq) (pq)) (Pq) (pq) (pq) (pq)) 1 即((pq) (qp))(pq)是重言式。 (3) (p→q)→(q→p). 解：(p→q)→(q→p) ((p∨q)) ∨ (q∨p) (p∧q) ∨(q∨p) (p∨(p∧q)) ∧(q∨(q∨p)) ( (p∨p)∨q) ∧((q∨q)∨p] (p∨q) ∧(p∨q) (p∨q) 或 (p→q)→(q→p) ((p∨q)) ∨ (q∨p) (p∧q) ∨(q∨p) （ (p∧q) ∨q）∨p結(jié)合律 p∨q 吸收律 結(jié)論：該公式為可滿足式。 1.12(1)求下面命題公式的主析取范式、主合取范式、成真賦值、成假賦值。 (p∨(q∧r))→（p∧q∧r） (p∨(q∧r))∨(p∧q∧r) (p∧(q∨r)) ∨(p∧q∧r) (p∧q) ∨(p∧r)∨(p∧q∧r) ((p∧q)∧(r∨r)) ∨((p∧r)∧(q∨q)) ∨(p∧q∧r) (p∧q∧r)∨(p∧q∧r)∨(p∧q∧r) ∨(p∧q∧r) ∨(p∧q∧r) (p∧q∧r)∨(p∧q∧r) ∨(p∧q∧r) ∨(p∧q∧r) ((p∧q∧r) ∨(p∧q∧r)∨(p∧q∧r) ∨(p∧q∧r) m0∨m1∨m2∨m7 ∑(0,1,2,7) 故 其主析取范式為 (p∨(q∧r))→（p∧q∧r）∑(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∨(q∧r))→（p∧q∧r）∏(3,4,5,6) （3）（pq）q r 解：（pq）q r （pq）qr pqqr 0 既（pq）q r是矛盾式。（pq）q r的主合取范式為M0 M1 M2 M3 M4 M5 M6 M7， 成假賦值為：000，001，010，011，100，101，111． 13.通過求主析取范式判斷下列各組命題公式是否等值。 （1）①p→(q→r);② q→(p→r). 解：p→(q→r) ﹁p (q→r) ﹁p (﹁qr) ﹁p﹁qr (﹁p(q﹁q)(r﹁r))((p﹁p)﹁q(r﹁r))((p﹁p)(q﹁q) r) (﹁pqr) (﹁pq﹁r) (﹁p﹁qr) (﹁p﹁q﹁r) (p﹁qr) (p﹁q﹁r) (﹁pq r) ∑(0,1,2,3,4,5,7) q→(p→r) ﹁q (﹁pr) ﹁p﹁qr ∑(0,1,2,3,4,5,7) 所以兩式等值。 （2）① pq (p∧q) (p∧(q∨q))∨(q∧(p∨p)) (p∧q)∨(p∧q) ∨(q∧p) ∨(p∧q) (p∧q) ∨(p∧q) ∨(p∧q) m1∨m0∨m2 ∑(0,1,2) (p∧q)處原為(q∧p)，不是極小項 ②令A(yù) = pq B= (p∧q) C=(p∧q) ∨(p∧q) ∨(p∧q) D = p↓q 則B*=(p∨q) ? p↓q=D 且A?B?C 所以D?A*?C* C* = (p∨q)∧(p∨q)∧(p∨q) ?∏（0，1，2）?∑(3) 所以①!?② 1.15某勘探隊有3名隊員，有一天取得一塊礦樣，3人判斷如下： 甲說：這不是鐵，也不是銅； 乙說：這不是鐵，是錫； 丙說：這不是錫，是鐵； 經(jīng)實驗室鑒定后發(fā)現(xiàn)，其中一人兩個判斷都正確，一個人判對一半，另一個人全錯了。根據(jù)以上情況判斷礦樣的種類。 解：p：是鐵 q：是銅 r：是錫 由題意可得共有6種情況： 1)甲全對，乙對一半，丙全錯：(﹁p∧﹁q) ∧ ((﹁p∧﹁r)∨(p∧r)) ∧(r∧﹁p) ① 2)甲全對，丙對一半，乙全錯：(﹁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) ∧( (﹁p∧q) ∨(p∧﹁q)) ∧(p∧﹁r) ⑤ 6)丙全對，乙對一半，甲全錯：(﹁r∧p) ∧((﹁p∧﹁r)∨(p∧r)) ∧(p∧q) ⑥ 則①∨②∨③∨④∨⑤∨⑥1 ①(﹁p∧﹁q∧﹁p∧﹁r∧r∧﹁p) ∨(﹁p∧﹁q∧p∧r∧r∧﹁p) 0∨00 ②(﹁p∧﹁q∧﹁r∧﹁p∧p∧﹁r)∨(﹁p∧﹁q∧r∧p∧p∧﹁r) 0∨00 ③(﹁p∧r∧﹁p∧q∧r∧﹁p) ∨（﹁p∧r∧﹁q∧p∧r∧﹁p） (﹁p∧q∧r) ∨0﹁p∧q∧r ④（﹁p∧r∧﹁r∧﹁p∧p∧q）∨（﹁p∧r∧r∧p∧p∧q） 0∨00 ⑤(﹁r∧p∧﹁p∧q∧p∧﹁r) ∨ (﹁r∧p∧p∧﹁q∧p∧﹁r)0∨(p∧﹁q∧﹁r) p∧﹁q∧﹁r ⑥(﹁r∧p∧﹁p∧﹁r∧p∧q) ∨ (﹁r∧p ∧p∧r∧p∧q)0∨00 所以①∨②∨③∨④∨⑤∨⑥（﹁p∧q∧r）∨（p∧﹁q∧﹁r） 而這塊礦石不可能既是銅又是錫，所以只能是 1.16判斷下列推理是否正確，先將命題符號化，再寫出前提和結(jié)論，讓后進(jìn)行判斷。 3 如果今天是1號，則明天是5號。今天是1號，所以明天是5號。 p：今天是1號 q：明天是5號 解：前提：p→q ,p 結(jié)論：q 推理的形式結(jié)構(gòu)為：((p→q)∧p)→q 證明：①　　p→q 前提引入 　　　　　　　 ②　 p 前提引入　 　　　　　　　 ③ q 假言推理 　　　　此命題是正確命題　 1.16（2） 判斷下列推理是否正確，先將命題符號化再寫出前提和結(jié)論，然后進(jìn)行判斷 如果今天是1號，則明天是5號。明天是5號，所以今天是1號。 解 設(shè)p: 今天是1號,q: 明天是5號,則該推理可以寫為 ( (p→q)∧q)→p 前提 p→q，q 結(jié)論 p 判斷 證明 ( (p→q)∧q)→p ( (p→q)∧q)∨p ( p→q)∨q∨p ( p∨q) ∨q∨p (p∧q) ∨q∨p q∨p 此式子為非重言式的可滿足式，故不可以判斷其正確性 所以此推理不正確 1.16（3）如果今天是1號，則明天是5號，明天不是5號，所以今天不是1號。 解：p:今天1號. q:明天是5號. ((p→q)∧q)→p 前提:p→q,q. 結(jié)論: p. 證明:①p→q 前提引入 ②q 前提引入 ③p ①②拒取式 推理正確 1.17(1)前提：﹁（p∧﹁q）,﹁q∨r,﹁r 結(jié)論：﹁p. 證明：①﹁q∨r 前提引入 ②﹁r 前提引入 ③﹁q ①②析取三段論 ④ ﹁(p∧﹁q) 前提引入 ⑤﹁p∨q ④置換 ⑥﹁p ③⑤析取三段論 即推理正確。 （2）前提：p→(q→s),q, p∨﹁r 結(jié)論：r →s. 證明：① p∨﹁r 前提引入 ② r 附加前提引入 ③ p 析取三段論 ④ p→(q→s) 前提引入 ⑤ q→s 假言推理 ⑥ q 前提引入 ⑦ s 假言推理 由附加前提證明法可知，結(jié)論正確。 (3): 前提: p→q. 結(jié)論: p→(p∧q). 證明: ①p→q. 前提引入 ②p 附加前提引入 ③q ①②假言推理 ④p∧q ②③合取引入規(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)的化簡 10) q；6),9)的假言推理 11) qp；前提引入 12) p；10),11)的假言推理 13）r 1)的化簡 14) pqsr 6),10),12),13)的合取 所以推理正確。 1．18 如果他是理科學(xué)生，他必學(xué)好數(shù)學(xué)。如果他不是文科學(xué)生，他必是理科學(xué)生。他沒學(xué)好數(shù)學(xué)。所以它是文科學(xué)生。 判斷上面推理是否正確，并證明你的結(jié)論。 解：p:他是理科學(xué)生 q:他學(xué)好數(shù)學(xué) r:他是文科學(xué)生 前提：p→q ，┐r→p ，┐q 結(jié)論：r ① ┐p 前提引入 ② p→q 前提引入 ③ ┐p ①②拒取式 ④ ┐r→p 前提引入 ⑤ r ③④拒取式 1.19 給定命題公式如下：p(qr)。 求命題公式的主析取范式、主合取范式、成真賦值、成假賦值。 解： p(qr) (( 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、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∨1 1 所以為重言式 （2）(p?q) ? ((p→q)∧(q→p)) 解：(p?q) ? ((p→q)∧(q→p)) (p?q) ? (?q) ((p?q)→(p?q))∧((p?q)→(p?q)) (p?q)→(p?q) (p?q) ∨(p?q) ((p→q) ∧(q→p)) ∨((p→q) ∧(q→p)) (((p→q) ∨ (q→p)) ∨(p→q)) ∧((p→q) ∨ (q→p)) ∨(q→p)) (1∨ (q→p))∧(1∨(q→p)) 1 ∧1 1 所以此式是重言式(紅色字體部分可刪去) （3） (p→q)∧q 解： (p→q)∧q(p∨q)∧q (p∧q)∧q p∧(q∧q) p∧00 由上使等值演算結(jié)果可知：此式為矛盾式。 (4) (pp)q 0q (0q)(q0) (0q)(q0) 1q q 由此結(jié)果可得此式為：非重言式的可滿足式 （5）p(pq); 解：p(pq) p( pq) （p p）q 1q 1 所以該命題公式是重言式。 （6）（p∨﹁p）→((q∧﹁q)∧r) 1→（0∧r） 1→0 ﹁1∨0 0 所以為矛盾式 (7)((p→q)→p)?p 解: ((p→q)→p) ?p ?(（p→q）∨p) ?p ?((p∨q) ∨p) ?p ?(p∧q) ∨p?p ?p?p ?(p→p)∧(p→p) 等價等值式 ?p→p 等冪律 ?p∨p 蘊(yùn)涵等值式 ?1 所以該式為重言式 例1.25 第（8）題 （p∧q）∨(p∧﹁q) ((p∧q)∨p)∧(（p∧q）∨﹁q) (p∨p)∧(q∨p)∧(p∨﹁q)∧(q∨﹁q) p∧(p∨q)∧(p∨﹁q) p∧(p∨﹁q) p 或（p∧q）∨(p∧﹁q) p∧(q∨﹁q) p∧1 p 為可滿足式 (9) (p∨q∨r) ?(p∧q∧r) ?((p∨q) ∨r) ?(p∧q∧r) ?(p∨q)∧r) ?(p∧q∧r) ?(p∧q∧r) ?(p∧q∧r) ?((p∧q∧r)→(p∧q∧r))∧((p∧q∧r)→(p∧q∧r)) ?(p∧q∧r)→(p∧q∧r) ?(p∧q∧r)∨(p∧q∧r) ?1 所以該式為重言式 （10）（p∧q）∧r 解： 是非重言式的可滿足式，因為000是其成假賦值，111是其成真賦值。