離散數(shù)學(xué)-命題演算

1、命題邏輯的等值演算和推理演算Lu Chaojun, SJTU 2主要內(nèi)容 公式間的等值關(guān)系與等值演算 利用真值表列寫公式 聯(lián)結(jié)詞的完備集 對(duì)偶定理 范式和主范式 公式間的重言蘊(yùn)涵關(guān)系與推理演算2Lu Chaojun, SJTU 3公式間的等值關(guān)系 一種重要的數(shù)學(xué)論證方法是:將一個(gè)命題用另一個(gè)等值命題替換. 給定兩個(gè)命題公式和,設(shè)P1 , Pn是出現(xiàn)在和 中的所有命題變項(xiàng). 若在所有解釋(共2n個(gè))下和 的真值都相同, 就稱和 等值等值(或邏輯等價(jià)邏輯等價(jià),logical equivalence).記作 = (或 ). 例如: PQ = P Q這兩個(gè)公式語法上是不同的,但語義上相同(即有相同意義

2、).Lu Chaojun, SJTU 4如何證明兩公式等值? 真值表法 利用等值定理 利用基本等值式進(jìn)行推導(dǎo)4Lu Chaojun, SJTU 5例:利用真值表證明等值證明(PP)Q = Q.證:列出真值表即可看出等式成立.PQPP(PP)QFFFFFTFTTFFFTTFTLu Chaojun, SJTU 6等值定理 等值定理等值定理:對(duì)公式對(duì)公式 和和 , = iff 是重言式是重言式證明:若 是重言式,則在任一解釋下,其真值都為T,依的定義知和真值相同.故 =.若 =, 則在任一解釋下,和都有相同的真值,依的定義即真值為T.故是重言式.Lu Chaojun, SJTU 7 = 與 的異同

3、從形式系統(tǒng)角度看 是系統(tǒng)內(nèi)的符號(hào), 是系統(tǒng)內(nèi)的合式公式.(語法) =是系統(tǒng)外的符號(hào), = 不是合式公式! =是在系統(tǒng)外觀察系統(tǒng)內(nèi)兩個(gè)公式是否等值.(語義) 從真假性來看 寫下,不代表和 等值.只有為真,才能得知和 等值.但 可為假. 寫下 =,則肯定了和 等值.Lu Chaojun, SJTU 8等值關(guān)系“=”的性質(zhì) 和大家在數(shù)學(xué)里用的等號(hào)一樣,具有下面三個(gè)性質(zhì):1.自反性: =2.對(duì)稱性: 若 =, 則 =3.傳遞性: 若 =且 =, 則 = 這三條性質(zhì)體現(xiàn)了兩事物“等同”、“同一性”概念. 滿足這三條性質(zhì)的關(guān)系稱為等價(jià)關(guān)系.8Lu Chaojun, SJTU 9例:利用等值定理證明等值證明

4、(PQ) = (PQ).證:轉(zhuǎn)化為證明(PQ)(PQ)是重言式.比如列出此公式的真值表. 這里本質(zhì)上還是在利用真值表. 還可利用重言式推理系統(tǒng)(見3.2)證明重言式.9Lu Chaojun, SJTU 10基本等值式(等價(jià)定律)1.結(jié)合(associative)律(P Q) R = P (Q R)(P Q) R = P (Q R)(P Q) R = P (Q R)2. 交換(commutative)律P Q = Q PP Q = Q PP Q = Q P注意:沒有的結(jié)合律和交換律.Lu Chaojun, SJTU 11基本等值式(續(xù))3. 分配(distributive)律P (Q R) =

5、(P Q) (P R)P (Q R) = (P Q) (P R)P(QR) = (PQ)(PR)4.吸收(absorption)律P (P Q) = PP (P Q) = PLu Chaojun, SJTU 12基本等值式(續(xù))5. 關(guān)于否定詞的等值式P = P(雙重否定律)(P Q) = P Q(De Morgan律)(P Q) = P Q(De Morgan律)(PQ) = P Q(PQ) = PQ = P Q = (P Q) (P Q)Lu Chaojun, SJTU 13基本等值式(續(xù))6.冪等律P P = PP P = PP P = TP P = T注:這兩組等值公式的共同特點(diǎn)是“變

