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

離散數(shù)學(屈婉玲版)第一章部分習題離散數(shù)學(屈婉玲版)第一章部分習題離散數(shù)學(屈婉玲版)第一章部分習題資料僅供參考文件編號：2022年4月離散數(shù)學(屈婉玲版)第一章部分習題版本號：A修改號：1頁次：1.0審核：批準:發(fā)布日期：第一章習題&判斷下列語句是否為命題,若是命題請指出是簡單命題還是復合命題.并將命題符號化,并討論它們的真值.(1)√2是無理數(shù).是命題,簡單命題.p:√2是無理數(shù).真值:1(2)5能被2整除.是命題,簡單命題.p:5能被2整除.真值:0現(xiàn)在在開會嗎不是命題.x+5>0.不是命題.(5)這朵花真好看呀! 不是命題.(6)2是素數(shù)當且僅當三角形有3條邊.是命題,復合命題.p:2是素數(shù).q:三角形有3條邊.pq真值:1(7)雪是黑色的當且僅當太陽從東方升起.是命題,復合命題.p:雪是黑色的.q:太陽從東方升起.pq真值:0(8)2008年10月1日天氣晴好.是命題,簡單命題.p:2008年10月1日天氣晴好.真值唯一.(9)太陽系以外的星球上有生物.是命題,簡單命題.p:太陽系以外的星球上有生物.真值唯一.(10)小李在宿舍里.是命題,簡單命題.P:小李在宿舍里.真值唯一.(11)全體起立!不是命題.(12)4是2的倍數(shù)或是3的倍數(shù).是命題,復合命題.p:4是2的倍數(shù).q:4是3的倍數(shù).p∨q真值:1(13)4是偶數(shù)且是奇數(shù).是命題,復合命題.P:4是偶數(shù).q:4是奇數(shù).p∧q真值:0(14)李明與王華是同學.是命題,簡單命題.p:李明與王華是同學.真值唯一.(15)藍色和黃色可以調(diào)配成綠色.是命題,簡單命題.p:藍色和黃色可以調(diào)配成綠色.真值:1判斷下列各命題的真值.(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+3≠6.(7)2+2≠4當且僅當3+3=6.(8)2+2≠4當且僅當3+3≠6.答案:設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）2是偶數(shù)又是素數(shù)。（2）小王不但聰明而且用功。（3）雖然天氣很冷，老王還是來了。（4）他一邊吃飯，一邊看電視。（5）如果天下雨，他就乘公共汽車上班。（6）只有天下雨，他才乘公共汽車上班。（7）除非天下雨，否則他不乘公共汽車上班。(意思為：如果他乘公共汽車上班，則天下雨或如果不是天下雨，那么他就不乘公共汽車上班)（8）不經(jīng)一事，不長一智。答案：（1）設p：2是偶數(shù)，q：2是素數(shù)。符號化為：p∧q（2）設p：小王聰明，q：小王用功。符號化為：p∧q（3）設p：天氣很冷，q：老王來了。符號化為：p∧q（4）設p：他吃飯,q：他看電視。符號化為：p∧q（5）設p：天下雨，q：他乘公共汽車。符號化為：p→q（6）設p：天下雨，q：他乘公共汽上班。符號化為：q→p（7）設p：天下雨，q：他乘公共汽車上班。符號化為：q→p或q→p（8）設p：經(jīng)一事，q：長一智。符號化為：p→q設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)pqrq∧rp∨(q∧r)00100(2)(p?r)∧(?p∨s)pqrspr?p?p∨s(pr)∧(?p∨s)00110110(3)(p∧(q∨r))→(p∨q)∧(r∧s)pqrsq∨rp∧(q∨r)p∨qr∧s(p∨q)∧(r∧s)(p∧(q∨r))→(p∨q)∧(r∧s)0011100101(4)?(p∨(q→(r∧?p))→(r∨?s)pqrs?pr∧?pq→(r∧?p)(p∨(q→(r∧?p))(r∨?s)?(p∨(q→(r∧?p))→(r∨?s)00111111111．7判斷下列命題公式的類型。（1）p(pqr)解：pqrpqpqrp(pqr)000001001011010111011111100111101111110111111111由真值表可知，該命題公式為重言式。（2）（p→┑p）→┑pp┑pp→┑p（p→┑p）→┑p01111001由真值知命題公式的類型是：重言式（3）┐(q→p)∧ppqq→p┐（q→p）┐(q→p)∧p00100010101010011100此命題公式是矛盾式。(4)(p→q)→(﹁q→﹁p)解:其真值表為:pq﹁p﹁qp→q﹁q→﹁p(p→q)→(﹁q→﹁p)0011111011011110010011100111由真值表觀察,此命題為重言式.(5)(﹁p→q)→(q→﹁p)解:其真值表為:pq﹁p﹁p→qq→﹁p(﹁p→q)→(q→﹁p)001011011111100111110100由真值表觀察,此命題為非重言式的可滿足式.（7）（p∨p）→((q∧q)∧r)解：pqrp∨pq∧qr(q∧q)∧r（p∨p）→((q∧q)∧r)00010100001100000101010001110000100101001011000011010101111000結論：此命題為矛盾式(8)(pq)→﹁(p∨q).pq(pq)(p∨q)﹁(p∨q)(pq)→﹁(p∨q)001011010101100101111100由此可以知道，上式為非重言式的可滿足式.(9)((ｐ→ｑ)∧(ｑ→ｒ))→(ｐ→ｒ)解:pｑｒｐ→ｑｑ→ｒ（ｐ→ｑ）∧（ｑ→ｒ）ｐ→ｒA0001111100111111010100110111111110001001101010111101000111111111該命題為永真式（10）（（p∨q）→r）s解：pqrsp∨q（p∨q）→r（p∨q）→r）s0000010000101100100100011011010010101011000110110011111111111111110110110110011001011001100101011010111111000101結論：此命題為非重言式可滿足式用等值演算法證明下列等值式（1）（p∧q）∨(p∧﹁q)p證明：（p∧q）∨(p∧﹁q)（分配律）p∧(q∨﹁q)（排中律）p∧1(同一律)p（3）（pq）((pq)(pq))證明：（pq）((pq)(qp))((pq)(qp))(pq)(qp)(pq)(qp)((pq)q)((pq)p)((pq)(qq))((pp)(qp))((pq)1)(1(qp))(pq)(qp)(pq)(pq)用等值演算法判斷下列公式的類型。（1）（（pq）p）.解：（1）（（pq）p）（（pq）p）蘊含等值式（（pq））p德·摩根律pqp雙重否定律ppq交換律0q矛盾律0零律即原式為矛盾式.((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結合律p∨q吸收律結論：該公式為可滿足式。(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)由主析取范式和主合取范式的關系即可知道主合取范式為(p∨(q∧r))→（p∧q∧r）∏(3,4,5,6)（3）（pq）qr解：（pq）qr（pq）qrpqqr0既（pq）qr是矛盾式。（pq）qr的主合取范式為M0M1M2M3M4M5M6M7，成假賦值為：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)(﹁pqr)∑(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=pqB=?(p∧q)C=(?p∧q)∨(?p∧?q)∨(p∧?q)D=p↓q則B*=?(p∨q)p↓q=D且ABC所以DA*C*C*=(?p∨q)∧(?p∨?q)∧(p∨?q)∏（0，1，2）∑(3)所以①!②某勘探隊有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號，則明天是5號。今天是1號，所以明天是5號。p：今天是1號q：明天是5號解：前提：p→q,p結論：q推理的形式結構為：((p→q)∧p)→q證明：①p→q前提引入②p前提引入③q假言推理此命題是正確命題（2）判斷下列推理是否正確，先將命題符號化再寫出前提和結論，然后進行判斷如果今天是1號，則明天是5號。明天是5號，所以今天是1號。解設p:今天是1號,q:明天是5號,則該推理可以寫為((p→q)∧q)→p前提p→q，q結論p判斷證明((p→q)∧q)→p?((p→q)∧q)∨p?(p→q)∨?q∨p?(?p∨q)∨?q∨p(p∧?q)∨?q∨p?q∨p此式子為非重言式的可滿足式，故不可以判斷其正確性所以此推理不正確（3）如果今天是1號，則明天是5號，明天不是5號，所以今天不是1號。解：p:今天1號.q:明天是5號.((p→q)∧?q)→?p前提:p→q,?q.結論:?p.證明:①p→q前提引入②?q前提引入③?p①②拒取式推理正確(1)前提：﹁（p∧﹁q）,﹁q∨r,﹁r結論：﹁p.證明：①﹁q∨r前提引入②﹁r前提引入③﹁q①②析取三段論④﹁(p∧﹁q)前提引入⑤﹁p∨q④置換⑥﹁p③⑤析取三段論即推理正確。（2）前提：p→(q→s),q,p∨﹁r結論：r→s.證明：①p∨﹁r前提引入②r附加前提引入③p析取三段論④p→(q→s)前提引入⑤q→s假言推理⑥q前提引入⑦s假言推理由附加前提證明法可知，結論正確。(3):前提:p→q.結論:p→(p∧q).證明:①p→q.前提引入②p附加前提引入③q①②假言推理④p∧q②③合取引入規(guī)則（4）前提：qp,qs,st,tr.結論：pqsr.證明：1)tr；前提引入2)t；1)的化簡3)st；前提引入4)（st）(ts);3)的置換5)ts4)的化簡6)s；2),5)的假言推理7)qs；前提引入8)(qs)(sq)；7)置換9)sq8)的化簡10)q；6),9)的假言推理11)qp；前提引入12)p；10),11)的假言推理13）r1)的化簡14)pqsr6),10),12),13)的合取所以推理正確。1．18如果他是理科學生，他必學好數(shù)學。如果他不是文科學生，他必是理科學生。他沒學好數(shù)學。所以它是文科學生。判斷上面推理是否正確，并證明你的結論。解：p:他是理科學生q:他學好數(shù)學r:他是文科學生前提：p→q，┐r→p，┐q結論：r①┐p前提引入②p→q前提引入③┐p①②拒取式④┐r→p前提引入⑤r③④拒取式給定命題公式如下：p(qr)。求命題公式的主析取范式、主合取范式、成真賦值、成假賦值。解：p(qr)((pqq))(rr))((qr)(pp))pqr)pqr)(pqr)(pqr)(pqr)(pqr)m7m6m5vm4m6m2m7m6m5vm4m22、4、5、6、7∴p(qr)0、1、3既010、100、101、110、111是成真賦值，000、001、011是成假賦值給定命題公式如下：（pq）r。求命題公式的主析取范式、主合取范式、成真賦值、成假賦值。解：（pq）r(pq)r((pq)(rr))((pp)(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m7m6m7m5m3m1m7m6m5m3m11、3、5、6、7∴（pq）r0、2、4既001、011、101、110、111是成真賦值，000、010、100是成假賦值。例題例給定命題公式如下，用等值演算判斷公式類型(1)(p∧q)→(p∨q)解：﹁(p∧q)∨(p∨q)﹁p∨﹁q∨p∨q(﹁p∨p)∨(﹁q∨q)1∨11所以為重言式（2）(p?q)?((p→q)∧(q→p))解：(p?q)?((p→q)∧(q→p))(p?q)?(?q)