Outline命題邏輯非形式命題演算(Informalstatementcalculus)形式命題演算(Formalstatementcalculus)謂詞邏輯(一階邏輯)非形式謂詞演算(Informalpredicatecalculus)形式謂詞演算(Formalpredicatecalculus)Ch1.非形式命題演算1.1命題和連接詞Example1.1IfSocratesisamanthenSocratesismortalSocratesisaman∴SocratesismortalAB,A,∴BCh1.非形式命題演算1.2真值函數(shù)和真值表NOT:~p(Negation)AND:p∧q(Conjunction)OR:p∨q(Disjunction)Imply:pq(Conditional)Ifandonlyif:p<->q(Biconditional)Definition1.2:命題形式((p∧q)r)(p(~((pq)∨r)))pqpqTTTTFFFTTFFTCh1.非形式命題演算Definition1.5重言式(tautology):恒真的命題形式矛盾式(contradition):恒假的命題形式Example1.6(p∨(~p))是重言式(p∧(~p))是矛盾式Ch1.非形式命題演算Definition1.7若(AB)是重言式，則稱A邏輯蘊(yùn)涵B(logicallyimply)若(A<->B)是重言式，則稱A邏輯等價(jià)于B(logicallyequivalent)Example1.8(p∧q)邏輯蘊(yùn)涵p(~(p∧q))邏輯等價(jià)于((~p)∨(~q))Proposition1.9若A和(AB)都是重言式，則B也是重言式Ch1.非形式命題演算Proposition1.17(DeMorgan’sLaw)((~A1)∨(~A2)∨…∨(~An))邏輯等價(jià)于(~(A1∧A2∧…∧An))((~A1)∧(~A2)∧…∧(~An))邏輯等價(jià)于(~(A1∨A2∨…∨An))嚴(yán)格證明略Ch1.非形式命題演算1.4范式(SGU182:OpentheBrackets)Proposition1.20(disjunctivenormalform)任何一個(gè)命題形式A都可以等價(jià)為如下形式的析取范式:(Qij如同p或~p的形式)證明：選取A的真值表中使A為真的的那些真值賦值，如(pq)∧(qp)中的p=T,q=T和p=F,q=F，然后寫(xiě)為：

((p∧q)∨((~p)∧(~q)))Ch1.非形式命題演算Proposition1.21(conjunctivenormalform)任何一個(gè)命題形式A都可以等價(jià)為如下形式的合取范式:(Qij如同p或~p的形式)證明：設(shè)~A的析取范式為B，如((p∧q)∨(p∧(~q))),則A邏輯等價(jià)于~B，如~((p∧q)∨(p∧(~q)))，邏輯等價(jià)于(((~p)∨(~q))∧((~p)∨q))為A的合取范式。

