離散數(shù)學(xué)3PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 離散數(shù)學(xué)離散數(shù)學(xué)3 2 第一章 命題邏輯的推理理論 3.1 推理的形式結(jié)構(gòu) 3.2 自然推理系統(tǒng)P 第1頁(yè)/共24頁(yè) 3 推理是指從一些已知的命題公式（稱(chēng)為前提)應(yīng)用推理規(guī)則推演出另一些命題公式（稱(chēng)為結(jié)論）的過(guò)程。 定義3.1 設(shè)A1, A2, , Ak和B是命題公式，若對(duì)于A1, A2, , Ak, B中出現(xiàn)的命題變項(xiàng)的任一組賦值，要么A1A2Ak為假，要么A1A2Ak為真且B也為真, 則稱(chēng)由前提A1, A2, , Ak 推出B的推理是有效的（或正確的)，并稱(chēng)B是有效的結(jié)論。 3.1 推理的形式結(jié)構(gòu) A1A2AkB永真 注： 1、由前提A1,A2,Ak 推結(jié)論B的推理是否正確與諸前

2、提的排列次序無(wú)關(guān)。 將一個(gè)推理諸前提的集合記為，則由推出結(jié)論B的推理記為 B。若該推理是正確的，則記為 B (或B), 否則記為 B (或 B)。稱(chēng) B 和 A1,A2,Ak B為推理的形式結(jié)構(gòu)。 第2頁(yè)/共24頁(yè) 4 2、設(shè)命題公式A1, A2, , Ak, B中共有n個(gè)命題變項(xiàng)。對(duì)于任一組 賦值1, 2, , n (i 取0或1, i=1,2, n), 前提和結(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

3、=1 按照定義，只要不出現(xiàn)(3)，推理就是正確的。因而判斷一個(gè)推理正確與否，只需判斷是否會(huì)出現(xiàn)情況(3)即可。 3、推理正確，并不能保證結(jié)論B一定為真。因?yàn)榍疤峥赡苁羌俚?情況(1)。 第3頁(yè)/共24頁(yè) 5 例3.1 判斷下列推理是否正確 (1)p, pq q； (2)p, qp q 解：用真值表法 p qp(pq) qp(qp) q 0 0 0 1 1 0 1 1 (1) 從真值表可見(jiàn)，沒(méi)有出現(xiàn)前提p(pq)為真，結(jié)論q為假的情況，故p, pq q。 (2) 在賦值為10時(shí)，出現(xiàn)了前提p(qp)為真而q為假的情況，故p,qp q。 0 0 0 1 0 0 0 1 0 0 1 0 1 11 1

4、 第4頁(yè)/共24頁(yè) 6 定理3.1 命題公式 A1,A2,Ak推 B的推理正確, 即A1,A2,Ak B當(dāng)且僅當(dāng)(A1A2Ak)B為重言式。 證明 見(jiàn)教材43頁(yè)。 由該定理，推理的形式結(jié)構(gòu)： A1,A2,AkB （3.1） 可用 (A1A2Ak)B （3.2） 表示。 判斷推理是否正確的三種直接方法： 1、真值表法 2、等值演算法 3 、主析取范式法 或?qū)懗?前提：A1,A2,Ak 結(jié)論：B （3.5） 然后論證推理是否正確！ 同時(shí)A1,A2,Ak B 換成A1A2Ak B 第5頁(yè)/共24頁(yè) 7 (1) 若a能被4整除，則a能被2整除。a 能被4整除，所以 a能被2 整除。 (2) 下午馬芳或

5、去看電影或去游泳。她沒(méi)去看電影，所以她去 游泳了。 (3) 若下午氣溫超過(guò)30，則王小燕必去游泳。若她去游泳， 她就不去看電影了。所以，若王小燕沒(méi)去看電影，下午氣溫必 超過(guò)了30。 解：(1) 設(shè)p：a能被4整除； q：a能被2整除 前提：pq，p 結(jié)論：q 推理的形式結(jié)構(gòu)：(pq)pq 由例3.1知道此推理正確，即(pq)p q。 例3.2 判斷下列推理是否正確。 第6頁(yè)/共24頁(yè) 8 (2) 設(shè) p: 馬芳下午去看電影；q：馬芳下午去游泳。 前提：pq, p 結(jié)論：q 推理的形式結(jié)構(gòu)：(pq)p)q 我們用等值演算來(lái)檢驗(yàn)該蘊(yùn)含式是否為重言式。 (pq)p)q (pq)p)q (pq)p)q

