離散數學(第1章習題課)

1、2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院1 1陳瑜陳瑜Email：2022-3-282022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院2 2第一章小結第一章小結一、基本概念一、基本概念命題命題-具有具有確切真值確切真值的陳述句稱為命題的陳述句稱為命題, ,該命題可以取一個該命題可以取一個“值值”，稱為真值。稱為真值。命題的解釋命題的解釋-用一個具體的命題代入命題標識符用一個具體的命題代入命題標識符P P的過程的過程, ,稱為對稱為對P P的解釋或賦值的解釋或賦值( (指派指派) )原子命題、復合命題原子命題、復合命題邏輯聯結詞邏輯聯

2、結詞（、（、 、與非與非、或非、或非、條件否定、條件否定 c c ）：（1 1）聯結詞）聯結詞“”是自然語言中的是自然語言中的“非非”、“不不”和和“沒有沒有”等的邏等的邏輯抽象；輯抽象；（2 2）聯結詞）聯結詞“”是自然語言中的是自然語言中的“并且并且”、“既既又又”、“但但”、“和和”等的邏輯抽象；等的邏輯抽象；（3 3）聯結詞）聯結詞“”是自然語言中的是自然語言中的“或或”、“或者或者”等邏輯抽象；但等邏輯抽象；但“或或”有有“可兼或可兼或”、“不可兼或不可兼或 ”、“近似或近似或”三種，前兩三種，前兩種是聯結詞，后一種是非聯結詞；種是聯結詞，后一種是非聯結詞；2022-3-282022

3、-3-28計算機科學與工程學院計算機科學與工程學院3 3（4 4）聯結詞）聯結詞“”是自然語言中的是自然語言中的“如果如果，則，則”，“若若，才能，才能”、“除非除非，否則，否則”等的邏輯抽等的邏輯抽象。在自然語言中，前件為假，不管結論真假，整個象。在自然語言中，前件為假，不管結論真假，整個語句的意義，往往無法判斷。但在數理邏輯中，當前語句的意義，往往無法判斷。但在數理邏輯中，當前件件P P為假時，不管為假時，不管Q Q的真假如何，則的真假如何，則PQPQ都為真。此時都為真。此時稱為稱為“善意推定善意推定”；這里要特別提醒一下；這里要特別提醒一下“”的含的含義，在自然語言中，條件式中前提和結論

4、間必含有某義，在自然語言中，條件式中前提和結論間必含有某種因果關系，但在數理邏輯中可以允許種因果關系，但在數理邏輯中可以允許兩者無必然因兩者無必然因果關系果關系，也就是說，也就是說并不要求前件和后件有什么聯系并不要求前件和后件有什么聯系；（5 5）雙條件聯結詞）雙條件聯結詞“”是自然語言中的是自然語言中的“充分必要條充分必要條件件”、“當且僅當當且僅當”等的邏輯抽象；等的邏輯抽象；2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院4 4（6 6）聯結詞連接的是聯結詞連接的是兩個命題真值兩個命題真值之間的聯結，而不是之間的聯結，而不是命題內容命題內容之間的連接，因此復合

5、命題的真值只取決于之間的連接，因此復合命題的真值只取決于構成他們的各原子命題的真值，而與它們的內容、含構成他們的各原子命題的真值，而與它們的內容、含義無關，與聯結詞所連接的兩原子命題之間是否有關義無關，與聯結詞所連接的兩原子命題之間是否有關系無關；系無關；（7 7）聯結詞）聯結詞“”、“”、“”具有對稱性，而聯具有對稱性，而聯結詞結詞“”、“”沒有；沒有；（8 8）聯結詞）聯結詞“”、“”、“”同構成計算機的與同構成計算機的與門、或門和非門電路是相對應的，從而命題邏輯是計門、或門和非門電路是相對應的，從而命題邏輯是計算機硬件電路的表示、分析和設計的重要工具。算機硬件電路的表示、分析和設計的重要

