離散數(shù)學3-命題演算系統(tǒng)

1、離散數(shù)學(3)chenbi2008.10.091目錄數(shù)理邏輯集合論圖論抽象代數(shù)2數(shù)理邏輯命題演算命題與聯(lián)結(jié)詞重言式范式命題演算形式系統(tǒng)謂詞演算個體、謂詞和量詞謂詞演算永真式謂詞公式的前束范式一階謂詞演算形式系統(tǒng)3上次我們講到幾種命題公式重言式、矛盾式、可滿足式邏輯等價、邏輯蘊含重言式的代入原理命題公式的替換原理析（合）取范式、主析（合）取范式聯(lián)結(jié)詞的（極?。┕δ芡陚浼?命題演算：形式系統(tǒng)重言式反應了人類邏輯思維的基本規(guī)律排中律AAt矛盾律 AAf假言推理A(AB)B歸謬推理(AB)BA窮舉推理(AB)(AC)(BC)C真值計算、以代入原理、替換原理進行推演難以反應人類思維推理過程，需要建立嚴密

2、的符號推理體系5命題演算：形式系統(tǒng)形式系統(tǒng)是一個符號體系系統(tǒng)中的概念由符號表示推理過程即符號變換的過程以若干最基本的重言式作為基礎，稱作公理（axioms）系統(tǒng)內(nèi)符號變換的依據(jù)是若干確保由重言式導出重言式的規(guī)則，稱作推理規(guī)則（rules of inference）公理和推理規(guī)則確保系統(tǒng)內(nèi)由正確的前提總能得到正確的推理結(jié)果6命題演算：證明與演繹證明(proof)公式序列A1,A2,Am稱作Am的一個證明，如果Ai(1im)或者是公理，或者由Aj1,Ajk(j1,jki)用推理規(guī)則推得。當這樣的證明存在時，稱Am為系統(tǒng)的定理(theorem)，記作*Am（*是形式系統(tǒng)的名稱），或者簡記為Am7命題

3、演算：證明與演繹演繹(deduction)設為一公式集合。公式序列A1,A2,Am稱作Am的以為前提的演繹，如果Ai(1im)或者是中的公式，或者是公理，或者由Aj1,Ajk(j1,jki)用推理規(guī)則推得。當有這樣的演繹時， Am稱作的演繹結(jié)果，記作*Am（*是形式系統(tǒng)的名稱），或者簡記為Am稱和的成員為Am的前提(hypothesis)證明是演繹在為空集時的特例8命題演算：形式系統(tǒng)PC命題演算形式系統(tǒng)PC(Proposition Calculus)PC的符號系統(tǒng)命題變元：p,q,r,s,p1,q1,r1,s1,命題常元：t,f聯(lián)結(jié)詞：,（注意是完備集）括號：(,)命題公式命題變元和命題常元是

