二章命題邏輯的等值和推理演算-ppt課件

1、第二章命題邏輯的等值和推理演算第二章命題邏輯的等值和推理演算 l內(nèi)容：推理方式和推理演算是數(shù)理邏輯研內(nèi)容：推理方式和推理演算是數(shù)理邏輯研討的根本內(nèi)容。討的根本內(nèi)容。l推理演算要用正確的推理：推理方式由前推理演算要用正確的推理：推理方式由前提和結(jié)論經(jīng)蘊(yùn)涵詞聯(lián)接而成。我們關(guān)注正提和結(jié)論經(jīng)蘊(yùn)涵詞聯(lián)接而成。我們關(guān)注正確的推理方式確的推理方式 。正確的推理方式可由邏輯。正確的推理方式可由邏輯關(guān)系符表達(dá)。關(guān)系符表達(dá)。l非方式描畫(huà)：本章對(duì)命題等值和推理演算非方式描畫(huà)：本章對(duì)命題等值和推理演算進(jìn)展的討論，是以語(yǔ)義的觀念進(jìn)展的非方進(jìn)展的討論，是以語(yǔ)義的觀念進(jìn)展的非方式的描畫(huà)。式的描畫(huà)。l等值演算等值演算(調(diào)查邏

2、輯關(guān)系符調(diào)查邏輯關(guān)系符 )：l 1)等值定理、公式等值定理、公式l 2)由真值表寫(xiě)命題公式由真值表寫(xiě)命題公式(由由T寫(xiě)、由寫(xiě)、由F寫(xiě)寫(xiě))l 3)結(jié)合詞的完備集結(jié)合詞的完備集(由個(gè)別結(jié)合詞表示由個(gè)別結(jié)合詞表示一切結(jié)合詞的問(wèn)題一切結(jié)合詞的問(wèn)題)l 4)對(duì)偶式對(duì)偶式(命題公式的對(duì)偶性命題公式的對(duì)偶性)l 5)范式范式(命題公式的一致規(guī)范命題公式的一致規(guī)范)推理演算推理演算(調(diào)查邏輯關(guān)系符調(diào)查邏輯關(guān)系符 ) ： 1)推理方式推理方式(正確推理方式的表示正確推理方式的表示) 2)根本推理公式根本推理公式(各種三段論及五種證各種三段論及五種證明方法明方法) 3)推理演算推理演算(證明推理公式的第六種方證明

3、推理公式的第六種方法，運(yùn)用推理規(guī)那么法，運(yùn)用推理規(guī)那么) 4)歸結(jié)推理法歸結(jié)推理法(證明推理公式的第七種證明推理公式的第七種方法，常用反證法方法，常用反證法)2.1.1 2.1.1 等值的定義等值的定義 l等值的定義：給定兩個(gè)命題公式等值的定義：給定兩個(gè)命題公式A A和和B, B, 而而P1PnP1Pn是出現(xiàn)于是出現(xiàn)于A A和和B B中的一切命題變中的一切命題變項(xiàng)項(xiàng), , 那么公式那么公式A A和和B B共有共有2n2n個(gè)解釋個(gè)解釋, , 假設(shè)假設(shè)對(duì)其中的任一解釋對(duì)其中的任一解釋, , 公式公式A A和和B B的真值都的真值都相等相等, , 就稱就稱A A和和B B是等值的是等值的( (或等價(jià)

4、的或等價(jià)的) )。記作記作A = BA = B或或A A B B。留意邏輯關(guān)系詞。留意邏輯關(guān)系詞2.1 2.1 等值定理等值定理 例例1: 1: 證明證明(P(P P)Q = QP)Q = Q證明證明: : 畫(huà)出畫(huà)出(P(P P)QP)Q與與Q Q的真值表可看出的真值表可看出等式是成立的。等式是成立的。例例2: 2: 證明證明PP P = QP = Q Q Q 證明: 畫(huà)出PP, QQ的真值表, 可看出它們是等值的, 而且它們都是重言式。l等值定義補(bǔ)充闡明：兩個(gè)公式等值并不要等值定義補(bǔ)充闡明：兩個(gè)公式等值并不要求它們一定含有一樣的命題變項(xiàng)。假設(shè)僅求它們一定含有一樣的命題變項(xiàng)。假設(shè)僅在等式一端的

