《3-命題邏輯-2》由會(huì)員分享，可在線閱讀，更多相關(guān)《3-命題邏輯-2（46頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,上海第二工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院軟件系 王帥,重言式、等價(jià)式和蘊(yùn)含式,公式的分類,一個(gè)命題公式，如果對(duì)于所有指派,命題公式的值都是,T,，則稱該公式為,重言式,(,永真式,),命題公式的值都是,F,，則稱該公式為,矛盾式,(,永假式,),至少存在一種真指派，則稱該公式為,可滿足的,至少存在一種假指派，則稱該公式為,非永真的,例：重言式,P,P,矛盾式,P,P,、,(P,Q),P,P,Q,P,Q,P,Q,T,T,T,T,T,F,F,F,F,T,T,T,F,F,T,T,P,Q,P,Q,P,(,P,Q,),P,T,T

2、,T,F,F,T,F,F,F,F,F,T,F,T,F,F,F,F,T,F,P,Q,P,Q,(P,Q),P,Q,P,Q,(P,Q),(P,Q),T,T,T,F,F,F,F,T,T,F,F,T,F,T,T,T,F,T,F,T,T,F,T,T,F,F,F,T,T,T,T,T,PQ,是可滿足式、是非永真的,(PQ)P,是永假式,(PQ)(PQ),是永真式,公式的分類,定理,任何兩個(gè)重言式的合取或析取，仍然是重言式,任何兩個(gè)矛盾式的合取或析取，仍然是矛盾式,對(duì)一個(gè)重言式的同一分量都用某個(gè)公式置換，得到的仍然是重言式,對(duì)一個(gè)矛盾式的同一分量都用某個(gè)公式置換，得到的仍然是矛盾式,公式的分類,例：,P,P,、

3、,Q,Q,是重言式,所以,(,P,P),(,Q,Q),、,(,P,P),(,Q,Q),都是重言式,P,P,是重言式,用公式,P,Q,置換,P,，得到的,P,Q,(P,Q),也是重言式,等價(jià)公式,定義,給定兩個(gè)命題公式,A,和,B,，設(shè),P,1,P,2,P,n,是所有出現(xiàn)在,A,和,B,中的原子變?cè)艚o,P,1,P,2,P,n,任一組真值指派，,A,和,B,的值都相同，則稱,A,和,B,是等價(jià)的，或邏輯相等的，記作,A,B,由上節(jié)真值表中的例子，可知,P,Q,P,Q,等價(jià)公式,命題公式之間的等價(jià)關(guān)系具有自反性、對(duì)稱性、傳遞性。即：,對(duì)任意公式,A,、,B,、,C,，有：,A,A,若,A,B,，

4、則,B,A,若,A,B,，,B,C,，則,A,C,判斷兩個(gè)命題公式是否等價(jià),真值表法,適用于公式中的變?cè)^少的情況,利用等價(jià)的傳遞性來推導(dǎo)公式（等值演算）,常用的公式 見教材,9,頁基本等式（,1,）,-,（,24,）,特別重要的等價(jià)公式,等價(jià)公式,-,例題,求證,Q,(P(PQ),QP,證明,1,Q,(P(PQ),Q,(P(PQ),(,Q,PP)(,Q,PQ),(,Q,P)T,Q,P,QP,證明,2,根據(jù)吸收律,P(PQ)P,所以,Q,(P(PQ),QP,命題邏輯的等式推理,推理理論,推理是利用一些推理規(guī)則由前提推出結(jié)論的思維過程。,在命題邏輯中，前提是已知的命題公式，結(jié)論是從前提出發(fā)應(yīng)用推

5、理規(guī)則推出的命題公式。,在傳統(tǒng)數(shù)學(xué)中定理的證明均是由前提（已知條件，全是真命題）推出結(jié)論（亦全是真命題），這樣的結(jié)論稱為,合法結(jié)論,。,數(shù)理邏輯有所不同，它著重研究的是推理的過程，這種過程稱為演繹或形式證明。在過程中使用的推理規(guī)則必須是公認(rèn)的且要明確列出，而對(duì)于作為前提和結(jié)論的命題并不一定要求它們?nèi)钦婷}，這樣的結(jié)論稱為,有效結(jié)論,。,命題邏輯的等式推理,等式推理由三部分組成,基本等式,(,是推理的基礎(chǔ),),推理規(guī)則,代入規(guī)則,替換規(guī)則,推理過程,代入規(guī)則,把等價(jià)公式中某個(gè)變?cè)乃谐霈F(xiàn)用另一命題公式代入后，等價(jià)關(guān)系不變。這個(gè)規(guī)則稱為代入規(guī)則,例：因?yàn)?A,B,A,B,用,PQ,代入,A,用