6、元混同”.7.補(bǔ)余律P P = TP P = FP P = PPP = PP P = F13Lu Chaojun, SJTU 14基本等值式(續(xù))8.同一律P F = PP T = PTP = PP F = PTP = PF P = P9.零律P T = TP F = FPT = TFP = T注:這兩組等值式的共同特點(diǎn)是“部分指派”.14Lu Chaojun, SJTU 15其他常用等值式 由于,更易理解和處理,常將含和的公式改寫成僅含有,的公式.10.PQ = P Q = (P Q)11.PQ = Q P 正定理與逆否定理12. P(QR) = (P Q)R 合取前提13. PQ = PQ

7、14. PQ = (PQ)(PQ) 同真或同假15. PQ = (PQ)(PQ) 一真一假Lu Chaojun, SJTU 16其他常用等值式(續(xù))16. PQ = (PQ) (QP) 充分必要17. P(QR) = Q(PR) 交換前提18. (PR)(QR) = (P Q)R 析取前提補(bǔ)充:19. P(QR) = (PQ) (PR)20. P(QR) = (PQ) (PR)21. (PQ)R = (PR) (QR)22. (PQ)R = (PR) (QR)Lu Chaojun, SJTU 17置換規(guī)則 置換置換:對(duì)公式的子公式用等值公式替換. 與代入代入不同! 定理定理:若對(duì)公式若對(duì)公式

8、的子公式置換后得到公的子公式置換后得到公式式 ,則有則有 = .證明思路:考慮 和 的解釋時(shí),將子公式及其替換公式視為新變?cè)?再判斷 和 的的同真假. 推論推論:若若 是重言式是重言式,則置換后得到的則置換后得到的 也也是重言式是重言式.Lu Chaojun, SJTU 18等值演算 等值演算等值演算:利用等值定律及替換規(guī)則進(jìn)行公式推演. 一般是為了化簡(jiǎn)公式. 例如:證明(P(QR)(QR)(PR) = R.證明:左端= (P(QR)(QP)R)(分配律)=(PQ)R) (QP)R) (結(jié)合律)=(PQ)R) (QP)R) (摩根律)=(PQ)(QP)R(分配律)=(PQ)(PQ)R (交換律

9、)=TR (置換)=R(同一律) Lu Chaojun, SJTU 19命題公式與真值表 給定公式,列出其真值表是容易的. 給定真值表(包括命題變?cè)狿1,Pn及相應(yīng)的真值),如何寫出公式 ? 有兩種方法: 方法一:利用使為真的解釋(真值指派) 方法二:利用使為假的解釋(真值指派)Lu Chaojun, SJTU 20方法一 從每個(gè)使為真的解釋寫出一個(gè)各命題變?cè)暮先∈?然后寫出各合取式的析取式.例:有三個(gè)成真解釋.由(P,Q)=(F,F)可寫出合取式:P Q由(P,Q)=(F,T)可寫出合取式:P Q由(P,Q)=(T,T)可寫出合取式:P Q于是得到: (PQ) (PQ) (PQ)20PQF

10、FTFTTTFFTTTLu Chaojun, SJTU 21方法二 從每個(gè)使為假的解釋寫出一個(gè)各命題變?cè)奈鋈∈?然后寫出各析取式的合取式.例:有兩個(gè)成假解釋.由(P,Q)=(T,F)可寫出析取式:P Q由(P,Q)=(T,T)可寫出析取式:P Q于是得到: (P Q) (P Q)21PQFFTFTTTFFTTFLu Chaojun, SJTU 22還有別的聯(lián)結(jié)詞嗎? 除,外還可定義其他聯(lián)結(jié)詞.如:異或: P Q = (P Q) (P Q)與非(NAND): P | Q = (P Q)Sheffer stroke或非(NOR): P Q = (P Q)Peirce arrow 問題:給定n個(gè)命

