數(shù)學(xué)的主要內(nèi)容是計算和證明。在十七世紀(jì)，算術(shù)因符號化促使了代數(shù)學(xué)的產(chǎn)生，代數(shù)使計算變得精確和方便，也使計算方法系統(tǒng)化。費爾馬和笛卡兒的解析幾何 把幾何學(xué)代數(shù)化，大大擴展了幾何的領(lǐng)域，而且使得少數(shù)天才的推理變成機械化的步驟。這反映了代數(shù)學(xué)作為普遍科學(xué)方法的效力，于是笛卡兒嘗試也把邏輯代數(shù) 化。與笛卡兒同時代的英國哲學(xué)家霍布斯也認(rèn)為推理帶有計算性質(zhì)，不過他并沒有系統(tǒng)地發(fā)展這種思想。

    現(xiàn) 在公認(rèn)的數(shù)理邏輯創(chuàng)始人是萊布尼茲。他的目的是選出一種“通用代數(shù)”，其中把一切推理都化歸為計算。實際上這正是數(shù)理邏輯的總綱領(lǐng)。他希望建立一套普遍的 符號語言，其中的符號是表義的，這樣就可以象數(shù)字一樣進(jìn)行演算，他的確將某些命題形式表達(dá)為符號形式，但他的工作只是一個開頭，大部分沒有發(fā)表，因此影響 不大。

    真正使邏輯代數(shù)化的是英國數(shù)學(xué)家布爾，他在1847年出版了《邏輯的數(shù)學(xué)分析》，給出了現(xiàn)代所謂的“布爾代數(shù)”的原型。布爾確信符號化會使邏輯變得嚴(yán)密。他的對象是事物的類，1表示全類，0表示空類；xy表示x和y的共同分子所組成的類，運算是邏輯乘法；x＋y表示x和y兩類所合成的類，運算是邏輯加法。

    所以邏輯命題可以表示如下：凡x是y可以表示成x(1－y)＝0；沒有x是y可以表示成xy＝0。它還可以表示矛盾律 x(1－x)＝0；排中律x＋(1－x)＝1。

    布爾看出類的演算也可解釋為命題的演算。當(dāng)x、y不是類而是命題，則x＝1表示的是命題 x為真，x＝0表示命題x為假，1－x表示x的否定等等。顯然布爾的演算構(gòu)成一個代數(shù)系統(tǒng)，遵守著某些規(guī)律，這就是布爾代數(shù)。特別是它遵從德·莫爾根定律。

    美國哲學(xué)家、數(shù)學(xué)家小皮爾斯推進(jìn)了命題演算，他區(qū)別了命題和命題函數(shù)。一個命題總是真的或假的，而一個命題函數(shù)包含著變元，隨著變元值選取的不同，它可以是真也可以是假。皮爾斯還引進(jìn)了兩個變元的命題函數(shù)以及量詞和謂詞的演算。

    對現(xiàn)代數(shù)理邏輯貢獻(xiàn)最大的是德國耶拿大學(xué)教授、數(shù)學(xué)家弗雷格。弗雷格在1879年出版的《概念文字》一書中不僅完備地發(fā)展了命題演算，而且引進(jìn)了量詞概念以及實質(zhì)蘊涵的概念，他還給出一個一階謂詞演算的公理系統(tǒng)，這可以說是歷史上第一個符號邏輯的公理系統(tǒng)。因此在這本只有88頁的小冊子中，包含著現(xiàn)代數(shù)理邏輯的一個頗為完備的基礎(chǔ)。

    1884年，弗雷格的《算術(shù)基礎(chǔ)》出版，后來又?jǐn)U展成《算術(shù)的基本規(guī)律》。不過由于他的符號系統(tǒng)煩瑣復(fù)雜，從而限制了它的普及，因此在十九世紀(jì)時，他的著作流傳不廣。后來由于羅素的獨立工作，才使得弗雷格的工作受到重視。

    用符號語言對數(shù)學(xué)進(jìn)行公理化的是意大利數(shù)學(xué)家皮亞諾，他在1889年用拉丁文寫了一本小冊子《用新方法陳述的算術(shù)原理》。在這之前，皮亞諾已經(jīng)把布爾和施羅德的邏輯用在數(shù)學(xué)研究上，并且引進(jìn)了一系列對于他前人工作的更新。例如對邏輯運算和數(shù)學(xué)運算使用不同的符號，區(qū)別范疇命題和條件命題，這引導(dǎo)他得出量詞理論。

    這些改進(jìn)都是對于布爾和施羅德理論的改進(jìn)，而不是對弗雷格理論的改進(jìn)，因為當(dāng)時皮亞諾還不知道弗雷格的工作。在《算術(shù)原理》中，他在引進(jìn)邏輯概念相公式之后，開始用符號的記法來重寫算術(shù)，在這本書中他討論了分?jǐn)?shù)、實數(shù)、甚至極限和點集論中的概念。

