01-命題邏輯-14~15

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

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,第一章 命題邏輯,30 十月 2024,第四節(jié) 對(duì)偶式與蘊(yùn)涵式,第四節(jié) 對(duì)偶式與蘊(yùn)涵式,一、對(duì)偶式,定義：在給定的僅使用聯(lián)結(jié)詞,、的命題公式,A,中，若把,和互換,，,F,和,T,互換,，得到一個(gè)公式,A,*,，,稱(chēng),A,*,是,A,的,對(duì)偶式,。,稱(chēng),A,和,A,*,互為對(duì)偶式,30 十月 2024,對(duì)偶式,例1.24 求下列公式的對(duì)偶式。,P,(Q,R),P,T,P,Q,P,(Q,R),P,F,P,Q,P,Q,(P,Q),*,=,P,Q,30 十月 2024,對(duì)偶式,對(duì)偶定理：設(shè),A,和,A,*,互為

2、對(duì)偶式，,P,1,，P,2,，P,n,是出現(xiàn)在,A,和,A,*,的原子命題變?cè)瑒t,A (P,1,，P,2,，P,n,),A,*,(,P,1,，,P,2,，,P,n,),A (,P,1,，,P,2,，,P,n,),A,*,(P,1,，P,2,，P,n,),30 十月 2024,A (P,1,，P,2,，,，P,n,),A,*,(,P,1,，,P,2,，,，,P,n,),證明：設(shè)公式,A,中含有聯(lián)結(jié)詞,、的數(shù)目為,L,當(dāng),L0,時(shí)，,A,P,1,A,*,A (P,1,),(P,1,),P,1,A,*,(,P,1,),當(dāng),L1,時(shí)，,A,(P,1,P,2,)（,或,(P,1,P,2,) ，,或,P

3、,1,）,當(dāng),A,(P,1,P,2,),時(shí)，,A,*,(P,1,P,2,),A (P,1,P,2,),(P,1,P,2,),(,P,1,P,2,),A,*,(,P,1,P,2,),當(dāng),A,(P,1,P,2,),時(shí)，,A,*,(P,1,P,2,),A (P,1,P,2,),(P,1,P,2,),(,P,1,P,2,),A,*,(,P,1,P,2,),當(dāng),A, ,P,1,時(shí)，,A,*, ,P,1,A,(,P,1,),(,P,1,),A,*,(,P,1,),30 十月 2024,A (P,1,，P,2,，,，P,n,),A,*,(,P,1,，,P,2,，,，,P,n,),設(shè)當(dāng),Lk-1,時(shí)(,k=1

4、,2,),時(shí),A (P,1,P,2,P,n,),A,*,(,P,1,P,2,P,n,),成立,當(dāng),Lk,時(shí),若,A (P,1,P,2,P,n,),A,1,(P,1,P,2,P,n,),A,2,(P,1,P,2,P,n,),則,L,A1,，L,A2,k-1。,由上面結(jié)論得：,A,1,(P,1,P,2,P,n,),A,1,*,(,P,1,P,2,P,n,),A,2,(P,1,P,2,P,n,),A,2,*,(,P,1,P,2,P,n,),30 十月 2024,A (P,1,，P,2,，,，P,n,),A,*,(,P,1,，,P,2,，,，,P,n,),A (P,1,P,2,P,n,),(,A,1,

5、(P,1,P,2,P,n,),A,2,(P,1,P,2,P,n,), ,A,1,(P,1,P,2,P,n,),A,2,(P,1,P,2,P,n,),A,1,*,(,P,1,P,2,P,n,),A,2,*,(,P,1,P,2,P,n,),A,*,(,P,1,P,2,P,n,),30 十月 2024,A (P,1,，P,2,，,，P,n,),A,*,(,P,1,，,P,2,，,，,P,n,),同理，若,A (P,1,P,2,P,n,),A,1,(P,1,P,2,P,n,),A,2,(P,1,P,2,P,n,),可證,A (P,1,P,2,P,n,),A,*,(,P,1,P,2,P,n,),若,A

6、(P,1,P,2,P,n,), ,A,1,(P,1,P,2,P,n,),可證,A (P,1,P,2,P,n,), ,A,1,*,(,P,1,P,2,P,n,),A,*,(,P,1,P,2,P,n,),由上證明，可得當(dāng),L=K,時(shí)，,A (P,1,P,2,P,n,),A,*,(,P,1,P,2,P,n,)。,證畢,30 十月 2024,對(duì)偶式,例1.25 設(shè),A(P, Q, R) =,P,(,Q,R),求證：,A,*,(,P,Q,R),P,(,Q,R),。,證明：,A(P, Q, R),(,P,(,Q,R) ),P,(,Q,R),又因?yàn)椋?A(P, Q, R),A,*,(,P,Q,R),所以：,

