邏輯學(xué) 第六講：命題邏輯的自然演繹系統(tǒng)三四節(jié)

1、第三節(jié)：條件證明規(guī)則第四節(jié)：間接證明規(guī)則規(guī)則概述規(guī)則應(yīng)用第六講：命題邏輯的自然演繹系統(tǒng)概論第三節(jié)：條件證明規(guī)則（一）條件證明規(guī)則概述AB /AAB 該推論的有效性可以用真值表方法予以驗證。 我們引如一條新的推演規(guī)則，即條件證明規(guī)則（條件證明規(guī)則（PA-CP）：）： 如果從前提PR和假設(shè)P推出Q，那么，僅從前提PR可以推得PQ。 PR 前提 P 假設(shè) Q 由PR或P推得的命題 PQ 結(jié)論假設(shè)域 （1）AB PR （2）A PA-CP （3）A （2），DN （4）B （1）、（3）， （5）AB （2）、（4） （6）AAB （2）（5），CP 條件證明規(guī)則與其它規(guī)則相比，它的最大特點在于，先引

2、入先引入假設(shè)然后撤出假設(shè)。假設(shè)然后撤出假設(shè)。 顯然，條件證明規(guī)則實際上就是對移出律的運用條件證明規(guī)則實際上就是對移出律的運用。 在證明過程中，無論增加多少前提，都必須撤出，而撤出的在證明過程中，無論增加多少前提，都必須撤出，而撤出的目的在于保證結(jié)論僅由前提得出的。目的在于保證結(jié)論僅由前提得出的。 由條件證明所得的結(jié)論一定是蘊(yùn)涵式，可見，條件證明規(guī)則最適合那些結(jié)論為蘊(yùn)涵式的推論。（二）條件證明規(guī)則的應(yīng)用 例1： PQRP /QR （證明略） 例2： P（QS）RP Q /RS （證明如下） 證明： （1）P（QS） PR （2）RP PR （3） Q PR （4）R PA-CP （5）R （4）

3、，DN （6）P （2）、（5）， （7）QS （1）、（6），MP （8）S （3）、（7），MP （9）RS （4）（8），CP 證畢 證明過程中局部使用條件證明規(guī)則。 需要注意的是，假設(shè)一旦被撤出，假設(shè)域內(nèi)的任何一行都不假設(shè)一旦被撤出，假設(shè)域內(nèi)的任何一行都不能再被使用，否則，就不能保證結(jié)論獨立于假設(shè)。能再被使用，否則，就不能保證結(jié)論獨立于假設(shè)。 例3： 如果外出忘記鎖門則家里被盜，那么社會秩序不好；或者家里被盜或者安心工作；然而，如果外出忘記鎖門，那么不安心工作；所以，社會秩序不好。 P：外出忘記鎖門 Q：家里被盜 R：社會秩序好 S：安心工作（PQ）RQSPS /R 證明： （1）（P

4、Q）R PR （2）QS PR （3） PS PR （4）P PA-CP （5）S （3）、（4），MP （6）Q （2）、（5）， （7）PQ （4）（6），CP （8）R （1）、（7），MP 證畢 有的推論的證明只需一次使用條件證明規(guī)則，但是有的卻需要多次使用條件證明規(guī)則。 例4： P（QR）R Q（PS） /PQ 例5： ABC CDE /A（DEC） （例4，結(jié)論： PQ ）證明：（1）P（QR） PR（2）R PR（3）Q（PS） PR （4）P PA-CP（5）QR （1）、（4），MP（6）Q （2）、（5），MT（7）PQ （4）（6），CP（8）Q PA-CP（9）PS （

5、3）、（8），（10）P （9），（11）QP （8）（10），CP（12）（PQ）（QP） （7）、（11），（13）PQ （12），Ep證畢例5，結(jié)論： A（DEC） 證明：（1）ABC PR（2）CDE PR（3）A PA-CP（4）D PA-CP（5）AB （3），（6）C （1）、（5），MP（7）CD （4）、（6），（8）E （2）、（7），MP（9）EC （6）、（8），（10）DEC （4）（9），CP（11）A（DEC） （3）（10），CP證畢條件證明規(guī)則小結(jié)： 一般來說，使用條件證明規(guī)則的推論具有如下形式：P1（P2（Pn Q） 那么，我們可以把P1，P2 ， Pn這n

