《命題邏輯的推理理論ch.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《命題邏輯的推理理論ch.ppt（46頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、本章說(shuō)明,本章的主要內(nèi)容 推理的形式結(jié)構(gòu) 自然推理系統(tǒng)P 本章與后續(xù)各章的關(guān)系 本章是第五章的特殊情況和先行準(zhǔn)備,,3.1 推理的形式結(jié)構(gòu) 3.2 自然推理系統(tǒng)P 本章小結(jié) 習(xí)題 作業(yè),3.1 推理的形式結(jié)構(gòu),數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法來(lái)研究數(shù)學(xué)中的推理。 推理是指從前提出發(fā)推出結(jié)論的思維過(guò)程。 前提是已知命題公式集合。 結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。 證明是描述推理正確或錯(cuò)誤的過(guò)程。 要研究推理，首先應(yīng)該明確什么樣的推理是有效的或正確的。,定義3.1 設(shè)A1,A2,,Ak和B都是命題公式，若對(duì)于A1,A2,,Ak和B中出現(xiàn)的命題變項(xiàng)的任意一組賦值，（1）或者A1A2
2、 Ak為假;（2）或者當(dāng)A1A2 Ak為真時(shí)，B也為真;則稱(chēng)由前提A1,A2,,Ak推出B的推理是有效的或正確的，并稱(chēng)B是有效結(jié)論。,有效推理的定義,關(guān)于有效推理的說(shuō)明,A1，A2，，Ak由 推B的推理記為 B若推理是正確的，記為 B若推理是不正確的，記為 B,由前提A1，A2，，Ak推結(jié)論B的推理是否正確與諸前提的排列次序無(wú)關(guān)。,關(guān)于有效推理的說(shuō)明,設(shè)A1，A2，，Ak，B中共出現(xiàn)n個(gè)命題變項(xiàng)，對(duì)于任何一組賦值12n(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為
3、0。(4) A1A2 Ak為1，B為1。 只要不出現(xiàn)(3)中的情況，推理就是正確的，因而判斷推理是否正確，就是判斷是否會(huì)出現(xiàn)(3)中的情況。 推理正確，并不能保證結(jié)論B一定為真。,(1) p,pq q (2) p,qp q,例3.1 判斷下列推理是否正確。（真值表法）,,例題,正確,不正確,定理3.1 命題公式A1,A2,,Ak推B的推理正確當(dāng)且僅當(dāng) (A1A2Ak )B 為重言式。,,該定理是判斷推理是否正確的另一種方法。,說(shuō)明,有效推理的等價(jià)定理,定理3.1的證明,(1)證明必要性。若A1,A2,,Ak推B的推理正確， 則對(duì)于A1,A2,,Ak,B中所含命題變項(xiàng)的任意一組賦值，不會(huì)出現(xiàn)
4、A1A2Ak為真，而B(niǎo)為假的情況， 因而在任何賦值下，蘊(yùn)涵式(A1A2Ak )B均為真，故它為重言式。 (2)證明充分性。若蘊(yùn)涵式(A1A2Ak)B為重言式， 則對(duì)于任何賦值此蘊(yùn)涵式均為真，因而不會(huì)出現(xiàn)前件為真后件為假的情況， 即在任何賦值下，或者A1A2Ak為假， 或者A1A2Ak和B同時(shí)為真，這正符合推理正確的定義。,當(dāng)推理正確時(shí)， 形式（1）記為 B。 形式（2）記為A1A2AkB。 表示蘊(yùn)涵式為重言式。,設(shè)= A1, A2, , Ak，記為B。 A1A2AkB 前提： A1, A2, , Ak 結(jié)論： B,說(shuō)明,推理的形式結(jié)構(gòu),真值表法 等值演算法 主析取范式法,判斷推理是否正確的方法
5、,是否有其他的證明方法？,思考,當(dāng)命題變項(xiàng)較少時(shí),這三種方法比較方便。,說(shuō)明,（1） 下午馬芳或去看電影或去游泳。她沒(méi)去看電影，所以，她 去游泳了。,例3.2 判斷下列推理是否正確。（等值演算法）,,解：設(shè)p:馬芳下午去看電影，q:馬芳下午去游泳。 前提： pq，p 結(jié)論： q 推理的形式結(jié)構(gòu)： ((pq)p)q ((pq)p)q ((pq)p) q ((pq)p) q ((pp )(qp)) q (qp) q 1,由定理 3.1可知，推理正確。,例題,,(2)若下午氣溫超過(guò)30，則王小燕必去游泳；若她去游泳，她就不去看電影了。所以王小燕沒(méi)有去看電影，下午氣溫必超過(guò)了30。
6、 （主析取范式法）,解：設(shè) p：下午氣溫超過(guò)30。 q：王小燕去游泳。 r：王小燕去看電影。 前提：pq，qr 結(jié)論：rp 推理的形式結(jié)構(gòu)：((pq)(qr))(rp) (3.4),,用主析取范式法判斷(3.4)式是否為重言式。 ((pq)(qr))(rp) ((pq)(qr))(rp) ((pq)(qr))rp rp (用兩次吸收律) (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) (pqr)(pqr) m1m3m4m5m6m7 （重排了序）可見(jiàn)(3.4)式不是重言式（主析取范式中少兩個(gè)極小項(xiàng) m0，m2），所以推理不正確。,(1) A
7、(AB) 附加律 (2) (AB) A 化簡(jiǎn)律 (3)(AB)A B 假言推理 (4) (AB)B A 拒取式 (5) (AB)B A 析取三段論 (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) 破壞性二難,推理定律--重言蘊(yùn)含式,小節(jié)結(jié)束,關(guān)于推理定律的幾點(diǎn)說(shuō)明,A,B,C為元語(yǔ)言符號(hào)，代表任意的命題公式。 若一個(gè)推理的形式結(jié)構(gòu)與某條推理定律對(duì)應(yīng)的蘊(yùn)涵式一致，則不用證明
8、就可斷定這個(gè)推理是正確的。 2.1節(jié)給出的24個(gè)等值式中的每一個(gè)都派生出兩條推理定律。例如雙重否定律A A產(chǎn)生兩條推理定律A A和 AA。 由九條推理定律可以產(chǎn)生九條推理規(guī)則,它們構(gòu)成了推理系統(tǒng)中的推理規(guī)則。,3.2 自然推理系統(tǒng)P,判斷推理是否正確的三種方法：真值表法、等值演算法和主析取范式法。 當(dāng)推理中包含的命題變項(xiàng)較多時(shí)，上述三種方法演算量太大。 對(duì)于由前提A1,A2,,Ak推B的正確推理應(yīng)該給出嚴(yán)謹(jǐn)?shù)淖C明。 證明是一個(gè)描述推理過(guò)程的命題公式序列，其中的每個(gè)公式或者是前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論（中間結(jié)論或推理中的結(jié)論）。 要構(gòu)造出嚴(yán)謹(jǐn)?shù)淖C明就必須在形式系統(tǒng)中進(jìn)行。,,定
9、義3.2 一個(gè)形式系統(tǒng)I由下面四個(gè)部分組成： （1） 非空的字符表集，記作A(I)。 （2） A(I)中符號(hào)構(gòu)造的合式公式集，記作E(I)。 （3） E(I)中一些特殊的公式組成的公理集，記作AX(I)。 （4） 推理規(guī)則集，記作R(I)。 可以將I記為.其中是I的形式語(yǔ)言系統(tǒng)，為I的形式演算系統(tǒng)。 形式系統(tǒng)一般分為兩類(lèi) :自然推理系統(tǒng) 公理推理系統(tǒng),自然推理系統(tǒng)的定義,1字母表（1） 命題變項(xiàng)符號(hào)：p，q，r，,pi，qi，ri， （2） 聯(lián)結(jié)詞符號(hào)：,,,,（3） 括號(hào)和逗號(hào)：( , )，， 2合式公式 同定義1.6,,3推理規(guī)則（1） 前提引入規(guī)則：在證明的任何步驟上都可以引入前提。 （
10、2） 結(jié)論引入規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以作為后繼證明的前提。 （3） 置換規(guī)則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又一個(gè)公式。,自然推理系統(tǒng)的定義,（4）假言推理規(guī)則 AB A B （5）附加規(guī)則 A AB （6）化簡(jiǎn)規(guī)則 AB A,（4）若今天下雪,則將去滑雪。今天下雪，所以去滑雪。 （5）現(xiàn)在氣溫在冰點(diǎn)以下。因此，要么現(xiàn)在氣溫在冰點(diǎn)以下，要么現(xiàn)在下雨。 （6）現(xiàn)在氣溫在冰點(diǎn)以下并且正在下雨。因此，現(xiàn)在氣溫在冰點(diǎn)以下。,自然推理系統(tǒng)的定義,（7）拒取式規(guī)則 AB B A （8）假言三段論規(guī)則 AB BC AC
11、 （9）析取三段論規(guī)則 AB B A,（7）如果x是偶數(shù), 則x2是偶數(shù)。 x不是偶數(shù)。 x2不是偶數(shù),自然推理系統(tǒng)的定義,（10）構(gòu)造性二難推理規(guī)則 AB CD AC BD （11）破壞性二難推理規(guī)則 AB CD BD AC （12） 合取引入規(guī)則 A B AB,例,1)、前提： 1.如果明天天晴，我們準(zhǔn)備外出旅游。PQ 2明天的確天晴。 P 結(jié)論：我們外出旅游。Q 上述例子可描述為：PQ，PQ(假言推理) 2)、前提： 1.如果一個(gè)人是單身漢，則他不幸福。PQ 2.如果一個(gè)人不幸福，則他死得早。QR 結(jié)論：?jiǎn)紊頋h死得早。PR 上述例子可描述為： PQ，QRP
12、R(前提三段論),考慮以下語(yǔ)句，并將其前提和結(jié)論符號(hào)化。,例,3)、某女子在某日晚歸家途中被殺害，據(jù)多方調(diào)查確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工廠(chǎng)值夜班，沒(méi)有外出，根據(jù)上述案情可得前提如下： 前提：1.兇手為王某或陳某。PQ 2.如果王某是兇手，則他在作案當(dāng)晚必外出。PR 3.王某案發(fā)之晚并未外出。R 結(jié)論：陳某是兇手。Q 則上述例子可描述為： PR,RP(拒取式) PQ，PQ (析取三段論),例,4)、前提： 1.如果某同學(xué)為省二級(jí)以上運(yùn)動(dòng)員，則他將被大學(xué)錄取。PR 2.如果某同學(xué)高考總分在560分以上，則將被大學(xué)錄取。QR 3.某同學(xué)高考總分在560分以上或者是省二級(jí)運(yùn)
13、動(dòng)員。PQ 結(jié)論：該同學(xué)被大學(xué)錄取。R 則上述例子可描述為： PQ，PR，QRR(構(gòu)造性二難推理),證明：令P：馬會(huì)飛；Q：羊吃草； R：母雞是飛鳥(niǎo)；S：那么烤熟的鴨子還會(huì)跑。,如果馬會(huì)飛或羊吃草，則母雞就會(huì)是飛鳥(niǎo)；如果母雞是飛鳥(niǎo)，那么烤熟的鴨子還會(huì)跑；烤熟的鴨子不會(huì)跑。所以羊不吃草。,例,證明： SP RSP R拒取式,PQRP (PQ)拒取式 PQ Q簡(jiǎn)化式,,符號(hào)化上述語(yǔ)句為：=PQR,RS,S,G=Q。證明G。,在自然推理系統(tǒng)P中構(gòu)造證明,P中構(gòu)造證明就是由一組P中公式作為前提，利用P中的規(guī)則，推出結(jié)論。 構(gòu)造形式結(jié)構(gòu)A1A2Ak B 的推理的書(shū)寫(xiě)方法：前提： A1,A2,,Ak 結(jié)論
14、： B 證明方法： 直接證明法 附加前提法 歸謬法（或稱(chēng)反證法）,例題,例3.3 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：前提：pq, rq ,rs 結(jié)論：ps pq 前提引入 pq 置換 rq 前提引入 qr 置換 pr 假言三段論 rs 前提引入 ps 假言三段論,例題,例3.3 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：前提：p（qr）, pq 結(jié)論： rs p（qr） 前提引入 pq 前提引入 p 化簡(jiǎn) q 化簡(jiǎn) qr 假言推理 r 假言推理 rs 附加 rs置換,,例3.4 若數(shù)a是實(shí)數(shù)，則它不是有理數(shù)就是無(wú)理數(shù)。若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)；a是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以a是無(wú)理
15、數(shù)。 解 首先將簡(jiǎn)單命題符號(hào)化： 設(shè) p：a是實(shí)數(shù)。 q：a是有理數(shù)。 r：a是無(wú)理數(shù)。 s：a能表示成分?jǐn)?shù)。 前提：p(qr), sq, ps 結(jié)論：r, ps 前提引入 p 化簡(jiǎn) s 化簡(jiǎn) p(qr) 前提引入 qr 假言推理 sq 前提引入 q 假言推理 r 析取三段論,例題,例題,例3.5 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明。 如果小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去看電影。 構(gòu)造證明： （1）將簡(jiǎn)單命題符號(hào)化： 設(shè) p:小張去看電影。 q:小王去看電影。 r:小李去看電影。 s:小趙去看電影。,例題,（
16、2）形式結(jié)構(gòu)： 前提：(pq)r,sp,q 結(jié)論：sr （3）證明：用附加前提證明法 s 附加前提引入 sp 前提引入 p 析取三段論 (pq)r 前提引入 q 前提引入 pq 合取 r 假言推理,例題,例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)有向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
17、 ,p 結(jié)論：q,例題,（3）證明：用歸謬法 q 結(jié)論的否定引入 rs 前提引入 s 前提引入 r 析取三段論 (pq)r 前提引人 (pq) 拒取式 pq 置換 p 前提引入 q 析取三段論 qq 合取 由于最后一步為矛盾式，所以推理正確。,小節(jié)結(jié)束,本章主要內(nèi)容,推理的形式結(jié)構(gòu)：推理的前提推理的結(jié)論推理正確 判斷推理是否正確的方法：真值表法等值演算法主析取范式法 對(duì)于正確的推理，在自然推理系統(tǒng)P中構(gòu)造證明: 自然推理系統(tǒng)P的定義自然推理系統(tǒng)P的推理規(guī)則：附加前提證明法歸謬法,本章學(xué)習(xí)要求,理解并記住推理的形式結(jié)構(gòu)的三種等價(jià)形式，即A1,A2,,AkBA1A2AkB前提：A1,A2,,Ak
18、結(jié)論：B 在判斷推理是否正確時(shí)，用；在P系統(tǒng)中構(gòu)造證明時(shí)用。 熟練掌握判斷推理是否正確的三種方法（真值表法，等值演算法，主析取范式法）。 牢記P系統(tǒng)中的各條推理規(guī)則。 對(duì)于給定的正確推理，要求在P系統(tǒng)中給出嚴(yán)謹(jǐn)?shù)淖C明序列。 會(huì)用附加前提證明法和歸謬法。,小節(jié)結(jié)束,習(xí)題,1、用不同的方法驗(yàn)證下面推理是否正確。對(duì)于正確的推理還要在P系統(tǒng)中給出證明。 （1） 前提：pq, q 結(jié)論：p （2）前提：qr, pr 結(jié)論：qp,,（1）不正確。 驗(yàn)證答案，只需證明(pq)qp不是重言式。 方法一 等值演算 (pq)qp ((pq)q)p (pq)qp ((pq)(qq))p pq 易知10是成
19、假賦值，故(pq)qp不是重言式，所以推理不正確。,,方法二 主析取范式法 經(jīng)過(guò)演算后可知 (pq)qp m0m1m3 未含m2, 故(pq)qp不是重言式。,方法三 直接觀(guān)察出10是成假賦值。,,方法四 真值表法 (pq)qp的真值表為,結(jié)論（不正確）是對(duì)的。,,（2）推理正確 方法一 真值表法（自己做） 方法二 等值演算法（自己做） 方法三 主析取范式法（自己做） 方法四 P系統(tǒng)中構(gòu)造證明 證明： （直接證明法） pr （前提引入） rp （置換） qr （前提引入） qp （假言三段論）,,2、在P系統(tǒng)中構(gòu)造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩。 如果頤和園游人太多，就不去頤和園。 今天是周六，并且頤和園游人太多。 所以我們?nèi)A明園或動(dòng)物園玩。,構(gòu)造證明： （1） 設(shè)p：今天是周六。q：到頤和園玩。 r：到圓明園玩。s：頤和園游人太多。 t：到動(dòng)物園玩。 （2）前提：p(qr), sq, p, s 結(jié)論：rt,（3）證明： p(qr) 前提引入 p 前提引入 qr 假言推理 sq 前提引入 s 前提引入 q 假言推理 r 析取三段論 rt 附加,小節(jié)結(jié)束,作業(yè),習(xí)題三：14（1）、15（1）、16（1）,結(jié)束,
命題邏輯的推理理論ch.ppt
