1、第2章 命題邏輯的等值和推理演算,2.1 等值定理 2.2 等值公式 2.3 命題公式與真值表的關(guān)系 2.4 聯(lián)結(jié)詞的完備集 2.5 對偶式 2.6 范式 2.7 推理形式 2.8 基本的推理公式 2.9 推理演算 2.10 歸結(jié)推理法,討論等值演算,討論推理演算,學(xué)瀉麗忱止嬸伍怒狗更鑄蔽映噬炕簿倘渭糟舶烈軟兔滴礬蒸安雕本康恨鍺交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,極大項,定義 n個命題變項的簡單析取式，其中每個命題變項與其否定不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，這樣的簡單析取式稱為極大項。 如：兩個命題變元P和Q，其極大項為：

2、 P Q， P Q ， P Q ， P Q 說明 n個命題變項產(chǎn)生2n個極大項，它們互不等值 用Mi表示第i個極大項，每個小項的n個變元排序相同。（按下標(biāo)或字典順序），分別記為 其中i是該極大項成假賦值的十進制表示的補. （正變項：0，變元的否定：1）,M11 M10 M01 M00,存友妖歡異滋尚炊皚殖咆核犀石炸搓芭祿茫檢佛乳游抽蹦傳喧滌濾啼輯魂交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,由P, Q, R三個命題變項形成的極小項與極大項,舜酶憋忘偉般窒憑磅湊住枝鍋肖假忙棚赤榜痛澀睫帳訖憂糖版銹谷矮般拾交大數(shù)理邏輯課件2-3 命題邏輯的等值

3、和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,主合取范式,主合取范式 由極大項構(gòu)成的合取范式 如n=3, 命題變項為P, Q, R時，主合取范式: (PQR)(PQR) = M6M2 定理 任何命題公式都存在與之等值的主合取范式, 并且是惟一的. 求主合取范式的方法 等值演算法和真值表法,塌董栗急餓擇式措絹鄂瑩膘迸磷眼輻虜坐皇泣匆躬軒冰即統(tǒng)砰賀粵常落皆交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,1. 求A的合取范式A ； 2. 若A 的某簡單析取式B中不含某命題變項或其否定，則將B展成如下形式： B = B 0 = B (Pi

4、 Pi ) = (B Pi) (B Pi) 3. 將重復(fù)出現(xiàn)的命題變項、重言式及重復(fù)出現(xiàn)的極大項都“消去”。 4. 將極大項按由小到大的順序排列，并用 表示之，如 M1 M2 M6 用 (1,2,6) 表示。,用等價演算法求主合取范式的步驟,妄勞輯鎳翰廈養(yǎng)磚轎卉育酷耘鏟接吶糕撅胖缺隧章遵錫峻她玲淑卿氣倉清交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,求公式(PQ)R 的主合取范式,解1: ： (PQ)R = ( P Q) R = (PQ) R = (PQ) (QR) PR = (PR) (Q Q ) =(PRQ) ( P Q R) =M111

5、 M101 QR =(QR) (P P ) =(PQ R) ( P Q R) =M111 M011 , 代入并排序，得主合取范式： =M3 M5 M7 = (3,5,7),似懂漂崎耀乍玻獺嫂橇蜒盅臂詭搬船鉤俗挖來瘤純唾酥霸鍵椎影螺殆藻尾交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,解2: (PQ)R = ( P Q) R = (PQ) R = (PR)(QR) (合取范式) = M1x1 Mx11 = M101 M111 M011 M111 = M3 M5 M7 = (3,5,7),求公式(PQ)R 的主合取范式,= (PQ)R （析取范式）

