離散數學第1章習題課

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

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

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

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

5、要工具。,2024/3/18,計算機學院,5/24,,命題公式----（1）命題變元（原子命題變元）本身是一個公式；（2）如P，Q是公式，則(～P)、(P∧Q)、(P∨Q)、(P→Q)、(P?Q)也是公式；（3）命題公式僅由有限步使用規(guī)則1-2后產生的結果。該公式常用符號G、H、…等表示。公式的解釋----設P1、P2、…、Pn是出現(xiàn)在公式G中的所有命題變元，指定P1、P2、…、Pn的一組真值（如1，0，1，…，0，1），則這組

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

7、 在給定的僅使用聯(lián)結詞～ 、∨、∧的命題公式A中，若把∧和∨，F(xiàn)和T互換而得的公式A*，則稱A*為A的對偶（公）式。對偶原理----設A和B是兩個命題公式，若A ? B， 則 A* ? B*,2024/3/18,計算機學院,7/24,基本等價式——命題定律,設G，H，S是任何的公式，則：Ｅ1:(G? H)?(G→H)∧(H→G)(等價)Ｅ2：(G→H) ?(～G∨H) (蘊涵)Ｅ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 (結合律) Ｅ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,計算機學院,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,又叫標準型式,正

11、規(guī)型式。把公式進行標準化，正規(guī)化，就叫對公式求范式。 命題變元或命題變元的否定稱為句節(jié)。 有限個句節(jié)的析取式稱為子句； 有限個句節(jié)的合取式稱為短語。 有限個短語的析取式稱為析取范式； 有限個子句的合取式稱為合取范式。,2024/3/18,計算機學院,9/24,,極小項----在n個變元的基本積（短語）中，若每一個變元與其否定并不同時存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱這種基本積為極小項。主析取范式--

12、--由有限個極小項組成的析取式。極大項----在n個變元的基本和（子句）中，若每一個變元與其否定并不同時存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則這種基本和稱為極大項。主合取范式----由有限個極大項組成的合取式。命題公式的蘊涵----設A和B是兩個合適公式，如果在任何解釋下，A取值1時B也取值1，則稱公式A蘊涵公式B，并記A ?B。,2024/3/18,計算機學院,10/24,,基本蘊含（關系）式I1：P?P∨Q ， Q?P∨Q

13、 ～P?P→Q ， Q?P→Q 擴充法則(析取引入律)I2：P∧Q ?P ， P∧Q?Q ～（P→Q）?P ，～（P→Q）?～Q 化簡法則(合取消去律)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 歸結原理,2024/3/18,計算機學院,11/24,,命題邏輯的推理方法----設G是由一組命題公式組成的集合，如果存在命題公式的有限序列： H1，H2，……，Hn（=H） 其中，Hi或者是G中的某個公式，或者是前面

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

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

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

18、則可用公式： （～Ｐ∨Ｐ）∧Q=Q將命題變元P補進去，并利用分配律展開，然后合并相同的短語，此時得到的短語將是標準的極小項；（7）若合取范式的某一個子句中缺少該命題公式中所規(guī)定的命題變元，則可用公式： （～Ｐ∧Ｐ）∨Q=Q將命題變元P補進去，并利用分配律展開，然后合并相同的子句，此時得到的子句將是標準的極大項。（8）利用冪等律將相同的極小項和極大項合并，同時利用交換律進行順序調整，由此可轉換成標準

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

20、的是原子的否定，則原子賦值為1。 （3）求出使公式取值1時的解釋所對應的全部極小項 極小項取值1 “當且僅當”：如果極小項中出現(xiàn)的是原子本身，則原子賦值為1；如果出現(xiàn)的是原子的否定，則原子賦值為0。3、推理的各種方法（1）直接法（2）利用CP規(guī)則（3）反證法,2024/3/18,計算機學院,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,計算機學院,16/24,,2、 G=～(Ｐ→Ｑ)∨Ｒ，求主析取和主合取范式。解：首先列出其真值表如下：,,,極大

22、項,極小項,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,計算機學院,17/24,,3、用公式轉換法求上題中的主析取和主合取范式～(Ｐ→

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,計算機學院,18/24,,4、P25 14解：根據給定的條件有下述命題公式：（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,計算機學院,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,計算機學院,20/24,,5、P25 18解：根據給定的條件有下述命題：P：珍寶藏在東廂房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏樹S：珍寶藏在花園正中地下T：后院栽有香樟樹M：珍寶藏在附近根據題意，得出：（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T

29、→M） ?？,2024/3/18,計算機學院,21/24,,5、P25 18解：根據給定的條件有下述命題：P：珍寶藏在東廂房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏樹S：珍寶藏在花園正中地下T：后院栽有香樟樹M：珍寶藏在附近根據題意，得出：（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,計算機學院,22/24,,6、P25 21（2）解：根據給定的條件有下述命題：P：現(xiàn)場無任何痕跡Q：失竊時，小花在OK廳R：失竊時，小英在OK廳S：失竊時，小胖在附近T：金剛是偷竊者M：瘦子是偷竊者則根據案情有如下命題公式：{P，Q∨R，S→ ～ P，Q→ T，～ S→ ～ R，R→ M},2024/3/18,計算機學院,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