1、離散數(shù)學(xué),第一章 命題邏輯,2/38,回顧,對偶原理 定義， 三條原理：非運(yùn)算與對偶，等價，永真蘊(yùn)含 析取范式和合取范式 基本積，基本和 基本和的積，基本積的和 主析取范式和主合取范式 極小項（積），極大項（和），基二進(jìn)制數(shù)十進(jìn)制數(shù)描述符 極小項的和，極大項的積，兩者的關(guān)系。,3/38,求范式步驟：,(2) 否定消去或內(nèi)移。,(3) 利用分配律。,(1) 消去聯(lián)結(jié)詞,回顧,4/38,1.7命題演算的推理理論,數(shù)理邏輯的一個主要任務(wù)就是提供一套推理規(guī)則，給定一些前提，利用所提供的推理規(guī)則，推導(dǎo)出一些結(jié)論來，這個過程稱為演繹或證明。 生活中： 倘若認(rèn)定前提是真的，從前提推導(dǎo)出結(jié)論的論證是遵守了邏輯

2、推理規(guī)則，則認(rèn)為此結(jié)論是真的，并且認(rèn)為這個論證過程是合法的。 數(shù)理邏輯中： 不關(guān)心前提的真實(shí)真值，把注意力集中于推理規(guī)則的研究，依據(jù)這些推理規(guī)則推導(dǎo)出的任何結(jié)論，稱為有效結(jié)論，而這種論證則被稱為有效論證。,5/38,有效結(jié)論,定義:設(shè)A和B是兩個命題公式，當(dāng)且僅當(dāng)AB是個永真式，即AB，則說B是A的有效結(jié)論，或B由A可邏輯的推出。 可把該定義推廣到有n個前提的情況。,6/38,有效結(jié)論,定義： 例： H1：今天周一或者今天下雨。 H2：今天不是周一。 C：今天下雨。,7/38,證明有效結(jié)論的方法,1，真值表法 思路:“證明使前提集合取值為真的那些組真值指派，也一定使結(jié)論取值為真”。 例:考察結(jié)

3、論C是否是下列前提H1，H2,H3的結(jié)論。 (1) H1：PQ，H2：P，C：Q,8/38,真值表法,(2) 真值表構(gòu)造如下：,9/38,真值表法,(3),10/38,真值表法,例：一份統(tǒng)計表格的錯誤或者是由于材料不可靠，或者是由于計算有錯誤；這份統(tǒng)計表格的錯誤不是由于材料不可靠，所以這份統(tǒng)計表格是由于計算有錯誤。 解： 設(shè)P:一份統(tǒng)計表格的錯誤是由于材料不可靠。 Q:一份統(tǒng)計表格的錯誤是由于計算有錯誤。 于是問題可符號化為： (PQ)PQ,11/38,真值表法,P Q (PQ)P Q 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1,12/38,證明有效結(jié)論的方法,2，直接證法

4、 在命題變元較多的情況下，真值表法顯得不方便，我們采用直接證明法，為此先給出如下的定義 定義：設(shè)S是一個命題公式的集合，從S推出命題公式C的推理過程是命題公式的一個有限序列： C1，C2，Cn。 其中，Ci或者屬于S，或者是某些Cj(ji)的有效結(jié)論，并且Cn就是C。 如何構(gòu)造這個推理序列以得出結(jié)論C呢？只要遵循下面的推理規(guī)則，使用列出的等價式或永真蘊(yùn)涵式，就能構(gòu)造出滿足要求的公式序列。為了幫助大家記憶，我們把常用的等價式和永真蘊(yùn)涵式再次列出來。,13/38,常用永真蘊(yùn)含式,I1：PQP, I2: PPQ, I3: PPQ I4: QPQ,I5: (PQ)P, I6: (PQ)Q I7：P,Q

5、 PQ,I8：P,PQQ, I9：P, PQ Q I10：Q,PQP, I11：PQ,QRPR I12： PQ,PR,QRR 公式中“,”代表“”,公式不必死記硬背，其證明均可從“”的定義出發(fā)。例如對I11前件為真時保證PQ和QR都必為真，PQ為真，則保證P為真時Q一定為真，而Q為真和QR為真則保證了R必為真， P為真，R為真自然保證了PR為真，問題得證。,14/38,常用等價式,E1: PP, E2: PQQP, E3: PQQP E4: (PQ)RP(QR ) E5: (PQ)RP(QR ) E6: (PQ)R(P R) (Q R) E7: (PQ)R(P R) (Q R) E8: (PQ

6、)PQ E9: (PQ)PQ E10:PPP E11:PPP,15/38,常用等價式,E12:R(PP)R E13:R(PP)R E14:R(PP)T E15:R(PP)F E16:PQPQ E17: (PQ)PQ E18:PQQP E19:P(QR)(PQ)R E20:(PQ)PQ E21:PQ(PQ)(QP) E22:PQ(PQ)(PQ),16/38,常用等價公式,17/38,直接證法,直接證明法：使用推理規(guī)則和給定的等價式及永真蘊(yùn)涵式進(jìn)行推導(dǎo)證明。 推理規(guī)則： 規(guī)則P：在推導(dǎo)過程中，任何時候都可以引入前提。引入一個前提稱為使用一次P規(guī)則。 規(guī)則T：在推導(dǎo)中，如果前面有一個或多個公式永真蘊(yùn)

