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

第三章命題邏輯的推理理論數(shù)理邏輯的主要任務(wù)是推理，即提供一套推理規(guī)則，從給定的前提出發(fā)，推導(dǎo)出一個(gè)結(jié)論來(lái)。前提是指已知的公式的集合。結(jié)論是對(duì)前提應(yīng)用推理規(guī)則推出的公式。3.1推理的形式結(jié)構(gòu)3.1推理的形式結(jié)構(gòu)

3.1推理的形式結(jié)構(gòu)定義（推理的形式結(jié)構(gòu)）設(shè)A1，A2，…，Ak，B都是命題公式，若（A1∧A2∧…∧Ak）→B為重言式，則稱由前提A1，A2，…，Ak推出B的推理是有效的或正確的，稱B是A1，A2，…，Ak的有效結(jié)論或正確結(jié)論。稱（A1∧A2∧…∧Ak）→B為由前提A1，A2，…，Ak推出結(jié)論B的推理的形式結(jié)構(gòu)。

說(shuō)明：（1）用（A1∧A2∧…∧Ak）B來(lái)表示A1，A2，…，Ak推出B的推理是有效的，即（A1∧A2∧…∧Ak）→B為重言式。（2）判斷推理是否正確的方法就是判斷重言蘊(yùn)涵式的方法：真值表法，等值演算法，主析取范式法3.1推理的形式結(jié)構(gòu)例：判斷下面各推理是否正確。（1）馬芳或去看電影或去游泳。她沒去看電影。所以她去游泳了。（2）若下午氣溫超過(guò)30度，則王燕必去游泳。若她去游泳，她就不去看電影了。所以，若王燕沒去看電影，下午氣溫必超過(guò)30度。解推理問題的步驟：（1）將簡(jiǎn)單命題符號(hào)化（2）以下述形式寫出前提、結(jié)論和推理的形式結(jié)構(gòu)前提：A1，A2，…，Ak

結(jié)論：B

推理的形式結(jié)構(gòu)：（A1∧A2∧…∧Ak）→B（3）進(jìn)行判斷(真值表法，等值演算法，主析取范式法)3.1推理的形式結(jié)構(gòu)（1）馬芳或去看電影或去游泳。她沒去看電影。所以她去游泳了。解：

設(shè)：p：馬芳去看電影，q：馬芳去游泳前提：p∨q，┐p

結(jié)論：q

推理的形式結(jié)構(gòu)：（（p∨q）∧┐p））→q3.1推理的形式結(jié)構(gòu)判斷方法一：真值表法真值表的最后一列全為1，所以（（p∨q）∧┐p）→q為重言式。因而推理正確。3.1推理的形式結(jié)構(gòu)判斷方法二：等值演算法

（（p∨q）∧┐p）→q

（（p∧┐p）∨（q∧┐p））→q（q∧┐p）→q

┐q∨p∨q 1

因?yàn)椋ǎ╬∨q）∧┐p）→q為重言式，所以推理正確。3.1推理的形式結(jié)構(gòu)判斷方法三：主析取范式法（（p∨q）∧┐p）→qm0∨m1∨m2∨m3所以（（p∨q）∧┐p）→q為重言式，推理正確。3.1推理的形式結(jié)構(gòu)（2）若下午氣溫超過(guò)30度，則王燕必去游泳。若她去游泳，她就不去看電影了。所以，若王燕沒去看電影，下午氣溫必超過(guò)30度。解：設(shè)p：下午氣溫超過(guò)30度；q：王燕去游泳；r：王燕去看電影 前提：p→q，q→┐r 結(jié)論：┐r→p 推理的形式結(jié)構(gòu)： （p→q）∧（q→┐r）→（┐r→p）（*）

m1∨m3∨m4∨m5∨m6∨m7 可見（*）不是重言式，所以推理不正確。3.1推理的形式結(jié)構(gòu)

