命題邏輯的推理理論P(yáng)PT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1命題邏輯的推理理論命題邏輯的推理理論q 本章的主要內(nèi)容推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)自然推理系統(tǒng)自然推理系統(tǒng)P Pq 本章與后續(xù)各章的關(guān)系本章是第五章的特殊情況和先行準(zhǔn)備本章是第五章的特殊情況和先行準(zhǔn)備 第1頁(yè)/共57頁(yè)第2頁(yè)/共57頁(yè)第3頁(yè)/共57頁(yè)概念描述問(wèn)題的句子判斷對(duì)概念的肯定與否定的判斷推理從一個(gè)或多個(gè)前提推出結(jié)論的思維過(guò)程認(rèn)識(shí)世界的漸進(jìn)過(guò)程第4頁(yè)/共57頁(yè)第5頁(yè)/共57頁(yè)q由前提A1，A2，Ak推結(jié)論B的推理是否正確與諸前提的排列次序無(wú)關(guān)。第6頁(yè)/共57頁(yè)q設(shè)A1，A2，Ak，B中共出現(xiàn)n個(gè)命題變項(xiàng)，對(duì)于任何一組賦值12n(i=0或者1，i=1,2,n)，前提和結(jié)論的取值情況

2、有以下四種： (1) A1A2 Ak為0，B為0。(2) A1A2 Ak為0，B為1。(3) A1A2 Ak為1，B為0。(4) A1A2 Ak為1，B為1。q只要不出現(xiàn)(3)中的情況，推理就是正確的，因而判斷推理是否正確，就是判斷是否會(huì)出現(xiàn)(3)中的情況。q推理正確，并不能保證結(jié)論B一定為真。 第7頁(yè)/共57頁(yè)例3.1 判斷下列推理是否正確。（真值表法） pqp (pq) qp (qp)q000000010101100010111111正確不正確第8頁(yè)/共57頁(yè)q該定理是判斷推理是否正確的另一種方法。 第9頁(yè)/共57頁(yè)(A1A2Ak)B為重言式，則對(duì)于任何賦值此蘊(yùn)涵式均為真，因而不會(huì)出現(xiàn)前件

3、為真后件為假的情況，即在任何賦值下，或者A1A2Ak為假，或者A1A2Ak和B同時(shí)為真，這正符合推理正確的定義。第10頁(yè)/共57頁(yè)當(dāng)推理正確時(shí)，q形式（1）記為 B。q形式（2）記為A1A2AkB。 表示蘊(yùn)涵式為重言式。第11頁(yè)/共57頁(yè)=G1, G2, ,Gn HG1G2Gn為永真公式真值表技術(shù)、演繹法和間接證明方法第12頁(yè)/共57頁(yè)q 真值表法 q 等值演算法 q 主析取范式法q是否有其他的證明方法？q當(dāng)命題變項(xiàng)較少時(shí),這三種方法比較方便。第13頁(yè)/共57頁(yè)例3.2 判斷下列推理是否正確。（等值演算法） 解：設(shè)p:馬芳下午去看電影，q:馬芳下午去游泳。 前提： pq，p 結(jié)論： q 推理的

4、形式結(jié)構(gòu)： (pq)p)q (pq)p)q (pq)p) q (pq)p) q (pp )(qp) q (qp) q 1由定理 3.1可知，推理正確。第14頁(yè)/共57頁(yè)(6)(AB) (BC) (AC) 假言三段論(7)(AB) (BC) (A C) 等價(jià)三段論(8)(AB)(CD)(AC) (BD) 構(gòu)造性二難 (AB)(AB)(AA) B 構(gòu)造性二難(特殊形式)(9)(AB)(CD)(BD) (AC) 破壞性二難第15頁(yè)/共57頁(yè)第16頁(yè)/共57頁(yè)第17頁(yè)/共57頁(yè)(2) 結(jié)論引入規(guī)則(3) 置換規(guī)則第18頁(yè)/共57頁(yè)（4）若今天下雪,則將去滑雪。今天下雪，所以去滑雪。（5）現(xiàn)在氣溫在冰點(diǎn)

5、以下。因此，要么現(xiàn)在氣溫在冰點(diǎn)以下，要么現(xiàn)在下雨。（6）現(xiàn)在氣溫在冰點(diǎn)以下并且正在下雨。因此，現(xiàn)在氣溫在冰點(diǎn)以下。第19頁(yè)/共57頁(yè)第20頁(yè)/共57頁(yè)第21頁(yè)/共57頁(yè)第22頁(yè)/共57頁(yè)任何一個(gè)問(wèn)題的推理，都可以采取三種推理方法中的任何一種來(lái)證明，針對(duì)不同的問(wèn)題選用不同的推理方法。一般而言，對(duì)于結(jié)論是蘊(yùn)涵式或析取式的，大多可以采取帶附加前提的直接證明方法。第23頁(yè)/共57頁(yè) qr 置換 pr 假言三段論 rs 前提引入 ps 假言三段論第24頁(yè)/共57頁(yè)簡(jiǎn) qr假言推理 r 假言推理 rs附加 rs置換第25頁(yè)/共57頁(yè)例3.4 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明： 若數(shù)a是實(shí)數(shù)，則它不是有

6、理數(shù)就是無(wú)理數(shù)；若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)；a是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以a是無(wú)理數(shù)。 （2）形式結(jié)構(gòu)：前提：p(qr), sq, ps結(jié)論：r第26頁(yè)/共57頁(yè) qr 假言推理 sq 前提引入 q 假言推理 r 析取三段論第27頁(yè)/共57頁(yè)設(shè)p:小張去看電影。q:小王去看電影。r:小李去看電影。s:小趙去看電影。第28頁(yè)/共57頁(yè)引入 q 前提引入 pq 合取 r 假言推理第29頁(yè)/共57頁(yè)例3.6 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明。如果小張守第一壘并且小李向B隊(duì)投球，則A隊(duì)將取勝；或者A隊(duì)未取勝，或者A隊(duì)獲得聯(lián)賽第一名；A隊(duì)沒(méi)有獲得聯(lián)賽的第一名；小張守第一壘。因此，小李沒(méi)有向

