《第一章命題演算基礎(chǔ)》由會員分享，可在線閱讀，更多相關(guān)《第一章命題演算基礎(chǔ)（33頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)1.3 1.3 范式及其應用范式及其應用 1.3.1 1.3.1 范式范式介紹命題演算公式的規(guī)范形式介紹命題演算公式的規(guī)范形式:l 析取范式析取范式l 合取范式合取范式討論范式與成真解釋、成假解釋的關(guān)系。討論范式與成真解釋、成假解釋的關(guān)系。合取式、析取式合取式、析取式定義定義1 命題變元、或者命題變元的否定、或由它們命題變元、或者命題變元的否定、或由它們利用合取詞組成的合式公式稱為利用合取詞組成的合式公式稱為合取式合取式。定義定義2 命題變元、或者命題變元的否定、或由它們命題變元、或者命題變元的否定、或由它們利用析取詞組成的合式公式稱為利用析取詞組成的合式

2、公式稱為析取式析取式。例例 顯然，顯然， P， P，P Q， P QR 均為合取式；均為合取式； P， P，P Q， P QR 均為析取式。均為析取式。(一一) 解釋與合取式、析取式之間的關(guān)系解釋與合取式、析取式之間的關(guān)系 定理定理1 任給一個成真解釋有且僅有一個合取式任給一個成真解釋有且僅有一個合取式與之對應；與之對應； 任給一個成假解釋有且僅有任給一個成假解釋有且僅有一個析取式與之對應。一個析取式與之對應。例例 成真解釋成真解釋(P，Q，R)= (T,F,T) 成假解釋成假解釋(P，Q，R)= (F,F,T)合取式合取式PQ R析取式析取式P QR析取范式、合取范式析取范式、合取范式定義定

3、義3 形如形如A1 A2 An的公式稱為的公式稱為析取范式析取范式， 其中其中Ai(i=1,2,n)為合取式。為合取式。定義定義4 形如形如A1 A2 An的公式稱為的公式稱為合取范式合取范式， 其中其中Ai(i=1,2,n)為析取式。為析取式。例例 P， P，P Q，P Q ，( P Q) (SR) 均為析取范式。均為析取范式。 P， P，P Q，P Q ， ( P Q) (SR)均為合取范式。均為合取范式。例例: 考察公式考察公式 =PQ的的析取范式析取范式對應于兩個合取式為對應于兩個合取式為 PQ, P Q于是，有于是，有 = (PQ) ( P Q)P Q P QT T TT F FF

4、T FF F T有兩個成真解釋：有兩個成真解釋： (T, T), (F, F)例例: 考察公式考察公式 =PQ的的合取范式合取范式對應析取式為對應析取式為 PQ, P Q于是，有：于是，有： = ( PQ) (P Q)P Q P QT T TT F FF T FF F T成假解釋成假解釋 (T, F), (F, T) 定理定理2 任何命題演算公式均可以化為合任何命題演算公式均可以化為合取范式，也可以化為析取范式。取范式，也可以化為析取范式。證明：證明： (1)設(shè)公式設(shè)公式 為永真公式為永真公式 =PP (2)設(shè)公式設(shè)公式 為永假公式為永假公式 =P P證明證明(3)： 設(shè)公式設(shè)公式 既非永真又

5、非永假。既非永真又非永假。設(shè)公式設(shè)公式 的成真解釋為的成真解釋為 1， 2， n， 成假解釋為成假解釋為 1， 2， t。根據(jù)解釋和范式的關(guān)系知：根據(jù)解釋和范式的關(guān)系知：對應于成真解釋對應于成真解釋 1， 2， n的合取式為的合取式為 1， 2， n對應于成假解釋對應于成假解釋 1， 2， t的析取式為的析取式為 1， 2， t而公式而公式 12 n的成真解釋為的成真解釋為 1， 2， n；公式公式 12 t的成假解釋為的成假解釋為 1， 2， t。根據(jù)根據(jù)兩個公式邏輯等價的定義兩個公式邏輯等價的定義知知 = 12 n = 12 t故公式故公式 既可表示為析取范式又可表示為合取范式。既可表示為

6、析取范式又可表示為合取范式。(二二) 析取范式和合取范式的求解方法析取范式和合取范式的求解方法 等價變換法等價變換法利用等價公式進行變換，利用等價公式進行變換，將范式變換出來。將范式變換出來。解解 釋釋 法法利用所有成真解釋或成假利用所有成真解釋或成假解釋，寫出范式。解釋，寫出范式。等價變換法等價變換法(1)去蘊含詞與等價詞：去蘊含詞與等價詞： PQ = P Q PQ =（ P Q） （P Q）(2)否定深入：否定深入： (P Q)= PQ (P Q)= PQ， P = P(3)重復使用分配律：重復使用分配律： P (Q R)=(P Q ) (P R) P (Q R)=(P Q ) (P R)