7、含公式S，則可以把公式S引進(jìn)推導(dǎo)過程中。換句話說，引進(jìn)前面推導(dǎo)過程中的推理結(jié)果稱為使用T規(guī)則。,18/38,直接證法,解: 1 (1) (P Q) P規(guī)則 1 (2) P Q T規(guī)則 (1)和E11 1 (3) PQ T規(guī)則 (2)和E27 4 (4) Q R P規(guī)則 4 (5) QR T規(guī)則 (4)和E27 1,4 (6) PR T , (3), (5)和I12 7 (7) R P規(guī)則 1,4,7(8) P T,(6),(7)和I12,19/38,直接證法,例：證明公式SR可由公式PQ，PR，QS推出 解：問題即證PQ，PR，QS SR 1、 PQ P規(guī)則 2、PQ T規(guī)則和1 3、 QS

8、P規(guī)則 4、 QS T規(guī)則和3 5、 PS T規(guī)則及2和4 6、 SP T規(guī)則和5 7、 PR P規(guī)則 8、（PR）（RP）T規(guī)則和7 9、 PR T規(guī)則和8 10、SR T規(guī)則及6和9； 11、SR T規(guī)則和9 得證。,20/38,直接證法,例： (PQ)(RS),(QP)R,R PQ 1、R P規(guī)則 2、(QP)R P規(guī)則 3、 QP T規(guī)則及1和2 4、 RS T規(guī)則及1 5、 (PQ)(RS) P規(guī)則 6、 PQ T規(guī)則及4和5 7、(PQ) (QP) T規(guī)則及3和6 8、PQ T規(guī)則和7,21/38,直接證法,推理規(guī)則： CP規(guī)則：如果能從R和前提集合中推導(dǎo)出S來，則就能夠從前提集合

9、中推導(dǎo)出RS。 換句話說，當(dāng)結(jié)論是RS的形式的時候，可以把結(jié)論的前件當(dāng)作一個附加前提使用，并且它和前提一起若能推出結(jié)論的后件，則問題得證 實(shí)際上恒等式E28就可以推出CP規(guī)則： （ P Q ） R （ P Q ） R （ P Q ） R P （ Q R ） P （Q R）,22/38,直接證法,解：1 (1) R P規(guī)則（附加前提） 2 (2) R P P規(guī)則 1,2 (3) P T規(guī)則,(1),(2)和I9 4 (4) P(QS) P規(guī)則 1,2,4(5) QS T規(guī)則,(3),(4)和I10 6 (6) Q P規(guī)則 1,2,4,6(7) S T規(guī)則,(5),(6)和I10 1,2,4,6(

10、8) R S CP規(guī)則,(1),(7) ,23/38,例：證明RS是前提P(QS),R(PQ)的有效結(jié)論 解：原證明即證:P(QS), R(PQ)RS 1、 R P規(guī)則（附加前提） 2、 R(PQ) P規(guī)則 3、 PQ T規(guī)則及1和2 4、 P T規(guī)則和3 5、 P(QS) P規(guī)則 6、 QS T規(guī)則及4和5 7、 Q T規(guī)則和3 8、 S T規(guī)則及6和7 9、RS CP規(guī)則及1和8,直接證法,24/38,例：證明P(QR),Q,PS SR 解：1、 S P規(guī)則（附加前提） 2、 PS P規(guī)則 3、 P T規(guī)則及1和2 4、 P(QR) P規(guī)則 5、 QR T規(guī)則及3和4 6、 Q P規(guī)則 7

11、、 R T規(guī)則及5和6 8、 SR CP規(guī)則及1和7,直接證法,25/38,證明有效結(jié)論的方法,3，間接證明法（反證法） 定義：設(shè)公式H1,H2,Hm中的原子變元是P1, P2 ,Pn。如果給各原子變元P1, P2 ,Pn指派某一個真值集合，能使H1H2 Hm具有真值T，則命題公式集合H1,H2,Hm稱為一致的(或相容的)； 對于各原子變元的每一個真值指派，如果命題公式H1,H2,Hm中至少有一個是假，從而使得H1H2 Hm是假，則稱命題公式集合是不一致的(或不相容的)。 例如：令H1=P， H2 = P，則H1H2 = PP是矛盾式，所以P，P是不相容的。,26/38,反證法,定理：若存在一