(注意多次使用DeMorgan’sLaw)Ch1.非形式命題演算1.5連接詞的完備集(Adequateset)Definition1.23若任何真值函數(shù)都可以表示為僅含一個(gè)集合中的連接詞的命題形式，則稱為連接詞的完備集Proposition1.24:{~,}是連接詞的完備集證明:{~,∧,∨}是完備集(A∧B)邏輯等價(jià)于(~(A(~B)))(A∨B)邏輯等價(jià)于((~A)B)因而任何僅包含{~,∧,∨}的命題形式都可以表示為僅含{~,}的命題形式Ch2.形式命題演算問(wèn)題起源：當(dāng)命題形式的連接詞過(guò)多時(shí)，我們的直覺(jué)并不一定很準(zhǔn)確，希望建立一個(gè)簡(jiǎn)單的系統(tǒng)來(lái)對(duì)應(yīng)直覺(jué)。這也符合我們計(jì)算機(jī)的思維?！叭绻鸄不正確蘊(yùn)涵A正確那么A一定正確”這句話對(duì)嗎？“如果當(dāng)對(duì)任意的B均有A蘊(yùn)涵B成立時(shí)，A一定成立，那么A一定成立”很容易理解嗎？Ch2.形式命題演算2.1形式系統(tǒng)L(Definition2.1)定義命題邏輯的形式推演系統(tǒng)L包含如下內(nèi)容：1.字母表：~,,(,),p1,p2,p3,…2.合式公式:由連接詞~,構(gòu)成的有限長(zhǎng)公式公理模式(L1)(A(BA))(L2)((A(BC))((AB)(AC))(L3)(((~A)(~B))(BA))推演規(guī)則(MP):從(AB)和A可以得到一個(gè)直接的結(jié)論BCh2.形式命題演算Definition2.2(證明的定義)L中的一個(gè)證明是一個(gè)有限合式公式的序列：A1,A2,…,An，對(duì)任何1≤i≤n,Ai要么是一個(gè)公理，要么有證明序列中靠前的兩個(gè)合適公式Aj和Ak由MP推演而來(lái)(j,k<i)。稱之為L(zhǎng)中An的一個(gè)證明，稱An為L(zhǎng)的一個(gè)定理，記為┣

AnRemark2.3:可見(jiàn)Aj和Ak一定為如同B和(BA)的形式Ch2.形式命題演算Definition2.5(從公式集Г出發(fā)的推演)類似于Definition2.2，只不過(guò)證明序列中的公式還可以是Г的一員。Example2.6{A,(B(AC))}┣(BC)(1)Aassumption(2)(B(AC))assumption(A(BA))(L1)(BA)(1),(3)MP((B(AC))((BA)(BC))(L2)((BA)(BC))(2),(5)MP(BC)(4),(6)MPCh2.形式命題演算Example2.7:┣(AA)(1)(A((AA)A))((A(AA))(AA))(L2)(2)(A((AA)A))(L1)(3)((A(AA))(AA))(1),(2)MP(4)(A(AA))(L1)(5)(AA)(3),(4)MP思考：上述過(guò)程的證明可不可以轉(zhuǎn)化為A┣A呢？這樣就容易多了。Ch2.形式命題演算Proposition2.8(演繹定理,TheDeductionTheorem)設(shè)Г∪{A}┣B則Г┣A

B[證明]施歸納法于Г∪{A}┣B的證明長(zhǎng)度n歸納奠基:(n=1)B是公理，則如下可證明Г┣A

B(1)B(公理)(2)(B(AB))(L1)(3)(AB)(1),(2)MPB是Г的一員，類似于上面的證明B就是A，那么由Example2.7有┣(A

A)，可得Г┣A

BCh2.形式命題演算歸納階段:設(shè)n>1,定理對(duì)一切長(zhǎng)度小于n的證明序列成立,現(xiàn)證明對(duì)長(zhǎng)度為n的證明亦正確:如歸納奠基，亦有B為公理,Г的一員,和B為A三種情況情況4:B由前方兩個(gè)公式MP得來(lái)，這兩個(gè)公式一定形如C和(CB)，由歸納假設(shè):Г┣(AC)且Г┣(A(CB))，如下證明Г┣(AB)(1)…(q)(AC)(q+1)…(k)(A(CB))(k+1)(A(CB))((AC)(AB))(L2)(k+2)(AC)(AB)(k),(k+1)MP(k+3)(AB)(q),(k+2)MPCh2.形式命題演算Remark:演繹定理的逆定理是平凡的:若有Г┣A

B則一定有Г∪{A}┣A

B同時(shí)顯然有Г∪{A}┣A使用一次MP就可以得到Г∪{A}┣BCh2.形式命題演算Corollary2.10{(AB),(BC)}┣(AC)(HS,HypotheticalSyllogism,假言三段論)(1)(AB)assumption(2)(BC)assumption(3)Aassumption(4)B(1),(3)MP(5)C(2),(4)MP這就證明了{(lán)(A

B),(B

C),A}┣C由演繹定理不難得{(A

B),(B

C)}┣(A

C)Ch2.形式命題演算Proposition2.11┣(~AA)A(1)(~AA)assumption(2)(~A(~~(~AA)~A))(L1)(3)(~~(~AA)~A)(A~(~AA))(L3)(4)(~A(A~(~AA)))(2),(3)HS(5)(~A(A~(~AA)))((~AA)(~A~(~AA)))(L2)(6)(~AA)(~A~(~AA))(4),(5)MP(7)(~A~(~AA))(1),(6)MP(8)(~A~(~AA))((~AA)A)(L3)(9)(~AA)A(7),(8)MP(10)A(1),(9)MPCh2.形式命題演算這就證明了(~AA)┣A，由演繹定理：

┣((~AA)A)幾個(gè)Exercises見(jiàn)后頁(yè)Remark:可見(jiàn)在命題邏輯的公理系統(tǒng)內(nèi)推演并不是一件容易的事情，是否可以證明這個(gè)系統(tǒng)的一些性質(zhì)，如系統(tǒng)的定理一定是直覺(jué)上正確的(可靠性定理)直覺(jué)上正確的公式一定可以在系統(tǒng)內(nèi)證明

(完備性定理)Ch2.形式命題演算Ex.1┣(~~AA)Ch2.形式命題演算Ex.2┣(A~~A)Ch2.形式命題演算Ex.3┣(AB)(~B~A)Ch2.形式命題演算Ex.4{B,~C}┣~(BC)Ch2.形式命題演算Ex.5┣~B(BC)Ch2.形式命題演算Ex.6{AB,~AB}┣BCh2.形式命題演算2.2完備性定理

(TheAdequacyTheoremforL)Proposition2.14可靠性定理(TheSoundnessTheorem):L的定理都是重言式證明思路：L的三條公理可靠推演規(guī)則(三段論)可靠由歸納法可知，L的所有定理可靠Ch2.形式命題演算Proposition(Extra):弱完備性定理,即若A是重言式，則A是L的定理(可以在系統(tǒng)內(nèi)證明)。Remark:聯(lián)想我們靠真值表來(lái)確定A是否為重言式，如果可以將真值表的思想對(duì)應(yīng)為系統(tǒng)內(nèi)的一個(gè)證明序列，問(wèn)題就迎刃而解了。Ch2.形式命題演算Definition2.12真值賦值真值賦值為一個(gè)函數(shù)v:{p1,p2,p3,…}{T,F}任何一個(gè)真值賦值v可以將定義域擴(kuò)張至整個(gè)合式公式集合，只要按照如下規(guī)則：v(~A)=Tiff.v(A)=FV(AB)=Tiff.v(A)=F或v(B)=T方便起見(jiàn)，擴(kuò)張后的真值賦值v通常仍記為vCh2.形式命題演算Lemma:設(shè)Σ是命題變?cè)蚱浞穸ㄐ问降募?，?duì)于任何一個(gè)真值賦值v，令其對(duì)應(yīng)的Σ為：若v(pi)=T則令pi∈∑,否則~pi∈∑v(A)=T則∑┣A,v(A)=F則∑┣(~A)證明:施歸納法于A的結(jié)構(gòu)歸納奠基:若A為命題變?cè)猵i,則顯然正確歸納證明:根據(jù)A的構(gòu)成方法分兩種情況:A為(~B)A為(BC)Ch2.形式命題演算若A為(BC),若v(A)=F,則v(B)=T,v(C)=F,由歸納假設(shè)∑┣B和∑┣(~C)