7、解釋法解釋法(1) 求所有成真解釋、成假解釋；求所有成真解釋、成假解釋；(2) 寫出成真解釋對應的合取式、寫出成真解釋對應的合取式、 成假解釋對應的析取式；成假解釋對應的析取式；(3) 把所有的合取式用析取詞聯(lián)結(jié)起來就構(gòu)成析把所有的合取式用析取詞聯(lián)結(jié)起來就構(gòu)成析取范式，把所有的析取式用合取詞聯(lián)結(jié)起取范式，把所有的析取式用合取詞聯(lián)結(jié)起來就構(gòu)成合取范式。來就構(gòu)成合取范式。例例 求公式的范式求公式的范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取范式析取范式 = P ( QR) 合取范

8、式合取范式解：解：P=T時時, 原式原式= (TQ) (RQ)T)= Q R P=F時時, 原式原式= (FQ) (RQ)F)=F 所以有所以有: 成真解釋為：成真解釋為：(P,Q,R)=(T,F,T), (T,F,F), (T,T,F) 成假解釋為：成假解釋為：(P,Q,R)=(T,T,T), (F, , )例例 求公式的范式求公式的范式 (PQ)(RQ)P)于是析取范式為于是析取范式為: (PQ R) (P Q R) (P Q R) 合取范式為：合取范式為： ( P QR) P范式不唯一性范式不唯一性例例 求公式的范式求公式的范式 (PQ)(RQ)P)解解1： 原式原式=(PQ) (PR)

9、 析取范式析取范式 = P ( QR) 合取范式合取范式解解2: 析取范式為析取范式為: (PQ R) (P Q R) (P Q R) 合取范式為：合取范式為： ( P QR) P1.3.2 1.3.2 主范式主范式定義定義1 對于對于n個命題變元個命題變元P1，P2，Pn，公式，公式 Q1 Q2 Qn 稱為稱為極小項極小項，其中，其中Qi=Pi或或 Pi(i=1，n)。例例 由兩個命題變元由兩個命題變元P，Q組成的極小項有四個，它們組成的極小項有四個，它們分別為：分別為： PQ P QPQ P Q(一一) 主析取范式主析取范式三個命題變元三個命題變元P、Q和和R可構(gòu)造可構(gòu)造8個極小項個極小項

10、把命題變元的否定形式看成把命題變元的否定形式看成0，肯定形式看成，肯定形式看成1，則每，則每個極小項對應一個二進制數(shù)，也對應一個十進制數(shù)。個極小項對應一個二進制數(shù)，也對應一個十進制數(shù)。它們對應如下：它們對應如下： PQR 與與000 或或0對應，簡記為對應，簡記為 m0 PQ R 與與001 或或1對應，簡記為對應，簡記為 m1 P QR 與與010 或或2對應，簡記為對應，簡記為 m2 P Q R 與與011 或或3對應，簡記為對應，簡記為 m3 PQR 與與100 或或4對應，簡記為對應，簡記為 m4 PQ R 與與101 或或5對應，簡記為對應，簡記為 m5 P QR 與與110 或或6

11、對應，簡記為對應，簡記為 m6 P Q R 與與111 或或7對應，簡記為對應，簡記為 m7主析取范式主析取范式 定義定義2 僅有極小項構(gòu)成的析取范式稱為僅有極小項構(gòu)成的析取范式稱為主析取范式主析取范式。定理定理1 任何一個合式公式，均有惟一的一個主析取范式任何一個合式公式，均有惟一的一個主析取范式與該合式公式等價。與該合式公式等價。主析取范式就是主析取范式就是公式的所有完全成真解釋對應的極小項的析取。公式的所有完全成真解釋對應的極小項的析取。 求主析取范式的兩種方法(1)解釋法解釋法: 根據(jù)公式的所有完全成真解釋，求出與這些根據(jù)公式的所有完全成真解釋，求出與這些成真解釋對應的合取式，所有合取

12、式的析取就為成真解釋對應的合取式，所有合取式的析取就為公式的主析取范式。公式的主析取范式。(2)等價變換法等價變換法: 將析取范式中的每一個合取式用將析取范式中的每一個合取式用AA填填滿命題變元，然后用等價公式進行變換，消去相滿命題變元，然后用等價公式進行變換，消去相同部分，即得公式的主析取范式。同部分，即得公式的主析取范式。例例 求公式的求公式的主析取范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取范式析取范式 =(PQ (R R) (P (QQ)R) = (PQ R) (PQ

13、 R) (P QR) =101 100 110=4 5 6解：解：P=T時時, 原式原式= (TQ) (RQ)T)= Q R P=F時時, 原式原式= (FQ) (RQ)F)=F 所以有所以有: 成真解釋為：成真解釋為：(P,Q,R)=(T,F,T), (T,F,F), (T,T,F) 例例 求公式的求公式的主析取范式 (PQ)(RQ)P)于是主析取范式為于是主析取范式為: (PQ R) (P Q R) (P Q R) =101 100 110 =4 5 6(二二) 主合取范式主合取范式定義定義3 對于對于n個命變元個命變元P1，P2，Pn，公式，公式 Q1 Q2 Qn 稱為稱為極大項極大項，