5、公式里有變項(xiàng)在等式一端的公式里有變項(xiàng)P P出現(xiàn)出現(xiàn), , 那么等那么等式兩端的公式其真值均與式兩端的公式其真值均與P P無(wú)關(guān)。例無(wú)關(guān)。例1 1中公中公式式(P(P P) QP) Q與與Q Q的真值都同的真值都同P P無(wú)關(guān)無(wú)關(guān), , 例例2 2中中PP P, QP, Q Q Q都是重言式都是重言式, , 它們的真值它們的真值也都與也都與P P、Q Q無(wú)關(guān)。無(wú)關(guān)。 2.1.2 2.1.2 等值定理等值定理 l定理定理2.1.1 2.1.1 對(duì)公式對(duì)公式A A和和B, A = BB, A = B的充分必的充分必要條件是要條件是A A B B是重言式。是重言式。l 即恣意解釋下，即恣意解釋下，A A和

6、和B B都有一樣的真值。都有一樣的真值。l證明：定理中的兩部分都與上一行等同。證明：定理中的兩部分都與上一行等同。A = BA = B是表示公式是表示公式A A與與B B的一種關(guān)系。這種關(guān)系的一種關(guān)系。這種關(guān)系具有三個(gè)性質(zhì)具有三個(gè)性質(zhì): : 1. 1. 自反性自反性 A = A A = A。2. 2. 對(duì)稱性對(duì)稱性 假設(shè)假設(shè)A = BA = B那么那么B = AB = A。3. 3. 傳送性傳送性 假設(shè)假設(shè)A = B, B = CA = B, B = C那么那么A = CA = C。這三條性質(zhì)表達(dá)了這三條性質(zhì)表達(dá)了“的本質(zhì)含義。的本質(zhì)含義。 2.2 2.2 等值公式等值公式( (真值表驗(yàn)證，真

7、值表驗(yàn)證，VennVenn圖了解圖了解) )2.2.1 根本的等值公式(特別留意藍(lán)色字)1. 雙重否認(rèn)律P = P2. 結(jié)合律(PQ) R = P(QR)(PQ) R = P(QR)(P Q) R = P (Q R)3. 交換律PQ = QPPQ = QPP Q = Q P4. 分配律P(QR) = (PQ)(PR)P(QR) = (PQ)(PR)P(QR) = (PQ)(PR)5. 等冪律(恒等律)PP = PPP = PPP = TPP = T6. 吸收律P(PQ) = PP(PQ) = P7. 摩根律(PQ) = PQ(PQ) = PQ對(duì)蘊(yùn)涵詞、雙條件詞作否認(rèn)有(PQ) = PQ(PQ)

8、 = PQ = PQ= (PQ)(PQ)8. 同一概PF = PPT = PTP = PTP = P還有PF = PFP = P 9. 零律PT = TPF = F還有PT = TFP = T10. 補(bǔ)余律PP = TPP = F還有PP = PPP = PPP = F VennVenn圖圖l這種圖是將這種圖是將P P、Q Q了解為某總體論域上了解為某總體論域上的子集合的子集合, , 而規(guī)定而規(guī)定PQPQ為兩集合的公為兩集合的公共部分共部分( (交集合交集合), PQ), PQ為兩集合的全為兩集合的全部部( (并集合并集合), ), P P為總體論域?yàn)榭傮w論域( (如矩形如矩形域域) )中中P

9、 P的余集。的余集。 VennVenn圖實(shí)例圖實(shí)例1. P(PQ) = P2. P(PQ) = P3. (PQ) = PQVennVenn圖可以用來(lái)了解圖可以用來(lái)了解集合間、命題邏輯中、集合間、命題邏輯中、部分信息量間的一些部分信息量間的一些關(guān)系。關(guān)系。2.2.2 2.2.2 假設(shè)干常用的等值公式假設(shè)干常用的等值公式 l等值演算中，由于人們對(duì)等值演算中，由于人們對(duì) 、更為熟更為熟習(xí)，常將含有習(xí)，常將含有和和的公式化成僅含有的公式化成僅含有 、的公式。這也是證明和了解含有的公式。這也是證明和了解含有，的公式的普通方法。但后面的推理演算的公式的普通方法。但后面的推理演算中，更希望見(jiàn)到中，更希望見(jiàn)到