如果AB成立，則推理AB是正確的；同時(shí)推理BA也是正確的。思考：AB和AB的關(guān)系？3.1推理的形式結(jié)構(gòu)推理定律（重言蘊(yùn)涵式）（1）AA∨B附加律（2）A∧BA

化簡(jiǎn)律（3）（A→B）∧AB

假言推理（4）（A→B）∧┐B┐A

拒取式（5）（A∨B）∧┐BA

析取三段論（6）（A→B）∧（B→C）（A→C）假言三段論（7）（AB）∧（BC）（AC）等價(jià)三段論（8）（A→B）∧（C→D）∧（A∨C）（B∨D）構(gòu)造性二難（9）（A→B）∧（C→D）∧（┐B∨┐D）（┐A∨┐C）破壞性二難3.1推理的形式結(jié)構(gòu)說(shuō)明：第2.1節(jié)等值式中給出的24個(gè)等值式，每個(gè)等值式可以派生出兩條推理定律。例如：A→B┐A∨B產(chǎn)生兩條推理定律

A→B┐A∨B和┐A∨BA→B3.1推理的形式結(jié)構(gòu)在解推理問題的過(guò)程中，如果命題變項(xiàng)較多，則采用真值表法，等值演算法，主析取范式法這三種方法來(lái)判斷推理的形式結(jié)構(gòu)的公式類型都不方便。解推理問題的構(gòu)造證明法。構(gòu)造證明是一個(gè)描述推理過(guò)程的命題公式的序列，其中每個(gè)公式或者是已知前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論。3.1推理的形式結(jié)構(gòu)構(gòu)造證明法的證明形式前提：p∨q，q→r，p→s，┐s

結(jié)論：r∧（p∨q）

證明：

①p→s

前提引入

②┐s

前提引入

③┐p①②拒取式

④p∨q

前提引入

⑤q③④析取三段論

⑥q→r

前提引入

⑦r⑤⑥假言推理

⑧r∧（p∨q）⑦④合取引入3.1推理的形式結(jié)構(gòu)3.2自然推理系統(tǒng)P

3.1推理的形式結(jié)構(gòu)定義（自然推理系統(tǒng)P）自然推理系統(tǒng)P由以下三個(gè)部分組成：1、字母表（1）命題變項(xiàng)符號(hào)：p，q，r，…，pi，qi，ri，…（2）聯(lián)結(jié)詞符號(hào)：┐，∧，∨，→，（3）括號(hào)與逗號(hào)：（）

，2、公式

參見命題公式的定義3.1推理的形式結(jié)構(gòu)3、推理規(guī)則（12個(gè)）（1）前提引入規(guī)則：在證明的任何步驟上都可以引入前提。（2）（中間）結(jié)論引入規(guī)則：在證明的任何步驟上所得到的中間結(jié)論都可以作為后繼證明的前提。（這是12個(gè)推理規(guī)則中唯一的一個(gè)隱規(guī)則。）（3）置換規(guī)則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又一個(gè)公式。3.1推理的形式結(jié)構(gòu)

由九條推理定律和結(jié)論引入規(guī)則可以導(dǎo)出以下各條推理定律。（4）假言推理規(guī)則（分離推理規(guī)則）：若證明的公式序列中出現(xiàn)過(guò)A→B和A，則由假言推理定律（A→B）∧AB可知，B是A→B和A的有效結(jié)論，由結(jié)論引入規(guī)則可知，可將B引入到命題序列中來(lái)。

（5）附加規(guī)則：A（A∨B）（6）化簡(jiǎn)規(guī)則：A∧BA（7）拒取式規(guī)則：（A→B）∧┐B┐A（8）假言三段論規(guī)則：

（A→B）∧（B→C）（A→C）3.1推理的形式結(jié)構(gòu)（9）析取三段論規(guī)則：（A∨B）∧┐BA（10）構(gòu)造性二難推理規(guī)則：

（A→B）∧（C→D）∧（A∨C）（B∨D）（11）破壞性二難推理規(guī)則：

（A→B）∧（C→D）∧（┐B∨┐D）

