離散數(shù)學數(shù)理邏輯部分

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邏輯蘊涵B(logicallyimply)若(A<->B)是重言式，則稱A邏輯等價于B(logicallyequivalent)Example1.8(p∧q)邏輯蘊涵p(~(p∧q))邏輯等價于((~p)∨(~q))Proposition1.9若A和(AB)都是重言式，則B也是重言式Ch1.非形式命題演算Proposition1.17(DeMorgan’sLaw)((~A1)∨(~A2)∨…∨(~An))邏輯等價于(~(A1∧A2∧…∧An))((~A1)∧(~A2)∧…∧(~An))邏輯等價于(~(A1∨A2∨…∨An))嚴格證明略Ch1.非形式命題演算1.4范式(SGU182:OpentheBrackets)Proposition1.20(disjunctivenormalform)任何一個命題形式A都可以等價為如下形式的析取范式:(Qij如同p或~p的形式)證明：選取A的真值表中使A為真的的那些真值賦值，如(pq)∧(qp)中的p=T,q=T和p=F,q=F，然后寫為：

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

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

AnRemark2.3:可見Aj和Ak一定為如同B和(BA)的形式Ch2.形式命題演算Definition2.5(從公式集Г出發(fā)的推演)類似于Definition2.2，只不過證明序列中的公式還可以是Г的一員。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思考：上述過程的證明可不可以轉化為A┣A呢？這樣就容易多了。Ch2.形式命題演算Proposition2.8(演繹定理,TheDeductionTheorem)設Г∪{A}┣B則Г┣A

B[證明]施歸納法于Г∪{A}┣B的證明長度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.形式命題演算歸納階段:設n>1,定理對一切長度小于n的證明序列成立,現(xiàn)證明對長度為n的證明亦正確:如歸納奠基，亦有B為公理,Г的一員,和B為A三種情況情況4:B由前方兩個公式MP得來，這兩個公式一定形如C和(CB)，由歸納假設:Г┣(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同時顯然有Г∪{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這就證明了{(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)幾個Exercises見后頁Remark:可見在命題邏輯的公理系統(tǒng)內推演并不是一件容易的事情，是否可以證明這個系統(tǒng)的一些性質，如系統(tǒng)的定理一定是直覺上正確的(可靠性定理)直覺上正確的公式一定可以在系統(tǒng)內證明

(完備性定理)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)內證明)。Remark:聯(lián)想我們靠真值表來確定A是否為重言式，如果可以將真值表的思想對應為系統(tǒng)內的一個證明序列，問題就迎刃而解了。Ch2.形式命題演算Definition2.12真值賦值真值賦值為一個函數(shù)v:{p1,p2,p3,…}{T,F}任何一個真值賦值v可以將定義域擴張至整個合式公式集合，只要按照如下規(guī)則：v(~A)=Tiff.v(A)=FV(AB)=Tiff.v(A)=F或v(B)=T方便起見，擴張后的真值賦值v通常仍記為vCh2.形式命題演算Lemma:設Σ是命題變元或其否定形式的集合，對于任何一個真值賦值v，令其對應的Σ為：若v(pi)=T則令pi∈∑,否則~pi∈∑v(A)=T則∑┣A,v(A)=F則∑┣(~A)證明:施歸納法于A的結構歸納奠基:若A為命題變元pi,則顯然正確歸納證明:根據(jù)A的構成方法分兩種情況:A為(~B)A為(BC)Ch2.形式命題演算若A為(BC),若v(A)=F,則v(B)=T,v(C)=F,由歸納假設∑┣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.形式命題演算有了這樣一個引理,則可以較容易的證明弱完備性定理:由于A是重言式,那么對任意真值賦值A都為真,再由演繹定理不難得到下述事實(假設A中僅出現(xiàn)p1和p2)┣p1(p2A)┣~p1(p2A)┣p1(~p2A)┣~p1(~p2A)由Ex.6的結論:{~AB,AB}┣B知┣p2A┣~p2A再合并一次就得到┣A由這個思路很容易得到定理的嚴格證明Ch2.形式命題演算Remark:可以看出,弱完備性定理的證明是構造性的,因此我們可以通過編寫一個程序完成系統(tǒng)內的證明,希望同學們在上機時實踐一下。Remark:事實上我們還有另外一種更強大的證明這一命題的方法，且這種方法對于一階謂詞邏輯中的完備性定理的證明有很大的幫助。Ch2.形式命題演算強完備性定理的證明Definition2.15形式系統(tǒng)L的一個擴充(extension)L*是指在L中修改或添加公理,而L的定理仍然是L*的定理Remark:顯然L是L的擴充

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