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

1、第三章第三章 命題邏輯的推理理論命題邏輯的推理理論 數(shù)理邏輯的主要任務(wù)是推理，即提供一套推理規(guī)則，從給定的前提出發(fā)，推導(dǎo)出一個(gè)結(jié)論來(lái)。 前提是指已知的公式的集合。 結(jié)論是對(duì)前提應(yīng)用推理規(guī)則推出的公式。3.1 3.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 定義（推理的形式結(jié)構(gòu)）定義（推理的形式結(jié)構(gòu)） 設(shè) a a1 1， a a2 2， ， a ak k， b b 都 是 命 題 公 式 ， 若 （a a1 1aa2 2aak k）bb為重言式，則稱由前提a a1 1， a a2 2，a ak k推出b b的推理是有效的有效的或正確的正確的，稱b b是a a1 1，a a2 2，a ak k的有效結(jié)論有效

2、結(jié)論或正確結(jié)論正確結(jié)論。 稱（a a1 1aa2 2aak k）bb為由前提a a1 1，a a2 2，a ak k推出結(jié)論b的推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)。 說(shuō)明：說(shuō)明： （1）用（a a1 1aa2 2aak k）b b來(lái)表示a a1 1，a a2 2，a ak k推 出b b的推理是有效的，即（a a1 1aa2 2aak k）bb為重言式。 （2）判斷推理是否正確的方法就是判斷重言蘊(yùn)涵式的方 法：真值表法，等值演算法，主析取范式法例：判斷下面各推理是否正確。 （1）馬芳或去看電影或去游泳。她沒去看電影。所以她去游泳了。 （2）若下午氣溫超過30度，則王燕必去游泳。若她去游泳，她就不去看

3、電影了。所以，若王燕沒去看電影，下午氣溫必超過30度。解推理問題的步驟：（1）將簡(jiǎn)單命題符號(hào)化（2）以下述形式寫出前提、結(jié)論和推理的形式結(jié)構(gòu) 前提：a a1 1，a a2 2，a ak k 結(jié)論：b b 推理的形式結(jié)構(gòu)：（a a1 1aa2 2aak k）bb（3）進(jìn)行判斷(真值表法，等值演算法，主析取范式法) （1）馬芳或去看電影或去游泳。她沒去看電影。所以她去游泳了。 解：解： 設(shè)：p：馬芳去看電影，q：馬芳去游泳 前提：pq，p 結(jié)論：q 推理的形式結(jié)構(gòu)：（pq）p）q判斷方法一：真值表法判斷方法一：真值表法 真值表的最后一列全為1，所以（pqpq）pp）qq為重言式。因而推理正確。判斷

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

5、m5m6m7可見（*）不是重言式，所以推理不正確。 如果ab成立，則推理ab是正確的； 同時(shí)推理ba也是正確的。思考：ab和ab的關(guān)系？推理定律（重言蘊(yùn)涵式）推理定律（重言蘊(yùn)涵式）（1 1） a a ab ab 附加律（2 2） ab ab a a 化簡(jiǎn)律（3 3）（）（abab） a a b b 假言推理（4 4）（）（abab）b b aa 拒取式（5 5）（）（abab）b b a a 析取三段論（6 6）（）（abab）（bcbc）（acac）假言三段論（7 7）（）（a ab b）（b bc c）（a ac c）等價(jià)三段論 （8 8）（）（abab）（cdcd）（acac）（bdbd

6、） 構(gòu)造性二難（9 9）（）（abab）（cdcd）（bdbd）（acac） 破壞性二難說(shuō)明：說(shuō)明：第2.1節(jié) 等值式中給出的24個(gè)等值式，每個(gè)等值 式可以派生出兩條推理定律。例如：ab ab ab ab產(chǎn)生兩條推理定律 abababab和abab ab ab 在解推理問題的過程中，如果命題變項(xiàng)較多，則采用真值表法，等值演算法，主析取范式法這三種方法來(lái)判斷推理的形式結(jié)構(gòu)的公式類型都不方便。 解推理問題的構(gòu)造證明法。 構(gòu)造證明是一個(gè)描述推理過程的命題公式的序列，其中每個(gè)公式或者是已知前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論。構(gòu)造證明法的證明形式 前提：pqpq，qrqr，psps，ss 結(jié)論