　　皮亞諾引進(jìn)最原始的算術(shù)概念是“數(shù)”“1”“后繼”和“等于”，并且陳述了關(guān)于這些概念的九條公理。今天我們認(rèn)為其中公理2、3、4、5都是討論恒等的，應(yīng)該屬于邏輯公理，所以就剩下了五條公理。這就是現(xiàn)在眾所周知的皮亞諾公理。最后一條公理即公理9，就是所謂數(shù)學(xué)歸納法原理，他用類的詞句來表述，其中包含一個類變元。皮亞諾承認(rèn)他的公理化來自戴德金。

    從1開始，皮亞諾用x＋1來表示后繼函數(shù)。然后作為定義引進(jìn)了加法和乘法。這些定義是遞歸的定義。雖然在他的系統(tǒng)中，皮亞諾沒有象戴德金那樣有力的定理可資利用，但皮亞諾并沒有公開地宣稱這些定義可以去掉。

    這 本書的邏輯部分還列出命題演算的公式，類演算的公式，還有一部分量詞的理論。皮亞諾的符號要比布爾和施羅德的符號高明得多，標(biāo)志著向近代邏輯的重要轉(zhuǎn)變。 他還對于命題的演算和類演算做了某些區(qū)別。這就是我們現(xiàn)在的兩種不同演算，而不是同一種演算的兩種不同解釋。它的普遍量詞記號是新的，而且是便利的。

    不過書里還是存在缺點，如公式只是列出來的，而不是推導(dǎo)出來的；因為沒有給出推導(dǎo)規(guī)則，皮亞諾引進(jìn)了代入規(guī)則的概念，但是也沒有給出任何規(guī)則；更嚴(yán)重的是他沒有給出任何分離規(guī)則，結(jié)果盡管他的系統(tǒng)有許多優(yōu)點，但他沒有可供使用的邏輯。一直到后來，他才在一系列文章，特別是1895年發(fā)表的《數(shù)學(xué)論集》中，對這些邏輯公式進(jìn)行了證明。然而他這些證明還是缺少推演規(guī)則，在這方面他受到了弗雷格的批評。后來皮亞諾盡力想比弗雷格的《概念文字》有更多的內(nèi)容，但是他做得并不夠。不過他的這些著作在數(shù)學(xué)界仍有很大影響，得到廣泛的傳播。

    2.1.1 命題演算

    邏 輯演算是數(shù)理邏輯的基礎(chǔ)，命題演算是邏輯演算最基本的組成部分。命題演算研究命題之間的關(guān)系，比如簡單命題和復(fù)雜命題之間的關(guān)系，簡單命題如何構(gòu)成復(fù)雜命 題，由簡單命題的真假如何推出復(fù)雜命題的真假等等。對于具體命題，我們不難通過機械運算來達(dá)到我們的目的，這就是命題的算術(shù)。

    對于命題演算最早是由美國邏輯學(xué)家波斯特在1921年給出證明的，他的證明方法是把命題化為標(biāo)準(zhǔn)形式—合取范式。教科書中常見的證明是匈牙利數(shù)學(xué)家卡爾馬給出的。除了這些構(gòu)造性證明之外，還有用布爾代數(shù)的非構(gòu)造性證明。

    2.1.2 一階謂詞演算

    在命題演算中，形式化的對象及演算的對象都是語句。但是，在數(shù)學(xué)乃至一般推理過程中，許多常見的邏輯推理并不能建立在命題演算的基礎(chǔ)上。例如：1．張三的每位朋友都是李四的朋友，王五不是李四的朋友，所以王五不是張三的朋友。因此，我們必須深入到語句的內(nèi)部，也就是要把語句分解為主語和謂語。

    謂 詞演算要比命題演算范圍寬廣得多，這由變元也可以反映出來。命題演算的變元只是語句或命題，而謂詞演算的變元有三類：個體變元、命題變元、謂詞變元。由于 謂詞演算中有全稱量詞和存在量詞，在這些量詞后面的變化稱為約束變元，其他變元稱為自由變元。最簡單的謂詞演算是狹義謂詞演算，現(xiàn)在通稱一階謂詞演算。

