離散數(shù)學(xué)第一章命題演算基礎(chǔ)-范式及其應(yīng)用.ppt

1、第一章 命題演算基礎(chǔ),1.1 命題和聯(lián)結(jié)詞 1.2 真假性 1.3 范式及其應(yīng)用 1.3.1 范式 1.3.2 主范式 1.3.3 范式的應(yīng)用,合取式、析取式,定義1 命題變?cè)?、或者命題變?cè)姆穸?、或由它們利用合取詞組成的合式公式稱(chēng)為合取式。 定義2 命題變?cè)⒒蛘呙}變?cè)姆穸?、或由它們利用析取詞組成的合式公式稱(chēng)為析取式。 例 顯然， P，P，PQ，PQR 均為合取式； P，P，PQ，PQR 均為析取式。,(一) 解釋與合取式、析取式之間的關(guān)系,定理1 任給一個(gè)成真解釋有且僅有一個(gè)合取式與之對(duì)應(yīng)； 任給一個(gè)成假解釋有且僅有一個(gè)析取式與之對(duì)應(yīng)。 反之亦然。,例 成真解釋(P，Q，R)= (T,

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

3、(T, F), (F, T), 對(duì)應(yīng)析取式為 PQ, PQ 于是，有： = (PQ) (PQ),定理2 任何命題演算公式均可以化為合取范式，也可以化為析取范式。,證明： (1)設(shè)公式為永真公式 因?yàn)槿魏我粋€(gè)永真公式均與公式PP邏輯等價(jià)，而PP既是析取范式又是合取范式，所以公式既可表示為析取范式又可表示為合取范式。 (2)設(shè)公式為永假公式 因?yàn)槿魏我粋€(gè)永假公式均與公式PP邏輯等價(jià)，而PP既是析取范式又是合取范式，所以公式既可表示為析取范式又可表示為合取范式。,定理2證明(續(xù)),(3)設(shè)公式既非永真又非永假 設(shè)公式的成真解釋為1，2，n， 成假解釋為1，2，t。 根據(jù)解釋和范式的關(guān)系知： 對(duì)應(yīng)于成

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

5、=(P Q )(P R) P (QR)=(P Q )(P R),解釋法,(1)求出公式的所有成真(假)解釋?zhuān)?(2)寫(xiě)出所有成真(假)解釋對(duì)應(yīng)有的合(析)取式； (3)把所有的合(析)取式用析(合)取詞聯(lián)結(jié)起來(lái)就構(gòu)成析(合)取范式。,例(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),解法二： 先求公式的所有成真解釋和成假解釋(見(jiàn)下一張) 成真解釋為：(P,Q,R)=(T,F,), (F,T), (T,F) 成假解釋為：(P,Q,R)=(T,T,T), (F,F) 由成真解釋可分別求出對(duì)應(yīng)的合取式： P

7、Q，P R，PR 公式的析取范式即為上面合取式的析?。?(PQ)(PR)(P R) 由成假解釋可分別求出對(duì)應(yīng)的析取式： P QR，PR 公式的合取范式為上面析取式的合?。?(P QR)(PR),例(p11) 求公式的范式 (PQ)(RP)(RQ)P),解：P=T時(shí), 原式=(TQ)(RT)(RQ)T) =(QT)(RQ) =Q(RQ) =Q (RQ) = QR P=F時(shí), 原式=(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？,例(補(bǔ)) 求

8、公式的成真(假)解釋 (PQ)(RP)(RQ)P),例(補(bǔ)) 求公式的成真(假)解釋 (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),例(補(bǔ)) 求公式的成真(假)解釋 (PQ)(RP)(RQ)P),范式不唯一性,例 求(PQ)P的析取范式和合取范式 解: (PQ)P=(PQ)P =(PQ)P 析取范式 = P 析取范式 (PQ)P=(PQ)P

