離散數(shù)學(xué)第1章習(xí)題課

1、陳瑜,Email：chenyu.inbox@gmail.com2024年3月18日星期一,離散　　數(shù)學(xué),計(jì)算機(jī)學(xué)院,2024/3/18,計(jì)算機(jī)學(xué)院,2/24,第一章小結(jié),一、基本概念命題----具有確切真值的陳述句稱為命題,該命題可以取一個(gè)“值”，稱為真值。命題的解釋----用一個(gè)具體的命題代入命題標(biāo)識(shí)符P的過程,稱為對(duì)P的解釋或賦值(指派)原子命題、復(fù)合命題邏輯聯(lián)結(jié)詞（～、∨、∧、?、→、?、與非↑、或非↓、條件否定 c

2、 ）：（1）聯(lián)結(jié)詞“～”是自然語(yǔ)言中的“非”、“不”和“沒有”等的邏輯抽象；（2）聯(lián)結(jié)詞“∧”是自然語(yǔ)言中的“并且”、“既…又…”、“但”、“和”等的邏輯抽象；（3）聯(lián)結(jié)詞“∨”是自然語(yǔ)言中的“或”、“或者”等邏輯抽象；但“或”有“可兼或∨”、“不可兼或?”、“近似或”三種，前兩種是聯(lián)結(jié)詞，后一種是非聯(lián)結(jié)詞；,,2024/3/18,計(jì)算機(jī)學(xué)院,3/24,,（4）聯(lián)結(jié)詞“→”是自然語(yǔ)言中的“如果…，則…”，“若…，才能…”、“除非…

3、，否則…”等的邏輯抽象。在自然語(yǔ)言中，前件為假，不管結(jié)論真假，整個(gè)語(yǔ)句的意義，往往無法判斷。但在數(shù)理邏輯中，當(dāng)前件P為假時(shí)，不管Q的真假如何，則P→Q都為真。此時(shí)稱為“善意推定”；這里要特別提醒一下“→”的含義，在自然語(yǔ)言中，條件式中前提和結(jié)論間必含有某種因果關(guān)系，但在數(shù)理邏輯中可以允許兩者無必然因果關(guān)系，也就是說并不要求前件和后件有什么聯(lián)系；（5）雙條件聯(lián)結(jié)詞“?”是自然語(yǔ)言中的“充分必要條件”、“當(dāng)且僅當(dāng)”等的邏輯抽象；,2024

4、/3/18,計(jì)算機(jī)學(xué)院,4/24,,（6）聯(lián)結(jié)詞連接的是兩個(gè)命題真值之間的聯(lián)結(jié)，而不是命題內(nèi)容之間的連接，因此復(fù)合命題的真值只取決于構(gòu)成他們的各原子命題的真值，而與它們的內(nèi)容、含義無關(guān)，與聯(lián)結(jié)詞所連接的兩原子命題之間是否有關(guān)系無關(guān)；（7）聯(lián)結(jié)詞“∧”、“∨”、“?”具有對(duì)稱性，而聯(lián)結(jié)詞“～”、“→”沒有；（8）聯(lián)結(jié)詞“∧”、“∨”、“～”同構(gòu)成計(jì)算機(jī)的與門、或門和非門電路是相對(duì)應(yīng)的，從而命題邏輯是計(jì)算機(jī)硬件電路的表示、分析和設(shè)計(jì)的重

5、要工具。,2024/3/18,計(jì)算機(jī)學(xué)院,5/24,,命題公式----（1）命題變?cè)ㄔ用}變?cè)┍旧硎且粋€(gè)公式；（2）如P，Q是公式，則(～P)、(P∧Q)、(P∨Q)、(P→Q)、(P?Q)也是公式；（3）命題公式僅由有限步使用規(guī)則1-2后產(chǎn)生的結(jié)果。該公式常用符號(hào)G、H、…等表示。公式的解釋----設(shè)P1、P2、…、Pn是出現(xiàn)在公式G中的所有命題變?cè)?，指定P1、P2、…、Pn的一組真值（如1，0，1，…，0，1），則這組

