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

2、換原理進(jìn)行推演難以反應(yīng)人類思維推理過(guò)程，需要建立嚴(yán)密的符號(hào)推理體系,命題演算：形式系統(tǒng),形式系統(tǒng)是一個(gè)符號(hào)體系 系統(tǒng)中的概念由符號(hào)表示 推理過(guò)程即符號(hào)變換的過(guò)程 以若干最基本的重言式作為基礎(chǔ)，稱作公理（axioms） 系統(tǒng)內(nèi)符號(hào)變換的依據(jù)是若干確保由重言式導(dǎo)出重言式的規(guī)則，稱作推理規(guī)則（rules of inference） 公理和推理規(guī)則確保系統(tǒng)內(nèi)由正確的前提總能得到正確的推理結(jié)果,命題演算：證明與演繹,證明(proof) 公式序列A1,A2,Am稱作Am的一個(gè)證明，如果Ai(1im)或者是公理，或者由Aj1,Ajk(j1,jki)用推理規(guī)則推得。 當(dāng)這樣的證明存在時(shí)，稱Am為系統(tǒng)的定理(t

3、heorem)，記作*Am（*是形式系統(tǒng)的名稱），或者簡(jiǎn)記為Am,命題演算：證明與演繹,演繹(deduction) 設(shè)為一公式集合。公式序列A1,A2,Am稱作Am的以為前提的演繹，如果Ai(1im)或者是中的公式，或者是公理，或者由Aj1,Ajk(j1,jki)用推理規(guī)則推得。 當(dāng)有這樣的演繹時(shí)， Am稱作的演繹結(jié)果，記作*Am（*是形式系統(tǒng)的名稱），或者簡(jiǎn)記為Am 稱和的成員為Am的前提(hypothesis) 證明是演繹在為空集時(shí)的特例,命題演算：形式系統(tǒng)PC,命題演算形式系統(tǒng)PC(Proposition Calculus) PC的符號(hào)系統(tǒng) 命題變?cè)簆,q,r,s,p1,q1,r1,s

4、1, 命題常元：t,f 聯(lián)結(jié)詞：,（注意是完備集） 括號(hào)：(,) 命題公式 命題變?cè)兔}常元是公式 如果A,B是公式，則(A)，(AB)均為公式（結(jié)合優(yōu)先級(jí)和括號(hào)省略約定同前） 只有有限次使用上面兩條規(guī)則得到的符號(hào)串才是命題公式,命題演算：形式系統(tǒng)PC,PC的公理（A,B,C表示任意公式） A1:A(BA) A2:(A(BC)(AB)(AC) A3:(AB)(BA) PC的推理規(guī)則（A,B表示任意公式） A,AB/B（分離規(guī)則）,命題演算：形式系統(tǒng)PC,PC的合理性(soundness) 如果公式A是系統(tǒng)PC的定理，則A是重言式（如果PCA，則A） 如果A是公式集合的演繹結(jié)果，那么A是的邏輯

5、結(jié)果（如果PCA，則A） PC合理性的證明 PC中的公理A1,A2,A3都是重言式； PC的分離規(guī)則是“保真”的，就是如果A真，AB真，總有B真。 這樣，由公理和規(guī)則導(dǎo)出的所有定理都是重言式 由、公理和規(guī)則導(dǎo)出的公式，在中的公式都為真時(shí)也為真,命題演算：形式系統(tǒng)PC,PC的一致性(consistency) 沒有公式A，使得PCA和PCA同時(shí)成立 由PC的合理性容易證明 PC的完備性(completeness) 如果公式A是重言式，則A一定是PC中的定理（如果A，則PCA） 如果公式A是公式集合的邏輯結(jié)果，則A一定是的演繹結(jié)果（如果A，則PCA） 證明很難，略。,命題演算：形式系統(tǒng)PC,證明定理

6、：PCAA 1(A(AA)A)(A(AA)(AA)：公理A2 2 A(AA)A)：公理A1 3 (A(AA)(AA)：對(duì)1,2使用分離規(guī)則 4 A(AA)：公理A1 5 AA：對(duì)3,4使用分離規(guī)則,命題演算：形式系統(tǒng)PC,證明：A,B(AC)BC 1 A：前提 2 B(AC)：前提 3 A(BA)：公理A1 4 BA：對(duì)1,3用分離規(guī)則 5 (B(AC)(BA)(BC)：公理A2 6 (BA)(BC)：對(duì)2,5用分離規(guī)則 7 BC：對(duì)4,6用分離規(guī)則,命題演算：形式系統(tǒng)PC,演繹定理 對(duì)任意公式集合和公式A,B，AB當(dāng)且僅當(dāng)AB 當(dāng)=時(shí)，AB當(dāng)且僅當(dāng)AB，或AB 歸謬定理 對(duì)任何公式集合和公式

7、A,B，若AB，AB，那么A 窮舉定理 對(duì)任何公式集合和公式A,B，若AB，AB，那么B,命題演算：形式系統(tǒng)PC,證明：AA A(AA)：公理A1，由演繹定理證明了：A,AA A(AA)：公理A1，由演繹定理證明了：A,AA，也就是A, AA 上面兩個(gè)前提，用歸謬定理得到AA 再用演繹定理，有AA,命題演算：形式系統(tǒng)PC,證明：(AC)(BC)(AB)C) 根據(jù)演繹定理，只需要證明AC,BC,ABC 因?yàn)锳C,BC,AB,AC是顯然的 AC,BC,AB,AC是易證的 根據(jù)窮舉定理AC,BC,ABC得證,命題演算：定理判定問(wèn)題,一個(gè)形式系統(tǒng)本質(zhì)上說(shuō)是一個(gè)符號(hào)串的集合 形式系統(tǒng)的定義就是符號(hào)串集合

8、的構(gòu)造性定義 符號(hào)體系規(guī)定了符號(hào)串可能包含的字符（或字符的合法組合模式，詞） 如PC中的命題變?cè)?、常元和公式的定義 公理規(guī)定了幾個(gè)集合中的符號(hào)串（或者這種符號(hào)串的模式） 如PC中的公理，實(shí)質(zhì)是公理模式 推理規(guī)則規(guī)定了從集合中已知符號(hào)串轉(zhuǎn)換生成集合中其它符號(hào)串的方法 如PC中的分離規(guī)則,命題演算：定理判定問(wèn)題,形式系統(tǒng)中的定理本質(zhì)上就是在集合中的符號(hào)串 定理的證明過(guò)程就是符號(hào)串的構(gòu)造過(guò)程 這個(gè)過(guò)程需要在有限步內(nèi)結(jié)束 定理判定問(wèn)題 給定一個(gè)符號(hào)串，判定是否形式系統(tǒng)中的定理 能否單靠形式系統(tǒng)本身的公理和推理規(guī)則在有限步驟內(nèi)判定定理和非定理？,命題演算：定理判定問(wèn)題,例子：一個(gè)簡(jiǎn)單的形式系統(tǒng)MIU 符

