命題邏輯的推理理論

命題邏輯的推理理論第1頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月上一節(jié)的復(fù)習(xí)

范式的定義定義2.3（1）由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式。（2）由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱為合取范式。（3）析取范式與合取范式統(tǒng)稱為范式。第2頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月上一節(jié)的復(fù)習(xí)

求范式的步驟（用等值演算）消去聯(lián)結(jié)詞→,

蘊(yùn)涵等值式:A→B┐A∨B

等價(jià)等值式:AB(A→B)∧(B→A)否定號(hào)的消去（利用雙重否定律）┐┐AA內(nèi)移否定號(hào)（利用德摩根律）┐(A∨B)┐A∧┐B┐(A∧B)┐A∨┐B利用∧對(duì)∨的分配律求析取范式，∨對(duì)∧的分配律求合取范式。第3頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月上一節(jié)的復(fù)習(xí)（續(xù)）定義2.5（主范式）設(shè)由n個(gè)命題變項(xiàng)構(gòu)成的析取范式（合取范式）中所有的簡(jiǎn)單合取式（簡(jiǎn)單析取式）都是極小項(xiàng)（極大項(xiàng)），則稱該析取范式（合取范式）為主析取范式（主合取范式）。第4頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月上一節(jié)的復(fù)習(xí)（續(xù)）求主范式的步驟（存在性證明過(guò)程）

(1)補(bǔ)充命題變項(xiàng)；

(2)消去重復(fù)出現(xiàn)的極?。ù螅╉?xiàng)和矛盾式（重言式）。第5頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月引言“命題”的形式前兩章介紹了“命題”的形式?！巴评怼钡男问奖菊陆榻B“推理”的形式。推理是邏輯的研究對(duì)象。第6頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月3.1.推理的形式結(jié)構(gòu)有效推理有效推理的等價(jià)定理重言蘊(yùn)涵式第7頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月有效推理數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法來(lái)研究數(shù)學(xué)中的推理。所謂推理是指從前提出發(fā)推出結(jié)論的思維過(guò)程，而前提是已知命題公式集合，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。要研究推理就應(yīng)該給出推理的形式結(jié)構(gòu)，為此，首先應(yīng)該明確什么樣的推理是有效的或正確的。第8頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月有效推理（續(xù)）定義3.1

設(shè)A1,A2,…,Ak和B都是命題公式，若對(duì)于A1,A2,…,Ak和B中出現(xiàn)的命題變項(xiàng)的任意一組賦值，或者A1∧A2

∧…∧Ak為假，或者當(dāng)A1∧A2∧…∧Ak為真時(shí)，B也為真，則稱由前提A1,A2,…,Ak推出B的推理是有效的或正確的，并稱B是有效結(jié)論。第9頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月定義3.1有關(guān)說(shuō)明由前提A1,A2,…,Ak推結(jié)論B的推理是否正確與諸前提的排列次序無(wú)關(guān)。因而前提的公式不一定是序列，而是一個(gè)有限的公式集合，若將這個(gè)集合記為Г，可將由Г推B的推理記為Г├B。若推理是正確的，則記為ГB，否則記為ГB。這里，可以稱Г├B和{A1,A2,…,Ak}├B為推理的形式結(jié)構(gòu)。第10頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月定義3.1有關(guān)說(shuō)明（續(xù)）設(shè)A1,A2,…,Ak，B中共出現(xiàn)n個(gè)命題變項(xiàng)，對(duì)于任何一組賦值α1,α2,…,αn(αi=0或者1，i=1,2,…,n)，前提和結(jié)論的取值情況有以下四種：

(1)A1∧A2∧…∧Ak為0，B為0.

(2)A1∧A2∧…∧Ak為0，B為1.

(3)A1∧A2∧…∧Ak為1，B為0.

(4)A1∧A2∧…∧Ak為1，B為1.

由定義3.1可知，只要不出現(xiàn)(3)中的情況，推理就是正確的，因而判斷推理是否正確，就是判斷是否會(huì)出現(xiàn)(3)中的情況。第11頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月定義3.1有關(guān)說(shuō)明（續(xù)）由以上的討論可知，推理正確，并不能保證結(jié)論B一定為真，這與數(shù)學(xué)中的推理是不同的。這個(gè)與前面我們所介紹的哪個(gè)內(nèi)容非常相關(guān)？

蘊(yùn)涵聯(lián)結(jié)詞!第12頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.1.判斷推理是否正確(1){p,p→q}q

分析：定義3.1;

真值表;10?第13頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.1（續(xù)）(1){p,p→q}q

解題：p∧(p→q),q的真值表第14頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月有效推理的等價(jià)定理定理3.1

命題公式A1,A2,…,Ak推B的推理正確當(dāng)且僅當(dāng)

(A1∧A2∧…∧Ak)→B為重言式。證明（課后練習(xí)）必要性（僅當(dāng)）；充分性（當(dāng)）。第15頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月推理的形式結(jié)構(gòu)由定理3.1知，推理形式：

前提：A1,A2,…,Ak

結(jié)論：B