10、和和. .12. 逆否認(rèn)理PQ=QP11. PQ = P Q13. 前提合并P(QR) = (PQ)R17. 前提交換P(QR) = Q(PR)18. 另一種前提合并(PR) (QR)=(PQ)R14. 從取真來(lái)描畫(huà)雙條件詞PQ = (PQ)(PQ)15.從取假來(lái)描畫(huà)雙條件詞PQ = (PQ)(PQ)16. 從蘊(yùn)涵詞描畫(huà)雙條件詞PQ = (PQ)(QP)2.2.3 2.2.3 置換規(guī)那么置換規(guī)那么( (留意與代入規(guī)那么留意與代入規(guī)那么p8p8的區(qū)別的區(qū)別) )置換定義：對(duì)公式置換定義：對(duì)公式A的子公式的子公式, 用與之等值的用與之等值的公式來(lái)代換便稱置換。公式來(lái)代換便稱置換。置換規(guī)那么：將公式

11、置換規(guī)那么：將公式A的子公式置換后，的子公式置換后，A化化為公式為公式B, 必有必有A = B。置換與代入是有區(qū)別的：代入規(guī)那么要求操置換與代入是有區(qū)別的：代入規(guī)那么要求操作重言式、對(duì)一切同一命題變?cè)甲鞔鷵Q作重言式、對(duì)一切同一命題變?cè)甲鞔鷵Q2.2.4 2.2.4 等值演算舉例等值演算舉例 例例1: 證明證明( P( QR)(QR)(PR) = R證明證明: 左端左端= ( P( QR) (QP)R) (分配律分配律)=( P Q)R)(QP)R) (結(jié)合律結(jié)合律)=( (PQ)R)(QP)R)(摩根律摩根律)=( (PQ)(QP)R(分配律分配律)=( (PQ)(PQ)R(交換律交換律)=

12、TR(置置 換換)=R(同一概同一概) 例例2: 試證試證 (PQ) ( P( Q R) ( P Q)( P R) = T證明證明:左端左端=(PQ)(P(QR) (PQ)(PR)(摩根律摩根律)=(PQ)(PQ)(PR) (PQ)(PR) (分配律分配律)=(PQ)(PR) (PQ)(PR)(等冪律等冪律)=T(置換規(guī)那么置換規(guī)那么)問(wèn)題提出：由命題公式寫(xiě)真值表是容易問(wèn)題提出：由命題公式寫(xiě)真值表是容易的，那么如何由真值表寫(xiě)命題公式呢？的，那么如何由真值表寫(xiě)命題公式呢？2.3 命題公式與真值表關(guān)系命題公式與真值表關(guān)系2.3.1 2.3.1 從從T T來(lái)列寫(xiě)來(lái)列寫(xiě)1.1.記憶方法：各項(xiàng)間用記憶方

13、法：各項(xiàng)間用，每項(xiàng)內(nèi)用，每項(xiàng)內(nèi)用2.2.每項(xiàng)內(nèi)書(shū)寫(xiě)方法：例每項(xiàng)內(nèi)書(shū)寫(xiě)方法：例 真值表中真值表中P=FP=F且且Q=FQ=F等價(jià)于等價(jià)于 PP Q=TQ=T3.3.簡(jiǎn)化方法：有時(shí)簡(jiǎn)化方法：有時(shí)A A的表達(dá)經(jīng)過(guò)的表達(dá)經(jīng)過(guò) A A來(lái)描畫(huà)來(lái)描畫(huà)2.3.2 2.3.2 從從F F來(lái)列寫(xiě)來(lái)列寫(xiě)1.1.記憶方法：各項(xiàng)間用記憶方法：各項(xiàng)間用 ，每項(xiàng)內(nèi)用，每項(xiàng)內(nèi)用2.2.每項(xiàng)內(nèi)書(shū)寫(xiě)方法：例每項(xiàng)內(nèi)書(shū)寫(xiě)方法：例 真值表中真值表中P=TP=T且且Q=FQ=F等價(jià)于等價(jià)于 PQ=FPQ=F3.3.簡(jiǎn)化方法：有時(shí)簡(jiǎn)化方法：有時(shí)A A的表達(dá)經(jīng)過(guò)的表達(dá)經(jīng)過(guò) A A來(lái)描來(lái)描畫(huà)畫(huà)4.4.恣意值的問(wèn)題恣意值的問(wèn)題( (圖圖2.3.

14、1)2.3.1)2.4 2.4 結(jié)合詞的完備集結(jié)合詞的完備集 問(wèn)題的提出：對(duì)問(wèn)題的提出：對(duì)n n 個(gè)命題變項(xiàng)個(gè)命題變項(xiàng)P1PnP1Pn來(lái)說(shuō)來(lái)說(shuō), , 共可定義出多少個(gè)結(jié)合詞共可定義出多少個(gè)結(jié)合詞? ? 在那么多結(jié)合詞在那么多結(jié)合詞中有多少是相互獨(dú)立的中有多少是相互獨(dú)立的? ? 引見(jiàn)引見(jiàn)3 3個(gè)新型結(jié)合詞：個(gè)新型結(jié)合詞： 異或異或 : PQ =( : PQ =( PQ)(PPQ)(P Q)Q)與非與非 : P : P Q = Q = (PQ)(PQ)或非或非 : P : P Q = Q = (PQ)(PQ)2.4.1 2.4.1 命題結(jié)合詞的個(gè)數(shù)命題結(jié)合詞的個(gè)數(shù)l要處理本節(jié)提出的第一個(gè)問(wèn)題，首先

15、要把要處理本節(jié)提出的第一個(gè)問(wèn)題，首先要把n n個(gè)命題變項(xiàng)構(gòu)造出的無(wú)限多個(gè)合式公式分個(gè)命題變項(xiàng)構(gòu)造出的無(wú)限多個(gè)合式公式分類。類。l將等值的公式視為同一類，從中選一個(gè)作將等值的公式視為同一類，從中選一個(gè)作代表稱之為真值函項(xiàng)。對(duì)一個(gè)真值函項(xiàng)，代表稱之為真值函項(xiàng)。對(duì)一個(gè)真值函項(xiàng)，或者說(shuō)對(duì)于該類合式公式，就可定義一個(gè)或者說(shuō)對(duì)于該類合式公式，就可定義一個(gè)結(jié)合詞與之對(duì)應(yīng)。結(jié)合詞與之對(duì)應(yīng)。 l例：一元結(jié)合詞是結(jié)合一個(gè)命題變項(xiàng)例：一元結(jié)合詞是結(jié)合一個(gè)命題變項(xiàng)( (如如P)P)的。的。P P有真假有真假2 2種值，因此種值，因此P(P(自變量自變量) )上上可定義可定義4 4種一元結(jié)合詞種一元結(jié)合詞( (真值函項(xiàng)

16、、函數(shù)真值函項(xiàng)、函數(shù)) )：真值表見(jiàn)圖。真值表見(jiàn)圖。lf0f0 f1 f1 f2 f2 f3f3l 或稱或稱 f0(P) f1(P) f2(P) f3(P)f0(P) f1(P) f2(P) f3(P)由真值表寫(xiě)出真值函項(xiàng)的命題公式：由真值表寫(xiě)出真值函項(xiàng)的命題公式：f0(P) = Ff1(P) = Pf2(P) = Pf3(P) = Tl例：二元結(jié)合詞結(jié)合兩個(gè)命題變項(xiàng)例：二元結(jié)合詞結(jié)合兩個(gè)命題變項(xiàng)( (如如P P、Q)Q)，兩個(gè)變項(xiàng)共有，兩個(gè)變項(xiàng)共有4 4種取值情形種取值情形, , 于是于是P P、Q Q上可建立起上可建立起1616種不同的真值函項(xiàng)種不同的真值函項(xiàng), , 相應(yīng)相應(yīng)的可定義出的可

17、定義出1616個(gè)不同的二元結(jié)合詞個(gè)不同的二元結(jié)合詞lg0, g1, , g15 g0, g1, , g15 l 圖圖2.4.22.4.2給出了這些結(jié)合詞給出了這些結(jié)合詞gigi或說(shuō)真值或說(shuō)真值函項(xiàng)函項(xiàng)gi(P, Q)gi(P, Q)的真值表定義。的真值表定義。 根據(jù)真值表寫(xiě)出各真值函項(xiàng)的命題表達(dá)式根據(jù)真值表寫(xiě)出各真值函項(xiàng)的命題表達(dá)式:g0 (P,Q) = Fg1(P,Q) = PQg2(P,Q) = P Qg3(P,Q) = (P Q)(PQ) = P( QQ) = Pg4(P,Q) = PQg5(P,Q) = ( PQ)(PQ) = ( PP)Q = Qg6(P,Q) = PQg7(P,Q)

18、 = PQg8(P,Q) = P Q = P Qg9(P,Q) = P Qg10(P,Q) = ( P Q)(P Q) = ( PP) Q = Qg11(P,Q) = P Q = QPg12(P,Q) = ( P Q)( PQ) = P( QQ) = Pg13(P,Q) = PQ = P Qg14(P,Q) = P Q = P Qg15(P,Q) = Tl結(jié)合詞個(gè)數(shù)統(tǒng)計(jì)：對(duì)結(jié)合詞個(gè)數(shù)統(tǒng)計(jì)：對(duì)n n 個(gè)命題變?cè)獋€(gè)命題變?cè)狿1Pn, P1Pn, 每個(gè)每個(gè)PiPi有兩種取值有兩種取值, , 從而對(duì)從而對(duì)P1PnP1Pn來(lái)說(shuō)共有來(lái)說(shuō)共有2n2n種取值情形。種取值情形。l 于是相應(yīng)的直值函項(xiàng)就有于是相應(yīng)

19、的直值函項(xiàng)就有22n22n個(gè)個(gè), , 或或說(shuō)可定義說(shuō)可定義22n22n個(gè)個(gè)n n元結(jié)合詞。元結(jié)合詞。2.4.2 2.4.2 結(jié)合詞的完備集結(jié)合詞的完備集 l關(guān)于本節(jié)提出的第二個(gè)問(wèn)題，也就是說(shuō)這關(guān)于本節(jié)提出的第二個(gè)問(wèn)題，也就是說(shuō)這些結(jié)合詞能否能相互經(jīng)過(guò)組合來(lái)表示呢些結(jié)合詞能否能相互經(jīng)過(guò)組合來(lái)表示呢? ?l結(jié)合詞的完備集定義結(jié)合詞的完備集定義: : 設(shè)設(shè)C C是結(jié)合詞的集合，是結(jié)合詞的集合，假設(shè)對(duì)任一命題公式假設(shè)對(duì)任一命題公式( (能直接運(yùn)用能直接運(yùn)用T T和和F)F)都都有由有由C C中的結(jié)合詞表示出來(lái)的公式中的結(jié)合詞表示出來(lái)的公式( (不能直不能直接運(yùn)用接運(yùn)用T T和和F)F)與之等值，就說(shuō)與

20、之等值，就說(shuō)C C是完備的結(jié)是完備的結(jié)合詞集合，或說(shuō)合詞集合，或說(shuō)C C是結(jié)合詞的完備集。是結(jié)合詞的完備集。l書(shū)上的書(shū)上的8 8個(gè)完備集個(gè)完備集( (提問(wèn)提問(wèn)) )：l1.1.顯然全體結(jié)合詞的無(wú)限集合是完備的。顯然全體結(jié)合詞的無(wú)限集合是完備的。 l2.2.定理定理: : , , , , 是完備的結(jié)合詞集合。是完備的結(jié)合詞集合。l 證明：從證明：從2.32.3節(jié)引見(jiàn)的由真值表列寫(xiě)邏輯公節(jié)引見(jiàn)的由真值表列寫(xiě)邏輯公式的過(guò)程可知式的過(guò)程可知, , 任一公式都可由任一公式都可由 , , , , 表示出來(lái)表示出來(lái), , 從而從而 , , , , 是完備的。是完備的。 l8.8. , , , , , , ,

21、 , 是完備的是完備的, , 由于它包由于它包含了含了2 2中的集合。另外，中的集合。另外，, , 不是不是完備的，由于完備的，由于F F不能僅由該集合的結(jié)合詞表達(dá)不能僅由該集合的結(jié)合詞表達(dá)出來(lái)。出來(lái)。 , , 也不是完備的。也不是完備的。特別留意特別留意假設(shè)一個(gè)結(jié)合詞的集合是不完備的，那假設(shè)一個(gè)結(jié)合詞的集合是不完備的，那么它的任何子集都是不完備的。因此，么它的任何子集都是不完備的。因此，, 的任何子集都是不完備的。的任何子集都是不完備的。 , 的任何子集也是不完備的。的任何子集也是不完備的。由此可推知，集合由此可推知，集合3,4,5,6,7都是獨(dú)立的完都是獨(dú)立的完備集?，F(xiàn)實(shí)上，備集。現(xiàn)實(shí)上，

22、6,7是僅有的兩個(gè)只需一個(gè)是僅有的兩個(gè)只需一個(gè)結(jié)合詞的完備集結(jié)合詞的完備集(不證不證).,不是完備的不是完備的(不證不證).2.5 2.5 對(duì)偶式對(duì)偶式 l新符號(hào)新符號(hào)“對(duì)偶式：將對(duì)偶式：將A A中出現(xiàn)的中出現(xiàn)的、T T、F F分別以分別以、F F、T T代換代換, , 得到公式得到公式A A* *, , 那么稱那么稱A A* *是是A A的對(duì)偶式的對(duì)偶式, , 或說(shuō)或說(shuō)A A和和A A* *互為對(duì)互為對(duì)偶式。偶式。 l 假設(shè)假設(shè)A = BA = B必有必有A A* *=B=B* *? ?對(duì)僅含對(duì)僅含 、三個(gè)結(jié)合詞的公式調(diào)查類似性三個(gè)結(jié)合詞的公式調(diào)查類似性新符號(hào)新符號(hào)“- -：假設(shè)：假設(shè)A=A

23、(P1, , Pn)A=A(P1, , Pn)令令 A A= A(= A( P1, , P1, , Pn)Pn)關(guān)于等值的三個(gè)定理關(guān)于等值的三個(gè)定理 ( (這不是這不是2.12.1節(jié)的等值定理節(jié)的等值定理) )定理定理2.5.1 2.5.1 (A(A* *) = () = ( A)A)* *, , (A(A) = () = ( A)A) 定理定理2.5.2 (A2.5.2 (A* *) )* * = A, (A = A, (A) )=A=A定理定理2.5.3 2.5.3 摩根律摩根律 A = AA = A* *可用數(shù)學(xué)歸納法可用數(shù)學(xué)歸納法, , 施歸納于施歸納于A A中中出現(xiàn)的結(jié)合詞個(gè)數(shù)出現(xiàn)的

24、結(jié)合詞個(gè)數(shù)n n來(lái)證明。來(lái)證明。定理定理 2.5.4 2.5.4 假設(shè)假設(shè)A = BA = B必有必有A A* *=B=B* *證明證明: : 由于由于A = BA = B等價(jià)于等價(jià)于A AB B 永真等價(jià)于永真等價(jià)于A AB B永真。永真。依定理依定理2.5.3, 2.5.3, A = AA = A* *, , B = BB = B* * 于是于是 A A* * B B* * 永真永真必有必有 A A* * B B* * 永真永真故故 A A* * = B = B* *關(guān)于推理的三個(gè)定理關(guān)于推理的三個(gè)定理定理定理2.5.5 2.5.5 假設(shè)假設(shè)A AB B永真永真, , 必有必有B B* *

25、A A* *永永真真定理定理2.5.6 A2.5.6 A與與A A同永真同永真, , 同可滿足同可滿足 A A與與A A* *同永真同永真, , 同可滿足同可滿足留意：留意： “A A與與B B同永真同永真, , 同可滿足的意思同可滿足的意思是：是：A A永真可推出永真可推出B B永真永真, ,反之亦然。反之亦然。2.6 2.6 范式范式( (命題的一致方式命題的一致方式) )ln n 個(gè)命題變項(xiàng)所能組成的具有不同真值表個(gè)命題變項(xiàng)所能組成的具有不同真值表的命題公式僅有的命題公式僅有22n22n個(gè)個(gè), , 然而與任何一個(gè)命然而與任何一個(gè)命題公式等值而方式不同的命題公式可以有題公式等值而方式不同的

26、命題公式可以有無(wú)窮多個(gè)。這些等值的公式，能否都可以無(wú)窮多個(gè)。這些等值的公式，能否都可以化為某一個(gè)一致的規(guī)范方式化為某一個(gè)一致的規(guī)范方式? ?2.6.1 2.6.1 范式范式l好多新概念好多新概念l文字、合取式、析取式、互補(bǔ)對(duì)、文字、合取式、析取式、互補(bǔ)對(duì)、l析取范式、合取范式析取范式、合取范式l范式定理：任一命題公式都存在與之等值的范式定理：任一命題公式都存在與之等值的析取范式、合取范式。析取范式、合取范式。l求范三步曲：求范三步曲：l1) 消去消去和和l2) 否認(rèn)深化到變?cè)裾J(rèn)深化到變?cè)猯3) 運(yùn)用分配律的等值變換運(yùn)用分配律的等值變換范式功能：范式功能：判別兩公式能否等值判別兩公式能否等值(

27、 (參主范式參主范式) )；判別重言式：合取范式中一切析取判別重言式：合取范式中一切析取式都有互補(bǔ)對(duì)；式都有互補(bǔ)對(duì)；判別矛盾式：析取范式中一切合取判別矛盾式：析取范式中一切合取式都有互補(bǔ)對(duì)；式都有互補(bǔ)對(duì)；2.6.2 2.6.2 主范式主范式l主析取范式主析取范式l極小項(xiàng)定義與編碼：極小項(xiàng)定義與編碼：l主析取范式定義主析取范式定義l主析取范式獨(dú)一性定理主析取范式獨(dú)一性定理l由真值表寫(xiě)主析取范式由真值表寫(xiě)主析取范式(從從T寫(xiě)寫(xiě))，例，例3l由析取范式寫(xiě)主析取范式，例由析取范式寫(xiě)主析取范式，例4) 120(niim極小項(xiàng)性質(zhì)極小項(xiàng)性質(zhì)一切極小項(xiàng)的個(gè)數(shù)一切極小項(xiàng)的個(gè)數(shù)極小項(xiàng)為真的獨(dú)一解極小項(xiàng)為真的獨(dú)一

28、解極小項(xiàng)互不一樣極小項(xiàng)互不一樣坐標(biāo)系功能坐標(biāo)系功能A與與 A的主析取范式關(guān)系的主析取范式關(guān)系主合取范式主合取范式極大項(xiàng)定義：極大項(xiàng)定義：主合取范式定義主合取范式定義主合取范式獨(dú)一性定理主合取范式獨(dú)一性定理由真值表寫(xiě)主合取范式由真值表寫(xiě)主合取范式(從從F寫(xiě)寫(xiě))，例，例5由合取范式寫(xiě)主合取范式，例由合取范式寫(xiě)主合取范式，例6) 120(niiM極大項(xiàng)性質(zhì)極大項(xiàng)性質(zhì)一切極大項(xiàng)的個(gè)數(shù)一切極大項(xiàng)的個(gè)數(shù)極大項(xiàng)為假的獨(dú)一解極大項(xiàng)為假的獨(dú)一解極大項(xiàng)互不一樣極大項(xiàng)互不一樣坐標(biāo)系功能坐標(biāo)系功能A與與 A的主合取范式關(guān)系的主合取范式關(guān)系主析取范式與主合取范式的轉(zhuǎn)化主析取范式與主合取范式的轉(zhuǎn)化參見(jiàn)板書(shū)！參見(jiàn)板書(shū)！留意

29、補(bǔ)集與數(shù)字補(bǔ)的不同含義。留意補(bǔ)集與數(shù)字補(bǔ)的不同含義。2.7 2.7 推理方式推理方式1.1.經(jīng)過(guò)蘊(yùn)涵詞建立正確經(jīng)過(guò)蘊(yùn)涵詞建立正確( (即條件真時(shí)，結(jié)論必即條件真時(shí)，結(jié)論必真真) )或不正確的推理方式或不正確的推理方式例：例：(P(PQ)P)Q)P)Q Q 是正確的推理方式是正確的推理方式 (P (PQ)Q) Q)Q)P P是正確的推理方式是正確的推理方式 (P (PQ)Q) P)P)Q Q是不正確的推理方式是不正確的推理方式2.2.正確推理方式的書(shū)寫(xiě)方法正確推理方式的書(shū)寫(xiě)方法運(yùn)用邏輯關(guān)系詞：重言蘊(yùn)涵運(yùn)用邏輯關(guān)系詞：重言蘊(yùn)涵A AB B表示命題表示命題A A為真時(shí)命題為真時(shí)命題B B一定為真一定

