數理邏輯簡介

在美國的研究生入學考試（GRE）中，有一節全是邏輯題。給你一種安排、或是分類、或是成分判定、或是決定等等，再給出一係列規則，要你找出合乎所有規則的各種答案來。半個小時5、6道題，每道題5、6小問，怎麽才能按時做完呢？

學校老師總是強調要 ” Thinking, Thinking， Thinking “，可怎麽去Think呢？有人說，Thinking就是你沒有被教過，仍然能夠Figure Out（想出來？），這聽起來怎麽陷入邏輯循環了？思考得有個由量變到質變的過程吧？試試這個問題：

一位女士到一家五金店為她父親買了一個電鑽。回家後才發現買錯了；父親要的那種電鑽的價錢是她買的這把的兩倍。她回到店裏，還回去剛買的那把，拿起更貴的那把就要往家走。店主叫住了她，說她還欠店主錢。女士說，沒有啊！她原來付過的錢，加上剛剛還回去的那把電鑽的價值，不正是等於手裏這個電鑽的價錢嗎？店主一時無言以對。你能幫他解圍嗎？

數理邏輯研究如何推理，是關於思考的學問，也可以說是一台測謊儀。數理邏輯的主要分支包括：模型論、證明論、遞歸論和公理化集合論。數理邏輯和計算機科學有許多重合之處，程序語言學、語義學的研究從模型論衍生而來，而程序驗證中的模型檢測則從模型論衍生而來。Curry-Howard correspondence給出了“證明”和“程序”的等價性。

數理邏輯的研究對象是命題和謂詞；命題就是一句斷言或者提議，謂詞就是聯係兩個客觀物件的關係詞，像是A物“是，屬於”B者。為了表述的方便，我們把一切對象都符號化：一個句子是一個符號，一個謂詞則用一個函數記號來表示，所以又稱其為符號邏輯或形式邏輯。將自然語言符號化是人類的必經之路，這是讓無法量化的東西進入到可計量世界的一種途徑。

人類進行演繹推理的格式是三段論：給定一個斷言：如果P，那麽Q；現有P，所以必有Q。這裏的P和Q都是原子命題—某種更基本的論斷或假設。P稱為前題，或者充分條件；Q是結論，或者必要條件。怎麽判定斷言 “P蘊含Q” 為真呢？一種辦法是把它作為公理，即不言自明、不容置疑的真理。

另一種辦法是，規定：隻有當P為真而Q為假時，整個斷言為假，推理無效。這也同時意味著，如果前題P為假，那麽任何結論Q，無論真假，你都不能說推理不對。比如說，“如果太陽從西邊出來，那麽，水就從高處往低處流”；這裏的結論是對的，前題是錯的，我們沒有理由說，推理有錯。如果有另外一個人說，“如果太陽從西邊出來，那麽，水從低處往高處流”；我們也不能說他錯，因為太陽是從東邊出來的，那是人類對東、西兩個方向的定義。這個規定不太合常理，但數學上也隻能一刀切了。

數理邏輯中還有逆命題，正如任何運算都有逆運算一樣；逆就是相反，把條件與結論顛倒過來：如果Q，那麽P。逆命題與原命題，意思上可能存在差異。例如，如果今天氣溫零下十度以下，那麽我就不出門了：這是常理。它的逆命題是，如果我今天沒有出門，那麽氣溫一定零下十度以下；這顯然不對，我可能是由於別的原因沒有出門。如果逆命題Q → P與原命題 P → Q同為真或者同為假，我們就說P與Q互為充分必要條件，或者邏輯等價。

我們還要把句子的連接詞符號化，也就是邏輯運算符。有“且、和、與（and）”記為  ，等同於集合的交集（）；”或（）”等同於集合的並；“非、否（~、）”等同於集合的補。這三個算符就可以表出所有的連接詞了。’如果P，則Q“， 或者”因為P，所以Q“，即 “P → Q” 等價於 ”~P   Q”；“P除非(unless)Q”等價於“ ~Q → P”或者“Q  P”。還有一個二元運算符“|”（Nor），就構成了一個完備集：P|Q =  (p  q).

三個算符滿足一係列的運算規律，如De Morgan定律，分配律，交換律，結合律，同一律等。這其實都與集合的 “並、交、補” 運算規則一致，可以用文氏圖來直觀地加以證明。命題的蘊含關係等同於集合的包含關係：A ⊆ B 就是從 x  A推出 x  B。說“中國人都是惹不得的”， 可以表示為 C ⊆ Y，C 是所有中國人的集合，Y是所有惹不得之人的集合。如果說“有些中國人是惹不得的”，則可以表示為 C ∩ Y ≠ Φ （空集）。全稱量詞（）和特稱量詞（）都可以集合化。

一個命題必須要能斷得了真假；含有自由變量的斷言，如x + 1 = 2 算不得一個命題。命令句、疑問句、感歎句都算不得命題。給定一個段落，一旦所有句子都符號化成為由邏輯算符連結起來的原子命題的等式了，就得出了N個變量（命題）的方程組：Ei（p1, p2, …, pN） = 1，這裏1表示“真”，Ei是以三個邏輯算符把各原子命題連接起來的式子。如果能夠得出無矛盾的（0，1）解，那麽此段落就是合理的。為了簡化求解，我們可以把式子邏輯等價地轉化為析取範式（用或（）連接起來的一些原子命題的且（）），或者合取範式（用且（）連接起來的一些原子命題的或（）），蘊含關係就等價於下標集的包含關係。

自然語言符號化的困難在於人類動作太多，謂語關係複雜；而命題邏輯的表達能力有限。舉個例子，“每個實數都有一個加法逆元”可以表示為“∀xR ∃yR (x + y = 0)”。怎麽表示“實數的所有有界的、非空集合都有上確界”呢？寫出來就是：

這裏需要對謂詞進行量化；也就是要有二階邏輯甚至更高階的邏輯。在一階邏輯中，不能對謂詞或者個體變量的性質進行量化。在二階邏輯中的 “句子” 也是沒有（任何種類的）自由變量的合式公式。

接下來，要討論表達式的有效性、可計算性，推理係統的完備性、緊致性。我們還有《模糊邏輯》，某個關係是否成立是隨機的，有一個機率！這還怎麽用一個確定的式子去表達？邏輯學家、數學家們是不是走偏了？公理化集合論套不上分析學（連續變量），句子的連貫意義無法表達。怎麽捏出句子的幾個意思來呢？且聽下回分解。