7、B隊(duì)投球。 構(gòu)造證明：（1）將簡(jiǎn)單命題符號(hào)化： 設(shè) p:小張守第一壘。 q:小李向B隊(duì)投球。 r:A隊(duì)取勝。 s:A隊(duì)獲得聯(lián)賽第一名。（2）形式結(jié)構(gòu)： 前提：(pq)r,rs,s ,p 結(jié)論：q 第30頁(yè)/共57頁(yè)（3）證明：用歸謬法 q 結(jié)論的否定引入 rs 前提引入 s 前提引入 r 析取三段論 (pq)r 前提引人 (pq) 拒取式 pq 置換 p 前提引入 q 析取三段論 qq 合取 由于最后一步為矛盾式，所以推理正確。 第31頁(yè)/共57頁(yè): 自然推理系統(tǒng)P的定義自然推理系統(tǒng)P的推理規(guī)則：附加前提證明法歸謬法第32頁(yè)/共57頁(yè)方法（真值表法，等值演算法，主析取范式法）。n牢記P系統(tǒng)中的

8、各條推理規(guī)則。n對(duì)于給定的正確推理，要求在P系統(tǒng)中給出嚴(yán)謹(jǐn)?shù)淖C明序列。n會(huì)用附加前提證明法和歸謬法。第33頁(yè)/共57頁(yè)1、用不同的方法驗(yàn)證下面推理是否正確。對(duì)于正確的推理還要在P系統(tǒng)中給出證明。（1） 前提：pq, q 結(jié)論：p（2） 前提：qr, pr 結(jié)論：qp 第34頁(yè)/共57頁(yè)易 知 1 0 是 成 假 賦 值 ， 故(pq)qp不是重言式，所以推理不正確。第35頁(yè)/共57頁(yè)方法三 直接觀察出10是成假賦值。第36頁(yè)/共57頁(yè)pq( pq)qp001101010111結(jié)論（不正確）是對(duì)的。第37頁(yè)/共57頁(yè)（置換） qr（前提引入） qp（假言三段論）第38頁(yè)/共57頁(yè)構(gòu)造證明：（1）

9、 設(shè)p：今天是周六。q：到頤和園玩。 r：到圓明園玩。s：頤和園游人太多。 t：到動(dòng)物園玩。（2）前提：p(qr), sq, p, s 結(jié)論：rt第39頁(yè)/共57頁(yè)提引入 q假言推理 r析取三段論 rt附加第40頁(yè)/共57頁(yè)R結(jié)論：陳某是兇手。Q則可描述為：PR，RP(否定后件式)PQ，PQ(選言三段論)第41頁(yè)/共57頁(yè) 設(shè)設(shè) P P：A A盜竊了盜竊了x x；Q Q：B B盜竊了盜竊了x x； R R：作案時(shí)間發(fā)生在午夜前；：作案時(shí)間發(fā)生在午夜前；S S：B B證詞正確；證詞正確； T T：在午夜時(shí)屋里燈光未滅。：在午夜時(shí)屋里燈光未滅。 則上述命題可符號(hào)化為：則上述命題可符號(hào)化為：PQPQ

10、，PP R R，STST， SRSR， T T Q Q 第42頁(yè)/共57頁(yè)（7） P(5),(6)拒取式（8） PQ前提引入（9） Q(7),(8)析取三段論第43頁(yè)/共57頁(yè)證明G。如果馬會(huì)飛或羊吃草，則母雞就會(huì)是飛鳥；如果母雞是飛鳥，那么烤熟的鴨子還會(huì)跑；烤熟的鴨子不會(huì)跑。所以羊不吃草。第44頁(yè)/共57頁(yè)S 前提引入RS 前提引入R ,拒取式PQR 前提引入(PQ) ,拒取式PQ 置換Q 化簡(jiǎn)第45頁(yè)/共57頁(yè)第46頁(yè)/共57頁(yè)第47頁(yè)/共57頁(yè)第48頁(yè)/共57頁(yè)第49頁(yè)/共57頁(yè) 6 ExamBKnow P 7 Know T (5)(6) 8 Know P所以，有ExamD第50頁(yè)/共57頁(yè)P(yáng) 7 Know T (5)(6) 8 Know P所有，有 ExamB綜合（1）和（2），有ExamBExamD第51頁(yè)/共57頁(yè)第52頁(yè)/共57頁(yè)第53頁(yè)/共57頁(yè)絕大多數(shù)實(shí)際數(shù)學(xué)系統(tǒng)的形式化是不完備的（哥德爾第一不完備性定理），甚至其一致性也無(wú)法在系統(tǒng)之內(nèi)得到證明（哥德爾第二不完備性定理）。數(shù)學(xué)真理不可能由包括程序在內(nèi)的任何機(jī)械過(guò)程所窮盡，而必然包含直覺(jué)和洞察的成份。存在著對(duì)于人的直覺(jué)來(lái)說(shuō)明顯為真，但無(wú)法形式證明的良定義數(shù)學(xué)命題（哥德爾）；存在無(wú)限多不可由“機(jī)械過(guò)程”計(jì)算的函數(shù)（圖靈）；存在著具有重要實(shí)際意義，但無(wú)法被機(jī)械過(guò)程解決的判定問(wèn)題（停機(jī)問(wèn)題圖靈）。第54頁(yè)/共57頁(yè)定