30、為真3.3.重言蘊(yùn)涵的進(jìn)一步運(yùn)用重言蘊(yùn)涵的進(jìn)一步運(yùn)用( (與與2.8.12.8.1推推理公式不同，是一些推理規(guī)那么即證理公式不同，是一些推理規(guī)那么即證明推理公式的方法明推理公式的方法) )假設(shè)假設(shè)A AB, AB, A為重言式，那么為重言式，那么B B也是重言式。也是重言式。假設(shè)假設(shè)A AB B，B BA A同時(shí)成立，必有同時(shí)成立，必有A=BA=B。假設(shè)假設(shè)A AB B，B BC C，那么，那么A AC C。假設(shè)假設(shè)A AB B，A AC C，那么，那么A ABCBC。假設(shè)假設(shè)A AC C，B BC C，那么，那么A AB B C C。2.8 2.8 根本的推理公式根本的推理公式2.8.11.

31、 (PQ) P 化簡(jiǎn)律化簡(jiǎn)律2. (P Q) P 3. (P Q) Q4. P (PQ) 附加律附加律 5. P P Q6. Q P Q7. (PQ)P Q 析取三段論析取三段論8. (P Q)P Q 假言推理、分別規(guī)那假言推理、分別規(guī)那么么留意留意2、3、5、6的關(guān)系的關(guān)系9. (PQ)Q P 拒取式拒取式10. (PQ)(QR) (PR) 假言三段論、三段論假言三段論、三段論11. (PQ)(QR) (PR) 等價(jià)三段論等價(jià)三段論12. (P R)(Q R)(PQ) R 構(gòu)造性二難構(gòu)造性二難(特殊方式特殊方式)13. (PQ)(RS)(PR) (QS) 構(gòu)造性二難構(gòu)造性二難14. (PQ)