14、其中，其中Qi=Pi或或 Pi(i=1，n)。例例 由兩個命題變元由兩個命題變元P，Q組成的極大項有四個，它們組成的極大項有四個，它們分別為：分別為： PQ P Q PQ P Q三個命題變元三個命題變元P、Q和和R可構(gòu)造可構(gòu)造8個極大項個極大項 把命題變元的否定形式看成把命題變元的否定形式看成1，肯定形式看成，肯定形式看成0，則每個，則每個極大項對應一個二進制數(shù)，也對應一個十進制數(shù)。它們極大項對應一個二進制數(shù)，也對應一個十進制數(shù)。它們對應如下：對應如下： P Q R 與與000 或或0對應，簡記為對應，簡記為 M0 P QR 與與001 或或1對應，簡記為對應，簡記為 M1 PQ R 與與01

15、0 或或2對應，簡記為對應，簡記為 M2 PQR 與與011 或或3對應，簡記為對應，簡記為 M3 P Q R 與與100 或或4對應，簡記為對應，簡記為 M4 P QR 與與101 或或5對應，簡記為對應，簡記為 M5 PQ R 與與110 或或6對應，簡記為對應，簡記為 M6 PQR與與111 或或7對應，簡記為對應，簡記為 M7主合取范式主合取范式定義定義4 僅有極大項構(gòu)成的合取范式稱為僅有極大項構(gòu)成的合取范式稱為主合取范式主合取范式。 定理定理2 任何一個合式公式，均有惟一的一個主合取范式與任何一個合式公式，均有惟一的一個主合取范式與該合式公式等價。該合式公式等價。主合取范式就是主合取

16、范式就是公式的所有完全成假解釋對應的極大項的合取。公式的所有完全成假解釋對應的極大項的合取。求主合取范式的兩種方法求主合取范式的兩種方法(1)解釋法解釋法 根據(jù)公式的所有完全成假解釋，求出與這些根據(jù)公式的所有完全成假解釋，求出與這些成假解釋對應的析取式，所有析取式的合取就為成假解釋對應的析取式，所有析取式的合取就為公式的主合取范式。公式的主合取范式。(2)等價變換法等價變換法 將合取范式中的每一個析取式用將合取范式中的每一個析取式用AA填滿命題變元，然后用等價公式進行變換，消去填滿命題變元，然后用等價公式進行變換，消去相同部份，即得公式的主合取范式。相同部份，即得公式的主合取范式。例例 求公式

17、的主合取范式求公式的主合取范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取范式析取范式 = P ( QR) 合取范式合取范式 =(P (QQ) (RR) ( QR) (PP) =(P Q R) (P QR) (PQ R) (PQR) ( PQR) =000 001 010 011 111=0 1 2 3 7解：解：P=T時時, 原式原式= (TQ) (RQ)T)= Q R P=F時時, 原式原式= (FQ) (RQ)F)=F 所以有所以有: 成假解釋為：成假解釋為：(P,Q,R)

