1、第一章 命題演算基礎,1.1 命題和聯(lián)結詞 1.2 真假性 1.3 范式及其應用 1.3.1 范式 1.3.2 主范式 1.3.3 范式的應用,合取式、析取式,定義1 命題變元、或者命題變元的否定、或由它們利用合取詞組成的合式公式稱為合取式。 定義2 命題變元、或者命題變元的否定、或由它們利用析取詞組成的合式公式稱為析取式。 例 顯然， P，P，PQ，PQR 均為合取式； P，P，PQ，PQR 均為析取式。,(一) 解釋與合取式、析取式之間的關系,定理1 任給一個成真解釋有且僅有一個合取式與之對應； 任給一個成假解釋有且僅有一個析取式與之對應。 反之亦然。,例 成真解釋(P，Q，R)= (T,

2、F,T) 成假解釋(P，Q，R)= (F,F,T),合取式PQR,析取式PQR,析取范式、合取范式,定義3 形如A1 A2 An的公式稱為析取范式， 其中Ai(i=1,2,n)為合取式。 定義4 形如A1 A2 An的公式稱為合取范式， 其中Ai(i=1,2,n)為析取式。 例 如：P，P，PQ，PQ ，(PQ)(SR) 均為析取范式。 如：P，P，PQ，PQ ， (PQ)(SR)均為合取范式。,例: 考察公式 =PQ的析取范式,有兩個成真解釋： (T, T), (F, F), 分別對應于兩個合取式為 PQ, PQ 于是，有 = (PQ) (PQ),例: 考察公式 =PQ的合取范式,成假解釋

3、(T, F), (F, T), 對應析取式為 PQ, PQ 于是，有： = (PQ) (PQ),定理2 任何命題演算公式均可以化為合取范式，也可以化為析取范式。,證明： (1)設公式為永真公式 因為任何一個永真公式均與公式PP邏輯等價，而PP既是析取范式又是合取范式，所以公式既可表示為析取范式又可表示為合取范式。 (2)設公式為永假公式 因為任何一個永假公式均與公式PP邏輯等價，而PP既是析取范式又是合取范式，所以公式既可表示為析取范式又可表示為合取范式。,定理2證明(續(xù)),(3)設公式既非永真又非永假 設公式的成真解釋為1，2，n， 成假解釋為1，2，t。 根據(jù)解釋和范式的關系知： 對應于成

4、真解釋1，2，n的合取式為 1，2，n 對應于成假解釋1，2，t的析取式為 1，2，t 而公式 12n的成真解釋為 1，2，n； 公式12t的成假解釋為 1，2，t。 根據(jù)兩個公式邏輯等價的定義知 =12n =12t 故公式既可表示為析取范式又可表示為合取范式。,(二) 析取范式和合取范式的求解方法,等價變換法 解釋法,等價變換法,(1)利用前面介紹的等價公式消去公式中的聯(lián)結詞“”和“”； (2)重復使用等值公式，把否定詞內移到命題變元上，等值公式如下： (P Q)= PQ (P Q)= PQ， P = P (3)重復使用分配律將公式化為合取式的析取或析取式的合取，等值公式如下： P (QR)

5、=(P Q )(P R) P (QR)=(P Q )(P R),解釋法,(1)求出公式的所有成真(假)解釋； (2)寫出所有成真(假)解釋對應有的合(析)取式； (3)把所有的合(析)取式用析(合)取詞聯(lián)結起來就構成析(合)取范式。,例(p11) 求公式的范式 (PQ)(RP)(RQ)P),解法一：求析取范式 原式=(PQ)(RP)(RQ)P) =(PQ)(RP)(RQ) P) =(PQ)(RP)(RQ)P) =(PQ)(RP)(PR)(PQ) =(PQ)(PR)(P R),解法一：再求合取范式 原式= (PQ)(PR)(P R) (析取范式) = (P(QR)(P R) = (P(P R)(

6、QR)(P R) (分配率) = (PP) (PR)(P QR)(QR R) = (PR)(P QR),例(p11) 求公式的范式 (PQ)(RP)(RQ)P),例(p11) 求公式的范式 (PQ)(RP)(RQ)P),另解: 由析取范式，有 = (PQ) (PR) (PR) 于是， = (PQ) (PR) (PR) = (PQR) (P R) 所以 =(PQR) (PR),解法二： 先求公式的所有成真解釋和成假解釋(見下一張) 成真解釋為：(P,Q,R)=(T,F,), (F,T), (T,F) 成假解釋為：(P,Q,R)=(T,T,T), (F,F) 由成真解釋可分別求出對應的合取式： P