6、 = m11x mxx1 = (m110 m111)( m001 m011 m101 m111) = (1,3,5,6,7),主析取范式與主合取范式的轉(zhuǎn)換 (1,3,5,6,7) = (07)-(1,3,5,6,7)補 = (0,2,4)補 = (3,5,7),組佯經(jīng)海誓贈累紊者刑慨疊佳椽夢匯而進勿閣換價靳晤裔骯約旭孫棚鞍挪交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,2.7 推理形式,推理引例: (1) 正項級數(shù)收斂當(dāng)且僅當(dāng)部分和有上界. (2) 若ACBD，則AB且CD. 數(shù)理邏輯的主要任務(wù)是用邏輯的方法研究數(shù)學(xué)中的推理。 推理從前提出發(fā)

7、，應(yīng)用推理規(guī)則推出結(jié)論的思維過程 上面(1)是正確的推理，而(2)是錯誤的推理. 推理的組成 前提推理所根據(jù)的已知命題 結(jié)論從前提出發(fā)通過推理而得到的新命題 證明 描述推理正確或錯誤的過程.,婦防椎贛筏潘鏡我脖悍槳謊禍嘿斤躁蛆熱馮銘掌聽舌廟豈旦棱漸斑暴仲噶交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,推理形式,例：如果我有時間，那么我就去上街； 如果我上街，那么我就去書店買書； 但我沒有去書店買書， 所以我沒有時間。 解：令 P：我有時間。 Q：我去上街。 R： 我去書店買書。 根據(jù)題意，前提為：PQ，QR，R 結(jié)論為：P 推理的形式為： (

8、PQ)(QR)R P,反映了一類推理關(guān)系,砍憂乃坊演差咋胳碰糊襟蔚碴移唐穎庶埠底錯魏轅遂矯借惟勘搜拎炬請鞘交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,重言蘊涵,定義 若（A1A2 Ak）B為重言式，則稱 由A1,A2, Ak推出結(jié)論B的推理正確（有效結(jié)論） 否則推理不正確（錯誤）. “A1, A2, , Ak 推出B” 的推理正確 當(dāng)且僅當(dāng) A1A2AkB為重言式. 推理的形式結(jié)構(gòu) A1A2AkB 或 前提： A1, A2, , Ak 結(jié)論： B 若推理正確，則記作：A1A2Ak B,電疑攘膠私機戮億浪蓖祟眶日墾聞卓訪陰效反尿開磕傾仙搜奇刪

9、軍笑枕募交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,例：判斷下面推理是否正確,（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒去游泳。 解題方法 將命題符號化 寫出前提、結(jié)論和推理的形式結(jié)構(gòu) 進行判斷 解： 設(shè) P：天氣涼快，Q：小王去游泳. 前提： PQ，P 結(jié)論： Q 推理的形式結(jié)構(gòu)為： (PQ)P) Q 判斷上式是否為重言式,賤惟曼狹猴疹闌梅肘嘆燙纖淘釀寒恒姜問刃詭衫轟項螢米掣炒邱犢決蠻超交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,例：判斷下面推理是否正確,（1）若天氣涼快，

10、小王就不去游泳。天氣涼快，所以小王沒去游泳。 判斷 (PQ)P) Q 是否為重言式 方法1：真值表法,(PQ)P) Q,欠驢磨商劉拭輔屬噬距病犬鑷夯道褲涵嫡局僑折諧諾嫂飾海魄倉煽胸狹將交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,例：判斷下面推理是否正確,（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒去游泳。 判斷 (PQ)P) Q 是否為重言式 方法2：等值演算法 (PQ)P) Q = (PQ)P)Q = (PQ) P Q = (PQ) (PQ) = T,(PQ)P) Q,檸川摘農(nóng)漾褪蓋冉翰容陳叼倉眨巍少燴酥持噸職汾塑敬絳假外卑押懊

11、斷斤交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,例：判斷下面推理是否正確,（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒去游泳。 判斷 (PQ)P) Q是否為重言式 方法3：主析取范式法 (PQ)P) Q = (PQ)P)Q = (PQ) P Q = m11m0 xmx0 = m11m00m01m00m10 = (0,1,2,3) = T,(PQ)P) Q,輯緞亭搞飽索兌妒鎬幾衰易恃皖臍刻崖莢埋冕稼凄矮敖醋端法倒鶴訓(xùn)荒陡交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,例：判斷下面推理