6、工具。2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院5 5命題公式命題公式-（1 1）命題變元（）命題變元（原子命題變元原子命題變元）本身是一個公式；）本身是一個公式；（2 2）如）如P P，Q Q是公式，則是公式，則( (P)P)、(PQ)(PQ)、(PQ)(PQ)、(PQ)(PQ)、(P(PQ)Q)也是公式；也是公式；（3 3）命題公式命題公式僅由僅由有限步有限步使用規(guī)則使用規(guī)則1-21-2后產生的結果。后產生的結果。該公式常用符號該公式常用符號G G、H H、等表示。等表示。公式的解釋公式的解釋-設設P P1 1、P P2 2、P Pn n是出現在公式是出現

7、在公式G G中的所中的所有命題變元有命題變元，指定指定P P1 1、P P2 2、P Pn n的的一組真值（如一組真值（如1 1，0 0，1 1，0 0，1 1），則這組真值稱為），則這組真值稱為G G的一個的一個解釋解釋, ,常常記為記為。2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院6 6永真式永真式( (重言式重言式) )永假式永假式( (矛盾式，不可滿足公式矛盾式，不可滿足公式) )可滿足的可滿足的命題公式的等價命題公式的等價-設設G G、H H是是公式，公式，如果在如果在任意解釋任意解釋下，下，G G與與H H的的真值相同，則稱公式真值相同，則稱公式G

8、G、H H是是等價的等價的 ，記作記作G GH H。替換定理替換定理-設設G G1 1是是G G的子公式的子公式( (即即 G G1 1是公式是公式G G的一部分的一部分) )，H H1 1是任意是任意的命題公式，在的命題公式，在G G中凡出現中凡出現G G1 1處都以處都以H H1 1替換后得到新的命題公式替換后得到新的命題公式H H，若若G G1 1 H H1 1，則則G G H H。對偶式對偶式- - 在給定的僅使用聯結詞在給定的僅使用聯結詞 、的命題公式的命題公式A A中，若中，若把把和和，F F和和T T互換而得的公式互換而得的公式A A* *，則稱，則稱A A* *為為A A的對偶

9、（公）式的對偶（公）式。對偶原理對偶原理-設設A A和和B B是兩個命題公式，若是兩個命題公式，若A A B B， 則則 A A* * B B* *2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院7 7基本等價式基本等價式命題定律命題定律 設設G G，H H，S S是任何的公式，則：是任何的公式，則：1:1:(G(G H) H)(GH)(HG)(GH)(HG)( (等價等價) )2 2：(GH) (GH) ( (GH) GH) ( (蘊涵蘊涵) )3 3：GG GG G G ( (冪等律冪等律) ) 4 4：GG GG G G5 5：GH GH HG HG ( (交

10、換律交換律) ) 6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S (GH)S ( (結合律結合律) ) 8:8: G(HS) G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 1111：G(HS) G(HS) (GH)(GS) (GH)(GS) (分配律分配律) ) 1212：G(HS) G(HS) (GH)(GS)(GH)(GS)1313：GF GF G G ( (同一律同一律) ) 1414：GTGT G G2022-3-282022-3-28計算機科學與工程學院計算機科學與工

11、程學院8 81515：GTGT T T( (零律零律) ) 1616：GFGF F F 1717：GGG G T T ( (矛盾律矛盾律) )1818：GGG G F F1919： ( (G) G) G G ( (雙重否定律雙重否定律) )2020：（GH)S GH)S G G（HSHS） （輸出律）（輸出律）2121：（G G H H）( (GH)(GGH)(GH) H) ( (排中律排中律) )2222：PQ PQ QQP P （逆反律）（逆反律）2323： (GH) (GH) GGH (De MorganH (De Morgan定律定律) ) 2424： (GH) (GH) GGH H。