7、A,*,(,P,Q,R),P,(,Q,R),證畢,A (P,1,，P,2,，P,n,),A* (,P,1,，,P,2,，,P,n,),30 十月 2024,對(duì)偶式,對(duì)偶定理：,設(shè),A,和,B,是兩個(gè)命題公式，若,A,B，,則,A,*,B,*,證明：,A,B,意味著,A (P,1,P,2,P,n,),B (P,1,P,2,P,n,),永真。,所以,A (P,1,P,2,P,n,),B (P,1,P,2,P,n,),永真。,因?yàn)?A (P,1,P,2,P,n,),A,*,(,P,1,P,2,P,n,),B (P,1,P,2,P,n,),B,*,(,P,1,P,2,P,n,),因此,A,*,(,P,

8、1,P,2,P,n,),B,*,(,P,1,P,2,P,n,),永真,。,用,P,i,代入,P,i,得到,A,*,(P,1, P,n,),B,*,(P,1, P,n,),永真,因此,A,*,B,*,，,證畢。,30 十月 2024,對(duì)偶式,例1.26 求證：,(P,Q),(,P,Q),P,Q,證明：,(P,Q),(,P,Q),(P,Q),(,P,Q,),E,1,E,11,(P,P,Q),(,Q,P,Q)E,2,E,4,T,(,P,Q)E,6,E,10,P,QE,7,30 十月 2024,對(duì)偶式,例1.27 求證：,(P,Q),(,P,Q),P,Q,證明：,由前面證明得知,(P,Q),(,P,Q

9、), ,P,Q,(,(P,Q),(,P,Q) ),*, (,P,Q ),*,(,P,Q),(,P,Q), ,P,Q,證畢,設(shè),A,和,B,是兩個(gè)命題公式，若,A,B，,則,A*,B*,30 十月 2024,蘊(yùn)涵式,二、蘊(yùn)涵式,定義：設(shè),A,和,B,是兩個(gè)命題公式，若,A,B,是永真式，則稱(chēng),A,蘊(yùn)涵,B，,記做,A,B,，,稱(chēng),A,B,為,蘊(yùn)涵式,或條件永真式。,與,的區(qū)別：,是邏輯聯(lián)結(jié)詞，出現(xiàn)在命題公式中,是一個(gè)符號(hào)，表示兩個(gè)命題公式之間的蘊(yùn)涵關(guān)系,30 十月 2024,蘊(yùn)涵式,蘊(yùn)涵式有以下性質(zhì),：,自反性對(duì)任意公式,A，,有,A,A,傳遞性對(duì)任意公式,A,、,B、C，,若有,A,B， B,

10、C，,則有,A,C,對(duì)任意公式,A,、,B、C，,若有,A,B， A,C,則,A,(B,C),對(duì)任意公式,A,、,B、C，,若有,A,C， B,C,則,(A,B),C,30 十月 2024,蘊(yùn)涵式,等價(jià)式和蘊(yùn)涵式的關(guān)系,：,定理：,設(shè),A,和,B,是兩個(gè)命題公式，,A,B,的充要條件是：,A,B,且,B,A,證明：(1)若,A,B，,則,A,B,是永真式。,因?yàn)椋?A,B,(A,B),(B,A),所以,(A,B),(B,A),是永真式,所以,(A,B),和,(B,A),都是永真式,所以,A,B,且,B,A（,必要條件得證）,P,Q P,是,Q,的,充分條件，,Q,是,P,的,必要條件,30 十

11、月 2024,蘊(yùn)涵式,證明：(2)若,A,B,且,B,A ，,則,(A,B),和,(B,A),都是永真式。,因?yàn)椋?A,B,(A,B),(B,A),所以,A,B,是永真式,所以,A,B（,充分條件得證,）,因此，,A,B,的充要條件是：,A,B,且,B,A,。,證畢,30 十月 2024,蘊(yùn)涵式的證明,蘊(yùn)涵式的證明方法,：,真值表法,若前件為真，能推得后件為真，則此蘊(yùn)涵式為真,若后件為假，能推得前件為假，則此蘊(yùn)涵式為真,指明兩種證明思路,30 十月 2024,蘊(yùn)涵式的證明,例1.28 求證：,Q,(,P,Q),P,證明：,1),真值表法,P Q,P,Q,P,Q,Q,(,P,Q),Q,(,P,Q

12、),P,0 0,1,1,1,1,1,0 1,1,0,1,0,1,1 0,0,1,0,0,1,1 1,0,0,1,0,1,30 十月 2024,蘊(yùn)涵式的證明,2),前件真則后件真,(,Q,(,P,Q),P),設(shè),Q,(,P,Q),為,T，,則,Q,為,T， P,Q,也為,T,可得到：,Q,為,F，,故,P,為,F，,因此,P,為,T。,得證,3),后件假則前件假,設(shè),P,為,F，,則,P,為,T,若,Q,為,T，,則,Q,為,F，,則,Q,(,P,Q),為,F,若,Q,為,F，,則,P,Q,為,F，,則,Q,(,P,Q),為,F。,證畢,30 十月 2024,基本蘊(yùn)涵公式,基本蘊(yùn)涵公式,A、B、