11、題變項(xiàng)P1,Pn ,可定義出多少種命題聯(lián)結(jié)詞? Lu Chaojun, SJTU 23聯(lián)結(jié)詞是真值函數(shù) 命題聯(lián)結(jié)詞可看作是真值函數(shù)真值函數(shù),即以真值為定義域和值域的函數(shù). 例如: 是一元真值函數(shù),其真值表實(shí)際上給出了這個(gè)函數(shù)定義.若用常見函數(shù)記法可記為: : T,F T,FT | FT | T 又如: 是二元真值函數(shù): : T,FT,F T,F 前述問題轉(zhuǎn)化成: n元真值函數(shù)有多少個(gè)?Lu Chaojun, SJTU 24一元聯(lián)結(jié)詞的個(gè)數(shù) 一元真值函數(shù)只有一個(gè)自變?cè)狿(命題變項(xiàng)). P只有T和F兩種取值,對(duì)每一種取值又有兩種可能的函數(shù)值T和F.于是可定義22 種不同的真值函數(shù).即下表中的f0

12、f3. 相應(yīng)地共有4種不同的一元聯(lián)結(jié)詞. 例如上面的f2就是我們熟悉的.Pf0(P)f1(P)f2(P)f3(P)FFFTTTFTFTLu Chaojun, SJTU 25二元聯(lián)結(jié)詞的個(gè)數(shù) 二元真值函數(shù)有兩個(gè)自變?cè)狿和Q,可取4種真值組合.對(duì)每一種取值組合又有兩種可能的函數(shù)值T和F.于是可定義24種不同的真值函數(shù). 即下表中的g0 g15. 相應(yīng)地共有16種不同的二元聯(lián)結(jié)詞. 顯然g1就是我們熟悉的. g0 g15 中除了,之外,也定義了, , 等等.PQg0(P,Q)g1(P,Q)g2(P,Q)g15(P,Q)FFFFFTFTFFFTTFFFTTTTFTFTLu Chaojun, SJTU

13、26n元聯(lián)結(jié)詞的個(gè)數(shù) 一般地, n元真值函數(shù)有n個(gè)自變?cè)狿1, , Pn .每個(gè)Pi有兩種取值,從而P1, , Pn共有2n種真值組合.對(duì)每一種取值組合又有兩種可能的函數(shù)值T和F.于是可定義22n種不同的真值函數(shù). 相應(yīng)地可定義22n個(gè)n元聯(lián)結(jié)詞. 例:定義一個(gè)三元聯(lián)結(jié)詞#(P,Q,R)為真 iff P,Q,R中至少兩個(gè)為真. 無法用習(xí)慣的中綴法表示.Lu Chaojun, SJTU 27聯(lián)結(jié)詞的完備集 可定義的聯(lián)結(jié)詞很多,但并非都彼此獨(dú)立,即:能夠相互表示. 例如: PQ = P Q. 即可用和表示. 定義: 設(shè)C是聯(lián)結(jié)詞的集合.如果對(duì)任一命題公式都有由C中聯(lián)結(jié)詞表示出來的公式與之等值,就說

14、C是完備的完備的(adequate)聯(lián)結(jié)詞集合,或聯(lián)結(jié)詞的完備集. Lu Chaojun, SJTU 28聯(lián)結(jié)詞的完備集(續(xù)) 全體聯(lián)結(jié)詞的集合(無窮集)是完備的. 和,都不是完備的. 定理: ,是完備的聯(lián)結(jié)詞集合. 證明思路:回顧由真值表列寫命題公式的過程可知任一公式都可由,表示出來. 是后面即將學(xué)到的范式定理范式定理的直接推論. 由PQ = (PQ)可知:可由,表示,故,也是聯(lián)結(jié)詞的完備集.類似地,等也是.Lu Chaojun, SJTU 29對(duì)偶式 觀察下面兩個(gè)等值公式(分配律):P (Q R) = (P Q) (P R)P (Q R) = (P Q) (P R) 命題邏輯公式存在“對(duì)偶