7、：rr（pqpq） 證明證明： psps 前提引入 s s 前提引入 p p 拒取式 pq pq 前提引入 q q 析取三段論 qr qr 前提引入 r r 假言推理 r r（pqpq） 合取引入3.2 3.2 自然推理系統(tǒng)自然推理系統(tǒng)p 定義（自然推理系統(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、推理規(guī)則（12個(gè)） （1）前提引入規(guī)則：在證明的任何步驟上都可以引入前提。 （2）（中間）結(jié)論引入規(guī)則：在證明的任何步驟上所得到的中間結(jié)論都可以作為后繼證明的

8、前提。（這是12個(gè)推理規(guī)則中唯一的一個(gè)隱規(guī)則。） （3）置換規(guī)則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又一個(gè)公式。 由九條推理定律和結(jié)論引入規(guī)則可以導(dǎo)出以下各條推理定律。 （4）假言推理規(guī)則（分離推理規(guī)則）：若證明的公式序列中出現(xiàn)過abab和a a，則由假言推理定律（abab）aab b可知，b b是abab和a a的有效結(jié)論，由結(jié)論引入規(guī)則可知，可將b b引入到命題序列中來(lái)。 （5）附加規(guī)則：a a（abab） （6）化簡(jiǎn)規(guī)則：ab ab a a （7）拒取式規(guī)則：（abab）bbaa （8）假言三段論規(guī)則： （abab）（bcbc）（acac）

9、 （9）析取三段論規(guī)則：（abab）bba a （10）構(gòu)造性二難推理規(guī)則： （abab）（cdcd）（acac）（bdbd） （11）破壞性二難推理規(guī)則： （abab）（cdcd）（bdbd） （acac） （12）合取引入規(guī)則：若證明的公式序列中出現(xiàn)過a a和b b，則abab是a a和b b的有效結(jié)論。推理規(guī)則（推理規(guī)則（12個(gè)）個(gè)）（1）前提引入規(guī)則（2）結(jié)論引入規(guī)則（隱規(guī)則）（3）置換規(guī)則：等值置換（4）假言推理規(guī)則：（ab）ab（5）附加規(guī)則：a（ab）（6）化簡(jiǎn)規(guī)則：ab a（7）拒取式規(guī)則：（ab）ba（8）假言三段論規(guī)則：（ab）（bc）（ac）（9）析取三段論規(guī)則：（ab）

10、ba（10）構(gòu)造性二難推理規(guī)則（11）破壞性二難推理規(guī)則（12）合取引入規(guī)則 利用構(gòu)造證明來(lái)證明形式結(jié)構(gòu)為（a a1 1aa2 2aak k）bb的推理時(shí) 首先寫出： 前提：a a1 1，a a2 2，a ak k 結(jié)論：b b 證明： 注意：不用寫出推理的形式結(jié)構(gòu)： （a1a2ak）b例例 在自然推理系統(tǒng)p中構(gòu)造下面推理的證明：（1）前提：pqpq，qrqr，psps，ss 結(jié)論：rr（pqpq） 證明證明： psps 前提引入 s s 前提引入 p p 拒取式（ab）ba pq pq 前提引入 q q 析取三段論（ab）ba qr qr 前提引入 r r 假言推理（ab）ab r r（pq

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

12、前提和結(jié)論 （3）證明前提：pp（qrqr），），sqsq，psps結(jié)論：r r證明： psps 前提引入 p p 化簡(jiǎn)（ab）a s s 化簡(jiǎn) sqsq 前提引入 q q 假言推理（ab）ab pp（qrqr） 前提引入 qr qr 假言推理 r r 析取三段論（ab）ba前提：pp（qrqr），），sqsq，psps結(jié)論：r r 使用構(gòu)造證明法進(jìn)行推理時(shí)的證明技巧 （1）附加前提證明法附加前提證明法 有時(shí)要證明的結(jié)論以蘊(yùn)涵式的形式出現(xiàn)，即推理的形式結(jié)構(gòu)為 （a a1 1aa2 2aak k）（abab） 對(duì)該式進(jìn)行等值演算： （a a1 1aa2 2aak k）（abab） （a a1 1

13、aa2 2aak k）（abab） （a a1 1aa2 2aak k）aa）bb （a a1 1aa2 2aak k a a）bb （a a1 1aa2 2aak k a a）b b 可見，如果能證明是重言式，則也是重言式。在中，原來(lái)的結(jié)論中的前件a已經(jīng)變成前提了，稱a為附加前提附加前提。稱這種將結(jié)論中的前件作為前提的證明方法為附加前提法附加前提法。例：例：在自然推理系統(tǒng)p中構(gòu)造下面推理的證明 如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去。解：解：將簡(jiǎn)單命題符號(hào)化 令 p p：小張去看電影； q q：小王去看電影； r

14、 r：小李去看電影； s s：小趙去看電影前提：（pqpq）rr， sp sp， q q結(jié)論： srsr前提：（前提：（pqpq）rr， sp sp， q q，s s結(jié)論：結(jié)論： r r證明： s s 附加前提引入 spsp 前提引入 p p 析取三段論（ab）ba q q 前提引入 pqpq 合取引入 （pqpq）rr 前提引入 r r 假言推理（ab）ab 前提：（前提：（pqpq）rr，spsp，q q，s s 結(jié)論：結(jié)論： r r證明方法一：附加前提法證明方法一：附加前提法前提：（pqpq）rr， sp sp， q q結(jié)論： srsr證明方法二：直接證明證明方法二：直接證明 前提：（p

15、qpq）rr，spsp，q q 結(jié)論： srsr證明： spsp 前提引入 spsp 置換 （pqpq）rr 前提引入 prpr 化簡(jiǎn) srsr 假言三段論證明： spsp 前提引入 spsp 置換 （pqpq）rr 前提引入 pqrpqr 置換 q q 前提引入 prpr 析取三段論 prpr 置換 srsr 假言三段論證明方法二：直接證明證明方法二：直接證明 前提：（pqpq）rr，spsp，q q 結(jié)論： srsr（2 2）歸謬法）歸謬法 在構(gòu)造形式結(jié)構(gòu)為（a a1 1aa2 2aak k）bb的推理證明中，若將b b作為前提能推出形如（aaaa）的矛盾來(lái)，則說(shuō)明推理正確，這種方法稱為歸

16、謬法歸謬法。例：例：在自然推理系統(tǒng)p中構(gòu)造下面推理的證明 如果小張守第一壘并且小李向b b隊(duì)投球，則a a隊(duì)將取勝。或者a a隊(duì)未取勝，或者a a隊(duì)成為聯(lián)賽第一名。a a對(duì)沒有成為聯(lián)賽的第一名。小張守第一壘。因此，小李沒向b b隊(duì)投球。解：解：將簡(jiǎn)單命題符號(hào)化： 令 p p：小張守第一壘；q q：小李向b b隊(duì)投球； r r：a a隊(duì)取勝； s s：a a隊(duì)成為聯(lián)賽第一名 前提：（pqpq）rr，rsrs，ss，p p 結(jié)論： q q前提：（pqpq）rr，rsrs，ss，p p，q q結(jié)論： 0 0證明：證明： q q 結(jié)論的否定引入 p p 前提引入 pq pq 合取 （pqpq）rr 前

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