6、真值稱為G的一個(gè)解釋,常記為Ｉ。,2024/3/18,計(jì)算機(jī)學(xué)院,6/24,,永真式(重言式)永假式(矛盾式，不可滿足公式)可滿足的命題公式的等價(jià)----設(shè)G、H是公式，如果在任意解釋Ｉ下，G與H的真值相同，則稱公式G、H是等價(jià)的 ，記作G?H。替換定理----設(shè)G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命題公式，在G中凡出現(xiàn)G1處都以H1替換后得到新的命題公式H，若G1 ? H1，則G ? H。對(duì)偶式----

7、 在給定的僅使用聯(lián)結(jié)詞～ 、∨、∧的命題公式A中，若把∧和∨，F(xiàn)和T互換而得的公式A*，則稱A*為A的對(duì)偶（公）式。對(duì)偶原理----設(shè)A和B是兩個(gè)命題公式，若A ? B， 則 A* ? B*,2024/3/18,計(jì)算機(jī)學(xué)院,7/24,基本等價(jià)式——命題定律,設(shè)G，H，S是任何的公式，則：Ｅ1:(G? H)?(G→H)∧(H→G)(等價(jià))Ｅ2：(G→H) ?(～G∨H) (蘊(yùn)涵)Ｅ3：G∨G ?

8、G (冪等律) Ｅ4：G∧G ? GＥ5：G∨H ? H∨G (交換律) Ｅ6：G∧H ? H∧GＥ7：G∨(H∨S) ?(G∨H)∨S (結(jié)合律) Ｅ8: G∧(H∧S) ?(G∧H)∧SＥ9：G∨(G∧H) ? G (吸收律) Ｅ10：G∧(G∨H) ? G Ｅ11：G∨(H∧S) ?(G∨H)∧(G∨S) (分配律) Ｅ12

9、：G∧(H∨S) ?(G∧H)∨(G∧S)Ｅ13：G∨F ? G (同一律) Ｅ14：G∧T? G,2024/3/18,計(jì)算機(jī)學(xué)院,8/24,,Ｅ15：G∨T? T(零律) Ｅ16：G∧F? F Ｅ17：G∨～G ? T (矛盾律)Ｅ18：G∧～G ? FＥ19：～ (～G) ? G

10、 (雙重否定律)Ｅ20：（G∧H)→S ? G→（H→S） （輸出律）√Ｅ21：（G?H）?(～G∧H)∨(G∧～H) (排中律)Ｅ22：P→Q ? ～Q→～P （逆反律）√Ｅ23：～ (G∨H) ? ～G∧～H (De Morgan定律) Ｅ24：～ (G∧H) ? ～G∨～H。范式——全名叫規(guī)范型式normal form,又叫標(biāo)準(zhǔn)型式,正

11、規(guī)型式。把公式進(jìn)行標(biāo)準(zhǔn)化，正規(guī)化，就叫對(duì)公式求范式。 命題變?cè)蛎}變?cè)姆穸ǚQ為句節(jié)。 有限個(gè)句節(jié)的析取式稱為子句； 有限個(gè)句節(jié)的合取式稱為短語(yǔ)。 有限個(gè)短語(yǔ)的析取式稱為析取范式； 有限個(gè)子句的合取式稱為合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,9/24,,極小項(xiàng)----在n個(gè)變?cè)幕痉e（短語(yǔ)）中，若每一個(gè)變?cè)c其否定并不同時(shí)存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱這種基本積為極小項(xiàng)。主析取范式--

12、--由有限個(gè)極小項(xiàng)組成的析取式。極大項(xiàng)----在n個(gè)變?cè)幕竞停ㄗ泳洌┲?，若每一個(gè)變?cè)c其否定并不同時(shí)存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則這種基本和稱為極大項(xiàng)。主合取范式----由有限個(gè)極大項(xiàng)組成的合取式。命題公式的蘊(yùn)涵----設(shè)A和B是兩個(gè)合適公式，如果在任何解釋下，A取值1時(shí)B也取值1，則稱公式A蘊(yùn)涵公式B，并記A ?B。,2024/3/18,計(jì)算機(jī)學(xué)院,10/24,,基本蘊(yùn)含（關(guān)系）式I1：P?P∨Q ， Q?P∨Q