12、范式范式全名叫規(guī)范型式全名叫規(guī)范型式normal form,normal form,又叫標準型式又叫標準型式, ,正規(guī)型正規(guī)型式。式。把公式進行標準化，正規(guī)化，就叫對公式求范式。把公式進行標準化，正規(guī)化，就叫對公式求范式。 命題變元或命題變元的命題變元或命題變元的否定否定稱為稱為句節(jié)句節(jié)。 有限個有限個句節(jié)句節(jié)的的析取式析取式稱為稱為子句子句； 有限個有限個句節(jié)句節(jié)的的合取式合取式稱為稱為短語短語。 有限個有限個短語短語的的析取式析取式稱為稱為析取范式析取范式； 有限個有限個子句子句的的合取式合取式稱為稱為合取范式合取范式。2022-3-282022-3-28計算機科學與工程學院計算機科學與工

13、程學院9 9 極小項極小項-在在n n個變元的基本積（個變元的基本積（短語短語）中，若每一個）中，若每一個變元與其否定變元與其否定并不同時存在并不同時存在，且，且二者之一必出現且僅二者之一必出現且僅出現一次出現一次，則稱這種基本積為，則稱這種基本積為極小項極小項。 主析取范式主析取范式-由有限個極小項組成的析取式由有限個極小項組成的析取式。 極大項極大項-在在n n個變元的基本和（個變元的基本和（子句子句）中，若每一個）中，若每一個變元與其否定變元與其否定并不同時存在并不同時存在，且，且二者之一必出現且僅二者之一必出現且僅出現一次出現一次，則這種基本和稱為，則這種基本和稱為極大項極大項。 主合

14、取范式主合取范式-由有限個極大項組成的合取式由有限個極大項組成的合取式。 命題公式的蘊涵命題公式的蘊涵-設設A A和和B B是兩個合適公式，如果在是兩個合適公式，如果在任何解釋任何解釋下，下，A A取值取值1 1時時B B也取值也取值1 1，則稱公式，則稱公式A A蘊涵公式蘊涵公式B B，并記，并記A A B B。2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院1010 基本蘊含（關系）式基本蘊含（關系）式I I1 1：P PPQ PQ ， Q QPQ PQ P PPQ PQ ， Q QPQ PQ 擴充法則擴充法則( (析取引入律析取引入律) )I I2 2：PQ

15、PQ P P ， PQPQQ Q （PQPQ）P P ，（，（PQPQ）Q Q 化簡化簡法則法則( (合取消去律合取消去律) )I I3 3：P P（PQPQ） Q Q 假言推論（分離規(guī)則）假言推論（分離規(guī)則）I I4 4：Q Q（PQPQ） P P 否定式假言推論（拒取式）否定式假言推論（拒取式）I I5 5：PP（PQPQ） Q Q 析取三段論（選言三段論）析取三段論（選言三段論）I I6 6：（：（PQPQ）（QRQR） PR PR 假言（前提條件）三段論假言（前提條件）三段論I I7 7：（：（PQPQ）（PRPR）（QRQR） R R 二難推論二難推論I I8 8：（：（PQPQ）（

16、RSRS）（PRPR）（QSQS）I I9 9：（：（P PQ Q）（Q QR R） P PR RI I1010：（：（PQPQ）（PRPR） QR QR 歸結原理歸結原理2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院1111 命題邏輯的推理方法命題邏輯的推理方法-設設G G是由一組命題公式組成的集合，如果存在命題公式的有限序列：是由一組命題公式組成的集合，如果存在命題公式的有限序列： H1H1，H2H2，HnHn（=H=H） 其中，其中，HiHi或者是或者是G G中的某個公式，或者是前面的某些中的某個公式，或者是前面的某些HjHj（jiji）的有）的有效結論，并

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

18、式，規(guī)則標明為價式，規(guī)則標明為TETE，若依據的是蘊涵式，規(guī)則標明為，若依據的是蘊涵式，規(guī)則標明為TI TI 。 規(guī)則（附加前提規(guī)則）：規(guī)則（附加前提規(guī)則）：如果能從給定的前提集合如果能從給定的前提集合G G與公式與公式P P推推導出導出S S，則能從此前提集合，則能從此前提集合G G推導出推導出PSPS。 即即G G1 1,G,G2 2,G,Gn n PS PS 當且僅當當且僅當 G G1 1,G,G2 2,G,Gn n，P P S S2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院1212 二、基本方法二、基本方法 1、應用基本等價式及置換規(guī)則進行等價演算應用基