32、(RS)(QS) (PR) 破壞性二難破壞性二難15. (QR) ( (P Q)(P R) )16. (QR) ( (PQ)(PR) )2.8.2 2.8.2 證明推理公式的證明推理公式的5 5種方法種方法定理定理2.8.1 A2.8.1 AB B成立的充分必要條件是成立的充分必要條件是A AB B為重言式。留意：為重言式。留意：1)1)比較定理比較定理2.1.12.1.1 2) 2)證明證明A AB B為重言式的方法：等值演為重言式的方法：等值演算、主析取范式、真值表算、主析取范式、真值表例例1 1 用等值演算法證明用等值演算法證明(p(pq)q)p pq q為重言式為重言式 (p (pq)

33、q)p pq q (p pq)q)p)p)q q (p (pq)q)p)p)q q p pq qq q T T例例2 2 用主析取范式法證明用主析取范式法證明(p(pq)q)q qp p不是重言式不是重言式 (p (pq)q)q qp p ( (p pq)q)q qp p (p pq)q)q)q)p p q qp p ( (p pq)q)(p(pq)q)(p(pq)q)(p(pq) q) m0 m0 m2 m2 m3 m3 短少短少m1m1即即p pq, q, 所以所以(p(pq)q)q qp p不是重言式，不是重言式，或者說(shuō)推理方式或者說(shuō)推理方式(p(pq)q)q qp p不正確。不正確。2