15、”規(guī)律. 設(shè)公式 中只出現(xiàn),. 將 中的, 分別以,替換, 所得公式稱為的對(duì)偶式對(duì)偶式*. 將 中所有肯定形式出現(xiàn)的變?cè)狿i換成Pi, 所有否定形式出現(xiàn)的變?cè)狿i換成Pi, 所得公式記為. 注意:求*時(shí)不能有,;求時(shí)無此限制.Lu Chaojun, SJTU 30*和的性質(zhì) 定理(*)* = ()= 定理(*) = ()*() = () 定理 = *(De Morgan律的一般形式)Lu Chaojun, SJTU 31對(duì)偶定理 定義和 同永真同永真: 永真 iff 永真和 同可滿足同可滿足: 可滿足 iff 可滿足 定理:以下兩對(duì)公式都是同永真且同可滿足的: 與, 與*. 對(duì)偶定理對(duì)偶定理:

16、以下兩對(duì)公式都是同永真且同以下兩對(duì)公式都是同永真且同可滿足的可滿足的: 與與 * *, 與與 * *. 推論推論: = iff * = *.Lu Chaojun, SJTU 32公式有沒有標(biāo)準(zhǔn)形式? 公式的數(shù)量是無窮多的. 即便只有一個(gè)變?cè)狿,也可以寫出P , P P , P P P , P P P P, 但若按等值關(guān)系對(duì)全體公式進(jìn)行劃分, n個(gè)命題變項(xiàng)所能形成的不同公式僅有22n個(gè). 問題:與命題公式 等值的公式能否都化為某種標(biāo)準(zhǔn)形式? 借助于標(biāo)準(zhǔn)形容易判斷兩個(gè)公式是否等值. 借助于標(biāo)準(zhǔn)形容易判斷公式是否重言式或矛盾式.Lu Chaojun, SJTU 33范式(normal form) 由

17、命題變?cè)蛎}變?cè)姆穸ɡ?)聯(lián)結(jié)而成的公式稱為合合(析析)取式取式. 合取式例:P, P, PQ, PQP 析取式例:P, P, PQ, PQP 由合(析)取式利用()聯(lián)結(jié)而成的公式稱為析析(合合)取范式取范式. 析取范式形如: 1 2 n (諸i是合取式) 合取范式形如: 1 2 n (諸i是合取式)Lu Chaojun, SJTU 34公式轉(zhuǎn)化為范式 范式定理范式定理: 任一公式都有與之等值的合取任一公式都有與之等值的合取范式和析取范式范式和析取范式. 根據(jù)真值表列寫公式就是求范式一法. 等值變換法求范式1.消去,2.否定詞深入到變?cè)?.合(析)取詞深入這時(shí)已經(jīng)是范式.4.(可選)化

18、簡(jiǎn)34Lu Chaojun, SJTU 351.消去, 方法:利用下列等值式 = = ( )( ) 適合求析取范式 = ( )( ) 適合求合取范式 例:求(PQ)(PQ)的析取范式 (PQ)(PQ)= (PQ) (PQ) (PQ) (PQ)35Lu Chaojun, SJTU 362.否定詞深入 方法:利用下列等值式( ) = ( ) = = 例 (PQ)(PQ) = (PQ) (PQ) (PQ) (PQ)= (PQ PQ) (PQ) (PQ)36Lu Chaojun, SJTU 373.合(析)取詞深入 方法:利用分配律 ( ) = ( ) ( ) 用于析取范式 ( ) = ( ) ( )