謂 詞演算中的普遍有效公式與命題演算中的重言式還是有差別的。我們有行之有效的具體方法來判定一個公式是不是重言式。這種方法每一步都有明確的規(guī)定，并且可 以在有限步內(nèi)完成，這種方法我們稱為能行的。但是在謂詞演算中，并沒有一種能行的方法來判定任何一個公式是否普遍有效的。這就需要尋找一種能行的方法來判 定某個具體公式或一類公式是否普遍有效，這就是所謂判定問題。它是數(shù)理邏輯中最主要的問題之一。

    一 階謂詞演算的普遍有效公式也有一個公理系統(tǒng)。另外，同樣也有代入規(guī)則及推理規(guī)則。另外，還有約束變元改字規(guī)則等變形規(guī)則。在謂詞演算中也可以將每一個公式 通過變形規(guī)則化為標(biāo)準(zhǔn)形式。其中最常用的是所謂前束范式，也就是公式中所有的量詞都放在最前面，而且還可以把前束范式進(jìn)一步化成斯科蘭路范式，它不但具有 前束范式的形狀，而且每一個存在量詞都在所有全稱量詞之前。

    利用范式可以解決許多問題，最重要的是哥德爾證明的一階謂詞演算的公理系統(tǒng)的完全性定理，即可以證明：公式A在公理系統(tǒng)中可以證明的當(dāng)且僅當(dāng)A是普遍有效的。同樣，一階謂詞演算的公理系統(tǒng)也是協(xié)調(diào)(無矛盾)的、相獨立的。1936年丘奇和圖林獨立的證明一階謂詞演算公式的一般判定問題不可解問題，可以變?yōu)槿ソ鉀Q具有特殊形式的范式公式的判定問題。

    2.1.3 其他邏輯演算

    邏輯演算系統(tǒng)很多，命題演算應(yīng)該說來源于布爾，布爾的系統(tǒng)是非真即假的二值系統(tǒng)。真值大于2的邏輯系統(tǒng)稱為多值邏輯。多值邏輯首先由波蘭數(shù)學(xué)家盧卡西維茨在1920年引進(jìn)，波斯特在1921年也獨立地引進(jìn)。多值邏輯有著廣泛的應(yīng)用，在二十世紀(jì)七十年代，國際上就曾多次召開專門的多值邏輯會議。

    另一種常見的邏輯是模態(tài)邏輯，它是美國邏輯學(xué)家劉易斯在1918年引進(jìn)的。他考慮的不是實質(zhì)蘊涵而是嚴(yán)格蘊涵。另外，他在邏輯中也考慮所謂必要性與可能性等問題，引進(jìn)著名的模態(tài)算子，這是直觀可能性的形式化。

    還有一個包括古典邏輯演算的公理系統(tǒng)，即直覺主義公理系統(tǒng)，其中否定排中律，它是荷蘭數(shù)學(xué)家海丁于1930年引進(jìn)的。它雖因直覺主義而得名，但是可以得到其他的解釋，在現(xiàn)代數(shù)理邏輯的研究中十分重要。

    在 數(shù)理邏輯的研究中，狹義謂詞演算是最重要的。狹義謂詞演算也稱一階謂詞演算，許多人默認(rèn)數(shù)學(xué)中所用的邏輯通用為一階謂詞演算。但是，許多涉及數(shù)學(xué)問題的邏 輯演算必須加進(jìn)有關(guān)等號的謂詞，稱為具等式的一階謂詞演算。這是現(xiàn)在最常用的一種邏輯系統(tǒng)，在研究算術(shù)系統(tǒng)中就要用到它。

    但是，即使象實數(shù)的算術(shù)系統(tǒng)，一階謂詞演算也是不夠的，更何況現(xiàn)代數(shù)學(xué)中涉及集合的子集，因此一階謂詞演算是不足以表達(dá)的。這時需要二階謂詞演算乃至高階謂詞演算，其中首先出現(xiàn)的是謂詞變元。

    不 過，在現(xiàn)代數(shù)理邏輯的研究中，常常通過其它方式推廣一階謂詞演算。比如一種常用的“無窮”邏輯允許無窮公式，即公式中容許可數(shù)多合取或析取，不過量詞仍限 制為有限多。這種無窮邏輯現(xiàn)在在集合論、遞歸論、模型論當(dāng)中是必不可少的。另外一種推廣一階謂詞演算的途徑是引進(jìn)新的量詞，比如“存在許多……”。