1、談談離散數(shù)學中數(shù)理邏輯的教學,一、弄清數(shù)理邏輯演算形式系統(tǒng)的語構和語義,學習數(shù)理邏輯的命題演算和謂詞演算形式系統(tǒng)，其實也是在學習一類語言系統(tǒng)-形式語言系統(tǒng)。要教好或?qū)W好這兩個演算，弄清這類語言的語構（也稱語法syntax）和語義（semantic）這兩個方面是極其重要的。,語言的語構通常指語言的成分和構成，包括：字，詞法，句法。在命題演算和謂詞演算形式語言中則是指字母表（或符號表）： 命題演算符號表=(,), , , ，,p1 ,p2 ,p3 ,，q1 ,q2 ,q3 ,其中(,)是技術符號-括號, pi ,qi為命題變元或命題常元。,謂詞演算符號表組成如下： 個體變元x1,x2,x3, ,

2、y1,y2,y3, （簡稱變元） 個體常元a1,a2,a3, , b1,b2,b3, （簡稱常元） 函詞,（一元函詞） ,（二元函詞） ,（n元函詞） 謂詞,（一元謂詞） ,（二元謂詞） ,（n元謂詞） 其真值聯(lián)結詞，, , , ， 量詞 , 括號（，）,由于命題演算形式語言以命題為最小研究單元，因此它不需要表示個體對象的詞法，只有表示命題公式的詞法。謂詞演算形式語言的詞法便是它的項的構成規(guī)則和合式公式的構成規(guī)則： 謂詞演算中項（terms）定義如下： （1）變元和常元為項。 （2）對任意正整數(shù)n，如果t1,t2, ，tn為項，那么f(n)t1t2tn亦為項。 除有限次使用（1），（2）條款可

3、確認為項的符號串外，沒有別的是項。,謂詞演算形式語言中的合式公式（well found formula）定義如下： (1)對任意正整數(shù)n，如果t1,，tn為項，那么P(n) t1t2tn為公式，并稱之為原子公式。 (2)如果A，B為公式，那么（A）, （AB）, （AB）, （AB）,（AB）,（vA）,（vA）（v為任一變元）均為公式。 （3）除有限次使用（1），（2）條款可確認為公式的符號串外，沒有別的是公式。,命題演算和謂詞演算形式語言的句法則是它們各自系統(tǒng)內(nèi)的推理規(guī)則，即由公理導出定理（或由公式重寫公式的重寫規(guī)則）,語言的語義通常指語言成分的含義或?qū)φZ言成分的指稱，包括詞義，句義（文意

4、）。在命題演算和謂詞演算形式語言中則是對個體域的確定（變元的語義：取值范圍），對常元、函詞、謂詞的解釋（個體域上的函數(shù)、性質(zhì)和關系），對聯(lián)接詞、量詞的真值規(guī)定，進而確定項的語義（個體域中的個體）以及公式的意義（即它的真值）。,我們知道語構的機器處理是十分簡單的，就是通常所說的數(shù)據(jù)處理問題；而語義的機器處理是相當困難的，一個簡單的命題公式的可滿足性判斷就已經(jīng)是NP完全的了，一階邏輯公式的可滿足性判斷則是理論不可計算的（或半可計算的）。,離散數(shù)學中通常先從邏輯代數(shù)說起，即非形式地介紹數(shù)理邏輯，大體是在介紹數(shù)理邏輯形式系統(tǒng)的語義，然后才介紹形式系統(tǒng)本身，也就是它的語構部分。這種次序的顛倒對于教學是十

5、分必要的，但由此引起了學生的混淆。因此，建議在講解形式系統(tǒng)后，給予學生一個回顧和整理，區(qū)分數(shù)理邏輯形式系統(tǒng)的語構和語義這兩個方面。以下的對照表，也許在教學中是會有幫助的。,二、弄清數(shù)理邏輯形式系統(tǒng)的研究的幾個層面,對數(shù)理邏輯演算形式系統(tǒng)的研究將使用兩種語言三個層面。一種是數(shù)理邏輯形式系統(tǒng)本身所使用的那個形式語言，我們稱之為對象語言（object Language），另一種是介紹和研討這個形式系統(tǒng)時使用的語言，為通常所用的數(shù)學語言，常稱為元語言（meta Language）。后者也用大量符號，包括（1）沿用形式系統(tǒng)的符號（它們是討論的對象）；（2）表示形式系統(tǒng)中同一類符號的符號，稱為語法變元（s

