離散數(shù)學(xué)答案 第二章 命題邏輯.doc

第二章 命題邏輯習(xí)題2.11解 不是陳述句，所以不是命題。 x取值不確定，所以不是命題。 問句，不是陳述句，所以不是命題。 驚嘆句，不是陳述句，所以不是命題。 是命題，真值由具體情況確定。 是命題，真值由具體情況確定。 是真命題。 是悖論，所以不是命題。 是假命題。 2解 是復(fù)合命題。設(shè)p：他們明天去百貨公司；q：他們后天去百貨公司。命題符號化為。 是疑問句，所以不是命題。 是悖論，所以不是命題。 是原子命題。 是復(fù)合命題。設(shè)p：王海在學(xué)習(xí)；q：李春在學(xué)習(xí)。命題符號化為pq。 是復(fù)合命題。設(shè)p：你努力學(xué)習(xí)；q：你一定能取得優(yōu)異成績。pq。 不是命題。 不是命題 。是復(fù)合命題。設(shè)p：王海是女孩子。命題符號化為：p。 3解 如果李春遲到了，那么他錯過考試。 要么李春遲到了，要么李春錯過了考試，要么李春通過了考試。 李春錯過考試當(dāng)且僅當(dāng)他遲到了。 如果李春遲到了并且錯過了考試，那么他沒有通過考試。4解 p(qr)。pq。qp。q p。習(xí)題2.2 1解 是1層公式。 不是公式。 一層： pq，p 二層：pq所以，是3層公式。 不是公式。 (pq)(q( qr)是5層公式，這是因為 一層：pq，q，r 二層：qr 三層：q( qr) 四層：(q( qr) 2解 A=(pq)q是2層公式。真值表如表2-1所示：表2-1pq0000011110101111 是3層公式。真值表如表2-2所示：表2-2pq00101011101000111111 是3層公式。真值表如表2-3所示：表2-3pqr00000010010001010001101100111000011101001111010111111111是4層公式。真值表如表2-4所示： 3解 真值表如表2-5所示：表2-5pq001111011000100101110001所以其成真賦值為：00，10，11；其成假賦值為01。 真值表如表2-6所示：表2-6pqr0000100100010010110010001101001101111111所以其成真賦值為：000，010，100，110，111；其成假賦值為001，011，101。真值表如表2-7所示，所以其成真賦值為：00，11；成假賦值為：01，10，。 4解 設(shè)，其真值表如表2-8所示：表2-8pq00011010111001111101故為重言式。 設(shè)A=(pq)(pq)，其真值表如表2-9所示：表2-9pqpqpq(pq)A000010010100100100111100故A=(pq)(pq)為矛盾式。 設(shè)A=(pq)(pq)，其真值表如表2-10所示：表2-10pq001010011111100100110010故A=(pq)(pq)為可滿足式。 設(shè)，其真值表如表2-11所示：表2-11pqr0001111100111111010100110111111110001001101010111101000111111111故為重言式。習(xí)題2.3 1解 真值表如表2-12所示：表2-12pq0011101011001010010101100010由真值表可以看出和所在的列相應(yīng)填入值相同，故等值。 真值表如表2-13所示：表2-13pq001000010000101011110101由真值表可以看出和所在的列相應(yīng)填入值相同，故等值。 真值表如表2-14所示：表2-14pq0011111011011110010101100100由真值表可以看出p和(pq)(pq)所在的列相應(yīng)填入值相同，故等值。真值表如表2-15所示：pqrqr p(qr) pq (pq)r 00011010011101010010101111011001101101110111000101111111表2-15 由真值表可以看出p(qr)和(pq)r所在的列相應(yīng)填入值相同，故等值。2證明 (pq) (pq) (pq)( pq) p (qq) p。(pq)(qp)(pq) (qp)(pq)(p p)( qq)(q p)( pq)(pq)。由可得，(pq)( pq)(pq)( pq)(pq)(qp)(pq)pq。p(qr) p(q r) q(p r) q( p r)。 3解 (pq)(pq)pq (pq)( pq)pq (pq)(pq)(qp)(pq)(qp)(pq) (pq) pq。同理可證(pq) pq。 4解 與習(xí)題2.2第4（4）相同。 真值表如表2-16所示：表2-16p q p q pq q p A 0011111011011110010011100111所以公式是重言式。真值表如表2-17所示，所以公式是矛盾式。表2-170011100011010010010101100100 真值表如表2-18所示，所以公式是重言式。表2-18000001001001010001011001100001101001110101111111 真值表如表2-19所示，所以公式僅為可滿足式。表2-19001011011101100100110100 真值表如表2-20所示，所以公式是重言式。表2-20pqr pqrqpr(pq)(rq)(pr)qA000110111001100011010110111011110111100010011101001001110110111111111111 5解 設(shè)p：他努力學(xué)習(xí)；q：他會通過考試。則命題符號化pq。其否定(pq) pq。 所以語句的否定：他學(xué)習(xí)很努力但沒有通過考試。 設(shè)p：水溫暖；q：他游泳。則命題符號化pq。其否定(pq) pq。 所以語句的否定：當(dāng)且僅當(dāng)水不溫暖時他游泳。 設(shè)p：天冷；q：他穿外套；r：他穿襯衫。則命題符號化p(qr) 其否定( p(qr) (p(qr) p( qr) p(q r) 所以語句的否定：天冷并且他不穿外套或者穿襯衫。 設(shè)p：他學(xué)習(xí)；q：他將上清華大學(xué)；r：他將上北京大學(xué)。則命題符號化其否定所以語句的否定：他努力學(xué)習(xí)，但是沒有上清華大學(xué)，也沒有上北京大學(xué)。 6解 設(shè)p：張三說真話；q：李四說真話；r：王五說真話。則：pq, qr(qr), r(pq)為真,因此p(pq)(ppq)(p(pq)pq為真。因此，p為假，q為真，所以r為假。故張三說謊，李四說真話，王五說謊。 7解 設(shè)p：甲得冠軍；q：乙得亞軍；r：丙得亞軍；s：丁得亞軍。前提：p(qr)，qp，sr，p結(jié)論：s證明 p(qr)為真，其前件p為真，所以qr為真，又qp為真，其后件p為假，所以要求q為假，所以r為真。又sr為真，其后件r為假，所以要求s為假，故s為真。習(xí)題2.4 1解 設(shè)p：明天下雨；q：后天下雨。命題符號化。 設(shè)p：明天我將去北京；q：明天我將去上海。命題符號化。 2解 3證明 因為，是功能完備聯(lián)結(jié)詞集，所以，含有外的其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含中的聯(lián)結(jié)詞的公式。又因為即含有的公式均可以轉(zhuǎn)換為僅含中的聯(lián)結(jié)詞的公式。因此，含外其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含中的聯(lián)結(jié)詞的公式。 故是功能完備聯(lián)結(jié)詞集。 4證明 是極小功能完備集，因而只需證明中的每個聯(lián)結(jié)詞都可以用 表示，就說明是功能完備集。只有一個聯(lián)結(jié)詞，自然是極小功能完備集。事實上，p(pp)pp，pq(pq)(pq)(pq)(pq)。對于證明是極小功能完備集，可類似證明。習(xí)題2.5 1解 ； 2解 即為其析取范式。即為其合取范式。即為其合取范式。p(qr)p(qr)(qr)(pqr)(pqr) 即為其析取范式。即為其合取范式。為其析取范式。即為其析取范式和合取范式。 3解 即為其主合取范式。其主析取范式為3pq。 。故其主析取范式為(0,1,2,3)=(pq)(pq)(pq)(pq)。 即為其主合取范式。其主析取范式為(2,4,5,6,7) (pqr)(pqr)(pqr)(pqr)(pqr)。 即為其主合取范式。其主析取范式為。 4解 真值表如表2-21所示, 所以其極小項是pq，極大項為pq，pq，pq。表2-21pq0010011010011110其主析取范式是：pq，主合取范式為：(pq)( pq)(pq)。 真值表如表2-222所示, 所以其極小項是pq, pq, pq, 極大項為pq。表2-22pq000100011101101011111101其主析取范式是：(pq)(pq)(pq)，主合取范式為：pq。 真值表如表2-23所示，所以其極小項是pqr,pqr, pqr, pqr,pqr,表2-23pqr000100001100010100011111100001101001110001111001極大項為pqr，pqr，pqr。其主析取范式是：(pqr)(pqr)(pqr)(pqr)(pqr)，主合取范式為：(pqr)(pqr)(pqr) 。 真值表如表2-24所示,所以其極小項為pqr,pqr,pqr,pqr,pqr,而極大項分為pqr，pqr，pqr.主合取范式為(pqr)(pqr)(pqr),主析取范式為(pqr)(pqr)(pqr,)(pqr)(pqr)。表2-24pqr00010001110101001111100011010111010111115解 (pq)(pq)(pq)(pq) q (pq)(pq)， 故為可滿足式。 故為重言式。(p(qr)(pq)(pr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)p(qr)(pqr)(qr)0。 故為矛盾式。 故僅為可滿足式。6證明 右邊已經(jīng)是主合取范式。而左邊主合取范式已是pq，因此，(p q)pq，證畢。右邊(p q)(pq)已經(jīng)是主合取范式。pp(qq) (p q)(pq)。因此，。左邊p(qr)p(qr)pqr，而右邊(pq)rpqr，因此，。習(xí)題2.61解 設(shè)p：這里有演出；q：這里通行是困難的；r：他們按照指定時間到達(dá)。前提：pq, rq,r結(jié)論：p證明 r Prq Pq T假言推理pq P p T拒取式2證明 s Psp P p T假言推理pq Pq T假言推理證明 r P附加前提引入rq Pq T假言推理pq Pp T拒取式ps Ps T假言推理rs TCP證明 p P否定結(jié)論引入pq Pq T假言推理qr Pr T假言推理rs Pr T化簡rr T合取證明 p P附加前提引入pq Pq 析取三段論rq Pr 拒取式pr CP證明 p P附加前提引入p(qr) Pqr T假言推理q P附加前提引入r T假言推理(rs)t Prst T蘊(yùn)涵等價式st T析取三段論h(st) Pst h T假言易位 h T假言推理 qh TCP13. p(qh) TCP 3解 推理不正確。在到化簡時，只能對整個公式進(jìn)行而不是子公式。 4解 正確。P，P附加前提引入；T析取三段論；P；T假言推理；P；T假言推理；TCP。 5解 設(shè)p：張三努力工作，q：李四高興，r：王五高興，s：劉六高興 前提：p(qr)，qp，sr 結(jié)論：ps 證明：p P附加前提引入p(qr) Pqr T假言推理qp Pq T拒取式r T析取三段論sr Ps T拒取式ps TCP 6解 設(shè)：p：天下雪；q：馬路結(jié)冰；r：汽車開得快；s：馬路塞車。前提：pq，qr，rs，s結(jié)論：p證明pq Pqr Ppr 推理三段論rs Pps 推理三段論s P p 拒取式復(fù)習(xí)題2 1解 設(shè)p：3是偶數(shù)，q：中國人的母語是漢語。命題符號化。 設(shè)p：你抽煙，q：你很容易得病。命題符號化。 設(shè)p：今天是星期一，q：明天才是星期二。命題符號化。 設(shè)p：李春這個學(xué)期離散數(shù)學(xué)考了100分。q：李春這個學(xué)期數(shù)據(jù)結(jié)構(gòu)考了100分。命題符號化。 設(shè)p：下雪路滑，q：他遲到了。命題符號化。 設(shè)p：經(jīng)一事，q：長一智。命題符號化。 設(shè)p：一朝被蛇咬，q：十年怕井繩。命題符號化。 設(shè)p：以物喜，q：以己悲。命題符號化。 2. 解 命題中的“或”是不可兼或，因此，可以直接用“”符號化；根據(jù)聯(lián)結(jié)詞的性質(zhì)及其之間的轉(zhuǎn)換關(guān)系，可知命題“李春生于1979年或生于1980年”的本意是“李春生于1979年（但不能生于1980年）或生于1980年（但不能生于1979年）”，因此，也可以轉(zhuǎn)化為“”對其進(jìn)行符號化。3解 設(shè)p：李剛會拳擊，q：李春會唱歌。命題符號化(pq)(pq)。而(pq)(pq)(pq)(pq)(pq)pqpq因此，李剛會拳擊并且李春不會唱歌。 4解 A的極小項對應(yīng)于其真值表中的成真賦值0001，0110，1000，1001，1010，1100，1101，1111。成真賦值對應(yīng)二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)就是A的極小項的下標(biāo)。由此可得，A的極小項為： ；。 相應(yīng)的，A的極大項對應(yīng)于其真值表中的成假賦值，成假賦值對應(yīng)二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)就是A的極大項的下標(biāo)。由此可得，A的極大項為： ；。 由問題得到了A的極小項和極大項，于是與A等值的主析取范式和主合取范式可以直接得到，分別為：；。 從A的主析取范式出發(fā)，進(jìn)行等值演算化簡，可得析取范式的最簡形式：(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(qrs)(pqr)(pqrs)(pqr)(pr)(pqrs)(qrs)(pqrs)(pr)(qrs)(qrs)(pqrs)(pr)(qrs)(qrs)(pqs) 5 證明 6解 公式的真值表如表2-27所示：表2-27p0011111011011110011001100010 從真值表可見，公式所在列的填入值有1也有0，故僅為可滿足式。(pq)(qp)(pq)(qp)(2,3)為其主合取范式，可見公式僅為可滿足式。 公式真值表如表2-28所示：表2-28pqr0000100111010110111110011101111101111111 p(pqr)ppqr1(0,1,2,3,4,5,6,7) 從真值表可見，公式所在的列的填入值均為1，等值演算，以及求出的主析取范式均說明公式是重言式。A=(pq)(qr)(pr)真值表見習(xí)題2.2第4(4)題。(pq)(qr)(pr)(pq)(qr)(pr)(pq)(qr)pr1. 從真值表可見，公式所在的列的填入值均為1，由等值演算，以及求出的主析取范式均說明公式是重言式。7證明 p P附加前提引入p(qr) Pqr T假言推理q P附加前提引入q(rs) Prs T假言推理qs T假言三段論p(qs) TCP證明 w Puw Pu T拒取式su Ps T析取三段論rs Pr T析取三段論(pq)r P(pq) T拒取式pq) T德摩根律證明 p P附加前提引入pqr Pqr T假言推理qp Pq T拒取式r T析取三段論sr Ps T拒取式ps TCP8解 pr Pp T化簡pq Pq T假言推理(qs) Pqs T德摩根律q T化簡qq T合取由得到矛盾，可見pq，(qs)，pr不能同時成立。9解 設(shè)p：小王曾經(jīng)到過受害人的房間，q：小王11點以前離開，r：小王犯了謀殺罪，s：看門人看到小王。符號化：(pq)r)p(qs