6、,R,S,代入,B,得,到新的等價(jià)公,式,(PQ)(,R,S,),(PQ)(,R,S,),置換規(guī)則,設(shè),A,是一個(gè)命題公式，,C,是,A,的子公式，且,C,D,，若將,A,中出現(xiàn)子公式,C,的某處（未必是全部）替換為,D,后得到公式,B,，則,AB,例如,對(duì)公式,(,P,Q,),R,因?yàn)?PQ,P,Q,由置換規(guī)則即得重言式,(,P,Q,),R,(,P,Q,),R,推理過程,等式推理過程是一個(gè)有命題公式,P,經(jīng)等式推理，最終得到另一個(gè)等價(jià)的命題公式,Q,的過程,等價(jià)公式,-,例題,求證,(P,(QS)(,P,(QS),QS,證明,(P,(QS)(,P,(QS),(,(QS)P)(QS),P),(

7、QS)(P,P),(QS)T,QS,等價(jià)公式,-,例題,求證,Q,(P,Q)P),T,證明,Q,(P,Q)P),Q,(,(P,Q),P),Q,(,P,Q),P),Q,(,P,P)(,Q,P),Q,(T(,Q,P),Q,(,Q,P),(Q,Q),P,T,P,T,等價(jià)公式,-,例題,求證,(A,B)C)(B(DC),(B,(DA)C,證明,：,左邊,(,(A,B)C)(,B,(DC),(,A,BC)(,B,CD),(,BC,A,)(,B,CD),(,BC)(,A,D),右邊,(B,(DA)C,B,(,DA)C,B,(D,A)C,(,BC)(,A,D),左邊,重言式,-,定理,A,、,B,是兩個(gè)命題

8、公式，,A,B,當(dāng)且僅當(dāng),A,B,是重言式,證明,：（,根據(jù)等價(jià)和雙條件的定義證明）,（,1,）若,A,B,，則,A,B,有相同的真值，即,A,B,永真,（,2,）若,A,B,是重言式，即,A,B,永真，所以,A,B,的真值相同，即,A,B,利用該定理，可以證明兩個(gè)命題公式等價(jià),例題,證明,(P,Q)(P,Q),P,證：,(,(P,Q)(P,Q),P,(,(,P,Q)(,P,Q),P,(,P,(Q,Q),P,(,P,F,),P,P,P,T,注意,和,是兩個(gè)完全不同的符號(hào),區(qū)別：,不是命題聯(lián)結(jié)詞。,是命題聯(lián)結(jié)詞,聯(lián)系：,A,B,當(dāng)且僅當(dāng),A,B,是重言式,蘊(yùn)含式,定義,當(dāng)且僅當(dāng),P,Q,是一個(gè)重

9、言式時(shí)，我們稱“,P,蘊(yùn)含,Q”,，記為,P,Q,注意,也不是命題聯(lián)結(jié)詞,判定蘊(yùn)含的方法,分析,要判斷,P,Q,是否成立，也就是判斷,P,Q,是否為永真,根據(jù),P,Q,的真值表,P,Q,P,Q,T,T,T,T,F,F,F,T,T,F,F,T,要想使,PQ,取真，,需要排除第二種情況,方法一：,假定前件,P,為真，檢查此情況下的,Q,是否也為真，如果,Q,也是真，則說明,PQ,取真，,PQ,是重言式，從而有,P,Q,方法二：,假定后件,Q,為假，檢查此情況下的,P,是否有可能為真，如果,P,不可能是真，則說明,PQ,取真，,PQ,是重言式，從而有,P,Q,判定蘊(yùn)含的方法,方法一,設(shè)前件,P,為,

10、T,如果證出后件,Q,為,T,，則,P,Q,永真,方法二,設(shè)后件,Q,為,F,如果證出前件,P,為,F,，則,P,Q,永真,方法三,真值表法,方法四,公式推導(dǎo),判定蘊(yùn)含,-,例題,證明,P,(PQ),Q,方法一,：（前真推后真,）,設(shè),P,(PQ),為,T,，,則,P,為,T,，且,PQ,為,T,P,為,F,，,Q,為,T,P,(PQ),Q,永真,P,(PQ),Q,判定蘊(yùn)含,-,例題,證明,P,(PQ),Q,方法二：（后假推前假）,設(shè),Q,的真值為,F,，,若,P,為,T,，則,P,為,F,P,(PQ),為,F,若,P,為,F,，則,PQ,為,F,P,(PQ),為,F,當(dāng),Q,為,F,時(shí)，無論

11、,P,為,T,或,F,，都有,P,(PQ),為,F,P,(PQ),Q,永真,P,(PQ),Q,判定蘊(yùn)含,-,例題,證明,P,(PQ),Q,方法三：（真值表法）,P,Q,P,PQ,P,(PQ),P,(PQ),Q,T,T,F,T,F,T,T,F,F,T,F,T,F,T,T,T,T,T,F,F,T,F,F,T,判定蘊(yùn)含,-,例題,證明,P,(PQ),Q,方法四：（公式推導(dǎo)）,P,(PQ),Q,(P,(PQ),Q,(P,(PQ),Q,P,(,P,Q),Q,(,P,P)(,P,Q),Q,(T,(,P,Q),Q,(,P,Q),Q,P,(,Q,Q),P,T,T,P,(PQ),Q,判定蘊(yùn)含,-,練習(xí),用各種方

12、法證明,(P,Q)Q,PQ,蘊(yùn)含與等價(jià),P,Q,(PQ)(QP),從這個(gè)式子中可以看出,與,有緊密地聯(lián)系,若,PQ,，則,PQ,永真，即,(PQ)(QP),永真,PQ,永真，,且,QP,永真,PQ,且,QP,反之，若,PQ,且,QP,，則,PQ,永真且,QP,永真,(PQ)(QP),永真，即,PQ,永真,PQ,蘊(yùn)含與等價(jià),-,定理,設(shè),P,、,Q,為任意兩個(gè)命題公式，,P,Q,的充要條件是,P,Q,且,Q,P,蘊(yùn)含的性質(zhì),設(shè),A,、,B,、,C,為任意公式,若,A,B,，且,A,是重言式，則,B,必是重言式,若,A,B,，,AC,，則,A,(B,C),若,A,B,，,CB,，則,(,A,C),

13、B,對(duì)任意公式,A,，有,AA,（蘊(yùn)含的自反性）,若,A,B,，,BC,，則,A,C,（蘊(yùn)含的傳遞性）,蘊(yùn)含的性質(zhì),證明蘊(yùn)含的傳遞性,若,A,B,，,BC,，則,A,C,證明,A,B,，,BC,AB,永真，,BC,永真,AC,AC(,AC)(,BB),(,AC,B)(,ACB),(,A(,BC)(,AB)C),(,A(B,C)(A,B)C),(,AT)(TC),TTT,即,AC,永真，,A,C,常用的蘊(yùn)含公式,23,頁公式（,1,）,-,（,8,）,特別重要的蘊(yùn)含公式,命題邏輯中的蘊(yùn)含推理,蘊(yùn)含式,A,B,表示“如果,A,為真則,B,必為真”,如果把,A,看作前提，,B,作為結(jié)論，則,A,B,

14、可,表示“若前提,A,為真必可推得結(jié)論,B,為真”,我們用符號(hào)“,”表示推理、推出的意思，則,P1,P2,Pn,Q,表示 以,P1,P2,Pn,為前提可以推出結(jié)論,Q,A,B,也就可以表示為,A,B,蘊(yùn)含推理規(guī)則,在蘊(yùn)含推理中之允許使用三種規(guī)則：,P,規(guī)則：前提引入規(guī)則,在推理過程中可以隨時(shí)使用已知前提,T,規(guī)則：推理引入規(guī)則,在推理過程中可使用基本蘊(yùn)含式和等價(jià)式等推理規(guī)則,CP,規(guī)則：附加前提引入規(guī)則,如果待證結(jié)論形如,AB,，則可以把結(jié)論中的前件,A,作為附加前提引入，即把,A,作為已知，把,B,作為結(jié)論,蘊(yùn)含推理,-,例,例：試證,P,Q,Q,R,P,R,。,證明,(1),P,Q,（,P

15、,規(guī)則）,(2),P,（,P,規(guī)則）,(3),Q,（,(1),(2),規(guī)則）,(4),Q,R,（,P,規(guī)則）,(5),R,（,(3),(4),規(guī)則）,蘊(yùn)含推理,-,例,例,:,證明,P,Q,Q,R,P,M,M,R,(,P,Q,),本例要復(fù)雜得多。分析如下,:,1),要證明的結(jié)論是,R,(,P,Q,),因?yàn)?P,Q,是前提,所以只要能推出,R,就可以由,67,推得,R,(,P,Q,);,2),因?yàn)?R,僅含在前提,Q,R,中,且是該蘊(yùn)含式的后件,如果能先推出前件,Q,則可由,69,得出,R,;,3),除前提,Q,R,外,Q,僅含在前提,P,Q,中,若能推得,P,則由,I,52,和前提,P,Q,可

16、得出,Q,;,4),由前提,P,M,和,M,根據(jù),55,即可推得,P,。由此問題得到解決,將以上分析的步反過來按證明的格式書寫,就可以得到證明的過程,證明,(1),M,（,P,）,(2),P,M,（,P,）,(3),P,（,T(1),(2),）,(4),P,Q,（,P,）,(5),Q,（,T(3),(4),）,(6),Q,R,（,P,）,(7),R,（,T(5),(6),）,(8),R,(,P,Q,)(T(7),(4),）,試證,P,(,Q,S),R,P,Q,R,S,證明,(1),P,(,Q,S),（,P,）,(2),P,Q,S,（,T(1),）,(3),Q,P,S,（,T(2),）,(4),Q,(,P,S),（,T(3),）,(5),Q,（,P,）,(6),P,S,（,T(4),(5),）,(7),R,P,（,P,）,(8),R,P,（,T(7),）,(9),R,S,（,T(6),(8),）,該題也可用,CP,規(guī)則證明,蘊(yùn)含推理,-,例,蘊(yùn)含推理,-,例,試證,P,(,Q,S),R,P,Q,R,S,證明,(1),R,P,（,P,）,(2),R,P,（,T(1),）,(3),R,（,P