6、yntactic variables），例如用v 表示系統(tǒng)中的變元x1,x2,x3, , y1,y2,y3, 中的任意一個；（3）為表達元語言概念引入的新符號例如， 等。,對數(shù)理邏輯演算形式系統(tǒng)的研究的三個層面是：,第一個是對對象語言語構的研究，即形式系統(tǒng)的建立和系統(tǒng)內(nèi)的推演，構成形式系統(tǒng)內(nèi)的公理、推理規(guī)則及其由它們導出的定理所組成的那個邏輯學理論； 第二個是對這個形式系統(tǒng)的語義進行研究所得的語義學結論，即邏輯代數(shù)和模型理論； 第三個是關于這個系統(tǒng)的性質(zhì)的定理（稱為元定理（meta theorems）所組成的理論，稱為元理論（meta fheory）。元理論又包括兩個方面：（1）系統(tǒng)導出規(guī)則的

7、研究，以及（2）對語構和語義的一致性研究，即系統(tǒng)的合理性、完備性等的研究。,一個例子,在離散數(shù)學教學教材中，常常有所謂“全稱消除規(guī)則”和“存在消除規(guī)則”：即 （t對x可代入） ， 其實，這是兩個層面的的事情，前者可以用做系統(tǒng)內(nèi)的推理規(guī)則，而后者實際上是一條元定理的不正確的表述形式，這條元定理是： 定理 設為一階邏輯的任一公式集，A，B為任意公式，變元v在的每一公式及公式B中均無自由出現(xiàn)，那么由vA 及 ；AB可推出 B。,該定理是這樣一條導出規(guī)則；當我們有了vA后便可將A看作附加的演繹前提，當?shù)玫脚cv無關的B時，可確認B已推出，即它并不依賴于A而成立。這就象數(shù)學證明中我們常做的那樣：當推知方程

8、F（x）=0有根（即x(F(x)=0)）時，可設這個根為x0（即F(x0)=0），然后再據(jù)此去證所需的結論，只要所證結論與x0的性質(zhì)（除x0為F(x)=0的根這一性質(zhì)）無關，它就是有效的演繹結果。也就是說， 表示：有了xA(x),可以假定A(x)，而不是由xA(x)推出A(x)（這顯然是不正確的）。,當然，可以把這一定理引入系統(tǒng)，作為一個自然推理系統(tǒng)的推理規(guī)則，那么應當正確地表示為 （和C中無e的出現(xiàn)）,三、講一點自然推理系統(tǒng),不少離散數(shù)學教材不講形式系統(tǒng)，也有不少教材所給的形式系統(tǒng)是不嚴謹?shù)?。我認為這都是不適當?shù)?，建議簡要地介紹一個自然推理系統(tǒng)。不講形式系統(tǒng)，學生無法了解現(xiàn)代邏輯學的真諦，無

9、法弄清形式系統(tǒng)的語構和語義，也無法弄清形式系統(tǒng)研究的幾個層面，也就談不上掌握形式化方法和技術。事實上，不講形式系統(tǒng)，許多重要概念也無法說得清楚。,另一個例子,全稱推廣規(guī)則通常是必定要講的，但這條規(guī)則有一個重要的應用前提：“x不在導出A（x）的前提中自由出現(xiàn)”。這個應用前提就很難講得清楚，很難掌握得好，特別是碰到xyA(x,y)的情況時，更是如此。以下推理的錯誤是明顯的： （1）xyA(x,y) 前提 （2）yA(x,y) 全稱消除規(guī)則 （3）A(x,y) 存在消除規(guī)則 （4）xA(x,y) 全稱推廣規(guī)則 （5）yxA(x,y) 存在推廣規(guī)則 也許你會告訴學生對xyA(x,y)應該注意什么，但還

10、有許多其他情況很難一一加以注明，如何處置？可是，在自然推理系統(tǒng)中，我們可以處理得很簡單。,推廣規(guī)則 (v在 的任一公式里均不自由出現(xiàn)) 其中 為前提和假設的集合（直觀上即為符號 的左邊部分的所有公式的集合）。顯然，條件“v在的任一公式里均不自由出現(xiàn)”是不可缺少的。例如，A為中一個含自由變元v的公式(記為A(v)，顯然A(v)，如果由此得到 vA(v)顯然是荒謬的，因為A(v)正是一個關于v的假設，怎么能由此即斷定由 能演繹出vA(v)呢？這猶如從y=5 y2=52而推出y=5y(y2=52)，是十分荒謬的。當然，由y=5 y2=52 可得 y=5y2=52，進而有 y(y=5y2=52)，這是因為 y=5y2=52中的 為空集合，v在 里不會有自由出現(xiàn)，從而可以使用全稱推廣規(guī)則。,在上文提到的推理中的（3）A(x,y)，在自然推理中是一個假設，處于 中，因而 中有自由變元x，對A(x,y)的全稱推廣便被阻斷，錯誤也就不會發(fā)生。 值得向大家推薦的是文獻3中給出的自然推理系統(tǒng)，在4中也有介紹。,四、自然推理形式