19、 用于合取范式 例 (PQ)(PQ) = (PQ) (PQ) (PQ) (PQ)= (PQ PQ) (PQ) (PQ)= (PQ PQ) (PP) (PQ) (QP) (QQ)37Lu Chaojun, SJTU 384.(可選)化簡(jiǎn) 方法:利用下列等值式消去矛盾式P F = F F = 例 (PQ)(PQ) = (PQ) (PQ) (PQ) (PQ)= (PQ PQ) (PQ) (PQ)= (PQ PQ) (PP) (PQ) (QP) (QQ)= (PQ) (PQ)38Lu Chaojun, SJTU 39范式的用途 判斷是否重言式 求的合取范式,若每個(gè)析取式都含有某個(gè)變?cè)捌浞穸?如P和P

20、),則是重言式. 判斷是否矛盾式 求的析取范式,若每個(gè)合取式都含有某個(gè)變?cè)捌浞穸?如P和P),則是矛盾式. 判斷 = ? 求 和 的同一種范式,看是否相同. 問題是: 范式唯一嗎?39Lu Chaojun, SJTU 40主范式假設(shè)以下討論的公式都只涉及n個(gè)命題變?cè)狿1, , Pn. 極小項(xiàng)極小項(xiàng): n個(gè)命題變?cè)荚谄渲谐霈F(xiàn)一次的合取式. 極小項(xiàng)有2n個(gè). 主析取范式主析取范式:僅由極小項(xiàng)構(gòu)成的析取式. 定理:任一公式都有唯一與之等值的主析取范式.假設(shè)以下討論的公式都只涉及n個(gè)命題變?cè)狿1, , Pn. 極大項(xiàng)極大項(xiàng): n個(gè)命題變?cè)荚谄渲谐霈F(xiàn)一次的析取式. 極大項(xiàng)有2n個(gè). 主合取范式主合

21、取范式:僅由極大項(xiàng)的構(gòu)成的合取式. 定理:任一公式都有唯一與之等值的主合取范式.Lu Chaojun, SJTU 41主范式的求法求主析取范式 方法一: 利用真值表中的成真指派列寫公式. 例:根據(jù)PQ的真值表中的T行(PQ) (PQ)求主合取范式 方法一: 利用真值表中的成假指派列寫公式. 例:根據(jù)PQ的真值表中的F行(PQ)(PQ)41Lu Chaojun, SJTU 42主范式的求法(續(xù))求主析取范式 方法二: 為析取范式中的合取式補(bǔ)足未出現(xiàn)的命題變?cè)? 例: PQ = P QP = P (Q Q)= (PQ) (PQ)Q = Q (P P) = (PQ) (PQ)于是PQ = 求主合取范

22、式 方法二: 為合取范式中的析取式補(bǔ)足未出現(xiàn)的命題變?cè)?例: (PQ) = PQP = P (Q Q)= (PQ) (PQ)Q = Q (P P) = (PQ) (PQ)于是(PQ) = 42Lu Chaojun, SJTU 43極小(大)項(xiàng)的性質(zhì) 極小項(xiàng)與真值指派(解釋)一一對(duì)應(yīng),都有2n個(gè). 每個(gè)極小項(xiàng)只在一個(gè)解釋下為真. 一個(gè)解釋下兩個(gè)極小項(xiàng)不能都為真.(其合取為F) 極小項(xiàng)兩兩不等值. 若由k個(gè)極小項(xiàng)的析取組成,則其余2nk個(gè)極小項(xiàng)的析取就是. 若k = 2n,則是重言式. 極大項(xiàng)與真值指派(解釋)一一對(duì)應(yīng),都有2n個(gè). 每個(gè)極大項(xiàng)只在一個(gè)解釋下為假. 一個(gè)解釋下兩個(gè)極小項(xiàng)不能都為假.