（┐A∨┐C）（12）合取引入規(guī)則：若證明的公式序列中出現(xiàn)過(guò)A和B，則A∧B是A和B的有效結(jié)論。3.1推理的形式結(jié)構(gòu)推理規(guī)則（12個(gè)） （1）前提引入規(guī)則 （2）結(jié)論引入規(guī)則（隱規(guī)則） （3）置換規(guī)則：等值置換 （4）假言推理規(guī)則：（A→B）∧AB （5）附加規(guī)則：A（A∨B） （6）化簡(jiǎn)規(guī)則：A∧BA （7）拒取式規(guī)則：（A→B）∧┐B┐A （8）假言三段論規(guī)則：（A→B）∧（B→C）（A→C） （9）析取三段論規(guī)則：（A∨B）∧┐BA （10）構(gòu)造性二難推理規(guī)則 （11）破壞性二難推理規(guī)則 （12）合取引入規(guī)則3.1推理的形式結(jié)構(gòu)利用構(gòu)造證明來(lái)證明形式結(jié)構(gòu)為（A1∧A2∧…∧Ak）→B的推理時(shí)首先寫出：

前提：A1，A2，…，Ak

結(jié)論：B

證明：

注意：不用寫出推理的形式結(jié)構(gòu)：（A1∧A2∧…∧Ak）→B3.1推理的形式結(jié)構(gòu)例在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：（1）前提：p∨q，q→r，p→s，┐s

結(jié)論：r∧（p∨q）

證明：

①p→s

前提引入

②┐s

前提引入

③┐p①②拒取式（A→B）∧┐B┐A

④p∨q

前提引入

⑤q③④析取三段論（A∨B）∧┐BA

⑥q→r

前提引入

⑦r⑤⑥假言推理（A→B）∧AB

⑧r∧（p∨q）⑦④合取引入3.1推理的形式結(jié)構(gòu)（2）前提：┐p∨q，r∨┐q，r→s

結(jié)論：p→s證明：

①┐p∨q

前提引入

②p→q①置換

③r∨┐q

前提引入

④q→r③置換

⑤p→r②④假言三段論⑥r(nóng)→s

前提引入

⑦p→s⑤⑥假言三段論規(guī)則3.1推理的形式結(jié)構(gòu)例在自然推理系統(tǒng)P中構(gòu)造下面的推理的證明：

若數(shù)a是實(shí)數(shù)，則它不是無(wú)理數(shù)就是有理數(shù)。若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)。a是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以a是無(wú)理數(shù)。解：首先將簡(jiǎn)單命題符號(hào)化：令p：a是實(shí)數(shù)；q：a是有理數(shù)；

r：a是無(wú)理數(shù)；s：a能表示成分?jǐn)?shù)解題步驟：（1）簡(jiǎn)單命題的符號(hào)化（2）寫出前提和結(jié)論（3）證明前提：p→（q∨r），┐s→┐q，p∧┐s結(jié)論：r3.1推理的形式結(jié)構(gòu)證明：

①p∧┐s

前提引入

②p①化簡(jiǎn)（A∧B）A

③┐s①化簡(jiǎn)

④┐s→┐q

前提引入

⑤┐q③④假言推理（A→B）∧AB

⑥p→（q∨r）

前提引入

⑦q∨r②⑥假言推理⑧r⑤⑦析取三段論（A∨B）∧┐BA前提：p→（q∨r），┐s→┐q，p∧┐s結(jié)論：r3.1推理的形式結(jié)構(gòu)使用構(gòu)造證明法進(jìn)行推理時(shí)的證明技巧（1）附加前提證明法有時(shí)要證明的結(jié)論以蘊(yùn)涵式的形式出現(xiàn)，即推理的形式結(jié)構(gòu)為

（A1∧A2∧…∧Ak）→（A→B）對(duì)該式進(jìn)行等值演算：（A1∧A2∧…∧Ak）→（A→B）★

┐（A1∧A2∧…∧Ak）∨（┐A∨B）