13、 ～P?P→Q ， Q?P→Q 擴(kuò)充法則(析取引入律)I2：P∧Q ?P ， P∧Q?Q ～（P→Q）?P ，～（P→Q）?～Q 化簡(jiǎn)法則(合取消去律)I3：P∧（P→Q）? Q 假言推論（分離規(guī)則）I4：～Q∧（P→Q）? ～P 否定式假言推論（拒取式）I5：～P∧（P∨Q）? Q 析取三段論（選言三段論）I6：（P→Q）∧（Q→R）? P→R 假言（前提條件）三段論I7：（P∨Q

14、）∧（P→R）∧（Q→R）? R 二難推論I8：（P→Q）∧（R→S）?（P∧R）→（Q∧S）I9：（P?Q）∧（Q?R）? P?RI10：（P∨Q）∧（～P∨R）? Q∨R 歸結(jié)原理,2024/3/18,計(jì)算機(jī)學(xué)院,11/24,,命題邏輯的推理方法----設(shè)G是由一組命題公式組成的集合，如果存在命題公式的有限序列： H1，H2，……，Hn（=H） 其中，Hi或者是G中的某個(gè)公式，或者是前面

15、的某些Hj（j<i）的有效結(jié)論，并且Hn就是H，則稱公式H是G的邏輯結(jié)果（有效結(jié)論），或者稱由G演繹出結(jié)論H來。推理規(guī)則----① P規(guī)則（稱為前提引用規(guī)則）：在推導(dǎo)的過程中，可隨時(shí)引入前提集合中的任意一個(gè)前提；② Ｔ規(guī)則（邏輯結(jié)果引用規(guī)則）：在推導(dǎo)的過程中，利用基本等價(jià)式和蘊(yùn)涵式，由證明過程中某些中間公式變換出新的公式，若依據(jù)的是等價(jià)式，規(guī)則標(biāo)明為TE，若依據(jù)的是蘊(yùn)涵式，規(guī)則標(biāo)明為TI 。③ ＣＰ規(guī)則（附加前提規(guī)則）：如

16、果能從給定的前提集合G與公式P推導(dǎo)出S，則能從此前提集合G推導(dǎo)出P→S。 即G1,G2,…,Gn? P→S 當(dāng)且僅當(dāng) G1,G2,…,Gn，P? S,2024/3/18,計(jì)算機(jī)學(xué)院,12/24,,二、基本方法1、應(yīng)用基本等價(jià)式及置換規(guī)則進(jìn)行等價(jià)演算2、求主析?。ㄖ骱先。┓妒降姆椒ü睫D(zhuǎn)換法（1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的→、?用聯(lián)結(jié)詞～、∧、∨來取代；（2）利用德?摩根定律將否定號(hào)～移到各個(gè)命題變

17、元的前端；（3）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范式和合取范式。（4）在析取范式的短語(yǔ)和合取范式的子句中，如同一命題變?cè)霈F(xiàn)多次，則將其化成只出現(xiàn)一次。（5）去掉析取范式中所有永假式的短語(yǔ)和合取范式中所有永真式的子句，即去掉短語(yǔ)中含有形如P∧～P的子公式和子句中含有形如P∨～P的子公式。,2024/3/18,計(jì)算機(jī)學(xué)院,13/24,,（6）若析取范式的某一個(gè)短語(yǔ)中缺少該命題公式中所規(guī)定的命題變?cè)?/p>

