離散數(shù)學(xué)3完整版

1、 Discrete Math. 2 第一章第一章 命題邏輯的推理理論命題邏輯的推理理論 3.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 3.2 自然推理系統(tǒng)自然推理系統(tǒng)P Discrete Math. 3 推理是指從一些已知的命題公式（稱為前提推理是指從一些已知的命題公式（稱為前提) )應(yīng)用推理規(guī)則應(yīng)用推理規(guī)則 推演出另一些命題公式（稱為結(jié)論）的過程。推演出另一些命題公式（稱為結(jié)論）的過程。 定義定義3.1 3.1 設(shè)設(shè)A A1 1, A, A2 2, , A, , Ak和和B B是命題公式，若對于是命題公式，若對于A A1 1, A, A2 2, , , , A Ak, B, B中出現(xiàn)的命題變項的任一

2、組賦值，中出現(xiàn)的命題變項的任一組賦值，要么要么A A1 1AA2 2AAk為為 假假，要么要么A A 1 1A A 2 2A A k為真且 為真且B B也為真也為真, , 則稱由前提則稱由前提A A1 1, , A A2 2, , A, , Ak 推出推出B B的推理是的推理是有效的有效的（或正確的（或正確的) )，并稱，并稱B B是有效是有效 的結(jié)論的結(jié)論。 3.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) A A1 1AA2 2AAk kB B永真永真 注：注： 1 1、由前提、由前提A A1 1,A,A2 2,A,Ak k 推結(jié)論推結(jié)論B B的推理是否正確與諸前提的排列的推理是否正確與諸前提的排列

3、次序無關(guān)。次序無關(guān)。 將一個推理諸前提的集合記為將一個推理諸前提的集合記為，則由，則由推出結(jié)論推出結(jié)論B B的推理記的推理記 為為 B B。若該推理是正確的，則記為。若該推理是正確的，則記為 B ( B (或或B B), ), 否否 則記為則記為 B B ( (或或 B)B)。稱。稱 B B 和和 AA1 1,A,A2 2,A,Ak k B B 為為推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)。 Discrete Math. 4 2、設(shè)命題公式設(shè)命題公式A1, A2, , Ak, B中共有中共有n個命題變項。對于任一組個命題變項。對于任一組 賦值賦值 1, 2, , n ( i 取取0或或1, i=1,2,

4、n), 前提和結(jié)論的取值情前提和結(jié)論的取值情 況有如下四種：況有如下四種： (1) A1A2 Ak 為為0，B為為0 (2) A1A2 Ak 為為0，B為為1 (3) A1A2 Ak 為為1，B為為0 (4) A1A2 Ak 為為1，B為為1 12k 0 0 , B= AA.A =1 1 , B=1 按照定義，按照定義，只要不出現(xiàn)只要不出現(xiàn)(3)，推理就是正確的，推理就是正確的。因而判斷一個推。因而判斷一個推 理正確與否，只需判斷是否會出現(xiàn)情況理正確與否，只需判斷是否會出現(xiàn)情況(3)即可。即可。 3、推理正確，并不能保證結(jié)論推理正確，并不能保證結(jié)論B一定為真。因為前提可能是假的一定為真。因為前