是有效的當(dāng)且僅當(dāng)(A1∧A2∧…∧Ak)→B為重言式。

(A1∧A2∧…∧Ak)→B稱為上述推理的形式結(jié)構(gòu)。第16頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月推理的有效性推理的有效性等價(jià)于它的形式結(jié)構(gòu)為永真式。即推理正確

{A1∧A2∧…∧Ak}B

可記為

A1∧A2∧…∧AkB

其中同一樣是一種元語(yǔ)言符號(hào)，用來(lái)表示蘊(yùn)涵式為重言式。第17頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月推理有效性的判斷方法分析

(1)A1∧A2∧…∧AkB(2)形式結(jié)構(gòu)為永真式(重言式)

(A1∧A2∧…∧Ak)→B(3)判斷命題公式永真性的方法真值表法；等值演算法；主析（合）取范式法.第18頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.2.判斷下面推理是否正確(1)若a能被4整除，則a能被2整除；a能被4整除。所以a能被2整除。簡(jiǎn)單命題符號(hào)化:p:a能被4整除.q:a能被2整除.前提:p→q,p結(jié)論:q推理的形式結(jié)構(gòu):(p→q)∧p→q第19頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.2（續(xù)）可以真值表法或等值演算或主析取范式方法來(lái)計(jì)算推理的形式結(jié)構(gòu)是否為重言式。pqp→q(p→q)∧p(p→q)∧p→q00011011110100011111第20頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.2（續(xù)）（練習(xí)）(2)下午馬芳或去看電影或去游泳；她沒(méi)有看電影。所以，她去游泳了。（要求用命題等值演算法解題）(3)若下午氣溫超過(guò)30℃，則王小燕必去游泳；若她去游泳，她就不去看電影了。所以王小燕沒(méi)有去看電影，下午氣溫必超過(guò)了30℃。（要求用主析取范式法解題）

第21頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.2

（續(xù)）(2)下午馬芳或去看電影或去游泳；她沒(méi)有看電影。所以，她去游泳了。第22頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.2（續(xù)）

若下午氣溫超過(guò)30℃，則王小燕必去游泳；

若她去游泳，她就不去看電影了。

所以王小燕沒(méi)有去看電影，下午氣溫必超過(guò)了30℃。第23頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式形如A→B的重言式在推理中十分重要若A→B為重言式，則稱B為A的推論，記為AB九個(gè)重要的重言蘊(yùn)涵式推理定律。第24頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式(1)附加律

A(A∨B)第25頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式(2)化簡(jiǎn)律

(A∧B)A第26頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式(3)假言推理

(A→B)∧AB第27頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式(4)拒取式

(A→B)∧┐B┐A第28頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式(5)析取三段論

(A∨B)∧┐BA第29頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式(6)假言三段論

(A→B)∧(B→C)(A→C)第30頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式(7)等價(jià)三段論

(AB)∧(BC)(AC)第31頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式(8)構(gòu)造性二難

(A→B)∧(C→D)∧(A∨C)(B∨D)構(gòu)造性二難(特殊形式)(A→B)∧(┐A→B)∧(A∨┐A)B第32頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月重言蘊(yùn)涵式(9)破壞性二難

(A→B)∧(C→D)∧(┐B∨┐D)

(┐A∨┐C)第33頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月24個(gè)等值式派生的推理定律2.1中的24個(gè)等值式中的每一個(gè)都派生出兩條推理定律

第34頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月16組（24個(gè)）重要的等值式1.雙重否定律

A┐┐A（2.1）

A┐┐A┐┐AA第35頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月課后作業(yè)(1)默寫(xiě)9個(gè)重要的重言蘊(yùn)涵式；(2)復(fù)習(xí)16組（24個(gè)）重要的等值式。第36頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月上一節(jié)課的復(fù)習(xí)推理的形式結(jié)構(gòu)

(1){A1,A2,…,Ak}├B(2)(A1∧A2∧…∧Ak)→B有效推理命題公式A1,A2,…,Ak推B的推理正確當(dāng)且僅當(dāng)

(A1∧A2∧…∧Ak)→B為重言式。第37頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月上一節(jié)課的復(fù)習(xí)（續(xù)）推理形式：

前提：A1,A2,…,Ak

結(jié)論：B

是有效的當(dāng)且僅當(dāng)(A1∧A2∧…∧Ak)→B為重言式。第38頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月3.2.自然推理系統(tǒng)P判斷推理是否正確的三種方法：真值表法;

等值演算法;

主析取范式法.