18、=(T,T,T), (F, , )例例 求公式的主合取范式求公式的主合取范式 (PQ)(RQ)P)于是于是主合取范式主合取范式= ( PQR) (PQR) (PQ R) (P QR) (P Q R) =111 011 010 001 000 =0 1 2 3 7(F,TT),(F,T,F),(F,F,T),(F,F,F)例例 試求試求 =(PR)( P ( Q R) 的主析取范式和主合取范式的主析取范式和主合取范式解解: =( PR) ( P( QR)(P( ( QR)（去蘊涵詞、等價詞）（去蘊涵詞、等價詞） =( PR) ( P QR) (PQ) (P R)（化簡）（化簡） =(P R) (

19、 P QR) (PQ) (P R)（去蘊涵詞）（去蘊涵詞） = (P R) ( P QR)(PQ) =(110 100) 001 (111 110) =(1,4,6,7)解解(續(xù)續(xù)): 已經(jīng)得到已經(jīng)得到主析取范式如下主析取范式如下: = ( P QR)(PQ)(P R)=( PP)( PQ)( QP) ( QQ)(PR)(QR)(P R) =( PQ)( QP)(PR)(QR) (P R) =(T( PQ R) ( QP)(P Q R) )(PR) T) (PQR) T) =101 (010 011) (010 000) 000 =(0,2,3,5)例例 試求試求 =(PR)( P ( Q R

20、) 的主析取范式和主合取范式的主析取范式和主合取范式主合取范式和主析取范式的關(guān)系主合取范式和主析取范式的關(guān)系(1)緊密相關(guān)性：緊密相關(guān)性： 一個公式的主合取范式和主析取范式是緊密相關(guān)的。一個公式的主合取范式和主析取范式是緊密相關(guān)的。 如例： = (PR)( P ( Q R) = = (PR)( P ( Q R) =(2) 惟一性惟一性: 任何一個命題演算公式，具有惟一的主合取范式和主任何一個命題演算公式，具有惟一的主合取范式和主析取范式，因此如果兩個公式具有相同的主析取范式析取范式，因此如果兩個公式具有相同的主析取范式或主合取范式，則稱兩公式邏輯等價?；蛑骱先》妒?，則稱兩公式邏輯等價。)5 ,

21、 3 , 2 , 0() , 7 , 6 , 4 , 1 (1.3.3 1.3.3 范式的應用范式的應用你面前有黑白兩扇門，其中一扇門后有寶藏，你面前有黑白兩扇門，其中一扇門后有寶藏，一扇門后有吃人妖怪。一扇門后有吃人妖怪。在這兩扇門前面，有兩個人，這兩個人都知道在這兩扇門前面，有兩個人，這兩個人都知道哪扇門后有寶藏，哪扇門后有吃人妖怪，而這哪扇門后有寶藏，哪扇門后有吃人妖怪，而這兩個人呢，一個人只說真話，一個人只說假話兩個人呢，一個人只說真話，一個人只說假話。你只能問這兩個人每人一個問題。你怎么問才你只能問這兩個人每人一個問題。你怎么問才能找到寶藏？能找到寶藏？蘋果考題：寶藏在哪里蘋果考題：

22、寶藏在哪里?問其中一個人：你的同伴怎么回答問其中一個人：你的同伴怎么回答“哪扇門后有寶藏哪扇門后有寶藏”？令令 P：被問人說真話；：被問人說真話； Q：被問人回答是：被問人回答是“黑門黑門”； R：同伴的回答是：同伴的回答是“黑門黑門” ； S：黑門后有：黑門后有寶藏寶藏。根據(jù)題意可得真值表如圖所示。根據(jù)題意可得真值表如圖所示。根據(jù)真值表知，主析取范式為：根據(jù)真值表知，主析取范式為： S=(PQ) ( PQ) =(PP)Q = Q因此被問人回答是因此被問人回答是“黑門黑門”時，此門后一定沒有時，此門后一定沒有寶藏寶藏。P Q R ST T T (假話假話) FT F F (假話假話) TF T

23、 F (真話真話) FF F T (真話真話) T結(jié)論結(jié)論: 否定被問人的回答否定被問人的回答!例例 從從A,B,C三人中挑選三人中挑選12人去完成一個任務。選派時人去完成一個任務。選派時要滿足以下條件：要滿足以下條件： （）若（）若A去，則去，則C同去。同去。 （）若（）若B去，則去，則C不能去。不能去。 （）若（）若C不去，則不去，則A或或B可以去?？梢匀ァ?問應如何選派他們?nèi)?？問應如何選派他們?nèi)?？解? 選派條件可以表述并利用分配率化簡為選派條件可以表述并利用分配率化簡為: (AC)(B C)( C(AB) = ( AC)( B C)(ABC) = ( A B) ( A C) ( BC)

24、(ABC) = ( A BC) ( AB C) (A BC) 可知，選派方案有可知，選派方案有3種：種： （1）C去，而去，而A,B都不去。都不去。 （2）B去，而去，而A,C都不去。都不去。 （3）A,C去，而去，而B不去。不去。例例 從從A,B,C三人中挑選三人中挑選12人去完成一個任務。選派時人去完成一個任務。選派時要滿足以下條件：要滿足以下條件： （）若（）若A去，則去，則C同去。同去。 （）若（）若B去，則去，則C不能去。不能去。 （）若（）若C不去，則不去，則A或或B可以去?？梢匀?。 問應如何選派他們?nèi)ィ繂枒绾芜x派他們?nèi)?？另解另? 選派條件可以表述并利用分配率化簡為選派條件可以表述并利用分配率化簡為: (AC)(B C)( C(AB) = ( AC)( B C)(ABC) =100110111011000=001010101 = ( A BC) ( AB C) (A BC) 可知，選派方案有可知，選派方案有3種：種： （1）C去，而去，而A,B都不去。都不去。 （2）B去，而去，而A,C都不去。都不去。 （3）A,C去，而去，而B不去。不去。