13、C、D,代表任意命題,I,1,化簡(jiǎn)式,A,B,AI,2,A,B,B,I,3,附加式,A,A,B， A,B,A,I,4,附加式變形,A,A,B I,5,B,A,B,I,6,化簡(jiǎn)式變形,(,A,B),A I,7,(,A,B),B,30 十月 2024,基本蘊(yùn)涵公式,I,8,假言推論,A,(,A,B),B,I,9,拒取式,B,(,A,B),A,I,10,析取三段論,A,(,A,B),B,I,11,條件三段論(,A,B),(,B,C),A,C,I,12,雙條件三段論(,A,B),(,B,C),A,C,I,13,合取構(gòu)造二難(,A,B),(,C,D),(,A,C),B,D,A、B、C、D,代表任意命題,

14、如果,A,則,B; A,；所以,B,如果,A,則,B;,B,；所以,A,要么,A,，要么,B,；,A,；所以,B,30 十月 2024,基本蘊(yùn)涵公式,I,14,析取構(gòu)造二難 (,A,B),(,C,D),(,A,C),B,D,特別的，當(dāng),B=D,時(shí)，有(,A,B),(,C,B),(,A,C),B,(,A,B),(,C,B),(,A,C),B,I,15,前后件附加,A,B,(,A,C),(,B,C) A,B,(,A,C),(,B,C),A、B、C、D,代表任意命題,如果,A,則,B;,并且如果,C,則,D;,但是要幺,A,要幺,C;,所以,要幺,B,要幺,D,30 十月 2024,基本蘊(yùn)涵公式,補(bǔ)

15、充：,I,16,A,B,(,B,C),(,A,C),I,17,(,A,B),(,C,D),(,A,C),(,B,D),I,18,A,B,A,B A,B,B,A,I,19,A, B,A,B,A、B、C、D,代表任意命題,A,和,B,分別為真，所以,A,B,為真,30 十月 2024,蘊(yùn)涵式,例1.29 求證：,PQ,P,Q,證明：,1),(PQ),(P,Q), ,(PQ),(,P,Q),(,P,Q),(,P,Q),P,Q,Q,T,2) PQ,QI,2,P,Q I,5,指明兩種證明思路,按定義,套公式,定義：,若,A,B,是,永真式，則稱(chēng),A,蘊(yùn)涵,B,30 十月 2024,第五節(jié) 聯(lián)結(jié)詞的擴(kuò)充與

16、功能完全組,第五節(jié) 聯(lián)結(jié)詞的擴(kuò)充與功能完全組,一、聯(lián)結(jié)詞的擴(kuò)充,合取非,設(shè),P、Q,是任意兩個(gè)原子命題，定義：,P,Q,(P,Q),當(dāng)且僅當(dāng),P,和,Q,的值均為,T,時(shí)，,P,Q,的值為,F P,Q,讀作“,P,合取非,Q,”，,“合取非”又稱(chēng)“,與非,”,30 十月 2024,聯(lián)結(jié)詞的擴(kuò)充,析取非,設(shè),P、Q,是任意兩個(gè)原子命題，定義：,P,Q,(P,Q),當(dāng)且僅當(dāng),P,和,Q,的值均為,F,時(shí)，,P,Q,的值為,T P,Q,讀作“,P,析取非,Q,”，,“析取非”又稱(chēng)“,或非,”,30 十月 2024,聯(lián)結(jié)詞的擴(kuò)充,條件非,設(shè),P、Q,是任意兩個(gè)原子命題，定義：,P,Q,(P,Q),當(dāng)且

17、僅當(dāng),P,為,T,而,Q,為,F,時(shí)，,P,Q,的值為,T P,Q,讀作“,P,條件非,Q,”,30 十月 2024,聯(lián)結(jié)詞的擴(kuò)充,雙條件非,設(shè),P、Q,是任意兩個(gè)原子命題，定義：,P,Q,(P,Q),當(dāng)且僅當(dāng),P,和,Q,的真值不同時(shí)，,P,Q,的值為,T P,Q,讀作“,P,雙條件非,Q,”，,“雙條件非”又稱(chēng)“,異或,”,30 十月 2024,擴(kuò)充聯(lián)結(jié)詞的性質(zhì),與非的性質(zhì),交換律,P,Q,Q,P,冪律,P,P, ,P,(P,Q),(P,Q),P,Q,(P,P),(Q,Q),P,Q,30 十月 2024,擴(kuò)充聯(lián)結(jié)詞的性質(zhì),與非的性質(zhì)（補(bǔ)充）,P,T, ,P,P,F,T,德摩根律,(P,Q)