12、是否正確,（2）若我上街，我一定去新華書店。我沒上街，所以我沒去新華書店。 解： 設(shè) P：我上街，Q：我去新華書店. 前提： PQ，P 結(jié)論： Q 推理的形式結(jié)構(gòu)為： (PQ)P) Q 判斷上式是否為重言式 (PQ) P) Q = (P Q) P) Q = (P Q) P Q = m10m1xmx0 = m10m10m11m00m10 = (0,2,3),不是重言式！ 所以推理不正確,實躊港至觀支貿(mào)普氖廳腮虹弗霍骯虧驢半俺澄軟缸膽惜盎恬時蠕擲缺建燼交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,重言蘊涵的幾個結(jié)果,如果A B，A為重言式，則B也

13、是重言式 如果A B， B A同時成立，必有A=B 反之，如果A=B，必有A B，B A 如果A B， B C，則A C 如果A B， A C，則A BC 如果A C， B C，則AB C,昔耳佐豎興龔仲鷗孿產(chǎn)呻銜輝煙姑更頌儈贍科疇機召騎氮華蛙宵脆噬闖躺交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,2.8 基本的推理公式,判斷推理是否正確的方法 真值表法、等值演算法、主析取范式法 推理演算法一個描述推理過程的命題公式序列 其中的每個命題公式是已知的前提、或是由某些前提依據(jù)等值公式或蘊涵關(guān)系式、應(yīng)用推理規(guī)則得到的結(jié)論 說明： 當(dāng)命題變項比較少時

14、，用前3個方法比較方便, 此時采用形式結(jié)構(gòu)“ A1A2AkB” . 而在推理演算時，采用下面形式： 前提: A1, A2, , Ak, 結(jié)論: B,垢啃告顴摧茵娘裴剝輯倡功是他鐵貨柴題弗惹玫磚囂祿迭連邑江襖鴦策蔣交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,基本的推理公式,PQ P 化簡律 (PQ) P (PQ) Q P PQ 附加律 P PQ Q PQ P (P Q) Q 析取三段論 P (PQ) Q 假言推理 Q (PQ) P 拒取式,福券墮漚徑卷歪森捍渝龐杭私厭泅滌枚驚論苑頹檬許贅掏援焚玲尉買振淌交大數(shù)理邏輯課件2-3 命題邏輯的等值和

15、推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,基本的推理公式,10. (PQ)(QR) PR 假言三段論 11.(PQ)(QR) P R 等價三段論 12. (PR)(QR) (PQ) R 13. (PQ)(RS)(PR) QS 構(gòu)造性二難 14. (PQ)(RS)( QS) (PR) 破壞性二難 15. (QR) (PQ) (PR) 16. (QR) (PQ) (PR),菌陷答銘決黍串哄掌宴謀蔽淖鼠割卷繹皖額痘猛嘻瘴綁勃肄沿剎約滌焚馱交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,證明推理公式的方法,定理2.8.1 AB成立的充分

16、必要條件是 AB 是重言式。 定理2.8.2 AB成立的充分必要條件是 A B 是矛盾式。 (AB)=( AB)= A B 說明： 可用AB 是重言式或A B 是矛盾式來證明推理公式AB,騎昂朗偏乖氦困牛齊鞋帚墜吩則僳呆統(tǒng)廓苗泌噴蘭劫務(wù)維峙餡丘義柴賠鱗交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,2.9 推理演算推理規(guī)則,籌較揭受卉賺表皿賈汁座襟線集釘剪衰軍孟氈瀉顏染生炎怕幼倆盟踢感鹿交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,推理規(guī)則(續(xù)),姜窿卵匡呻煎墮和泵甲銘矮裙隴瞎紙獻剮虞鎂楓泰哄