19、本等價式及置換規(guī)則進行等價演算 2 2、求主析取（主合?。┓妒降姆椒ㄇ笾魑鋈。ㄖ骱先。┓妒降姆椒?公式轉換法公式轉換法（1 1）利用等價公式中的等價式和蘊涵式將公式中的）利用等價公式中的等價式和蘊涵式將公式中的、用聯用聯結詞結詞、來取代；來取代；（2 2）利用德）利用德 摩根定律將否定號摩根定律將否定號移到各個命題變元的前端；移到各個命題變元的前端；（3 3）利用結合律、分配律、吸收律、冪等律、交換律等將公式）利用結合律、分配律、吸收律、冪等律、交換律等將公式化成其等價的析取范式和合取范式。化成其等價的析取范式和合取范式。（4 4）在析取范式的短語和合取范式的子句中，如同一命題變元在析取范式的

20、短語和合取范式的子句中，如同一命題變元出現多次，則將其化成只出現一次。出現多次，則將其化成只出現一次。（5 5）去掉析取范式中所有永假式的短語和合取范式中所有永真去掉析取范式中所有永假式的短語和合取范式中所有永真式的子句，即去掉短語中含有形如式的子句，即去掉短語中含有形如PPP P的子公式和子句中含有的子公式和子句中含有形如形如PPP P的子公式。的子公式。2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院1313（6 6）若析取范式的某一個短語中缺少該命題公式中所規(guī)定的命題）若析取范式的某一個短語中缺少該命題公式中所規(guī)定的命題變元，則可用公式：變元，則可用公式： （

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

22、交換律）利用冪等律將相同的極小項和極大項合并，同時利用交換律進行順序調整，由此可轉換成標準的主析取范式和主合取范式。進行順序調整，由此可轉換成標準的主析取范式和主合取范式。 真值表技術法真值表技術法主合取范式主合取范式-在命題公式的真值表中，使公式取值在命題公式的真值表中，使公式取值0 0時的解釋所時的解釋所對應的對應的全部極大項的合取式全部極大項的合取式。主析取范式主析取范式-在命題公式的真值表中，使公式取值在命題公式的真值表中，使公式取值1 1時的解釋所時的解釋所對應的對應的全部極小項的析取式全部極小項的析取式。2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院1

23、414（1 1）求出公式的）求出公式的真值表真值表（2）求出求出使公式取值使公式取值0 0時的解釋所對應的時的解釋所對應的全部極大項全部極大項 極大項取值極大項取值0“0“當且僅當當且僅當”：如果極大項中出現的是原子本：如果極大項中出現的是原子本身，則原子賦值為身，則原子賦值為0 0；如果出現的是原子的否定，則原子賦值為；如果出現的是原子的否定，則原子賦值為1 1。 （3 3）求出使公式取值）求出使公式取值1 1時的解釋所對應的時的解釋所對應的全部極小項全部極小項 極小項取值極小項取值1 “1 “當且僅當當且僅當”：如果極小項中出現的是原子：如果極小項中出現的是原子本身，則原子賦值為本身，則原