4、公式如果A,B是公式，則(A)，(AB)均為公式（結(jié)合優(yōu)先級和括號省略約定同前）只有有限次使用上面兩條規(guī)則得到的符號串才是命題公式9命題演算：形式系統(tǒng)PCPC的公理（A,B,C表示任意公式）A1:A(BA)A2:(A(BC)(AB)(AC)A3:(AB)(BA)PC的推理規(guī)則（A,B表示任意公式）A,AB/B（分離規(guī)則）10命題演算：形式系統(tǒng)PCPC的合理性(soundness)如果公式A是系統(tǒng)PC的定理，則A是重言式（如果PCA，則A）如果A是公式集合的演繹結(jié)果，那么A是的邏輯結(jié)果（如果PCA，則A）PC合理性的證明PC中的公理A1,A2,A3都是重言式；PC的分離規(guī)則是“保真”的，就是如果

5、A真，AB真，總有B真。這樣，由公理和規(guī)則導出的所有定理都是重言式由、公理和規(guī)則導出的公式，在中的公式都為真時也為真11命題演算：形式系統(tǒng)PCPC的一致性(consistency)沒有公式A，使得PCA和PCA同時成立由PC的合理性容易證明PC的完備性(completeness)如果公式A是重言式，則A一定是PC中的定理（如果A，則PCA）如果公式A是公式集合的邏輯結(jié)果，則A一定是的演繹結(jié)果（如果A，則PCA）證明很難，略。12命題演算：形式系統(tǒng)PC證明定理：PCAA1(A(AA)A)(A(AA)(AA)：公理A22 A(AA)A)：公理A13 (A(AA)(AA)：對1,2使用分離規(guī)則4 A

6、(AA)：公理A15 AA：對3,4使用分離規(guī)則13命題演算：形式系統(tǒng)PC證明：A,B(AC)BC1 A：前提2 B(AC)：前提3 A(BA)：公理A14 BA：對1,3用分離規(guī)則5 (B(AC)(BA)(BC)：公理A26 (BA)(BC)：對2,5用分離規(guī)則7 BC：對4,6用分離規(guī)則14命題演算：形式系統(tǒng)PC演繹定理對任意公式集合和公式A,B，AB當且僅當AB當=時，AB當且僅當AB，或AB歸謬定理對任何公式集合和公式A,B，若AB，AB，那么A窮舉定理對任何公式集合和公式A,B，若AB，AB，那么B15命題演算：形式系統(tǒng)PC證明：AAA(AA)：公理A1，由演繹定理證明了：A,AAA

7、(AA)：公理A1，由演繹定理證明了：A,AA，也就是A, AA上面兩個前提，用歸謬定理得到AA再用演繹定理，有AA16命題演算：形式系統(tǒng)PC證明：(AC)(BC)(AB)C)根據(jù)演繹定理，只需要證明AC,BC,ABC因為AC,BC,AB,AC是顯然的AC,BC,AB,AC是易證的根據(jù)窮舉定理AC,BC,ABC得證17命題演算：定理判定問題一個形式系統(tǒng)本質(zhì)上說是一個符號串的集合形式系統(tǒng)的定義就是符號串集合的構(gòu)造性定義符號體系規(guī)定了符號串可能包含的字符（或字符的合法組合模式，詞）如PC中的命題變元、常元和公式的定義公理規(guī)定了幾個集合中的符號串（或者這種符號串的模式）如PC中的公理，實質(zhì)是公理模式

8、推理規(guī)則規(guī)定了從集合中已知符號串轉(zhuǎn)換生成集合中其它符號串的方法如PC中的分離規(guī)則18命題演算：定理判定問題形式系統(tǒng)中的定理本質(zhì)上就是在集合中的符號串定理的證明過程就是符號串的構(gòu)造過程這個過程需要在有限步內(nèi)結(jié)束定理判定問題給定一個符號串，判定是否形式系統(tǒng)中的定理能否單靠形式系統(tǒng)本身的公理和推理規(guī)則在有限步驟內(nèi)判定定理和非定理？19命題演算：定理判定問題例子：一個簡單的形式系統(tǒng)MIU符號系統(tǒng)：M, I, U組成的串初始串：MI公理：MI規(guī)則1：如果串的最后一個符號是I，則可以加上一個U如果xI是定理，那么xIU也是定理規(guī)則2：如果串符合Mx，則可以再加上x而生成Mxx，x代表任何一個由M,I,U組

9、成的串如果Mx是定理，那么Mxx也是定理20命題演算：定理判定問題一個簡單的形式系統(tǒng)MIU規(guī)則3：如果串中出現(xiàn)連續(xù)3個I，則可以用U代替III得到新串如果xIIIy是定理，那么xUy也是定理規(guī)則4：如果串中出現(xiàn)UU，則可以將UU刪去得到新串如果xUUy是定理，那么xy也是定理判定問題：MU是否系統(tǒng)中的串？MU是否定理？21命題演算：定理判定問題一個簡單的形式系統(tǒng)MIU由公理和推理規(guī)則，我們?nèi)菀讟?gòu)造定理樹MIMIUMII12MIUIUMIUIUIUIU22MIIUMIIUIIU12MIIIIMIIIIUMIIIIIIIIMUIMIU1233MU?222命題演算：定理判定問題一個簡單的形式系統(tǒng)MI

10、U用構(gòu)造系統(tǒng)中所有定理的方法并不能保證在有限的步驟內(nèi)能夠判定定理到底MU是不是定理？我們需要利用同構(gòu)機制求助于系統(tǒng)之外的自然數(shù)運算定律23命題演算：定理判定問題MIU的一種同構(gòu)M對應3，I對應1，U對應0自然數(shù)31在集合中規(guī)則1：如果集合中有數(shù)以1結(jié)尾，則添一個0也是集合中的數(shù)規(guī)則2：如果集合中有數(shù)以3開始，則把3后面的數(shù)再重復一次添在末尾也是集合中的數(shù)規(guī)則3：如果集合中有數(shù)包含111，則把111替換成0也是集合中的數(shù)規(guī)則4：如果集合中有數(shù)包含00，則去掉00的數(shù)也是集合中的數(shù)問：30是不是集合中的數(shù)？24命題演算：定理判定問題MIU的一種同構(gòu)通過分析數(shù)的構(gòu)造規(guī)則，我們發(fā)現(xiàn)集合中的數(shù)都不可能被

11、3整除31不能被3整除規(guī)則14都不能從不能被3整除的數(shù)生成能被3整除的數(shù)30可以被3整除，所以30不屬于這個集合結(jié)論：MU不是MIU系統(tǒng)中的定理25命題演算：定理判定問題形式系統(tǒng)PC定理判定問題一個符合PC符號體系定義的命題公式，是否是PC中的定理？同樣，用PC系統(tǒng)中公理和分離規(guī)則不能保證能在有限步驟判定一個命題公式是否定理但是，PC有一個非常重要的同構(gòu)：真值函數(shù)運算系統(tǒng)只需要用真值表判定命題公式對應的真值函數(shù)是否重言式，即可判定是否PC中的定理，真值表的運算是有限步驟可以完成的。（注意：真值表并不是PC中的成分）26下次我們講謂詞演算個體、謂詞和量詞謂詞公式永真式一階謂詞演算形式系統(tǒng)FC自然推理系統(tǒng)ND27數(shù)理邏輯教學進程第1課：概論和課程介紹（07.02.27）第2課：命題和聯(lián)結(jié)詞（07.03.01）第3課：重言式和范式（07.03.06）第4課：命題演算系