5、提可能是假的 (情況情況(1)。 Discrete Math. 5 例例3.1 判斷下列推理是否正確判斷下列推理是否正確 (1)(1)p, pq q； (2)(2)p, qp q 解：用真值表法解：用真值表法 p qp(pq) qp(qp) q 0 0 0 1 1 0 1 1 (1) 從真值表可見，沒有出現(xiàn)前提從真值表可見，沒有出現(xiàn)前提p(pq)為真，結(jié)論為真，結(jié)論q為假的為假的 情況，故情況，故p, pq q。 (2) 在賦值為在賦值為10時，出現(xiàn)了前提時，出現(xiàn)了前提p(qp)為真而為真而q為假的情況，為假的情況， 故故p,qp q。 0 0 0 1 0 0 0 1 0 0 1 0 1 11

6、 1 Discrete Math. 6 定理定理3.13.1 命題公式命題公式 A A1 1,A,A2 2,A,Ak k推推 B B的推理正確的推理正確, 即即AA1 1,A,A2 2,A,Ak k B B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)( (A A1 1A A2 2A Ak k)BB為重言式為重言式。 證明證明 見教材見教材4343頁。頁。 由該定理，推理的由該定理，推理的形式結(jié)構(gòu)形式結(jié)構(gòu)： AA1 1,A,A2 2,A,Ak kB B （3.13.1） 可用可用 (A(A1 1AA2 2AAk k)B )B （3.23.2） 表示。表示。 判斷推理是否正確的三種直接方法：判斷推理是否正確的三種直接方法：

7、1、真值表法、真值表法 2、等值演算法、等值演算法 3 、主析取范式法、主析取范式法 或?qū)懗苫驅(qū)懗?前提：前提：A A1 1,A,A2 2,A,Ak k 結(jié)論：結(jié)論：B B （3.53.5） 然后論證推理是否正確！然后論證推理是否正確！ 同時同時AA1 1,A,A2 2,A,Ak k B B 換成換成A A1 1AA2 2AAk k B B Discrete Math. 7 (1) 若若a能被能被4整除，則整除，則a能被能被2整除。整除。a 能被能被4整除，所以整除，所以 a能被能被2 整除。整除。 (2) 下午馬芳或去看電影或去游泳。她沒去看電影，所以她去游下午馬芳或去看電影或去游泳。她沒去

8、看電影，所以她去游 泳了。泳了。 (3) 若下午氣溫超過若下午氣溫超過30，則王小燕必去游泳。若她去游泳，她，則王小燕必去游泳。若她去游泳，她 就不去看電影了。所以，若王小燕沒去看電影，下午氣溫必超就不去看電影了。所以，若王小燕沒去看電影，下午氣溫必超 過了過了30。 解：解：(1) 設(shè)設(shè)p：a能被能被4整除；整除； q：a能被能被2整除整除 前提：前提：pq，p 結(jié)論：結(jié)論：q 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)：(pq)pq 由例由例3.1知道此推理正確，即知道此推理正確，即(pq)p q。 例例3.2 判斷下列推理是否正確。判斷下列推理是否正確。 Discrete Math. 8 (2) 設(shè)

9、設(shè) p: 馬芳下午去看電影；馬芳下午去看電影；q：馬芳下午去游泳。：馬芳下午去游泳。 前提：前提：pq, p 結(jié)論：結(jié)論：q 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)：(pq)p)q 我們用等值演算來檢驗該蘊含式是否為重言式。我們用等值演算來檢驗該蘊含式是否為重言式。 (pq)p)q (pq)p)q (pq)p)q (pp)(qp)q qpq 1 可見可見(pq)p)q 是重言式，故是重言式，故(pq)p) q, 推理正確。推理正確。 Discrete Math. 9 (3) 設(shè)設(shè)p: 下午超過下午超過30；q：王小燕去游泳；：王小燕去游泳；r：王小燕去看電影。：王小燕去看電影。 前提：前提：pq，q