6、 (pp)(qp)q qpq 1 可見(jiàn)(pq)p)q 是重言式，故(pq)p) q, 推理正確。 第7頁(yè)/共24頁(yè) 9 (3) 設(shè)p: 下午超過(guò)30；q：王小燕去游泳；r：王小燕去看電影。 前提：pq，q r 結(jié)論：rp 推理形式結(jié)構(gòu)：(pq)(q r)(rp) 我們用主析取式法檢驗(yàn)該蘊(yùn)含式是否為重言式。 (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 可見(jiàn)，主析取范式中少兩個(gè)極小項(xiàng)m0和 m2，從而推

7、理不正確。 第8頁(yè)/共24頁(yè) 10 在研究推理過(guò)程中，人們發(fā)現(xiàn)了一些重要的重言蘊(yùn)含式，并將它 們作為推理定律，在推理過(guò)程中可直接引用。常用的推理定律有： (1) 附加律: A AB (2) 化簡(jiǎn)律: AB A (3) 假言推理: (AB)A B (4) 拒取式: (AB)B A (5) 析取三段論: (AB)B A (6) 假言三段論: (AB)(BC) (AC) (7) 等價(jià)三段論: (AB)(BC) (AC) (8) 構(gòu)造性二難: (AB)(CD)(AC) (BD) 構(gòu)造性二難(特殊形式): (AB)(AB)(AA) B (9) 破壞性二難: (AB)(CD)(BD)(AC) 推理定律 第

8、9頁(yè)/共24頁(yè) 11 此外, 2.1中給出的24個(gè)等值式中的每一個(gè)都派生出兩條推理定律. 比 如 A A產(chǎn)生出AA 和A A . 還有一些等值式和重言蘊(yùn)含式可在推理中引用。如: A (AB)(AB) (AB) AB A(BC) (AB) C (AB) (AB)(AB) (AB) AB A AB B AB AB (AC)(BC) AB (AC)(BC) 第10頁(yè)/共24頁(yè) 12 “證明”是一個(gè)描述推理過(guò)程的命題公式序列,其中的每個(gè)公式或者是已知前提,或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論. 注: 前已述及,可以用真值表法、等值演算法和主析取范式法來(lái)判斷推理是否正確。但當(dāng)推理中包含的命題變項(xiàng)較多時(shí)

9、,這些方法的演算量很大.因而需要對(duì)推理進(jìn)行嚴(yán)謹(jǐn)?shù)淖C明。證明應(yīng)在推理系統(tǒng)中進(jìn)行. 3.2 自然推理系統(tǒng) 第11頁(yè)/共24頁(yè) 13 第12頁(yè)/共24頁(yè) 14 定義3.3 自然推理系統(tǒng)P由以下三部分要素組成: 1. 字母表: (1) 命題變項(xiàng)符號(hào): p, q, r, (2) 聯(lián)結(jié)詞符號(hào): , , (3)逗號(hào)與括號(hào): ，, ( ) 2. 合式公式集 (合式公式的定義見(jiàn)定義1.6). 3. 推理規(guī)則: (1) 前提引入規(guī)則: 在證明的任何步驟上都可引入前提; (2) 結(jié)論引入規(guī)則: 在證明的任何步驟上所得到的結(jié)論都可做為 后續(xù)證明的前提. (3) 置換規(guī)則: 在證明的任何步驟上, 命題公式中的子公式都可

10、 以用與之等值的公式置換. P 第13頁(yè)/共24頁(yè) 15 推理規(guī)則推理規(guī)則 (4)假言推理規(guī)則 AB _A_ B （6）化簡(jiǎn)規(guī)則 AB_ A （7）拒絕式規(guī)則 AB _B_ A (5)附加規(guī) 則 _A_ AB (8)假言三段論規(guī)則 AB _BC_ AC (9)析取三段論規(guī)則 AB _B _ A （10）構(gòu)造性二難推理規(guī)則 AB CD _AC_ BD (12)合取引入規(guī)則 A _B_ AB （11）破壞性二難推理規(guī)則 AB CD _BD_ AC 第14頁(yè)/共24頁(yè) 16 q qr r r(pq) 前提引入規(guī)則, 結(jié)論引入規(guī)則, 置換規(guī)則, 假言推理規(guī)則, 附加規(guī)則, 化簡(jiǎn)規(guī)則, 拒絕式規(guī)則,假言