（┐（A1∧A2∧…∧Ak）∨┐A）∨B┐（A1∧A2∧…∧Ak∧A）∨B

（A1∧A2∧…∧Ak∧A）→B★★可見，如果能證明★★是重言式，則★也是重言式。在★★中，原來(lái)的結(jié)論中的前件A已經(jīng)變成前提了，稱A為附加前提。稱這種將結(jié)論中的前件作為前提的證明方法為附加前提法。3.1推理的形式結(jié)構(gòu)例：在自然推理系統(tǒng)P中構(gòu)造下面推理的證明如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去。解：將簡(jiǎn)單命題符號(hào)化

令p：小張去看電影；q：小王去看電影；

r：小李去看電影；s：小趙去看電影前提：（p∧q）→r，┐s∨p，q結(jié)論：s→r前提：（p∧q）→r，┐s∨p，q，s結(jié)論：r3.1推理的形式結(jié)構(gòu)證明：①s

附加前提引入②┐s∨p

前提引入③p

①②析取三段論（A∨B）∧┐BA④q

前提引入⑤p∧q

③④合取引入⑥（p∧q）→r

前提引入⑦r

⑤⑥假言推理（A→B）∧AB

前提：（p∧q）→r，┐s∨p，q，s結(jié)論：r證明方法一：附加前提法前提：（p∧q）→r，┐s∨p，q結(jié)論：s→r3.1推理的形式結(jié)構(gòu)證明方法二：直接證明前提：（p∧q）→r，┐s∨p，q結(jié)論：s→r證明：

①┐s∨p

前提引入

②s→p

①置換

③（p∧q）→r

前提引入

④p→r

③化簡(jiǎn)

⑤s→r

②④假言三段論3.1推理的形式結(jié)構(gòu)證明：

①┐s∨p

前提引入

②s→p

①置換

③（p∧q）→r

前提引入

④┐p∨┐q∨r

③置換

⑤q

前提引入

⑥┐p∨r

④⑤析取三段論

⑦p→r

⑥置換

⑧s→r

②⑦假言三段論證明方法二：直接證明前提：（p∧q）→r，┐s∨p，q結(jié)論：s→r3.1推理的形式結(jié)構(gòu)（2）歸謬法在構(gòu)造形式結(jié)構(gòu)為（A1∧A2∧…∧Ak）→B的推理證明中，若將┐B作為前提能推出形如（A∧┐A）的矛盾來(lái)，則說(shuō)明推理正確，這種方法稱為歸謬法。3.1推理的形式結(jié)構(gòu)例：在自然推理系統(tǒng)P中構(gòu)造下面推理的證明

如果小張守第一壘并且小李向B隊(duì)投球，則A隊(duì)將取勝?；蛘逜隊(duì)未取勝，或者A隊(duì)成為聯(lián)賽第一名。A對(duì)沒有成為聯(lián)賽的第一名。小張守第一壘。因此，小李沒向B隊(duì)投球。解：將簡(jiǎn)單命題符號(hào)化：

令p：小張守第一壘；q：小李向B隊(duì)投球；r：A隊(duì)取勝；s：A隊(duì)成為聯(lián)賽第一名前提：（p∧q）→r，┐r∨s，┐s，p結(jié)論：┐q前提：（p∧q）→r，┐r∨s，┐s，p，q結(jié)論：03.1推理的形式結(jié)構(gòu)證明：①q

結(jié)論的否定引入②p

前提引入③p∧q①②合?、埽╬∧q）→r

前提引入⑤r

③④假言推理⑥┐r∨s前提引入⑦┐s前提引入⑧┐r

⑥⑦析取三段論⑨r∧┐r

⑤⑧合取前提：（p∧q）→r，┐r∨s，┐s，p，q結(jié)論：0前提：（p∧q）→r，┐r∨s，┐s，p結(jié)論：┐q3.1推理的形式結(jié)構(gòu)證明：①┐r∨s前提引入②┐s前提引入③┐r

①②析取三段論