24、子賦值為1 1；如果出現的是原子的否定，則原子賦值；如果出現的是原子的否定，則原子賦值為為0 0。 3 3、推理的各種方法、推理的各種方法 （1 1）直接法）直接法 （2 2）利用）利用CPCP規(guī)則規(guī)則 （3 3）反證法）反證法 2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院1515 三、典型例題三、典型例題1 1、證明、證明 (PQ) (PQ) (PQ) (PQ) (P(PQ)Q)(PQ)(PQ)(PQ) (PQ) (PQ)(PQ)(P PQ) Q) (PQ)(PQ)P)P) (PQ)(PQ)Q) Q) (P(PP)(QP)(QP)P)(P(PQ)(QQ)(QQ

25、)Q) (Q(QP)P)(P(PQ)Q) (Q(QP)P)(P(PQ)Q) ( (QP)QP)( (P PQ)Q)(QP)(QP)(P(PQ)Q)(P(PQ)Q)2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院16162 2、 G=G=( ()，求主析取和主合取范式。，求主析取和主合取范式。解解：首先列出其真值表如下：首先列出其真值表如下：P Q R P Q R PQPQ（PQPQ）( (PQ)RPQ)R0 0 00 0 01 10 00 00 0 10 0 11 10 01 10 1 00 1 01 10 00 00 1 10 1 11 10 01 11 0 01

26、 0 00 01 11 11 0 11 0 10 01 11 11 1 01 1 01 10 00 01 1 11 1 11 10 01 1極大項極大項極小項極小項PQRPQRPPQRQRPPQRQRPPQRQRPQRPQRPPQQR RPPQRQRPQRPQR主析取范式主析取范式= =（PPQRQR）（PQRPQR） （PPQQR R）（PPQRQR）（PQRPQR）主合取范式主合取范式= =（ PQRPQR ）（ PPQRQR ）（PPQRQR）2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院17173 3、用公式轉換法求上題中的主析取和主合取范式、用公式轉換法

27、求上題中的主析取和主合取范式( ()（PQPQ）R R （PPQ Q）RR（PRPR）（QRQR）（PRPR（QQQQ）（QRQR（PPPP）（PRPRQ Q）（PRQPRQ）（QRQRP P）（QRPQRP）（PRPRQ Q）（PRQPRQ）（QRQRP P） （主合取范式）主合取范式）( ()（PQPQ）R R （PPQ Q）RR（PPQQ（RRR R）（RR（PPP P）（QQQ Q）（PPQRQR）（PPQQR R）（RPRP）（RRP P）（PPQRQR）（PPQQR R）（RPRP（QQQ Q） （RRP P（QQQ Q）（PPQRQR）（PPQQR R）（RPQRPQ） （RPR

28、PQ Q）（RRP PQQ）（RRP PQ Q）（主析取范式）（主析取范式）2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院1818 4 4、P P2525 14 14 解：根據給定的條件有下述命題公式：解：根據給定的條件有下述命題公式：（AA（C C D D）（BCBC）（CDCD）（AA（CCD D）（CDCD）（BBC C）（CCD D）（AAB B）（CCDDB B）（CDCDB B） （AAC C）（CCDDC C）（CDCDC C）（CCD D）（AAB B）（CCDDB B）（CDCDB B） （AAC C）（CDCDC C） （CCD D）（AABB

29、C C）（CCDDBBC C）（CDCDBBC C）（AACCC C）（CDCDCCC C）（AABBD D）（CCDDBBD D）（CDCDBBD D）（AACCD D）（CDCDCCD D）（由題意和矛盾律）（由題意和矛盾律）2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院1919（CDCDB B）（AAC C）（CDCD）（CCDDB B）（CDCDB BAA） （CDCDB BA A） （AACBCB） （AACCB B） （CDCDAA） （CDCDA A）（CCDDBABA）（CCDDBBA A）（CDCDB BAA） （AACBDCBD） （AACBC

30、BD D） （AACCBDBD） （AACCBBD D） （CDCDABAB） （CDCDAAB B） （CDCDABAB） （CDCDAAB B）（CCDDBABA）（CCDDBBA A）（CDCDB BAA） （AACBDCBD） （CDCDAAB B） （CDCDABAB） （CCDDBABA）（CDCDB BAA） （AACBDCBD）（CCDDBABA）所以，共有三種選派方案：所以，共有三種選派方案：A和和C，A和和D，B和和D 2022-3-282022-3-28計算機科學與工程學院計算機科學與工程學院20205 5、P P2525 18 18解：根據給定的條件有下述命題：解：根據給定的條件有下述命題：P P：珍寶藏在東廂房：珍寶藏在東廂房Q Q：藏寶的房子靠近池塘：藏寶的房子靠近池塘R R：