推理的形式結構

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

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

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

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

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

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

7、過AB和A，則由假言推理定律（AB）AB可知，B是AB和A的有效結論，由結論引入規(guī)則可知，可將B引入到命題序列中來。 （5）附加規(guī)則：A（AB） （6）化簡規(guī)則：AB A （7）拒取式規(guī)則：（AB）BA （8）假言三段論規(guī)則： （AB）（BC）（AC,9）析取三段論規(guī)則：（AB）BA （10）構造性二難推理規(guī)則： （AB）（CD）（AC）（BD） （11）破壞性二難推理規(guī)則： （AB）（CD）（BD） （AC） （12）合取引入規(guī)則：若證明的公式序列中出現(xiàn)過A和B，則AB是A和B的有效結論,推理規(guī)則（12個） （1）前提引入規(guī)則 （2）結論引入規(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）構造性二難推理規(guī)則 （11）破壞性二難推理規(guī)則 （12）合取引入規(guī)則,利用構造證明來證明形式結構為（A1A2Ak）B的推理時 首先寫出： 前提：A1，A2，Ak 結論：B 證明,注意：不用寫出推理的形式結構： （A1A2Ak）B,例 在自然推理系統(tǒng)P中構造下面推理的證明： （1）前提：pq，qr，ps，s 結論：r（pq） 證明： ps 前提引入 s 前提引入 p 拒取式（AB）BA pq 前

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

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

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

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

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

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