9、號(hào)系統(tǒng)：M, I, U組成的串 初始串：MI 公理：MI 規(guī)則1：如果串的最后一個(gè)符號(hào)是I，則可以加上一個(gè)U 如果xI是定理，那么xIU也是定理 規(guī)則2：如果串符合Mx，則可以再加上x而生成Mxx，x代表任何一個(gè)由M,I,U組成的串 如果Mx是定理，那么Mxx也是定理,命題演算：定理判定問(wèn)題,一個(gè)簡(jiǎn)單的形式系統(tǒng)MIU 規(guī)則3：如果串中出現(xiàn)連續(xù)3個(gè)I，則可以用U代替III得到新串 如果xIIIy是定理，那么xUy也是定理 規(guī)則4：如果串中出現(xiàn)UU，則可以將UU刪去得到新串 如果xUUy是定理，那么xy也是定理 判定問(wèn)題：MU是否系統(tǒng)中的串？ MU是否定理？,命題演算：定理判定問(wèn)題,一個(gè)簡(jiǎn)單的形式

10、系統(tǒng)MIU 由公理和推理規(guī)則，我們?nèi)菀讟?gòu)造定理樹,MI,MIU,MII,1,2,MIUIU,MIUIUIUIU,2,2,MIIU,MIIUIIU,1,2,MIIII,MIIIIU,MIIIIIIII,MUI,MIU,1,2,3,3,MU,?,?,?,?,?,?,2,命題演算：定理判定問(wèn)題,一個(gè)簡(jiǎn)單的形式系統(tǒng)MIU 用構(gòu)造系統(tǒng)中所有定理的方法并不能保證在有限的步驟內(nèi)能夠判定定理 到底MU是不是定理？ 我們需要利用同構(gòu)機(jī)制求助于系統(tǒng)之外的自然數(shù)運(yùn)算定律,命題演算：定理判定問(wèn)題,MIU的一種同構(gòu) M對(duì)應(yīng)3，I對(duì)應(yīng)1，U對(duì)應(yīng)0 自然數(shù)31在集合中 規(guī)則1：如果集合中有數(shù)以1結(jié)尾，則添一個(gè)0也是集合中的

11、數(shù) 規(guī)則2：如果集合中有數(shù)以3開始，則把3后面的數(shù)再重復(fù)一次添在末尾也是集合中的數(shù) 規(guī)則3：如果集合中有數(shù)包含111，則把111替換成0也是集合中的數(shù) 規(guī)則4：如果集合中有數(shù)包含00，則去掉00的數(shù)也是集合中的數(shù) 問(wèn)：30是不是集合中的數(shù)？,命題演算：定理判定問(wèn)題,MIU的一種同構(gòu) 通過(guò)分析數(shù)的構(gòu)造規(guī)則，我們發(fā)現(xiàn)集合中的數(shù)都不可能被3整除 31不能被3整除 規(guī)則14都不能從不能被3整除的數(shù)生成能被3整除的數(shù) 30可以被3整除，所以30不屬于這個(gè)集合 結(jié)論：MU不是MIU系統(tǒng)中的定理,命題演算：定理判定問(wèn)題,形式系統(tǒng)PC定理判定問(wèn)題 一個(gè)符合PC符號(hào)體系定義的命題公式，是否是PC中的定理？ 同樣，用PC系統(tǒng)中公理和分離規(guī)則不能保證能在有限步驟判定一個(gè)命題公式是否定理 但是，PC有一個(gè)非常重要的同構(gòu)：真值函數(shù)運(yùn)算系統(tǒng) 只需要用真值表判定命題公式對(duì)應(yīng)的真值函數(shù)是否重言式，即可判定是否PC中的定理，真值表的運(yùn)算是有限步驟可以完成的。（注意：真值表并不是PC中的成分）,下次我們講,謂詞演算 個(gè)體、謂詞和量詞 謂詞公式 永真式 一階謂詞演算形式系統(tǒng)FC 自然推理系統(tǒng)ND,數(shù)理邏輯教學(xué)進(jìn)程,第1課：概論和課程介紹（07.02.27） 第2課：命題和聯(lián)結(jié)詞（07.03.01） 第3課：重言式和范式（07.03.06） 第4課：命題演算系統(tǒng)（