推理的形式結(jié)構(gòu)

1、第三章 命題邏輯的推理理論,數(shù)理邏輯的主要任務(wù)是推理，即提供一套推理規(guī)則，從給定的前提出發(fā)，推導(dǎo)出一個(gè)結(jié)論來,前提是指已知的公式的集合,結(jié)論是對前提應(yīng)用推理規(guī)則推出的公式,3.1 推理的形式結(jié)構(gòu),定義（推理的形式結(jié)構(gòu)） 設(shè)A1，A2，Ak，B都是命題公式，若 （A1A2Ak）B為重言式，則稱由前提A1， A2，Ak推出B的推理是有效的或正確的，稱B是A1，A2，Ak的有效結(jié)論或正確結(jié)論。 稱（A1A2Ak）B為由前提A1，A2，Ak推出結(jié)論B的推理的形式結(jié)構(gòu),說明： （1）用（A1A2Ak）B來表示A1，A2，Ak推 出B的推理是有效的，即（A1A2Ak）B為重言式,2）判斷推理是否正確的方法

2、就是判斷重言蘊(yùn)涵式的方 法：真值表法，等值演算法，主析取范式法,例：判斷下面各推理是否正確。 （1）馬芳或去看電影或去游泳。她沒去看電影。所以她去游泳了。 （2）若下午氣溫超過30度，則王燕必去游泳。若她去游泳，她就不去看電影了。所以，若王燕沒去看電影，下午氣溫必超過30度,解推理問題的步驟： （1）將簡單命題符號化 （2）以下述形式寫出前提、結(jié)論和推理的形式結(jié)構(gòu) 前提：A1，A2，Ak 結(jié)論：B 推理的形式結(jié)構(gòu)：（A1A2Ak）B （3）進(jìn)行判斷(真值表法，等值演算法，主析取范式法,1）馬芳或去看電影或去游泳。她沒去看電影。所以她去游泳了。 解： 設(shè)：p：馬芳去看電影，q：馬芳去游泳 前提：

3、pq，p 結(jié)論：q 推理的形式結(jié)構(gòu)：（pq）p）q,判斷方法一：真值表法,真值表的最后一列全為1，所以（pq）p）q為重言式。因而推理正確,判斷方法二：等值演算法,pq）p）q （pp）（qp）q （ qp ）q qpq 1 因?yàn)椋╬q）p）q為重言式，所以推理正確,判斷方法三：主析取范式法,pq）p）q m0m1m2m3 所以（pq）p）q為重言式，推理正確,2）若下午氣溫超過30度，則王燕必去游泳。若她去游泳，她就不去看電影了。所以，若王燕沒去看電影，下午氣溫必超過30度。 解：設(shè)p：下午氣溫超過30度；q：王燕去游泳； r：王燕去看電影 前提：pq，qr 結(jié)論：rp 推理的形式結(jié)構(gòu)： （

4、pq）（qr）（rp）（*） m1m3m4m5m6m7 可見（*）不是重言式，所以推理不正確,如果AB成立，則推理AB是正確的； 同時(shí)推理BA也是正確的,思考：AB和AB的關(guān)系,推理定律（重言蘊(yùn)涵式） （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）等價(jià)三段論 （8）（AB）（CD）（AC）（BD） 構(gòu)造性二難 （9）（AB）（CD）（BD）（AC） 破壞性二難,說明：第2.1節(jié) 等值式中給出的24個(gè)等值式，每個(gè)等值 式可

5、以派生出兩條推理定律。 例如：AB AB產(chǎn)生兩條推理定律 ABAB和AB AB,在解推理問題的過程中，如果命題變項(xiàng)較多，則采用真值表法，等值演算法，主析取范式法這三種方法來判斷推理的形式結(jié)構(gòu)的公式類型都不方便。 解推理問題的構(gòu)造證明法。 構(gòu)造證明是一個(gè)描述推理過程的命題公式的序列，其中每個(gè)公式或者是已知前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論,構(gòu)造證明法的證明形式 前提：pq，qr，ps，s 結(jié)論：r（pq） 證明： ps 前提引入 s 前提引入 p 拒取式 pq 前提引入 q 析取三段論 qr 前提引入 r 假言推理 r（pq） 合取引入,3.2 自然推理系統(tǒng)P,定義（自然推理系統(tǒng)P）