9、析取范式 =P(QP) 合取范式 =P 合取范式,第一章 命題演算基礎(chǔ),1.1 命題和聯(lián)結(jié)詞 1.2 真假性 1.3 范式及其應(yīng)用 1.3.1 范式 1.3.2 主范式 1.3.3 范式的應(yīng)用,(一) 主析取范式,定義1 對(duì)于n個(gè)命題變?cè)狿1，P2，Pn，公式 Q1Q2Qn 稱(chēng)為極小項(xiàng)，其中Qi=Pi或Pi(i=1，n)。,例 由兩個(gè)命題變?cè)狿，Q組成的極小項(xiàng)有四個(gè)，它們分別為： PQ PQ PQ PQ,三個(gè)命題變?cè)狿、Q和R可構(gòu)造8個(gè)極小項(xiàng),把命題變?cè)姆穸ㄐ问娇闯?，肯定形式看成1，則每個(gè)極小項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，也對(duì)應(yīng)一個(gè)十進(jìn)制數(shù)。它們對(duì)應(yīng)如下： PQR 與000 或0對(duì)應(yīng)，簡(jiǎn)記為 m0

10、PQR 與001 或1對(duì)應(yīng)，簡(jiǎn)記為 m1 PQR 與010 或2對(duì)應(yīng)，簡(jiǎn)記為 m2 PQR 與011 或3對(duì)應(yīng)，簡(jiǎn)記為 m3 PQR 與100 或4對(duì)應(yīng)，簡(jiǎn)記為 m4 PQR 與101 或5對(duì)應(yīng)，簡(jiǎn)記為 m5 PQR 與110 或6對(duì)應(yīng)，簡(jiǎn)記為 m6 PQR 與111 或7對(duì)應(yīng)，簡(jiǎn)記為 m7,n個(gè)命題變?cè)M成的極小項(xiàng)有2n個(gè),公式的每一個(gè)完全成真解釋對(duì)應(yīng)一個(gè)極小項(xiàng) 公式的所有完全成真解釋對(duì)應(yīng)極小項(xiàng)的析取,例: 考察公式 =PQ 有兩個(gè)成真解釋?zhuān)?(T, T), (F, F) 分別對(duì)應(yīng)于兩個(gè)極小項(xiàng)(合取式)為 PQ, PQ 于是，有 = (PQ) (PQ),主析取范式,定義2 僅有極小項(xiàng)構(gòu)成的析

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

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

13、，F(xiàn)，T),(T，T，T) 對(duì)應(yīng)于成真解釋的極小項(xiàng)為： P Q R , PQR , PQR 故主析取范式為： (P Q R)(PQR)(PQR),例(p12) 求 (PR)(P(Q R) 的主析取范式。,例(p12) 補(bǔ)求(PR)(P(Q R) 的解釋,解: P=T時(shí), 原式= (TR) (T (Q R) = R(Q R) = R (Q R) = (R Q) R = R P=F時(shí), 原式 = (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 對(duì)于n個(gè)命變?cè)狿1，P2，Pn，公式 Q1Q2Qn 稱(chēng)為極大項(xiàng)，其中Qi=Pi或Pi(i=1，n)。,例 由兩個(gè)命題變?cè)狿，Q組成的極大項(xiàng)有四個(gè)，它們分別為： PQ PQ PQ PQ,三個(gè)命題變?cè)狿、Q和R可構(gòu)造8個(gè)極大項(xiàng),把命題變?cè)姆穸ㄐ问娇闯?，肯定形式看成0，則每個(gè)極大項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，也對(duì)應(yīng)一個(gè)十進(jìn)制數(shù)。它們對(duì)應(yīng)如下： PQR 與000 或0對(duì)應(yīng)，簡(jiǎn)記為 M0 PQR 與001 或1對(duì)應(yīng)，簡(jiǎn)記為 M1 PQR 與010 或2對(duì)應(yīng)，簡(jiǎn)記為 M2 PQR 與011 或3對(duì)應(yīng)，簡(jiǎn)記為 M3 PQR 與100 或4對(duì)應(yīng)，簡(jiǎn)記為 M4 PQR 與101 或5對(duì)應(yīng)，簡(jiǎn)記為 M5 PQR