23、(其析取為真) 極大項(xiàng)兩兩不等值. 若由k個(gè)極大項(xiàng)的合取組成,則其余2nk個(gè)極大項(xiàng)的析取就是. 若k = 2n,則是矛盾式.43Lu Chaojun, SJTU 44推理形式 用命題公式來描述在科學(xué)和日常生活中進(jìn)行的推理,稱為推理形式推理形式. 公式形狀都 是蘊(yùn)涵式. 例如下面三個(gè)推理形式都是常見的:(PQ) P) Q正確(即MP)(PQ) P) Q錯(cuò)誤(PQ) Q) P正確(即換質(zhì)位法) 問題:什么樣的推理形式描述了正確的推理?Lu Chaojun, SJTU 45重言蘊(yùn)涵關(guān)系 給定兩個(gè)公式和,在任何解釋下,若為真則 也為真, 就稱 重言蘊(yùn)涵重言蘊(yùn)涵,或稱是的邏輯推論邏輯推論.記作 . 這是

24、討論從前提推出結(jié)論的問題. 是前提,一般形如12 n.也可理解成有n個(gè)前提. 例如:若PQ為真,顯然P也為真,所以PQ Q45Lu Chaojun, SJTU 46 與 的異同 從形式系統(tǒng)角度看 是系統(tǒng)內(nèi)的符號(hào), 是系統(tǒng)內(nèi)的合式公式.(語法) 是系統(tǒng)外的符號(hào), 不是合式公式! 這是在系統(tǒng)外觀察系統(tǒng)內(nèi)兩個(gè)公式間的邏輯蘊(yùn)涵關(guān)系.(語義) 從表達(dá)的意思來看 只是表達(dá)“不能真而 假”,因此除了包含“真則 真”的意思之外,還包含“假則 可真可假”的意思. 表達(dá)且僅表達(dá)“真則 真”的意思.Lu Chaojun, SJTU 47如何證明 ?1.利用真值表 列出所有命題變?cè)乃兄概?以及公式 和 相應(yīng)的真值

25、. 若使 為真的解釋也都使 為真,則 成立;否則, 就不成立.2.利用下面的定理定理定理: iff 是重言式是重言式所以 稱為“重言蘊(yùn)涵式重言蘊(yùn)涵式”.定理定理: iff 是矛盾式是矛盾式47Lu Chaojun, SJTU 48如何證明 ?(續(xù))3.利用的一些性質(zhì)(1) 自反性(2)若 且 , 則 =反對(duì)稱性(3)若 且 , 則 傳遞性(4)若 且 , 則 (5)若 且 , 則 (6)若 , 則 (7)若 , 則 48Lu Chaojun, SJTU 49基本的重言蘊(yùn)涵式作為基本的推理定律(1) P Q P(2) P P Q(3) P PQ假前提啥都蘊(yùn)涵(4) (PQ) P啥都不能蘊(yùn)涵的前提

26、,必真(5) Q PQ真結(jié)論被一切前提蘊(yùn)涵(6) (PQ) Q啥前提都不蘊(yùn)涵的結(jié)論,必假(7) P(PQ) Q排除法(8) P(PQ) Qmodus ponens, 或分離規(guī)則49Lu Chaojun, SJTU 50基本的重言蘊(yùn)涵式(續(xù))(9) (PQ)Q Pmodus tollens(10) (PQ)(QR) PR三段論法之一(11) (PQ)(QR) PR(12) (PR)(QR)(PQ) R(13) (PQ)(RS)(PQ) R S(14) (PQ)(RS)(QS) P R(15) (QR) (PQ) (PR)(16) (QR) (PQ) (PR)50Lu Chaojun, SJTU 51推理演算 前面介紹的證明 的方法,都是根據(jù)公式的真值來論證的.體現(xiàn)不出證明的層層推進(jìn)過程,而且變?cè)芏鄷r(shí)不方便. 推理演算推理演算:引入一些推理規(guī)則,利用前提和基本推理公式(重言式),實(shí)現(xiàn)逐步推進(jìn)的推理過程. 從若干前提1 ,2 , ,n 出發(fā)欲證明. 利用推理規(guī)則不斷產(chǎn)生中間結(jié)論 直至得出最終結(jié)論.51Lu Cha