12、個公式R，使得H1H2 Hm R R 則公式H1，H2，,Hm是不相容的。 證明： 設(shè)， H1H2 Hm R R 則意味著（ H1H2 Hm ）（RR）是重言式， 而RR是矛盾式，所以前件 H1H2 Hm必永假。 因此， H1，H2，,Hm是不相容的。,27/38,反證法,定理：設(shè)命題公式集合H1，H2，Hm是一致的，于是從前提集合出發(fā)可以邏輯的推出公式C的充要條件是從前提集合H1，H2，Hm，C出發(fā)，可以邏輯地推出一個矛盾（永假）式。 證明： 必要性：由于H1 H2 Hm C，即H1 H2 Hm C為永真式，因而使H1 H2 Hm 為真的真值指派一定使C為真，C為假，從而使H1 H2 Hm

13、C為假。必要性證完。,28/38,反證法,證充分性：由于H1 H2 Hm C可以邏輯地推出一個矛盾，即H1 H2 Hm C F即 H1 H2 Hm C F為永真式，即 H1 H2 Hm C為假，由假設(shè)知H1，H2，Hm是一致的，所以任何使H1 H2 Hm 為真的命題變元的真值指派必然使C 為假，從而使C為真。故有 H1 H2 Hm C 該定理說明用直接證明法可以證明的結(jié)論，用間接證明法都可以證明，反之亦然。 因此，為了證明B是A的結(jié)論，可以把A和B作為前提，然后推出一個矛盾，從而使問題得證。下面用例子說明。,29/38,反證法,F規(guī)則：如果前體集合和S不相容，那么可以從前提集合中推出S。 例：

14、證明(PQ)是PQ的有效結(jié)論。 解：把 (PQ)作為假設(shè)前提，并證明該假設(shè)前提導(dǎo)致一個永假式。 1 (1) (PQ) P規(guī)則（假設(shè)前提） 1 (2) PQ T規(guī)則，(1)和E10 1 (3) P T規(guī)則，(2)和I1 4 (4) PQ P規(guī)則 4 (5) P T規(guī)則，(4)和I1 1,4(6) P P T規(guī)則，(3),(5)和I16 1,4(7) (PQ) F規(guī)則，(1),(6),30/38,反證法,例：證明PQ，PR，QR R 解：1、R P規(guī)則（假設(shè)前提） 2、 PR P規(guī)則 3、 P T規(guī)則及1和2 4、 PQ P規(guī)則 5、 Q T規(guī)則及3和4 6、 QR P規(guī)則 7、 R T規(guī)則及5和

15、6 8、 RR T規(guī)則及1和7 9、 R F規(guī)則及1和8,31/38,反證法,例：足壇4支甲級隊進(jìn)行比賽，已知情況如下： 前提：1、若大連萬達(dá)獲冠軍，則北京國安和上海申花 獲得亞軍 2、若上海申花獲亞軍，則大連萬達(dá)不能獲冠軍 3、若陜西國力獲亞軍，則北京國安不能獲亞軍 4、最后大連萬達(dá)獲冠軍 結(jié)論：5、陜西國力未獲亞軍,32/38,反證法,用推理的方法證明由1、2、3、4能否推出5 解：首先將命題符號化 令P：大連萬達(dá)獲冠軍 Q：北京國安獲亞軍 R：上海申花獲亞軍 S：陜西國力獲亞軍,33/38,反證法,于是問題可符號化為： P(Q R),RP,SQ,P S/*注意這里自然語言中的和表示的是排

16、斥或，所以用 來表示*/ 解：1、 S P規(guī)則（假設(shè)前提） 2、S T規(guī)則和1 3、SQ P規(guī)則 4、 Q T規(guī)則2和3 5、P P規(guī)則 6、P(QR) P規(guī)則 7、QR T規(guī)則5和6 8、R T規(guī)則4和7 9、 RP P規(guī)則,34/38,反證法,10、 P T規(guī)則8和9 11、PP T規(guī)則5和10 12、 S F規(guī)則1和11 /*問題得證*/,35/38,證明有效結(jié)論使用方法規(guī)律,當(dāng)要證明的結(jié)論是條件式時，可考慮使用CP規(guī)則 當(dāng)要證明的結(jié)論比較簡單，而僅僅使用前提推導(dǎo)不明顯時，可考慮使用間接證明法即F規(guī)則，以使推導(dǎo)過程變得簡捷。,36/38,小結(jié),本章我們學(xué)習(xí)了命題的概念以及在命題集合上的運(yùn)算： 、 。 但是這些邏輯聯(lián)結(jié)詞并不是必不可少的，于是引出了邏輯聯(lián)結(jié)詞最小全功能完備集的概念： ，和，。,37/38,小結(jié),此外，我們完成了命題邏輯中的一個重要任務(wù)：合式公式的判定求解方法：A：真值表法；B：等價公式變換法；C：利用對偶原理 D：通過求主范式的方法。 我們學(xué)習(xí)了一些常用的等價式和永真蘊(yùn)涵式及推理規(guī)則；目的是用命題邏輯解決推理問題；我們介紹了P規(guī)則