6、自然推理系統(tǒng)P由以下三個(gè)部分組成,1、字母表 （1）命題變項(xiàng)符號：p，q，r， pi，qi，ri， （2）聯(lián)結(jié)詞符號：， （3）括號與逗號：（）,2、公式 參見命題公式的定義,3、推理規(guī)則（12個(gè),1）前提引入規(guī)則：在證明的任何步驟上都可以引入前提,2）（中間）結(jié)論引入規(guī)則：在證明的任何步驟上所得到的中間結(jié)論都可以作為后繼證明的前提。（這是12個(gè)推理規(guī)則中唯一的一個(gè)隱規(guī)則。,3）置換規(guī)則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又一個(gè)公式,由九條推理定律和結(jié)論引入規(guī)則可以導(dǎo)出以下各條推理定律。 （4）假言推理規(guī)則（分離推理規(guī)則）：若證明的公式序列中出現(xiàn)

7、過AB和A，則由假言推理定律（AB）AB可知，B是AB和A的有效結(jié)論，由結(jié)論引入規(guī)則可知，可將B引入到命題序列中來。 （5）附加規(guī)則：A（AB） （6）化簡規(guī)則：AB A （7）拒取式規(guī)則：（AB）BA （8）假言三段論規(guī)則： （AB）（BC）（AC,9）析取三段論規(guī)則：（AB）BA （10）構(gòu)造性二難推理規(guī)則： （AB）（CD）（AC）（BD） （11）破壞性二難推理規(guī)則： （AB）（CD）（BD） （AC） （12）合取引入規(guī)則：若證明的公式序列中出現(xiàn)過A和B，則AB是A和B的有效結(jié)論,推理規(guī)則（12個(gè)） （1）前提引入規(guī)則 （2）結(jié)論引入規(guī)則（隱規(guī)則） （3）置換規(guī)則：等值置換 （4）假

8、言推理規(guī)則：（AB）AB （5）附加規(guī)則：A（AB） （6）化簡規(guī)則：AB A （7）拒取式規(guī)則：（AB）BA （8）假言三段論規(guī)則：（AB）（BC）（AC） （9）析取三段論規(guī)則：（AB）BA （10）構(gòu)造性二難推理規(guī)則 （11）破壞性二難推理規(guī)則 （12）合取引入規(guī)則,利用構(gòu)造證明來證明形式結(jié)構(gòu)為（A1A2Ak）B的推理時(shí) 首先寫出： 前提：A1，A2，Ak 結(jié)論：B 證明,注意：不用寫出推理的形式結(jié)構(gòu)： （A1A2Ak）B,例 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明： （1）前提：pq，qr，ps，s 結(jié)論：r（pq） 證明： ps 前提引入 s 前提引入 p 拒取式（AB）BA pq 前

9、提引入 q 析取三段論（AB）BA qr 前提引入 r 假言推理（AB）AB r（pq） 合取引入,2）前提：pq，rq，rs 結(jié)論：ps,證明： pq 前提引入 pq 置換 rq 前提引入 qr 置換 pr 假言三段論 rs 前提引入 ps 假言三段論規(guī)則,例 在自然推理系統(tǒng)P中構(gòu)造下面的推理的證明： 若數(shù)a是實(shí)數(shù)，則它不是無理數(shù)就是有理數(shù)。若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)。a是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以a是無理數(shù),解：首先將簡單命題符號化： 令 p：a是實(shí)數(shù)； q：a是有理數(shù)； r：a是無理數(shù)； s：a能表示成分?jǐn)?shù),解題步驟： （1）簡單命題的符號化 （2）寫出前提和結(jié)論 （3）證明,