7、Q，P R，PR 公式的析取范式即為上面合取式的析?。?(PQ)(PR)(P R) 由成假解釋可分別求出對應的析取式： P QR，PR 公式的合取范式為上面析取式的合?。?(P QR)(PR),例(p11) 求公式的范式 (PQ)(RP)(RQ)P),解：P=T時, 原式=(TQ)(RT)(RQ)T) =(QT)(RQ) =Q(RQ) =Q (RQ) = QR P=F時, 原式=(FQ)(RF)(RQ)F) =(T R)T =( R)=R 所以有: 成真解釋為：(P,Q,R)=(T,F,), (F,T), (T,F) 成假解釋為：(P,Q,R)=(T,T,T), (F,F),6？,例(補) 求

8、公式的成真(假)解釋 (PQ)(RP)(RQ)P),例(補) 求公式的成真(假)解釋 (PQ)(RP)(RQ)P),PQ,P,Q,RP,R,P,P Q,R,Q,Q,P,P,(P Q) P,(PQ)(RP),(PQ)(RP),(P Q) P),另解：,所以有: 成真解釋為：(P,Q,R)=(T,F,), (F,T), (T,F) 成假解釋為：(P,Q,R)=(T,T,T), (F,F),例(補) 求公式的成真(假)解釋 (PQ)(RP)(RQ)P),范式不唯一性,例 求(PQ)P的析取范式和合取范式 解: (PQ)P=(PQ)P =(PQ)P 析取范式 = P 析取范式 (PQ)P=(PQ)P

9、析取范式 =P(QP) 合取范式 =P 合取范式,第一章 命題演算基礎,1.1 命題和聯(lián)結詞 1.2 真假性 1.3 范式及其應用 1.3.1 范式 1.3.2 主范式 1.3.3 范式的應用,(一) 主析取范式,定義1 對于n個命題變元P1，P2，Pn，公式 Q1Q2Qn 稱為極小項，其中Qi=Pi或Pi(i=1，n)。,例 由兩個命題變元P，Q組成的極小項有四個，它們分別為： PQ PQ PQ PQ,三個命題變元P、Q和R可構造8個極小項,把命題變元的否定形式看成0，肯定形式看成1，則每個極小項對應一個二進制數(shù)，也對應一個十進制數(shù)。它們對應如下： PQR 與000 或0對應，簡記為 m0

10、PQR 與001 或1對應，簡記為 m1 PQR 與010 或2對應，簡記為 m2 PQR 與011 或3對應，簡記為 m3 PQR 與100 或4對應，簡記為 m4 PQR 與101 或5對應，簡記為 m5 PQR 與110 或6對應，簡記為 m6 PQR 與111 或7對應，簡記為 m7,n個命題變元組成的極小項有2n個,公式的每一個完全成真解釋對應一個極小項 公式的所有完全成真解釋對應極小項的析取,例: 考察公式 =PQ 有兩個成真解釋： (T, T), (F, F) 分別對應于兩個極小項(合取式)為 PQ, PQ 于是，有 = (PQ) (PQ),主析取范式,定義2 僅有極小項構成的析

