【正文】 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程離 散 數(shù) 學(xué)電子科技大學(xué) 計算機科學(xué)與工程學(xué)院示 范 性 軟 件 學(xué) 院*電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程2第 5章 推理與證明技術(shù) 數(shù)學(xué)歸納法的使用 3CP規(guī)則相關(guān)證明4命題邏輯的推理理論 1謂詞邏輯的推理理論 2電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程3 本章學(xué)習(xí)要求1掌握各種不同類型的規(guī)則和公理，特別是命題邏輯和謂詞邏輯的推理規(guī)則和公理 3理解謂詞邏輯的精髓，將其思想貫穿于所有的證明之中 2熟練掌握不同證明方法的證明原理、不同的應(yīng)用場景 重點掌握 一般掌握 了解電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程4 命題邏輯的推理理論 概念描述問題的句子；Add Your Text判斷對概念的肯定與否定的判斷；推理從一個或多個前提推出結(jié)論的思維過程。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程5推理的有效性和結(jié)論的真實性有效的推理不一定產(chǎn)生真實的結(jié)論 ；而 產(chǎn)生真實結(jié)論的推理過程未必是有效的 。有效的推理 中可能包含為 “假 ”的前提 ，而 無效的推理 卻可能得到為 “真 ”的結(jié)論 。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程6推理的有效性和結(jié)論的真實性所謂 推理有效 ， 指的是 它的結(jié)論是它的前提的合乎邏輯的結(jié)果 。 即，如果它的 前提都為真，那么所得的結(jié)論也必然為真 ，而并不是要求前提或結(jié)論一定為真或為假； 如果推理是有效的話，那么不可能它的前提都為真時，而它的結(jié)論為假。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程7 推理的基本概念和推理形式 定義 設(shè) G1, G2, …, Gn,Ｈ是公式，稱 H是 G1, G2, …, Gn的邏輯結(jié)果 (G1, G2, …, Gn共同蘊涵 H)， 當(dāng)且僅當(dāng) H 是 G1∧G 2∧…∧ Gn的邏輯結(jié)果 (logic conclusion)。 記 G1, G2, …, Gn ?Ｈ ，此時稱 G1, G2, …, Gn ?Ｈ為有效的 (efficacious)，否則稱為 無效的 （inefficacious）。 G1, G2, …, Gn稱為一組前提 (Premise)，有時用集合Г 來表示，記 Г = {G 1, G2, …, Gn}。 H稱為 結(jié)論(conclusion)。又稱 H是前提集合的邏輯結(jié)果。記為 Г ? H。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程8判定定理定理 公式 H是前提集合 Г={G 1, G2, …, Gn}的邏輯結(jié)果 當(dāng)且僅當(dāng) G1∧G 2∧…∧ Gn→ Ｈ 為永真公式。 證明： “ ?” 若 G1, G2, …, Gn ?Ｈ，但G1∧G 2∧…∧ Gn→H 不是永真式。于是，必存在 G1, G2, …, Gn， H的一個解釋 I，使得G1∧G 2∧…∧ Gn為真，而 H為假，因此對于該解釋 I，有 G1, G2, …, Gn都為真，而 H為假，這就與推理形式 G1, G2, …, Gn ?Ｈ是有效的相矛盾 .故： G1∧G 2∧…∧ Gn→H 是永真公式。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程9判定定理 （續(xù)） “ ?” 若 G1∧G 2∧…∧ Gn→H 是永真式，但 G1, G2, …, Gn ?Ｈ不是有效的推理形式， 故存在 G1, G2, …, Gn, H的一個解釋 I，使得 G1, G2, …, Gn都為真，而 H為假，故G1∧G 2∧…∧ Gn為真，而 H為假，即是說G1∧G 2∧…∧ Gn →H 為假，這 就與G1∧G 2∧…∧ Gn→H 是永真式相矛盾， 所以 G1, G2, …, Gn ?Ｈ 是有效的推理形式。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程10“ ?” 與 “→” 的不同1.“→” 僅是一般的 蘊涵聯(lián)結(jié)詞 ， G→H 的結(jié)果仍是一個公式， 而 “ ?” 卻描述了兩個公式 G， H之間的一種邏輯蘊涵關(guān)系， G ? H的 “ 結(jié)果 ” ，是非命題公式；2. 用計算機來判斷 G ? H是辦不到的。 然而計算機卻可 “ 計算 ” 公式 G→H 是否為永真公式。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程11 判斷有效結(jié)論的常用方法 要求要求 Г= ｛ G1, G2, …, Gn｝ Г ? H也就是也就是 G1∧G 2∧…∧ Gn→ Ｈ為永真公式因而因而 真值表技術(shù)、演繹法和間接證明方法電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程12真值表技術(shù) 設(shè) P1,P2,…, Pn是出現(xiàn)在前提 G1,G2,…,G n和結(jié)論 H中的一切命題變元， 如果將 P1,P2,…, Pn中所有可能的解釋及G1,G2,…,G n， H的對應(yīng)真值結(jié)果都列在一個表中， 根據(jù) “ → ” 的定義， 則有判斷方法如下：1. 對所有 G1,G2,…,G n都具有真值 T的行 (表示前提為真的行 )， 如果在每一個這樣的行中， H也具有真值 T， 則 H是 G1,G2,…,G n的邏輯結(jié)果。2. 對所有 H具有真值為 F的行 (表示結(jié)論為假的行 ),如果在每一個這樣的行中， G1,G2,…,G n中至少有一個公式的真值為 F(前提也為假 )，則 H是 G1,G2,…,G n的邏輯結(jié)果 .電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程13例 判斷下列 H是否是前提 G1,G2的邏輯結(jié)果(1)　 H： Q； G1：P； G2： P→Q ；　(2)　 H： ┐ P； G1： P→Q ； G2： ┐ Q；(3)　 H： Q； G1：┐ P； G2： P→Q 。解 P Q G1 G2 H0 0 0 1 00 1 0 1 11 0 1 0 01 1 1 1 1(1)P Q G1 G2 H0 0 1 1 10 1 1 0 11 0 0 1 01 1 1 0 0(2)P Q G1 G2 H0 0 1 1 00 1 1 1 11 0 0 0 01 1 0 1 1(3)電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程142 推理定律設(shè) G， H， I， J是任意的命題公式，則有：1) I1： G∧H ? G　　　　　　 (簡化規(guī)則 )I2： G∧H ? H2) I3： G ? G∨H 　　　　　　 (添加規(guī)則 )I4： H ? G∨H3) I5： ┐ G ? G→HI6： H ? G→H4) I7： ┐ (G→H) ? GI8： ┐ (G→H) ? ┐H5) I9： G,H ? G∧H電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程152 推理定律 (續(xù) )6） I10： ┐G, G∨ H ? H (選言 /析取 三段論) I11： ┐G, G H ? H 7） I12： G, G→H ? H (分離規(guī)則 )8） I13： ┐H, G→H ? ┐G (否定后件式 )9） I14： G→H, H→I ? G→I (假言三段論 )10） I15： G∨ H, G→I, H→ I ? I (二難推論 )電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程16例子1)、前提：　 1. 如果明天天晴，我們準備外出旅游。 P→Q　 2． 明天的確天晴。 　 　　　　　　　 P　　 結(jié)論：我們外出旅游。 　　　　 Q　 可描述為： P→Q ， P ? Q　 (分離規(guī)則 )2)、前提：　 1.　如果一個人是單身漢，則他不幸福。P→ ┐ Q　 2.　如果一個人不幸福，則他死得早。 ┐ Q→R　 　結(jié)論：單身漢死得早。 P→R　可描述為： P→ ┐ Q， ┐ Q→R ? P→R 　 (假言三段論 )電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程17例子 (續(xù) 1)3)、某 人 在某日晚歸家途中被殺害，據(jù)多方調(diào)查確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工廠值夜班，沒有外出，根據(jù)上述案情可得 ：前提 ： 。 P∨Q ，則他在作案當(dāng)晚必外出 P→R。 ┐R結(jié)論：陳某是兇手。 Q則 可描述為 ： P→R,┐R ? ┐P (否定后件式 ) P∨Q ，┐P ? Q (選言三段論 )電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程18例子 (續(xù) 2)4)、前提： 果某同學(xué)為省二級以上運動員，則他將被大學(xué)錄取。 P→R 果某同學(xué)高考總分在 560分以上，則將被大學(xué)錄取。 Q→R 同學(xué)高考總分在 560分以上或者是省二級運動員。 P∨Q結(jié)論：該同學(xué)被大學(xué)錄取。 R則上述例子可描述為： P∨Q ， P→R ， Q→R ? R　 (二難推論 )電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程193 演繹法 演繹法 是從前提 (假設(shè) )出發(fā)，依據(jù)公認的推理規(guī)則和推理定律，推導(dǎo)出一個結(jié)論來。 YN觸發(fā)規(guī)則新事實 事實 =結(jié)論？事實庫 規(guī)則匹配公理庫將事實加入到事實庫中 結(jié)束引入事實電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程20引入推理規(guī)則在數(shù)理邏輯中，主要的推理規(guī)則有：① P規(guī)則（稱為前提引用規(guī)則）： 在推導(dǎo)的過程中，可 隨時引入前提集合中的任意一個前提；② 規(guī)則Ｔ（邏輯結(jié)果引用規(guī)則）： 在推導(dǎo)的過程中，可以 隨時引入公式 S， 該公式 S是由其前的一個或多個公式推導(dǎo)出來的邏輯結(jié)果 。③ 規(guī)則ＣＰ（附加前提規(guī)則）： 如果能從給定的 前提集合 Г 與公式 P推導(dǎo)出 S， 則能從此 前提集合 Г 推導(dǎo)出 P→S 。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程21演繹的定義定義 從前提集合 Г 推出結(jié)論 H的一個 演繹 是指構(gòu)造命題公式的一個有限序列： H1， H2， …… ， Hn 其中， Hi或者是 Г 中的某個前提，或者是前面的某些 Hj（ ji）的有效結(jié)論，并且 Hn就是H，則稱公式 H為該 演繹 的有效結(jié)論，或者稱從前提 Г 能夠 演繹 出結(jié)論 H來。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程22例 證明 1 ⑴ 　 P∨Q 　　　　　 P　 ⑵ 　 ┐ P→Q 　　　　 T(1)　 ⑶ 　 Q→S 　　　　　 P　 ⑷ 　 ┐ P→S 　　　　 T⑵⑶　 ⑸ 　 ┐ S→P 　　　　 T⑷　 ⑹ 　 P?R　　　　　 P ⑺ (P→R) ?(R→P) Ｔ ⑹ ⑻ P→R Ｔ ⑺　 ⑼ ┐ S→R 　　　 T⑸⑻　 ⑽ S∨R 　　　　　 T(9)設(shè)前提 Г={P∨Q,P ?R,Q→S},G=S∨R 。 證明 Г ?G。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程23設(shè)前提 Г={P∨Q,P ?R,Q→S},G=S∨R 。 證明Г ?G。證明 2⑴ 　 ┐ S P(附加前提 ) ⑵ 　 Q→S P ⑶ 　 ┐ Q T,⑴