由Ex.4有{B,~C}┣~(BC)=~A

即∑┣~A若v(A)=T,則v(B)=F或v(C)=T,即∑┣(~B)或∑┣C

顯然有┣C(BC)及┣~B(BC)(Ex.5)

因而一定有∑┣(BC)即∑┣ACh2.形式命題演算有了這樣一個(gè)引理,則可以較容易的證明弱完備性定理:由于A是重言式,那么對(duì)任意真值賦值A(chǔ)都為真,再由演繹定理不難得到下述事實(shí)(假設(shè)A中僅出現(xiàn)p1和p2)┣p1(p2A)┣~p1(p2A)┣p1(~p2A)┣~p1(~p2A)由Ex.6的結(jié)論:{~AB,AB}┣B知┣p2A┣~p2A再合并一次就得到┣A由這個(gè)思路很容易得到定理的嚴(yán)格證明Ch2.形式命題演算Remark:可以看出,弱完備性定理的證明是構(gòu)造性的,因此我們可以通過(guò)編寫(xiě)一個(gè)程序完成系統(tǒng)內(nèi)的證明,希望同學(xué)們?cè)谏蠙C(jī)時(shí)實(shí)踐一下。Remark:事實(shí)上我們還有另外一種更強(qiáng)大的證明這一命題的方法，且這種方法對(duì)于一階謂詞邏輯中的完備性定理的證明有很大的幫助。Ch2.形式命題演算強(qiáng)完備性定理的證明Definition2.15形式系統(tǒng)L的一個(gè)擴(kuò)充(extension)L*是指在L中修改或添加公理,而L的定理仍然是L*的定理Remark:顯然L是L的擴(kuò)充