11、取范式稱為主析取范式。 定理1 任何一個合式公式，均有惟一的一個主析取范式與該合式公式等價。,主析取范式就是 公式的所有完全成真解釋對應極小項的析取。,求主析取范式的兩種方法,(1)解釋法: 根據(jù)公式的所有完全成真解釋，求出與這些成真解釋對應的合取式，所有合取式的析取就為公式的主析取范式。 (2)等價變換法: 將析取范式中的每一個合取式用AA填滿命題變元，然后用等價公式進行變換，消去相同部分，即得公式的主析取范式。,例(p12) 求 (PR)(P(Q R) 的主析取范式。,解法1：等價變換法 原式 =(PR)(P Q R)(P(Q R) (去蘊涵詞、等價詞) =(PR)(P Q R)(P(Q

12、R) （否定深入） =(PR)(P Q R)(PQ)(PR) （分配率） =(P Q R)(PQR)(PR) (分解后，六項剩三項） =(P Q R)(PQR)(PR)(QQ),例(p12) 求 (PR)(P(Q R) 的主析取范式。,解法1：等價變換法（續(xù)上頁） 原式 =(P Q R)(PQR)(PR)(QQ) =(P Q R)(PQR)(PQR) (PQ R) =(P Q R)(PQR)(PQR) = 010 101 111 = m2 m5 m7 =,去等價詞的兩個公式需要靈活運用，才能將原式快速轉化為析取范式！,解法2：解釋法 公式的所有成真解釋為： (P，Q，R)=(F，T，F(xiàn)),(T

13、，F(xiàn)，T),(T，T，T) 對應于成真解釋的極小項為： P Q R , PQR , PQR 故主析取范式為： (P Q R)(PQR)(PQR),例(p12) 求 (PR)(P(Q R) 的主析取范式。,例(p12) 補求(PR)(P(Q R) 的解釋,解: P=T時, 原式= (TR) (T (Q R) = R(Q R) = R (Q R) = (R Q) R = R P=F時, 原式 = (FR) (F (Q R) = T(Q R) = Q R 于是, 所有成真解釋為： (T，*，T) 、(F，T，F(xiàn)) 所有成假解釋為： (T，*，F(xiàn))、(F，F(xiàn)，*)、(F，T，T),(二) 主合取范式,

14、定義3 對于n個命變元P1，P2，Pn，公式 Q1Q2Qn 稱為極大項，其中Qi=Pi或Pi(i=1，n)。,例 由兩個命題變元P，Q組成的極大項有四個，它們分別為： PQ PQ PQ PQ,三個命題變元P、Q和R可構造8個極大項,把命題變元的否定形式看成1，肯定形式看成0，則每個極大項對應一個二進制數(shù)，也對應一個十進制數(shù)。它們對應如下： PQR 與000 或0對應，簡記為 M0 PQR 與001 或1對應，簡記為 M1 PQR 與010 或2對應，簡記為 M2 PQR 與011 或3對應，簡記為 M3 PQR 與100 或4對應，簡記為 M4 PQR 與101 或5對應，簡記為 M5 PQR

15、 與110 或6對應，簡記為 M6 PQR與111 或7對應，簡記為 M7,n個命題變元組成的極大項有2n個,公式的每一個完全成假解釋對應一個極大項 公式的所有完全成假解釋對應極大項的合取,例: 考察公式 =PQ 有兩個成假解釋： (T, F), (F, T) 分別對應于兩個極大項(析取式)為 PQ, PQ 于是，有 = (PQ)(PQ),主合取范式,定義4 僅有極大項構成的合取范式稱為主合取范式。 定理2 任何一個合式公式，均有惟一的一個主合取范式與該合式公式等價。,主合取范式就是 公式的所有完全成假解釋對應的極大項的合取。,求主合取范式的兩種方法,(1)解釋法 根據(jù)公式的所有完全成假解釋，

16、求出與這些成假解釋對應的析取式，所有析取式的合取就為公式的主合取范式。 (2)等價變換法 將合取范式中的每一個析取式用AA填滿命題變元，然后用等價公式進行變換，消去相同部份，即得公式的主合取范式。,解： 原式 =(PR)(P (Q R)(P(Q R) （去蘊涵詞、等價詞） =(PR)(PQ )(PR) (PQR) 于是， (PR)=(PR)(QQ) =(PRQ)(PRQ) (PQ )= (PQ)(R R)= (PQR) (PQ R) (PR)=(PR)(QQ)= (PQR)(PQR) 原式 =(100110)(000001) (001 011) 110 =100 110 000 001 011

17、=,例(p12) 求 (PR)(P(Q R)的主合取范式,勘誤！,例 試求 =(PR)(P (Q R) 的主析取范式和主合取范式,解: =(PR) (P(QR)(P(QR) （去蘊涵詞、等價詞） =(PR) (PQR) (PQ) (PR) （化簡） =(PR) (PQR) (PQ) (PR) （去蘊涵詞） = (PR) (PQR)(PQ) =(110 100) 001 (111 110)=(1,4,6,7),例 試求 (PR)(P (Q R) 的主析取范式和主合取范式,解: 已經(jīng)得到 = (PQR)(PQ)(PR),=(PP)(PQ)(QP) (QQ)(PR)(QR)(PR) =(PQ)(QP

18、)(PR)(QR) (PR) =(T(PQR) (QP)(PQR) ) (PR) T) (PQR) T) =101 (010 011) (010 000) 000 =(0,2,3,5),例 試求 (PR)(P (Q R) 的主析取范式和主合取范式,另解: 已經(jīng)得到 = (PQR)(PQ)(PR),=(PQR ) (PQ) (PR) =(PQR ) (P(QR) =(PQR) (QP) (RP) 分解,共6項 =(PQR) (QPR) (QPR) (RQP) =(PQR) (PQR) (PQR) (PQR)=(0,2,3,5),主合取范式和主析取范式的關系,(1)緊密相關性： 一個公式的主合取范

19、式和主析取范式是緊密相關的。 如例： =(PR) (P (Q R)= =(PR) (P (Q R)= (2)惟一性： 任何一個命題演算公式，具有惟一的主合取范式和主析取范式，因此如果兩個公式具有相同的主析取范式或主合取范式，則稱兩公式邏輯等價。,第一章 命題演算基礎,1.1 命題和聯(lián)結詞 1.2 真假性 1.3 范式及其應用 1.3.1 范式 1.3.2 主范式 1.3.3 范式的應用,例 運籌學問題,從甲、乙、丙、丁4 個人之中派兩個出去執(zhí)行任務,按下列3 個條件共有幾種派法？如何派? (1) 如果派甲去,那么丙和丁之中至少要派一; (2)乙和丙不能同時都去; (3)如果派丙去,那么丁必須留

20、下。,解:,分別用A 、B 、C 、D 表示依次派甲、乙、丙、丁去, 則根據(jù)題意, 三種派法分別翻譯為: A (C D), (B C), C D 都是真命題。于是 T=(A (C D)(B C)(C D) =( A C D)( B C)( C D) =( A B C)( A B D) ( A C)( A C D) (C B D) (D B C ) (D C) =( A B C)( A B D) ( A C D)( A C D) (C B D) (D B C ) (DB C),解:,=( A B C)( A B D) ( A C D)( A C D) (C B D) (D B C )(DB C)

21、 =( A B C)( A B D) (ABCD) ( ABCD) ( A C D) (ACBD) (ACBD) (ADBC) (AD BC) (ADB C) (ADB C),另解：,從4人中任意取出2人，共有6種取法： (1)挑出甲、乙，不符合第一條。 (2)挑出甲、丙，符合所有條件。 (3)挑出甲、丁，符合所有條件。 (4)挑出乙、丙，不符合第二條。 (5)挑出乙、丁，符合所有條件。 (6)挑出丙、丁，不符合第三條。,例 問路問題,有A、B兩個相鄰的小島。 A 島居民都是誠實人，B 島居民都是騙子。一個旅游者獨自登上了兩島中的某個島，他分辨不清這個島是A 島還是B島，只知道這個島上的人既有本島的，也有另一島的，他可以向一個人問路1次。此旅游者問一個什么問題就可以斷定這是哪個島？,你是這個島的居民嗎？,例(p14) 趣味數(shù)理邏輯,有一個邏輯學家誤入某個部落，他被拘于牢，酋長意欲放行，他對邏輯學家說：“今有兩門，一為自由，一為死亡，你可任意開啟一門。為協(xié)助你離開，今加派兩名戰(zhàn)