11、三段論規(guī)則, 析取三段論規(guī)則, 構(gòu)造性二難推理規(guī)則, 破壞性二難推理規(guī)則, 合取引入規(guī)則 例3.3 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明: (1) 前提: pq,qr,ps,s 結(jié)論: r(pq) qr r(pq) spqps pq r p q 證明: ps s p pq 合取 假言推理 拒取式 析取三段 式 前提引入 前提引入 拒取式 前提引入 析取三段式 前提引入 假言推理 合取 第15頁(yè)/共24頁(yè) 17 (2) 前提: pq, rq, rs 結(jié)論: ps 前提引入規(guī)則, 結(jié)論引入規(guī)則, 置換規(guī)則, 假言推理規(guī)則, 附加規(guī)則, 化簡(jiǎn)規(guī)則, 拒絕式規(guī)則,假言三段論規(guī)則, 析取三段論規(guī)則, 構(gòu)

12、造性二難推理規(guī)則, 破壞性二難推理規(guī)則, 合取引入規(guī)則 證明: pq pq rq qr pr rs ps pr 假言三段論 pqrqrs ps rs pqqr 置換置換 假言三段論 前提引入 置換 前提引入 置換 假言三段論 前提引入 假言三段論 第16頁(yè)/共24頁(yè) 18 證明: ps p s p(qr) 例3.4 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明: 若數(shù)a 是實(shí)數(shù), 則它不是有理數(shù)就是無(wú)理數(shù)。若a不能表示成分?jǐn)?shù), 則它 不是有理數(shù)。a 是實(shí)數(shù)且它不能表示成分?jǐn)?shù), 所以a是無(wú)理數(shù)。 解: 令 p: a是實(shí)數(shù); q: a是有理數(shù); r: a是無(wú)理數(shù); s: a能表示成分?jǐn)?shù). 前提: p(qr

13、), s q, p s 結(jié)論: r qr s q q r p(qr)s qp s r q ps qr 析取三段論 假言推理 p 化簡(jiǎn) 假言推理 前提引入 化簡(jiǎn) 化簡(jiǎn) 前提引入 假言推理 前提引入 假言推理 析取三段論 第17頁(yè)/共24頁(yè) 19 1.附加前提證明法: 欲證 (A1A2 Ak)(AB), (A1A2Ak) (AB) (A1A2Ak) (AB) (A1 A2Ak A)B (A1A2Ak A) B (A1A2Ak A) B 可改證(A1A2AkA)B。 道理如下: 構(gòu)造證明的兩個(gè)技巧構(gòu)造證明的兩個(gè)技巧 第18頁(yè)/共24頁(yè) 20 例3.5 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明： 如果小張

14、和小王去看電影，則小李也去看電影。小趙不去看電影或小 張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李必定也去。 解：令 p: 小張去看電影；q: 小王去看電影； r: 小李去看電影； s: 小趙去看電影。 前提：(pq) r, sp, q 結(jié)論：sr 證明：用附加前提法。 s sp p q pq (pq)r r r (pq) r spqs pq p 假言推理 合取 析取三段論 附加前提引入 前提引入 析取三段 論 前提引入 合取 前提引入 假言推理 附加前提證明法附加前提證明法 第19頁(yè)/共24頁(yè) 21 前提：(pq) r, sp, q 結(jié)論：sr 證明： sp s p (pq)r p

15、qr q pr s r s r (pq) r spq 析取三段論 直接證明法 s p p r pqr 置換 置換 假言三段論 前提引入 置換 前提引入 置換 前提引入 析取三段論 假言三段論 第20頁(yè)/共24頁(yè) 22 2.歸謬法： 欲證 (A1A2 Ak)B， 道理如下： 若將B做為附加前提后能得出矛盾(比如得到AA), 則說(shuō)明原推理正確。 (A1A2Ak ) B (A1A2Ak) B (A1A2Ak B) 可見(jiàn),若A1A2AkB為矛盾式， 則A1A2AkB為重言式。 歸謬法歸謬法 第21頁(yè)/共24頁(yè) 23 如果小張守第一壘并且小李向B隊(duì)投球，則A 隊(duì)將取勝。或者A隊(duì)未取 勝，或者A隊(duì)成為聯(lián)賽第一名。A隊(duì)沒(méi)有成為聯(lián)賽第一名。小張守第一壘。 因此，小李沒(méi)向 B隊(duì)投球。 例3.6 在自然推理系統(tǒng)P 中構(gòu)造下面推理的證明： 解：令 p: 小張守第一壘； q: 小李向B隊(duì)投球； r: A隊(duì)取勝； s: A隊(duì)成為聯(lián)賽第一名。 前提：(pq) r, rs, s, p 結(jié)論：q (pq) r rs s