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

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

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

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

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

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

6、工具。2022-3-282022-3-28計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院5 5命題公式命題公式-（1 1）命題變?cè)ǎ┟}變?cè)ㄔ用}變?cè)用}變?cè)┍旧硎且粋€(gè)公式；）本身是一個(gè)公式；（2 2）如）如P P，Q Q是公式，則是公式，則( (P)P)、(PQ)(PQ)、(PQ)(PQ)、(PQ)(PQ)、(P(PQ)Q)也是公式；也是公式；（3 3）命題公式命題公式僅由僅由有限步有限步使用規(guī)則使用規(guī)則1-21-2后產(chǎn)生的結(jié)果。后產(chǎn)生的結(jié)果。該公式常用符號(hào)該公式常用符號(hào)G G、H H、等表示。等表示。公式的解釋公式的解釋-設(shè)設(shè)P P1 1、P P2 2、P Pn n是出現(xiàn)在公式是出現(xiàn)

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

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

9、（公）式的對(duì)偶（公）式。對(duì)偶原理對(duì)偶原理-設(shè)設(shè)A A和和B B是兩個(gè)命題公式，若是兩個(gè)命題公式，若A A B B， 則則 A A* * B B* *2022-3-282022-3-28計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院7 7基本等價(jià)式基本等價(jià)式命題定律命題定律 設(shè)設(shè)G G，H H，S S是任何的公式，則：是任何的公式，則：1:1:(G(G H) H)(GH)(HG)(GH)(HG)( (等價(jià)等價(jià)) )2 2：(GH) (GH) ( (GH) GH) ( (蘊(yùn)涵蘊(yùn)涵) )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 ( (結(jié)合律結(jié)合律) ) 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計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工

11、程學(xué)院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,又叫標(biāo)準(zhǔn)型式又叫標(biāo)準(zhǔn)型式, ,正規(guī)型正規(guī)型式。式。把公式進(jìn)行標(biāo)準(zhǔn)化，正規(guī)化，就叫對(duì)公式求范式。把公式進(jìn)行標(biāo)準(zhǔn)化，正規(guī)化，就叫對(duì)公式求范式。 命題變?cè)蛎}變?cè)拿}變?cè)蛎}變?cè)姆穸ǚ穸ǚQ為稱為句節(jié)句節(jié)。 有限個(gè)有限個(gè)句節(jié)句節(jié)的的析取式析取式稱為稱為子句子句； 有限個(gè)有限個(gè)句節(jié)句節(jié)的的合取式合取式稱為稱為短語短語。 有限個(gè)有限個(gè)短語短語的的析取式析取式稱為稱為析取范式析取范式； 有限個(gè)有限個(gè)子句子句的的合取式合取式稱為稱為合取范式合取范式。2022-3-282022-3-28計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工

13、程學(xué)院9 9 極小項(xiàng)極小項(xiàng)-在在n n個(gè)變?cè)幕痉e（個(gè)變?cè)幕痉e（短語短語）中，若每一個(gè)）中，若每一個(gè)變?cè)c其否定變?cè)c其否定并不同時(shí)存在并不同時(shí)存在，且，且二者之一必出現(xiàn)且僅二者之一必出現(xiàn)且僅出現(xiàn)一次出現(xiàn)一次，則稱這種基本積為，則稱這種基本積為極小項(xiàng)極小項(xiàng)。 主析取范式主析取范式-由有限個(gè)極小項(xiàng)組成的析取式由有限個(gè)極小項(xiàng)組成的析取式。 極大項(xiàng)極大項(xiàng)-在在n n個(gè)變?cè)幕竞停▊€(gè)變?cè)幕竞停ㄗ泳渥泳洌┲?，若每一個(gè)）中，若每一個(gè)變?cè)c其否定變?cè)c其否定并不同時(shí)存在并不同時(shí)存在，且，且二者之一必出現(xiàn)且僅二者之一必出現(xiàn)且僅出現(xiàn)一次出現(xiàn)一次，則這種基本和稱為，則這種基本和稱為極大項(xiàng)極大項(xiàng)。 主合

14、取范式主合取范式-由有限個(gè)極大項(xiàng)組成的合取式由有限個(gè)極大項(xiàng)組成的合取式。 命題公式的蘊(yùn)涵命題公式的蘊(yùn)涵-設(shè)設(shè)A A和和B B是兩個(gè)合適公式，如果在是兩個(gè)合適公式，如果在任何解釋任何解釋下，下，A A取值取值1 1時(shí)時(shí)B B也取值也取值1 1，則稱公式，則稱公式A A蘊(yùn)涵公式蘊(yùn)涵公式B B，并記，并記A A B B。2022-3-282022-3-28計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1010 基本蘊(yùn)含（關(guān)系）式基本蘊(yùn)含（關(guān)系）式I I1 1：P PPQ PQ ， Q QPQ PQ P PPQ PQ ， Q QPQ PQ 擴(kuò)充法則擴(kuò)充法則( (析取引入律析取引入律) )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 歸結(jié)原理歸結(jié)原理2022-3-282022-3-28計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1111 命題邏輯的推理方法命題邏輯的推理方法-設(shè)設(shè)G G是由一組命題公式組成的集合，如果存在命題公式的有限序列：是由一組命題公式組成的集合，如果存在命題公式的有限序列： H1H1，H2H2，HnHn（=H=H） 其中，其中，HiHi或者是或者是G G中的某個(gè)公式，或者是前面的某些中的某個(gè)公式，或者是前面的某些HjHj（jiji）的有）的有效結(jié)論，并

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

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