Ch2.形式命題演算Definition2.16L的一個(gè)擴(kuò)充L*是協(xié)調(diào)的(consistent)若不存在公式A使得A和(~A)都是L*的定理Proposition2.17L是協(xié)調(diào)的反設(shè)L不協(xié)調(diào),即存在A和(~A)都是L的定理,則由可靠性定理知A和(~A)都是重言式，這顯然是不可能的,因而L協(xié)調(diào)Ch2.形式命題演算Proposition2.18L*是協(xié)調(diào)的當(dāng)且僅當(dāng)存在一個(gè)公式A不是L*的定理若L*協(xié)調(diào),則任意A和(~A)總有一個(gè)不是L*的定理若L*不協(xié)調(diào),則存在~A和A同時(shí)是L*的定理,由Ex.5:┣~A(AB)對(duì)任意B成立，因而對(duì)任意B使用兩次MP可知B是L*的定理，即不存在A不是L*的定理Ch2.形式命題演算Proposition2.19設(shè)L*是L的一個(gè)協(xié)調(diào)擴(kuò)充,若A不是L*的定理,則將(~A)作為新公理擴(kuò)充入L*得到L**仍然是協(xié)調(diào)的反設(shè)L**不協(xié)調(diào),即任何公式都是L**的定理,如A這等價(jià)于從{~A}出發(fā)在L*中可以推演出A由演繹定理,(~AA)是L*的定理而由Proposition2.11:┣(~AA)A由一次MP得A是L*的定理,矛盾因此L**協(xié)調(diào)Ch2.形式命題演算Definition2.20設(shè)L*是L的一個(gè)擴(kuò)充,若對(duì)任意A和(~A),至少有一個(gè)是L*的定理,則稱L*是極大的(complete)Remark:顯然L不是極大的Ch2.形式命題演算Proposition2.21(Lindenbaum定理)若L*是L的一個(gè)協(xié)調(diào)擴(kuò)充,則一定存在L*的一個(gè)極大協(xié)調(diào)的擴(kuò)充首先合式公式集合是可數(shù)集,因此可以將所有合式公式排成一列A0,A1,A2,…按如下方式得到L*的擴(kuò)充序列J0,J1,J2,…令J0=L*,對(duì)n>0,若An-1是Jn-1的定理,則令Jn=Jn-1否則將(~An-1)作為一條新公理擴(kuò)充如Jn-1得到JnCh2.形式命題演算首先J0協(xié)調(diào),若Jn-1協(xié)調(diào)若An-1是Jn-1的定理,那么Jn=Jn-1亦協(xié)調(diào)若An-1不是Jn-1的定理,由Proposition2.19,將(~An-1)作為一條新公理擴(kuò)充入Jn-1得到Jn仍然協(xié)調(diào)由歸納原理:對(duì)有限的n都有Jn協(xié)調(diào)令J為L(zhǎng)的一個(gè)擴(kuò)充,其公理集為所有Ji集合的并反若J不協(xié)調(diào),在J中可推演出A和(~A),由于證明長(zhǎng)度有限,因而使用到的公理有限,存在有限n使得Jn包含了所有需要的公理,進(jìn)而A和(~A)都是Jn的定理，這和Jn的協(xié)調(diào)