6、個前件依次作為假設(shè)；由這些假設(shè)和前提PR推出Q后，再按相反的次序依次撤除它們。 PR 前提 P1 條件假設(shè) P2 條件假設(shè) Pn 條件假設(shè) Q 由前提或假設(shè)推出 PnQ 條件證明 P2（PnQ） 條件證明 P1（P2（PnQ）結(jié)論第四節(jié)：間接證明規(guī)則（一）間接證明規(guī)則概述 間接證明又叫做歸謬證明或反證法（間接證明又叫做歸謬證明或反證法（PA-RAA）。）。 當(dāng)我們要證明某一定理時，先引入該定理的否定為假設(shè)，然先引入該定理的否定為假設(shè)，然后由這一假設(shè)推出矛盾。由于矛盾是不可能的，所以假設(shè)一后由這一假設(shè)推出矛盾。由于矛盾是不可能的，所以假設(shè)一定錯誤，即該定理的否定不成立，由此就間接證明了該定理定錯

7、誤，即該定理的否定不成立，由此就間接證明了該定理成立。成立。 間接證明規(guī)則可以表達(dá)為如下模式： PR 前提 P 假設(shè) AA 由前提或假設(shè)推出的邏輯矛盾 P 結(jié)論 所謂的邏輯矛盾，主要有以下這些：所謂的邏輯矛盾，主要有以下這些： 1，推出的結(jié)果與已知條件矛盾。 2，推出的結(jié)果與已知定義矛盾。 3，推出的結(jié)果與已知公理矛盾。 4，推出的結(jié)果與已知定理矛盾。 5，推出的結(jié)果與所做假設(shè)矛盾。 6，推出兩個互相矛盾的結(jié)果。 一般來說，如下類型的待證命題更適合采用間接證明規(guī)則：一般來說，如下類型的待證命題更適合采用間接證明規(guī)則： 1，某些初始命題。 2，否定性命題。 3，以簡單命題為結(jié)論的命題。 4，結(jié)論

8、與前提沒有關(guān)系，結(jié)論是重言式的命題。（二）間接證明規(guī)則應(yīng)用例1 （證明略）PQR（RS）PT /TS例2 （證明略）P（QR）RP /QR例3：PQ（DP）（QR）P /（P（DR）例4：PQRS（PTR ）（IRS） /（IT）證明：（1）PQ（DP） PR（2）（QR）P PR （3）P（DR） PA-RAA（4）P （3），（5）P （4），DN（6）（QR） （2）、（5），MT（7）QR （6），Impl、DeM（8）Q （7），（9）PQ （4）、（8），（10）DP （1）、（9），MP（11）R （7），（12）DR （3），（13）D （11）、（12），（14）P （10）

9、、（13），MP（15）PP （4）、（14）， （16） （P（DR） （3）（15），RAA證畢證明：（1）PQR PR（2）S PR（3） （PTR ）（IRS） PR（4） （IT） PA-RAA（5） IT （4），DN（6）P PA-CP（7）PQ （6），（8）R （1）、（7），MP（9）T （5），（10）TR （8）、（9），（11） PTR （6）（10），CP（12） IRS （3）、（11），MP（13）I （5），（14） RS （12）、（13），MP（15）S （14）， （16）SS （2）、（15）， （17） （IT） （4）（16）RAA證畢 補(bǔ)充材料一

10、：證明重言式證明重言式 有一種命題的真是無條件的，不依賴于其它命題。這樣的命題就是重言式。 1，用條件證明方法證明重言式。，用條件證明方法證明重言式。 例：證明A（BA）是重言式。 2，用間接證明方法證明重言式。，用間接證明方法證明重言式。 例：證明A（AB）是重言式。 重言式的形式證明相當(dāng)于一個只有結(jié)論而沒有前提的推理的重言式的形式證明相當(dāng)于一個只有結(jié)論而沒有前提的推理的有效性。有效性。 補(bǔ)充材料二：無效推理的證明無效推理的證明 如果推理無效，那么運用推理規(guī)則不可能從前提推演出結(jié)論。這意味著形式證明方法不能證明推理是無效的。 1，用真值表證明推理是無效的。，用真值表證明推理是無效的。 如果一

11、個推理是無效的，至少存在一組賦值使得推理的前提真而結(jié)論假。 例：用真值表判定下列推理是否有效：C（AB），AC /BC 2，用歸謬賦值法證明推理的有效或無效。，用歸謬賦值法證明推理的有效或無效。 歸謬賦值法的基本思路同間接證明方法類似。我們要證明一個推理是有效的，先假設(shè)它無效，這就是歸謬。 例：判定下列推理是否有效：A（BC），（CD）F /AF 3，證明公式集合的協(xié)調(diào)性。，證明公式集合的協(xié)調(diào)性。（附錄）練習(xí)題： 一，用條件證明規(guī)則構(gòu)造以下推論： 1，JK /JJK 2，ZCB，QB /ZQ 3，P（QR），P（RQ） /P（QR） 二，使用間接證明構(gòu)造以下推論： 1，PQ，PQ /P 2，F(xiàn)N，NBJ，BFD /D 3，PR，QS，PQ /RS思考題： 根據(jù)你的總結(jié)，完成一個形式證明還有哪些策略和技巧？本講小結(jié)第六講