10、r 結(jié)論：結(jié)論：rp 推理形式結(jié)構(gòu)：推理形式結(jié)構(gòu)：( ( (pq)()(q r)(rp) ) 我們用主析取式法檢驗該蘊含式是否為重言式。我們用主析取式法檢驗該蘊含式是否為重言式。 (pq)()(q r)(rp) ) (pq)()(q r)( ( rp) ) (pq)()(q r )rp pr 兩次吸收律兩次吸收律 ( (pqr)(pqr)(pqr)(pqr) ( (pqr)(pqr)(pqr)(pqr) (用例用例2.11(1) m1 m3 m4m5 m6 m7 可見，主析取范式中少兩個極小項可見，主析取范式中少兩個極小項m0和和 m2，從而推理不正確。，從而推理不正確。 Discrete M

11、ath. 10 在研究推理過程中，人們發(fā)現(xiàn)了一些重要的重言蘊含式，并將它在研究推理過程中，人們發(fā)現(xiàn)了一些重要的重言蘊含式，并將它 們作為推理定律，在推理過程中可直接引用。常用的推理定律有：們作為推理定律，在推理過程中可直接引用。常用的推理定律有： (1)(1) 附加律附加律: A AB (2) 化簡律化簡律: AB A (3) 假言推理假言推理: (AB)A B (4) 拒取式拒取式: (AB)B A (5) 析取三段論析取三段論: (AB)B A (6) 假言三段論假言三段論: (AB)(BC) (AC) (7) 等價三段論等價三段論: (AB)(BC) (AC) (8) 構(gòu)造性二難構(gòu)造性二

12、難: (AB)(CD)(AC) (BD) 構(gòu)造性二難構(gòu)造性二難(特殊形式特殊形式): (AB)(AB)(AA) B (9) 破壞性二難破壞性二難: (AB)(CD)(BD)(AC) 推理定律推理定律 Discrete Math. 11 此外此外, 2.1中中給出的給出的24個等值式中的每一個都派生出兩條推理定個等值式中的每一個都派生出兩條推理定 律律. 比如比如 A A產(chǎn)生出產(chǎn)生出AA 和和A A . 還有一些還有一些等值式等值式和和重言蘊含式重言蘊含式可在推理中引用可在推理中引用。如如: A (AB)(AB) (AB) AB A(BC) (AB) C (AB) (AB)(AB) (AB) A

13、B A AB B AB AB (AC)(BC) AB (AC)(BC) Discrete Math. 12 “ “證明證明”是一個描述推理過程的命題公式序列是一個描述推理過程的命題公式序列, ,其中的每個其中的每個 公式或者是已知前提公式或者是已知前提, ,或者是由某些前提應(yīng)用推理規(guī)則得到的或者是由某些前提應(yīng)用推理規(guī)則得到的 結(jié)論結(jié)論. . 注注: : 前已述及前已述及, ,可以用真值表法、等值演算法和主析取范式法來可以用真值表法、等值演算法和主析取范式法來 判斷推理是否正確判斷推理是否正確。但當(dāng)推理中包含的命題變項較多時但當(dāng)推理中包含的命題變項較多時, ,這些這些 方法的演算量很大方法的演算

14、量很大. .因而需要對推理進行嚴(yán)謹(jǐn)?shù)淖C明因而需要對推理進行嚴(yán)謹(jǐn)?shù)淖C明。證明應(yīng)證明應(yīng) 在推理系統(tǒng)中進行在推理系統(tǒng)中進行. . 3.2 自然推理系統(tǒng)自然推理系統(tǒng) Discrete Math. 13 定義定義3.2一個形式系統(tǒng)一個形式系統(tǒng)I由下面四個部分組成：由下面四個部分組成： (1)非空的字母表集，記作非空的字母表集，記作A(I). (2)A(I)中符號構(gòu)造的合式公式集，記作中符號構(gòu)造的合式公式集，記作E(I). (3) E(I)中一些特殊的公式組成的公理集，記作中一些特殊的公式組成的公理集，記作AX(I). (4)推理規(guī)則集，記作推理規(guī)則集，記作R(I). 這樣可將這樣可將I記為記為4元組元組

15、.其中其中是是I的的形形 式語言系統(tǒng)式語言系統(tǒng),為為I的的形式演算系統(tǒng)形式演算系統(tǒng)。 形式系統(tǒng)一般分為兩類：形式系統(tǒng)一般分為兩類： 一是一是自然推理系統(tǒng)自然推理系統(tǒng)：它的特點是從任意給定的前提出發(fā)，應(yīng)用系統(tǒng)：它的特點是從任意給定的前提出發(fā)，應(yīng)用系統(tǒng) 中的推理規(guī)則進行推理演算，得到的最后命題公式是推理的結(jié)論。中的推理規(guī)則進行推理演算，得到的最后命題公式是推理的結(jié)論。 另外的則是另外的則是公理推理系統(tǒng)公理推理系統(tǒng)：它只能從若干給定的公理出發(fā)，應(yīng)用：它只能從若干給定的公理出發(fā)，應(yīng)用 系統(tǒng)的推理規(guī)則進行推理演算。得到的結(jié)論是系統(tǒng)中的重言式，稱為系統(tǒng)的推理規(guī)則進行推理演算。得到的結(jié)論是系統(tǒng)中的重言式，稱

16、為 系統(tǒng)中的系統(tǒng)中的定理定理。 Discrete Math. 14 定義定義3.3 自然推理系統(tǒng)自然推理系統(tǒng)P由以下三部分要素組成由以下三部分要素組成: 1. 字母表字母表: (1) 命題變項符號命題變項符號: : p, q, r, (2) 聯(lián)結(jié)詞符號聯(lián)結(jié)詞符號: , , (3)逗號與括號逗號與括號: ，, ( ) 2. 合式公式集合式公式集 (合式公式的定義見定義合式公式的定義見定義1.6). 3. 推理規(guī)則推理規(guī)則: (1) 前提引入規(guī)則前提引入規(guī)則: 在證明的任何步驟上都可引入前提在證明的任何步驟上都可引入前提; (2) 結(jié)論引入規(guī)則結(jié)論引入規(guī)則: 在證明的任何步驟上所得到的結(jié)論都可做為

17、在證明的任何步驟上所得到的結(jié)論都可做為 后續(xù)證明的前提后續(xù)證明的前提. (3) 置換規(guī)則置換規(guī)則: 在證明的任何步驟上在證明的任何步驟上, 命題公式中的子公式都可以命題公式中的子公式都可以 用與之等值的公式置換用與之等值的公式置換. Discrete Math. 15 (4)假言推理規(guī)則假言推理規(guī)則 AB AB _A_ _A_ B B （6 6）化簡規(guī)則）化簡規(guī)則 AB_ AB_ A A （7 7）拒絕式規(guī)則）拒絕式規(guī)則 AB AB _B_B_ AA (5) (5)附加規(guī)則附加規(guī)則 _A_A_ ABAB (8)(8)假言三段論規(guī)則假言三段論規(guī)則 AB AB _BC_BC_ AC AC (9)(

18、9)析取三段論規(guī)則析取三段論規(guī)則 AB AB _B _B _ _ A A （1010）構(gòu)造性二難推理規(guī)則）構(gòu)造性二難推理規(guī)則 ABAB CD CD _AC_AC_ BD BD (12)(12)合取引入規(guī)則合取引入規(guī)則 A A _B_B_ AB AB （1111）破壞性二難推理規(guī)則）破壞性二難推理規(guī)則 AB AB CD CD _BD_BD_ AC AC Discrete Math. 16 q q qr qr r r r r(p(pq)q) 前提引入規(guī)則前提引入規(guī)則, 結(jié)論引入規(guī)則結(jié)論引入規(guī)則, 置換規(guī)則置換規(guī)則, 假言推理規(guī)則假言推理規(guī)則, 附加規(guī)則附加規(guī)則, 化簡規(guī)則化簡規(guī)則, 拒絕式規(guī)則拒絕

19、式規(guī)則,假言三段論規(guī)則假言三段論規(guī)則, 析取三段論規(guī)則析取三段論規(guī)則, 構(gòu)造性二難推理規(guī)則構(gòu)造性二難推理規(guī)則, 破壞性二難推理規(guī)則破壞性二難推理規(guī)則, 合取引入規(guī)則合取引入規(guī)則 例例3.3 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明中構(gòu)造下面推理的證明: (1) 前提前提: pq,qr,ps,s 結(jié)論結(jié)論: r(pq) qr r(pq) spqps pq r p q 證明證明: : ps ps s s p p p pq q 合取 假言推理 拒取式 析取三段式 前提引入前提引入 前提引入前提引入 拒取式拒取式 前提引入前提引入 析取三段式析取三段式 前提引入前提引入 假言推理假言推理 合

20、取合取 Discrete Math. 17 (2)(2) 前提前提: : p pq, rq, rq, rsq, rs 結(jié)論結(jié)論: ps: ps 前提引入規(guī)則前提引入規(guī)則, 結(jié)論引入規(guī)則結(jié)論引入規(guī)則, 置換規(guī)則置換規(guī)則, 假言推理規(guī)則假言推理規(guī)則, 附加規(guī)則附加規(guī)則, 化簡規(guī)則化簡規(guī)則, 拒絕式規(guī)則拒絕式規(guī)則,假言三段論規(guī)則假言三段論規(guī)則, 析取三段論規(guī)則析取三段論規(guī)則, 構(gòu)造性二難推理規(guī)則構(gòu)造性二難推理規(guī)則, 破壞性二難推理規(guī)則破壞性二難推理規(guī)則, 合取引入規(guī)則合取引入規(guī)則 證明證明: : pq pq rq qr pr rs ps pr 假言三段論 pqrqrs ps rs pqqr 置換置換

21、 假言三段論 前提引入前提引入 置換置換 前提引入前提引入 置換置換 假言三段論假言三段論 前提引入前提引入 假言三段假言三段論論 Discrete Math. 18 證明證明: ps p s p(qr) 例例3.4 在在自然推理系統(tǒng)自然推理系統(tǒng)P中構(gòu)造下面推理的證明中構(gòu)造下面推理的證明: 若數(shù)若數(shù)a 是實數(shù)是實數(shù), 則它不是有理數(shù)就是無理數(shù)。若則它不是有理數(shù)就是無理數(shù)。若a不能表示成分?jǐn)?shù)不能表示成分?jǐn)?shù), 則它則它 不是有理數(shù)。不是有理數(shù)。a 是實數(shù)且它不能表示成分?jǐn)?shù)是實數(shù)且它不能表示成分?jǐn)?shù), 所以所以a是無理數(shù)。是無理數(shù)。 解解: 令令 p: a是實數(shù)是實數(shù); q: a是有理數(shù)是有理數(shù); r