18、, ,P,Q（,自己證明）,30 十月 2024,擴(kuò)充聯(lián)結(jié)詞的性質(zhì),或非的性質(zhì),交換律,P,Q,Q,P,冪律,P,P, ,P,(P,Q),(P,Q),P,Q,(P,P),(Q,Q),P,Q,30 十月 2024,擴(kuò)充聯(lián)結(jié)詞的性質(zhì),或非的性質(zhì)（補(bǔ)充）,P,F, ,P,P,T,F,德摩根律,(P,Q), ,P,Q（,自己證明）,30 十月 2024,擴(kuò)充聯(lián)結(jié)詞的性質(zhì),例1.30 求證：,P,Q,的對(duì)偶式是,P,Q,證明：,(P,Q),*,(,(P,Q),*,(,P,Q),*,(,P,Q),(P,Q),P,Q,30 十月 2024,擴(kuò)充聯(lián)結(jié)詞的性質(zhì),例1.31 求證：,(,P,Q), ,P,Q,P,

19、Q,證明：,(,P,Q), ,(P,Q),(,P,Q)E,12,P,Q,同理，可證,(,P,Q),P,Q。,30 十月 2024,擴(kuò)充聯(lián)結(jié)詞的性質(zhì),異或的性質(zhì),交換律,P,Q,Q,P,結(jié)合律,P,(Q,R),(P,Q),R,分配律,P,(Q,R),(P,Q),(P,R),冪律,P,P,F， P,P,T,同一律,P,F,P， P,T, ,P,若,P,Q,R，,則,Q,R,P， R,P,Q,且,P,Q,R,F,30 十月 2024,擴(kuò)充聯(lián)結(jié)詞的性質(zhì),我們一共學(xué)習(xí)了9個(gè)聯(lián)結(jié)詞，優(yōu)先級(jí)由高到低為：,、,、,、,、,、,、,由教材,P16,的真值表可知：,這9個(gè)命題聯(lián)結(jié)詞可以表示所有的命題間的聯(lián)結(jié)關(guān)系。

20、,是不是必須用這9個(gè)表示命題間的聯(lián)結(jié)關(guān)系呢？能不能再少一些？,30 十月 2024,聯(lián)結(jié)詞功能完全組,二、聯(lián)結(jié)詞功能完全組,由定義知：,P,Q,(P,Q),P,Q,(P,Q),P,Q,(P,Q),P,Q,(P,Q),因此，,僅使用,、,、,、,就足夠了,30 十月 2024,聯(lián)結(jié)詞功能完全組,又因?yàn)椋?P,Q,(,P,Q),(P,Q)E,12,P,Q,P,QE,11,P,Q, ,(,P,Q )E,5,P,Q, ,(,P,Q ) E,5,僅使用,、,或,、,就足夠了,30 十月 2024,聯(lián)結(jié)詞功能完全組,定義：,設(shè),D,為聯(lián)結(jié)詞集合，若,D,中一個(gè)聯(lián)結(jié)詞可以由,D,中其他的聯(lián)結(jié)詞表示，則該聯(lián)結(jié)

21、詞成為,冗余聯(lián)結(jié)詞,。,設(shè),D,為聯(lián)結(jié)詞集合，若任何命題公式總可以用含有,D,中的聯(lián)結(jié)詞的等值式表示，且,D,中不含有冗余聯(lián)結(jié)詞，則稱(chēng),D,為,全功能聯(lián)結(jié)詞集合,，或,聯(lián)結(jié)詞功能完全組,。,30 十月 2024,聯(lián)結(jié)詞功能完全組,可以證明：,、,，,、,， ,、,， ,， ,都是聯(lián)結(jié)詞功能完全組。,而,、,，,， ,， ,， ,、,都不是聯(lián)結(jié)詞功能完全組,為了表示方便，經(jīng)常使用聯(lián)結(jié)詞組,、,、,30 十月 2024,聯(lián)結(jié)詞功能完全組,例1.32 對(duì)下列公式，試僅用,或,表示,P,解：,P,P,P,P,P,P,Q,解：,P,Q,(P,Q),(P,Q),(P,P),(Q,Q),30 十月 2024,聯(lián)結(jié)詞功能完全組,P,Q,解：,P,Q,(P,Q),(P,Q),(P,P),(Q,Q),P,Q,解：,P,Q, ,P,Q,(P,P),Q,(P,P),Q),(P,P),Q),