10、前提：p（qr），sq，ps 結(jié)論：r,證明： ps 前提引入 p 化簡（AB）A s 化簡 sq 前提引入 q 假言推理（AB）AB p（qr） 前提引入 qr 假言推理 r 析取三段論（AB）BA,前提：p（qr），sq，ps 結(jié)論：r,使用構(gòu)造證明法進(jìn)行推理時(shí)的證明技巧 （1）附加前提證明法 有時(shí)要證明的結(jié)論以蘊(yùn)涵式的形式出現(xiàn)，即推理的形式結(jié)構(gòu)為 （A1A2Ak）（AB） 對該式進(jìn)行等值演算： （A1A2Ak）（AB） （A1A2Ak）（AB） （A1A2Ak）A）B （A1A2Ak A）B （A1A2Ak A）B,可見，如果能證明是重言式，則也是重言式。在中，原來的結(jié)論中的前件A已經(jīng)變

11、成前提了，稱A為附加前提。稱這種將結(jié)論中的前件作為前提的證明方法為附加前提法,例：在自然推理系統(tǒng)P中構(gòu)造下面推理的證明 如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去,解：將簡單命題符號化 令 p：小張去看電影； q：小王去看電影； r：小李去看電影； s：小趙去看電影,前提：（pq）r， sp， q 結(jié)論： sr,前提：（pq）r， sp， q，s 結(jié)論： r,證明： s 附加前提引入 sp 前提引入 p 析取三段論（AB）BA q 前提引入 pq 合取引入 （pq）r 前提引入 r 假言推理（AB）AB,前提：（pq）

12、r，sp，q，s 結(jié)論： r,證明方法一：附加前提法,前提：（pq）r， sp， q 結(jié)論： sr,證明方法二：直接證明 前提：（pq）r，sp，q 結(jié)論： sr,證明： sp 前提引入 sp 置換 （pq）r 前提引入 pr 化簡 sr 假言三段論,證明： sp 前提引入 sp 置換 （pq）r 前提引入 pqr 置換 q 前提引入 pr 析取三段論 pr 置換 sr 假言三段論,證明方法二：直接證明 前提：（pq）r，sp，q 結(jié)論： sr,2）歸謬法 在構(gòu)造形式結(jié)構(gòu)為（A1A2Ak）B的推理證明中，若將B作為前提能推出形如（AA）的矛盾來，則說明推理正確，這種方法稱為歸謬法,例：在自然推

13、理系統(tǒng)P中構(gòu)造下面推理的證明 如果小張守第一壘并且小李向B隊(duì)投球，則A隊(duì)將取勝。或者A隊(duì)未取勝，或者A隊(duì)成為聯(lián)賽第一名。A對沒有成為聯(lián)賽的第一名。小張守第一壘。因此，小李沒向B隊(duì)投球,解：將簡單命題符號化： 令 p：小張守第一壘；q：小李向B隊(duì)投球； r：A隊(duì)取勝； s：A隊(duì)成為聯(lián)賽第一名 前提：（pq）r，rs，s，p 結(jié)論： q,前提：（pq）r，rs，s，p，q 結(jié)論： 0,證明： q 結(jié)論的否定引入 p 前提引入 pq 合取 （pq）r 前提引入 r 假言推理 rs 前提引入 s 前提引入 r 析取三段論 rr 合取,前提：（pq）r，rs，s，p，q 結(jié)論： 0,前提：（pq）r，r

14、s，s，p 結(jié)論： q,證明： rs 前提引入 s 前提引入 r 析取三段論 （pq）r 前提引入 pq 拒取式 p 前提引入 q 析取三段論,前提：（pq）r，rs，s，p 結(jié)論： q,思考題 嘗試在自然推理系統(tǒng)P中利用構(gòu)造證明法證明著名的“蘇格拉底三段論”的正確性。 蘇格拉底三段論：“凡人要死。蘇格拉底是人。所以蘇格拉底要死。,顯然在命題邏輯中就根本無法判斷 “蘇格拉底三段論”的正確性。 蘇格拉底三段論：“凡人要死。蘇格拉底是人。所以蘇格拉底要死?！?p：凡人要死 q：蘇格拉底是人 r：蘇格拉底要死 則此三段論表示為（pq）r 蘇格拉底三段論是正確的，但（pq）r卻不是重言式,命題邏輯是有缺陷的,例如：張三和李四是兄弟。李四和王五是兄弟。所以張三和王五也是兄弟。