19、本等價(jià)式及置換規(guī)則進(jìn)行等價(jià)演算 2 2、求主析?。ㄖ骱先。┓妒降姆椒ㄇ笾魑鋈。ㄖ骱先。┓妒降姆椒?公式轉(zhuǎn)換法公式轉(zhuǎn)換法（1 1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的、用聯(lián)用聯(lián)結(jié)詞結(jié)詞、來取代；來取代；（2 2）利用德）利用德 摩根定律將否定號(hào)摩根定律將否定號(hào)移到各個(gè)命題變?cè)那岸?；移到各個(gè)命題變?cè)那岸?；? 3）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范式和合取范式。化成其等價(jià)的析取范式和合取范式。（4 4）在析取范式的短語和合取范式的子句中，如同一命題變?cè)谖鋈》妒降?/p>

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

21、）Q=QQ=Q將命題變?cè)獙⒚}變?cè)狿 P補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的短語，補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的短語，此時(shí)得到的短語將是此時(shí)得到的短語將是標(biāo)準(zhǔn)的極小項(xiàng)標(biāo)準(zhǔn)的極小項(xiàng)；（7 7）若合取范式的某一個(gè)子句中缺少該命題公式中所規(guī)定的命題）若合取范式的某一個(gè)子句中缺少該命題公式中所規(guī)定的命題變?cè)?，則可用公式：變?cè)?，則可用公式： （）Q=QQ=Q將命題變?cè)獙⒚}變?cè)狿 P補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的子句，補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的子句，此時(shí)得到的子句將是此時(shí)得到的子句將是標(biāo)準(zhǔn)的極大項(xiàng)標(biāo)準(zhǔn)的極大項(xiàng)。（8 8）利用冪等律將相同的極小項(xiàng)和極大項(xiàng)合并，同時(shí)利用

22、交換律）利用冪等律將相同的極小項(xiàng)和極大項(xiàng)合并，同時(shí)利用交換律進(jìn)行順序調(diào)整，由此可轉(zhuǎn)換成標(biāo)準(zhǔn)的主析取范式和主合取范式。進(jìn)行順序調(diào)整，由此可轉(zhuǎn)換成標(biāo)準(zhǔn)的主析取范式和主合取范式。 真值表技術(shù)法真值表技術(shù)法主合取范式主合取范式-在命題公式的真值表中，使公式取值在命題公式的真值表中，使公式取值0 0時(shí)的解釋所時(shí)的解釋所對(duì)應(yīng)的對(duì)應(yīng)的全部極大項(xiàng)的合取式全部極大項(xiàng)的合取式。主析取范式主析取范式-在命題公式的真值表中，使公式取值在命題公式的真值表中，使公式取值1 1時(shí)的解釋所時(shí)的解釋所對(duì)應(yīng)的對(duì)應(yīng)的全部極小項(xiàng)的析取式全部極小項(xiàng)的析取式。2022-3-282022-3-28計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1

23、414（1 1）求出公式的）求出公式的真值表真值表（2）求出求出使公式取值使公式取值0 0時(shí)的解釋所對(duì)應(yīng)的時(shí)的解釋所對(duì)應(yīng)的全部極大項(xiàng)全部極大項(xiàng) 極大項(xiàng)取值極大項(xiàng)取值0“0“當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”：如果極大項(xiàng)中出現(xiàn)的是原子本：如果極大項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為身，則原子賦值為0 0；如果出現(xiàn)的是原子的否定，則原子賦值為；如果出現(xiàn)的是原子的否定，則原子賦值為1 1。 （3 3）求出使公式取值）求出使公式取值1 1時(shí)的解釋所對(duì)應(yīng)的時(shí)的解釋所對(duì)應(yīng)的全部極小項(xiàng)全部極小項(xiàng) 極小項(xiàng)取值極小項(xiàng)取值1 “1 “當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”：如果極小項(xiàng)中出現(xiàn)的是原子：如果極小項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為本身，則原

24、子賦值為1 1；如果出現(xiàn)的是原子的否定，則原子賦值；如果出現(xiàn)的是原子的否定，則原子賦值為為0 0。 3 3、推理的各種方法、推理的各種方法 （1 1）直接法）直接法 （2 2）利用）利用CPCP規(guī)則規(guī)則 （3 3）反證法）反證法 2022-3-282022-3-28計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院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計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院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極大項(xiàng)極大項(xiàng)極小項(xiàng)極小項(xiàng)PQRPQRPPQRQRPPQRQRPPQRQRPQRPQRPPQQR RPPQRQRPQRPQR主析取范式主析取范式= =（PPQRQR）（PQRPQR） （PPQQR R）（PPQRQR）（PQRPQR）主合取范式主合取范式= =（ PQRPQR ）（ PPQRQR ）（PPQRQR）2022-3-282022-3-28計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院17173 3、用公式轉(zhuǎn)換法求上題中的主析取和主合取范式、用公式轉(zhuǎn)換法

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計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1818 4 4、P P2525 14 14 解：根據(jù)給定的條件有下述命題公式：解：根據(jù)給定的條件有下述命題公式：（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計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院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計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院20205 5、P P2525 18 18解：根據(jù)給定的條件有下述命題：解：根據(jù)給定的條件有下述命題：P P：珍寶藏在東廂房：珍寶藏在東廂房Q Q：藏寶的房子靠近池塘：藏寶的房子靠近池塘R R：