演算量大，比較繁瑣.用更嚴(yán)謹(jǐn)?shù)男问酵评硐到y(tǒng)描述推理第39頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月形式推理系統(tǒng)定義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記為<A(I),E(I),AX(I),R(I)>.其中<A(I),E(I)>是I的形式語(yǔ)言系統(tǒng)，<AX(I),R(I)>為I的形式演算系統(tǒng)。第40頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月形式系統(tǒng)的種類自然推理系統(tǒng)它的特點(diǎn)是從任意給定的前提出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推理演算，得到的最后命題公式是推理的結(jié)論。公理推理系統(tǒng)它只能從若干給定的公理出發(fā)，應(yīng)用系統(tǒng)中推理規(guī)則進(jìn)行推理演算，得到的結(jié)論是系統(tǒng)中的重言式，稱為系統(tǒng)中的定理。第41頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月自然推理系統(tǒng)PP是一個(gè)自然推理系統(tǒng)，因而沒(méi)有公理。故P只有三個(gè)部分。第42頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月自然推理系統(tǒng)P（續(xù)）定義3.3自然推理系統(tǒng)P定義如下：

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第43頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月自然推理系統(tǒng)P（續(xù)）

3．推理規(guī)則（1）前提引入規(guī)則：在證明的任何步驟上都可以引入前提。

（2）結(jié)論引入規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以作為后繼證明的前提。

（3）置換規(guī)則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又一個(gè)公式。第44頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月自然推理系統(tǒng)P（續(xù)）

3．推理規(guī)則（續(xù)）由九條推理定律和結(jié)論引入規(guī)則還可以導(dǎo)出以下各條推理規(guī)則。第45頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月（4）假言推理規(guī)則

（或稱分離規(guī)則）若證明的公式序列中已出現(xiàn)過(guò)A→B和A，則由假言推理定律(A→B)∧AB可知，B是A→B和A的有效結(jié)論。由結(jié)論引入規(guī)則可知，可將B引入到命題序列中來(lái)。用圖式表示為如下形式：

第46頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月（5）附加規(guī)則第47頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月（6）化簡(jiǎn)規(guī)則第48頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月（7）拒取式規(guī)則第49頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月（8）假言三段論規(guī)則第50頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月（9）析取三段論規(guī)則第51頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月（10）構(gòu)造性二難推理第52頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月（11）破壞性二難推理規(guī)則第53頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月（12）合取引入規(guī)則本條規(guī)則說(shuō)明，若證明的公式序列中已出現(xiàn)A和B，則可將A∧B引入序列中。第54頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月自然推理系統(tǒng)P中的證明P中的證明就是由一組P中公式作為前提，利用P中的規(guī)則，推出結(jié)論。當(dāng)然此結(jié)論也為P中公式。

構(gòu)造證明。第55頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.3.在自然推理系統(tǒng)P

中構(gòu)造下面推理的證明(1)前提：p∨q,q→r,p→s,┐s

結(jié)論：r∧(p∨q)證明:①p→s

前提引入

②┐s

前提引入

③┐p

①②拒取式

④p∨q

前提引入

⑤q

③④析取三段論

⑥q→r

前提引入

⑦r

⑤⑥假言推理

⑧r∧(p∨q)⑦④合取得證r∧(p∨q)為有效結(jié)論.第56頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.3（續(xù)，練習(xí)）

(2)前提：┐p∨q,r∨┐q,r→s

結(jié)論：p→s第57頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月P的簡(jiǎn)單實(shí)際應(yīng)用可以在自然推理系統(tǒng)P中構(gòu)造數(shù)學(xué)和日常生活中的一些推理，所得結(jié)論都是有效的，即當(dāng)各前提的合取式為真時(shí)，結(jié)論必為真。第58頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.4在自然推理系統(tǒng)P

中構(gòu)造下面推理的證明若數(shù)a是實(shí)數(shù)，則它不是有理數(shù)就是無(wú)理數(shù)；若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)；a是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以a是無(wú)理數(shù)。解首先將簡(jiǎn)單命題符號(hào)化：

設(shè)p：a是實(shí)數(shù)。

q：a是有理數(shù)。

r：a是無(wú)理數(shù)。

s：a能表示成分?jǐn)?shù)。

前提：p→(q∨r),┐s→┐q,p∧┐s

結(jié)論：r

第59頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.4（續(xù)，課后練習(xí)）

前提：p→(q∨r),┐s→┐q,p∧┐s

結(jié)論：r第60頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月P中常用證明方法附加前提證明法歸謬法第61頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月附加前提證明法有時(shí)推理的形式結(jié)構(gòu)具有如下形式

（A1∧A2∧…∧Ak)→(A→B)

（3.5）（3.5）式中結(jié)論也為蘊(yùn)涵式。此時(shí)可將結(jié)論中的前件也作為推理的前提，使結(jié)論只為B。即，將（3.5）化為下述形式

(A1∧A2∧…∧Ak∧A)→B

（3.6）第62頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月附加前提證明法（續(xù)）

(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

因?yàn)椋?.5）式與（3.6）式是等值的，因而若能證明（3.6）式是正確的，則（3.5）式也是正確的。用形式結(jié)構(gòu)（3.6）式證明，將A稱為附加前提，并稱此證明法為附加前提證明法。第63頁(yè)，課件共71頁(yè)，創(chuàng)作于2023年2月例3.5在P中構(gòu)造

下面推理的證明如果小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去看電影。解將簡(jiǎn)單命題符號(hào)化：

設(shè)p:小張去看電影。

q:小王去看電影。

r:小李去看電影。