15、 與110 或6對(duì)應(yīng)，簡(jiǎn)記為 M6 PQR與111 或7對(duì)應(yīng)，簡(jiǎn)記為 M7,n個(gè)命題變?cè)M成的極大項(xiàng)有2n個(gè),公式的每一個(gè)完全成假解釋對(duì)應(yīng)一個(gè)極大項(xiàng) 公式的所有完全成假解釋對(duì)應(yīng)極大項(xiàng)的合取,例: 考察公式 =PQ 有兩個(gè)成假解釋?zhuān)?(T, F), (F, T) 分別對(duì)應(yīng)于兩個(gè)極大項(xiàng)(析取式)為 PQ, PQ 于是，有 = (PQ)(PQ),主合取范式,定義4 僅有極大項(xiàng)構(gòu)成的合取范式稱(chēng)為主合取范式。 定理2 任何一個(gè)合式公式，均有惟一的一個(gè)主合取范式與該合式公式等價(jià)。,主合取范式就是 公式的所有完全成假解釋對(duì)應(yīng)的極大項(xiàng)的合取。,求主合取范式的兩種方法,(1)解釋法 根據(jù)公式的所有完全成假解釋?zhuān)?/p>

16、求出與這些成假解釋對(duì)應(yīng)的析取式，所有析取式的合取就為公式的主合取范式。 (2)等價(jià)變換法 將合取范式中的每一個(gè)析取式用AA填滿命題變?cè)?，然后用等價(jià)公式進(jìn)行變換，消去相同部份，即得公式的主合取范式。,解： 原式 =(PR)(P (Q R)(P(Q R) （去蘊(yùn)涵詞、等價(jià)詞） =(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) （去蘊(yùn)涵詞、等價(jià)詞） =(PR) (PQR) (PQ) (PR) （化簡(jiǎn)） =(PR) (PQR) (PQ) (PR) （去蘊(yùn)涵詞） = (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項(xiàng) =(PQR) (QPR) (QPR) (RQP) =(PQR) (PQR) (PQR) (PQR)=(0,2,3,5),主合取范式和主析取范式的關(guān)系,(1)緊密相關(guān)性： 一個(gè)公式的主合取范

19、式和主析取范式是緊密相關(guān)的。 如例： =(PR) (P (Q R)= =(PR) (P (Q R)= (2)惟一性： 任何一個(gè)命題演算公式，具有惟一的主合取范式和主析取范式，因此如果兩個(gè)公式具有相同的主析取范式或主合取范式，則稱(chēng)兩公式邏輯等價(jià)。,第一章 命題演算基礎(chǔ),1.1 命題和聯(lián)結(jié)詞 1.2 真假性 1.3 范式及其應(yīng)用 1.3.1 范式 1.3.2 主范式 1.3.3 范式的應(yīng)用,例 運(yùn)籌學(xué)問(wèn)題,從甲、乙、丙、丁4 個(gè)人之中派兩個(gè)出去執(zhí)行任務(wù),按下列3 個(gè)條件共有幾種派法？如何派? (1) 如果派甲去,那么丙和丁之中至少要派一; (2)乙和丙不能同時(shí)都去; (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)挑出丙、丁，不符合第三條。,例 問(wèn)路問(wèn)題,有A、B兩個(gè)相鄰的小島。 A 島居民都是誠(chéng)實(shí)人，B 島居民都是騙子。一個(gè)旅游者獨(dú)自登上了兩島中的某個(gè)島，他分辨不清這個(gè)島是A 島還是B島，只知道這個(gè)島上的人既有本島的，也有另一島的，他可以向一個(gè)人問(wèn)路1次。此旅游者問(wèn)一個(gè)什么問(wèn)題就可以斷定這是哪個(gè)島？,你是這個(gè)島的居民嗎？,例(p14) 趣味數(shù)理邏輯,有一個(gè)邏輯學(xué)家誤入某個(gè)部落，他被拘于牢，酋長(zhǎng)意欲放行，他對(duì)邏輯學(xué)家說(shuō)：“今有兩門(mén)，一為自由，一為死亡，你可任意開(kāi)啟一門(mén)。為協(xié)助你離開(kāi)，今加派兩名戰(zhàn)