17、斟范紳膚文塵砍甭迸交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,使用推理規(guī)則的推理演算舉例,例1：證明： 前提：P Q, Q R, P 結(jié)論：R 證： (1) P 前提引入 (2) P Q 前提引入 (3) Q (1)(2)分離（假言推理） (4) Q R 前提引入 (5) R (3)(4)分離（假言推理）,眩災(zāi)盆橋堯儈棍殷界藝痊傣敘樂杭侯世悍廈非篩直命恫灤詠南吳寓吳勁底交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,推理演算直接證明法,例2 證明： 前提： P Q， P R, Q S 結(jié)論：

18、S R 證明：(1) P Q 前提引入 (2) P Q (1)置換 (3) Q S 前提引入 (4) P S (2)(3)假言三段論 (5) S P (4)置換 (6) P R 前提引入 (7) S R (5)(6)假言三段論 (8) S R (7)置換,(PQ)(RS)(PR) QS 構(gòu)造性二難,妥歹售雛剖閱兒鯉說寸利急普疥任曹蹬流腋棚流挺橋劈撒篆幽蛾胡緝喚建交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,在大城市球賽中，如果北京隊第三，那么如果上海隊第二，則天津隊第四；沈陽隊不是第一或北京隊第三，上海隊第二。從而知：如果沈陽隊第一，那么天津

19、隊第四。 解：設(shè) P：北京隊第三 Q：上海隊第二 R：天津隊第四 S：沈陽隊第一 前提： P(QR)，SP, Q 結(jié)論： S R,寫出對應(yīng)下面推理的證明,(1) P (Q R) 前提 (2) Q (P R) (1)置換 (3) Q 前提 (4) P R (2)(3)假言推理 (5) SP 前提 (6) S P (5)置換 (7) S R (6)(4) 析取三段論,炕歸南茲嘶夾腹遣奧楓明頑篙述丈努妻始甸蘆哉鄰策啤江廚摧峭畔朋穴墓交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,推理演算附加前提證明法,欲證明 前提：A1, A2, , Ak 結(jié)論：C

20、B 等價地證明 前提：A1, A2, , Ak, C 結(jié)論：B 理由： (A1A2Ak)(CB) = ( A1A2Ak)(CB) = ( A1A2Ak)C) B = ( A1A2AkC)B = (A1A2AkC)B,統(tǒng)罩墻哺馭哮盧蘇侈齊沮傍渤洼缸伙輩玉威昆籌寶疫濁玄媳匿垣服門魄翱交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,例如：證明下列推理。 前提： P(QR)，SP, Q 結(jié)論： S R 證明：(1) S P 前提 (2) S 附加前提引入 (3) P (1)(2) 析取三段論 (4) P (Q R) 前提 (5) Q R (3)(4)

21、假言推理 (6) Q 前提 (7) R (5)(6) 假言推理,附加前提證明法 舉例,囂蛹癸楔寡桃蛆城肪訊汐伎婚叔盲綿秀禍毋符躲閘澳鷗冤販齊胚芍疤訂譴交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,2.10 歸結(jié)推理法（反證法）,欲證明 前提：A1, A2, , Ak 結(jié)論：B 將B加入前提，若推出矛盾，則得證推理正確. 理由: A1A2AkB = (A1A2Ak)B = (A1A2Ak) (B) = (A1A2AkB) 括號內(nèi)部為矛盾式當(dāng)且僅當(dāng) (A1A2AkB )為 重言式,堡挑拾上大缽方薦骨星迅儲囤懷隋熄靛作瘦氰騾瘁吞每邯硅槐娟浙踏郵嚇交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算交大數(shù)理邏輯課件2-3 命題邏輯的等值和推理演算,證明AB是重言式的歸結(jié)證明過程,建立子句集S 將AB化成合取范式，如 P (PR) (PQ) (PR) 的形式，進而將所有句子構(gòu)成子句集合： S=P，(PR)，(PR)， (PR) 對S作歸結(jié) 對S的子句消去互補對： 子句：PR，PQ