《離散數(shù)學-屈婉玲.ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學-屈婉玲.ppt（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、1,主要內(nèi)容 推理的形式結構 推理的正確與錯誤 推理的形式結構 判斷推理正確的方法 推理定律 自然推理系統(tǒng)P 形式系統(tǒng)的定義與分類 自然推理系統(tǒng)P 在P中構造證明:直接證明法、附加前提證明法、歸謬法,第三章 命題邏輯的推理理論,2,3.1 推理的形式結構,定義3.1 設A1, A2, , Ak, B為命題公式. 若對于每組賦值， A1A2 Ak 為假，或當A1A2Ak為真時，B也為真， 則稱由前提A1, A2, , Ak推出結論B的推理是有效的或正確 的, 并稱B是有效結論.,定理3.1 由命題公式A1, A2, , Ak 推B的推理正確當且僅當 A1A2AkB為重言式 注意: 推理正確不能保
2、證結論一定正確,3,推理的形式結構,2. A1A2AkB 若推理正確, 記為A1 A2 Ak B 3. 前提： A1, A2, , Ak 結論： B 判斷推理是否正確的方法: 真值表法 等值演算法 主析取范式法,推理的形式結構 1. A1, A2, , Ak B 若推理正確, 記為A1,A2,,An B,4,推理實例,例1 判斷下面推理是否正確 (1) 若今天是1號，則明天是5號. 今天是1號. 所以, 明天是5號. (2) 若今天是1號，則明天是5號. 明天是5號. 所以, 今天是1號.,解 設 p：今天是1號，q：明天是5號. (1) 推理的形式結構:,(pq)pq,用等值
3、演算法 (pq)pq ((pq)p)q pqq 1 由定理3.1可知推理正確,5,推理實例,(2) 推理的形式結構:,(pq)qp,用主析取范式法 (pq)qp (pq)qp ((pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 結果不含m1, 故01是成假賦值，所以推理不正確,6,推理定律重言蘊涵式,1. A (AB) 附加律 2. (AB) A 化簡律 3. (AB)A B 假言推理 4. (AB)B A 拒取式 5. (AB)B A
4、 析取三段論 6. (AB)(BC) (AC) 假言三段論 7. (AB)(BC) (AC) 等價三段論 8. (AB)(CD)(AC) (BD) 構造性二難 (AB)(AB) B 構造性二難(特殊形式) 9. (AB)(CD)( BD) (AC) 破壞性二難 每個等值式可產(chǎn)生兩個推理定律 如, 由AA可產(chǎn)生 AA 和 AA,7,3.2 自然推理系統(tǒng)P,定義3.2 一個形式系統(tǒng) I 由下面四個部分組成： (1) 非空的字母表，記作 A(I). (2) A(I) 中符號構造的合式公式集，記作 E(I). (3) E(I) 中一些特殊
5、的公式組成的公理集，記作 AX(I). (4) 推理規(guī)則集，記作 R(I). 記I=, 其中是 I 的 形式語言系統(tǒng), 是 I 的形式演算系統(tǒng). 自然推理系統(tǒng): 無公理, 即AX(I)= 公理推理系統(tǒng) 推出的結論是系統(tǒng)中的重言式, 稱作定理,8,自然推理系統(tǒng)P,定義3.3 自然推理系統(tǒng) P 定義如下: 1. 字母表 (1) 命題變項符號：p, q, r, , pi, qi, ri, (2) 聯(lián)結詞符號：, , , , (3) 括號與逗號：(, ), ， 2. 合式公式（同定義1.6） 3. 推理規(guī)則 (1) 前提引入規(guī)則 (2) 結論引入規(guī)則 (3) 置換規(guī)則,9,推理規(guī)則,(4) 假言推
6、理規(guī)則 (6) 化簡規(guī)則 (8) 假言三段論規(guī)則,(5) 附加規(guī)則 (7) 拒取式規(guī)則 (9) 析取三段論規(guī)則,10,推理規(guī)則,(10) 構造性二難推理規(guī)則 (11) 破壞性二難推理規(guī)則 (12) 合取引入規(guī)則,11,在自然推理系統(tǒng)P中構造證明,設前提A1, A2,, Ak,結論B及公式序列C1, C2,, Cl. 如果每 一個Ci(1il)是某個Aj, 或者可由序列中前面的公式應用推理 規(guī)則得到, 并且Cl =B, 則稱這個公式序列是由A1, A2,, Ak推 出B的證明 例2 構造下面推理的證明： 若明天是星期一或星期三，我明天就有課. 若我明天
7、有 課，今天必備課. 我今天沒備課. 所以，明天不是星期一、 也不是星期三. 解 (1) 設命題并符號化 設 p：明天是星期一，q：明天是星期三， r：我明天有課，s：我今天備課,12,直接證明法,(2) 寫出證明的形式結構 前提：(pq)r, rs, s 結論：pq (3) 證明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置換,13,附加前提證明法,附加前提證明法 適用于結論為蘊涵式 欲證 前提：A1, A2, , Ak 結論：CB 等價地證明 前提：A1, A2, ,
8、Ak, C 結論：B 理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,14,附加前提證明法實例,例3 構造下面推理的證明 2是素數(shù)或合數(shù). 若2是素數(shù)，則 是無理數(shù). 若 是無理數(shù)，則4不是素數(shù). 所以，如果4是素數(shù)，則2是合數(shù). 解 用附加前提證明法構造證明 (1) 設 p：2是素數(shù)，q：2是合數(shù)， r： 是無理數(shù)，s：4是素數(shù) (2) 推理的形式結構 前提：pq, pr, rs 結論：sq,15,附加前提證明法實例,(3) 證明 s 附加前提引入 pr 前提引入 rs
9、 前提引入 ps 假言三段論 p 拒取式 pq 前提引入 q 析取三段論,16,歸謬法（反證法）,歸謬法 (反證法) 欲證 前提：A1, A2, , Ak 結論：B 做法 在前提中加入B，推出矛盾. 理由 A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB0,17,歸謬法實例,例4 前提：(pq)r, rs, s, p 結論：q 證明 用歸繆法 q 結論否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提
10、引入 (pq) 析取三段論 pq 置換 p 析取三段論 p 前提引入 pp 合取,18,第三章 習題課,主要內(nèi)容 推理的形式結構 判斷推理是否正確的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系統(tǒng)P 構造推理證明的方法 直接證明法 附加前提證明法 歸謬法(反證法),19,基本要求,理解并記住推理形式結構的兩種形式： 1. (A1A2Ak)B 2. 前提：A1, A2, , Ak 結論：B 熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等） 牢記 P 系統(tǒng)中各條推理規(guī)則 熟練掌
11、握構造證明的直接證明法、附加前提證明法和歸謬 法 會解決實際中的簡單推理問題,20,練習1：判斷推理是否正確,1. 判斷下面推理是否正確: (1) 前提：pq, q 結論：p,解 推理的形式結構:,(pq)qp,方法一：等值演算法 (pq)qp ((pq)q)p (pq)qp ((pq)(qq))p pq,易知10是成假賦值，不是重言式，所以推理不正確.,21,練習1解答,方法二：主析取范式法， (pq)qp ((pq)q)p pq M2 m0m1m3 未含m2, 不是重言式, 推理不正確.,22,練習1解答,方法三 真值表法 不是重言式, 推理不正確,方法四
12、直接觀察出10是成假賦值,23,練習1解答,用等值演算法 (qr)(pr)(qp) (qr)(pr)(qp) ((qr)(pr))(qp) ((qp)(qr)(rp))(qp) ((qp)(qr)(rp))(qp) 1 推理正確,(2) 前提：qr, pr 結論：qp,解 推理的形式結構：,(qr)(pr)(qp),24,練習2：構造證明,2. 在系統(tǒng)P中構造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩. 如果頤和 園游人太多，就不去頤和園. 今天是周六，并且頤和園游 人太多. 所以, 我們?nèi)A明園或動物園玩.,證明： (1) 設 p：今天是周六，q：到頤和園玩， r：到圓明園玩，s：頤和園游人太多 t：到動物園玩 (2) 前提：p(qr), sq, p, s 結論：rt,25,練習2解答,(3) 證明： p(qr) 前提引入 p 前提引入 qr 假言推理 sq 前提引入 s 前提引入 q 假言推理 r 析取三段論 rt 附加,
離散數(shù)學-屈婉玲.ppt