18、則可用公式： （～Ｐ∨Ｐ）∧Q=Q將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的短語(yǔ)，此時(shí)得到的短語(yǔ)將是標(biāo)準(zhǔn)的極小項(xiàng)；（7）若合取范式的某一個(gè)子句中缺少該命題公式中所規(guī)定的命題變?cè)?，則可用公式： （～Ｐ∧Ｐ）∨Q=Q將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的子句，此時(shí)得到的子句將是標(biāo)準(zhǔn)的極大項(xiàng)。（8）利用冪等律將相同的極小項(xiàng)和極大項(xiàng)合并，同時(shí)利用交換律進(jìn)行順序調(diào)整，由此可轉(zhuǎn)換成標(biāo)準(zhǔn)

19、的主析取范式和主合取范式。 真值表技術(shù)法主合取范式----在命題公式的真值表中，使公式取值0時(shí)的解釋所對(duì)應(yīng)的全部極大項(xiàng)的合取式。主析取范式----在命題公式的真值表中，使公式取值1時(shí)的解釋所對(duì)應(yīng)的全部極小項(xiàng)的析取式。,2024/3/18,計(jì)算機(jī)學(xué)院,14/24,,（1）求出公式的真值表（2）求出使公式取值0時(shí)的解釋所對(duì)應(yīng)的全部極大項(xiàng) 極大項(xiàng)取值0“當(dāng)且僅當(dāng)”：如果極大項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為0；如果出現(xiàn)

20、的是原子的否定，則原子賦值為1。 （3）求出使公式取值1時(shí)的解釋所對(duì)應(yīng)的全部極小項(xiàng) 極小項(xiàng)取值1 “當(dāng)且僅當(dāng)”：如果極小項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為1；如果出現(xiàn)的是原子的否定，則原子賦值為0。3、推理的各種方法（1）直接法（2）利用CP規(guī)則（3）反證法,2024/3/18,計(jì)算機(jī)學(xué)院,15/24,,三、典型例題1、證明 ((P∨Q) ∧～(P∧Q)) ?～(P?Q)((P∨Q)∧～(P∧Q))

21、? ((P∨Q)∧(～P∨～Q)) ?((P∨Q)～P)∨ ((P∨Q)∧～Q)) ?((P∧～P)∨(Q∧～P))∨((P∧～Q)∨(Q∧～Q))? (Q∧～P)∨(P∧～Q)? (Q∧～P)∨(P∧～Q)? ～(～Q∨P)∨～(～P∨Q)?～((Q→P)∧～(P→Q))?～(P?Q),2024/3/18,計(jì)算機(jī)學(xué)院,16/24,,2、 G=～(Ｐ→Ｑ)∨Ｒ，求主析取和主合取范式。解：首先列出其真值表如下：,,,極大

22、項(xiàng),極小項(xiàng),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）,2024/3/18,計(jì)算機(jī)學(xué)院,17/24,,3、用公式轉(zhuǎn)換法求上題中的主析取和主合取范式～(Ｐ→

23、Ｑ)∨Ｒ?～（～P∨Q）∨R ?（P∧～Q）∨R?（P∨R）∧（～Q∨R）?（P∨R∨（～Q∧Q））∧（～Q∨R∨（～P∧P））?（P∨R∨～Q）∧（P∨R∨Q）∧（～Q∨R∨～P）∧（～Q∨R∨P）?（P∨R∨～Q）∧（P∨R∨Q）∧（～Q∨R∨～P） （主合取范式）～(Ｐ→Ｑ)∨Ｒ?～（～P∨Q）∨R ?（P∧～Q）∨R?（P∧～Q∧（R∨～R））∨（R∧（P∨～P）∧（Q∨～Q））?（P∧～Q∧R）∨（P∧～Q∧～

24、R））∨（R∧P）∨（R∧～P）?（P∧～Q∧R）∨（P∧～Q∧～R））∨（R∧P∧（Q∨～Q）） ∨（R∧～P∧（Q∨～Q））?（P∧～Q∧R）∨（P∧～Q∧～R）∨（R∧P∧Q） ∨ （R∧P∧～Q）∨（R∧～P∧Q）∨（R∧～P∧～Q）,（主析取范式）,2024/3/18,計(jì)算機(jī)學(xué)院,18/24,,4、P25 14解：根據(jù)給定的條件有下述命題公式：（A→（C?D））∧～（B∧C）∧～（C∧D）?（～A