22、: a是無理數(shù)是無理數(shù); s: a能表示成分?jǐn)?shù)能表示成分?jǐn)?shù). 前提前提: p(qr), s q, p s 結(jié)論結(jié)論: r qr s q q r p(qr)s qp s r q ps qr 析取三段論 假言推理 p 化簡 假言推理 前提引入前提引入 化簡化簡 化簡化簡 前提引入前提引入 假言推理假言推理 前提引入前提引入 假言推理假言推理 析取三段論析取三段論 Discrete Math. 19 1.1.附加前提證明法附加前提證明法: : 欲證欲證 (A(A1 1AA2 2 A Ak k) )(AB), (AB), (A (A1 1AA2 2AAk k) (AB) (AB) (A (A1 1AA

23、2 2AAk k) (AB) (AB) (A (A1 1 A A2 2AAk k A)BA)B (A (A1 1AA2 2AAk k A) B A) B (A(A1 1AA2 2AAk k A) B A) B 可改證可改證(A(A1 1AA2 2AAk kA)A)B B。 道理如下道理如下: : Discrete Math. 20 例例3.5 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明： 如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小 張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時，小李必

24、定也去。張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時，小李必定也去。 解：令解：令 p: 小張去看電影；小張去看電影；q: 小王去看電影；小王去看電影； r: 小李去看電影；小李去看電影； s: 小趙去看電影。小趙去看電影。 前提：前提：(pq) r, sp, q 結(jié)論：結(jié)論：sr 證明：用附加前提法。證明：用附加前提法。 s sp p q pq (pq)r r r (pq) r spqs pq p 假言推理 合取 析取三段論 附加前提引入附加前提引入 前提引入前提引入 析取三段論析取三段論 前提引入前提引入 合取合取 前提引入前提引入 假言推理假言推理 Discrete Math. 21

25、 前提：前提：(pq) r, sp, q 結(jié)論：結(jié)論：sr 證明：證明： sp s p (pq)r pqr q pr s r s r (pq) r spq 析取三段論析取三段論 直接證明法直接證明法 s p p r pqr 置換置換 置換置換 假言三段論假言三段論 前提引入前提引入 置換置換 前提引入前提引入 置換置換 前提引入前提引入 析取三段論析取三段論 假言三段論假言三段論 Discrete Math. 22 2.2.歸謬法：歸謬法： 欲證欲證 (A(A1 1AA2 2 A Ak k) )B B， 道理如下：道理如下： 若將若將BB做為附加前提后能得出矛盾做為附加前提后能得出矛盾( (比如得到比如得到AA), AA), 則