34、. 2. 定理定理2.8.2 A2.8.2 AB B成立的充分必要條件是成立的充分必要條件是A AB B為重言式即為重言式即A AB B為矛盾式。為矛盾式。3.3.逆否認(rèn)理逆否認(rèn)理 A AB B成立的充分必要條件成立的充分必要條件B BA A4. 4. 解釋法：參考書(shū)上解釋法：參考書(shū)上p32p32頁(yè)例子頁(yè)例子5. 5. 真值表法：即經(jīng)過(guò)真值表檢驗(yàn)真值表法：即經(jīng)過(guò)真值表檢驗(yàn)A A為真時(shí)為真時(shí)B B一一定為真。又見(jiàn)方法定為真。又見(jiàn)方法1 1中的第中的第3 3個(gè)子方法。個(gè)子方法。注：注： 證明證明A AB B時(shí)不思索時(shí)不思索A A為假的情況。為假的情況。2.9 2.9 推理演算推理演算( (證明推理公式證明推理公式A AB B的新方法的新方法) )從前提從前提A1, , AnA1, , An出發(fā)出發(fā)( (即即A= A1A= A1A2 A2 An)An)運(yùn)用推理規(guī)那么和根本推理公式，逐漸運(yùn)用推理規(guī)那么和根本推理公式，逐漸