25、∨（C∧～D）∨（～C∧D））∧（～B∨～C）∧（～C∨～D）?（（～A∧～B）∨（C∧～D∧～B）∨（～C∧D∧～B）∨ （～A∧～C）∨（C∧～D∧～C）∨（～C∧D∧～C））∧（～C∨～D）?（（～A∧～B）∨（C∧～D∧～B）∨（～C∧D∧～B）∨ （～A∧～C）∨（～C∧D∧～C）） ∧（～C∨～D）?（～A∧～B∧～C）∨（C∧～D∧～B∧～C）∨（～C∧D∧～B∧～C）∨（～A∧～C∧～C）∨（～C∧D

26、∧～C∧～C）∨（～A∧～B∧～D）∨（C∧～D∧～B∧～D）∨（～C∧D∧～B∧～D）∨（～A∧～C∧～D）∨（～C∧D∧～C∧～D）（由題意和矛盾律）,2024/3/18,計(jì)算機(jī)學(xué)院,19/24,,?（～C∧D∧～B）∨（～A∧～C）∨（～C∧D）∨（C∧～D∧～B）?（～C∧D∧～B∧A）∨ （～C∧D∧～B∧～A）∨ （～A∧～C∧B）∨ （～A∧～C∧～B）∨ （～C∧D∧A）∨ （～C∧D∧～A）∨（C∧～D∧～B∧A）∨

27、（C∧～D∧～B∧～A）?（～C∧D∧～B∧A）∨ （～A∧～C∧B∧D）∨ （～A∧～C∧B∧～D）∨ （～A∧～C∧～B∧D）∨ （～A∧～C∧～B∧～D）∨ （～C∧D∧A∧B）∨ （～C∧D∧A∧～B）∨ （～C∧D∧～A∧B）∨ （～C∧D∧～A∧～B）∨（C∧～D∧～B∧A）∨（C∧～D∧～B∧～A）?（～C∧D∧～B∧A）∨ （～A∧～C∧B∧D）∨ （～C∧D∧A∧～B）∨ （～C∧D∧～A∧B） ∨（C

28、∧～D∧～B∧A）?（～C∧D∧～B∧A）∨ （～A∧～C∧B∧D）∨（C∧～D∧～B∧A）所以，共有三種選派方案：A和C，A和D，B和D,2024/3/18,計(jì)算機(jī)學(xué)院,20/24,,5、P25 18解：根據(jù)給定的條件有下述命題：P：珍寶藏在東廂房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏樹S：珍寶藏在花園正中地下T：后院栽有香樟樹M：珍寶藏在附近根據(jù)題意，得出：（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T

29、→M） ?？,2024/3/18,計(jì)算機(jī)學(xué)院,21/24,,5、P25 18解：根據(jù)給定的條件有下述命題：P：珍寶藏在東廂房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏樹S：珍寶藏在花園正中地下T：后院栽有香樟樹M：珍寶藏在附近根據(jù)題意，得出：（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M） ?？,（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M） ～P∧（R→P）∧（R∨S）∧（T→M） ?～R∧（R∨S

30、）∧（T→M） ?S∧（T→M）?S 即珍寶藏在花園正中地下,2024/3/18,計(jì)算機(jī)學(xué)院,22/24,,6、P25 21（2）解：根據(jù)給定的條件有下述命題：P：現(xiàn)場(chǎng)無任何痕跡Q：失竊時(shí)，小花在OK廳R：失竊時(shí)，小英在OK廳S：失竊時(shí)，小胖在附近T：金剛是偷竊者M(jìn)：瘦子是偷竊者則根據(jù)案情有如下命題公式：{P，Q∨R，S→ ～ P，Q→ T，～ S→ ～ R，R→ M},2024/3/18,計(jì)算機(jī)學(xué)院,23

31、/24,{P，Q∨R，S→ ～ P，Q→ T，～ S→ ～ R，R→ M},6、P25 21（2）解： P P S→～P P ～S T①②I ～S→～R P ～R T③④I Q∨R