數(shù)理邏輯發(fā)展簡史

數(shù)理邏輯發(fā)展簡史第一頁，共六十二頁，2022年，8月28日什么是邏輯？邏輯示例有2個紅色帽子，3個黑色帽子。三個人站成一縱隊，各戴一頂帽子，每人僅能看到前面人帽子顏色。問？第三個人帽子顏色？回答：不知道！第二個人帽子顏色？回答：不知道！第一個人帽子顏色？回答：知道！第一個人帽子顏色是什么？為什么？第一個人推理：如果第一人和第二人都是紅色帽子，則第三人知道自己帽子顏色為黑色。因為第三人不知道自己帽子顏色為黑色，所以，第一人和第二人不都是紅色帽子。如果第一是紅色帽子，則第二人知道自己帽子顏色為黑色。因為第二人不知道自己帽子顏色為黑色，所以，第一不是紅色帽子。第一是黑色帽子。第二頁，共六十二頁，2022年，8月28日什么是邏輯？思維形式概念反映事物本質(zhì)屬性。判斷由概念組成的一種思維形式叫判斷。推理由幾個相關(guān)聯(lián)的判斷所構(gòu)成的思維形式叫推理。邏輯從結(jié)構(gòu)方面研究正確思維形式及其規(guī)律的科學(xué)。第三頁，共六十二頁，2022年，8月28日數(shù)理邏輯是什么？狹義數(shù)理邏輯用數(shù)學(xué)方法研究數(shù)學(xué)中演繹思維和數(shù)學(xué)基礎(chǔ)的學(xué)科。廣義數(shù)理邏輯用特制符號和數(shù)學(xué)方法來研究處理演繹方法的理論。狹義數(shù)理邏輯包括五個部分邏輯演算模型論集合論遞歸論證明論第四頁，共六十二頁，2022年，8月28日數(shù)理邏輯發(fā)展2種主要途徑借助數(shù)學(xué)的方法改進傳統(tǒng)邏輯不足；對數(shù)學(xué)基礎(chǔ)的研究，產(chǎn)生了大量與邏輯有關(guān)的問題。第五頁，共六十二頁，2022年，8月28日數(shù)理邏輯發(fā)展簡介史前時期亞里土多德的三段論，斯多阿學(xué)派的命題邏輯和中世紀形式邏輯。初創(chuàng)時期萊布尼茨的數(shù)理邏輯思想邏輯代數(shù)和關(guān)系邏輯奠基時期從弗雷格的《概念文字》到希爾伯特的元數(shù)學(xué)綱領(lǐng)邏輯演算的建立，素樸集合論、公理集合論邏輯類理論，直覺主義數(shù)學(xué)基礎(chǔ)和邏輯，形式公理學(xué)和證明論。發(fā)展初期哥德爾的幾項重大結(jié)果—完全性定理、不完全性定理和連續(xù)統(tǒng)假設(shè)的一致性等形式語言中真值概念的定義一般遞歸函數(shù)和圖靈機理論，判定問題的重要成果等?，F(xiàn)代時期各種非經(jīng)典邏輯演算模型論、集合論、遞歸論和證明論。第六頁，共六十二頁，2022年，8月28日史前時期古代希臘最偉大的哲學(xué)家，古典形式邏輯的創(chuàng)始人；在命題中引進了主謂項的變元，建立了三段論的理論；在邏輯史上第一次應(yīng)用了形式化、公理化的的演繹系統(tǒng)，開創(chuàng)了邏輯的形式化研究；構(gòu)造了模態(tài)三段論系統(tǒng)，開創(chuàng)了模態(tài)邏輯的研究；在《工具論》中，總結(jié)了正確的推理方法，建立了形式邏輯；在《分析篇》提出公理學(xué)理論的基礎(chǔ)。亞里土多德(Aristotle，公元前384—322)第七頁，共六十二頁，2022年，8月28日史前時期斯多阿學(xué)派的命題邏輯古希臘的一個哲學(xué)學(xué)派創(chuàng)造了命題邏輯，用形式化和公理化的方法第一次構(gòu)造了一個命題邏輯系統(tǒng)，給出5種公理化基本推理圖式。斐洛(Philo)第一個提出了相當(dāng)于現(xiàn)代命題演算中實質(zhì)蘊涵的真值表。歐布理得發(fā)現(xiàn)了說謊者悖論：一個說謊的人說“我正在說謊”；他是在說謊，還是說真話?這一悖論現(xiàn)在歸屬于語義悖論。中世紀的形式邏輯中世紀邏輯學(xué)家總共陳述了60多條推論原理第八頁，共六十二頁，2022年，8月28日傳統(tǒng)邏輯傳統(tǒng)邏輯主要是指亞里士多德邏輯經(jīng)過中世紀的演變一直沿用到十九世紀;在中世紀被認為金科玉律、完美元缺;到了十九世紀，它的缺點突出，急需改革。傳統(tǒng)邏輯主要缺點：傳統(tǒng)邏輯所討論的子句僅限于主賓式語句，分成四種：全稱肯定A：Asp，凡s均為p；全稱否定E，Esp，凡s均非p；特稱肯定I，Isp，有的s為p；特稱否定O，Osp；有的s非p。限于三段論。沒有關(guān)于量詞的研究，沒有“變元”的概念。第九頁，共六十二頁，2022年，8月28日初創(chuàng)時期德國哲學(xué)家和數(shù)學(xué)家，17世紀末創(chuàng)建了數(shù)理邏輯。建立一種理想的“通用語言”進行推理。他曾經(jīng)給一位友人的信上寫道：“要是我少受攪擾，或者要是我更年青些，或有一些年青人來幫助我，我將作出一種“通用代數(shù)”(在其中，一切推理的正確性將化歸于計算．它同時又將是通用語言，但卻和目前現(xiàn)有的一切語言完全不同；其中的字母和字將由推理來確定，除卻事實的錯誤以外；所有的錯誤將只由于計算失誤而來。要創(chuàng)作或發(fā)明這種語言或字母將是困難的，但要學(xué)習(xí)它，即使不用字典，也是很容易的?！比R布尼茨(Leibniz，1646—1716)第十頁，共六十二頁，2022年，8月28日初創(chuàng)時期萊布尼茨預(yù)創(chuàng)造兩種工具，其一是通用語言使用簡單明了的符號；合理的語言規(guī)則；便于邏輯分析和綜合。另一種是推理演算它將處理通用語言；規(guī)定符號的演變規(guī)則、運算規(guī)則；使得邏輯的演算進行機械式計算。萊布尼茨的思想是用代數(shù)方法處理古典形式邏輯的推理，延續(xù)了大約二百年。第十一頁，共六十二頁，2022年，8月28日初創(chuàng)時期德.摩根—關(guān)系邏輯19世紀英國數(shù)學(xué)家和邏輯學(xué)家，生于印度；1838年提出“數(shù)學(xué)歸納法”的概念；首先提出“論域”的概念，第一次明確用公式表達合取和析取的關(guān)系，稱為德摩根律；主張判斷擴充為一般的關(guān)系語句，明確主張發(fā)展關(guān)系邏輯，邏輯代數(shù)的創(chuàng)始人之一。DeMorgan1806-1871第十二頁，共六十二頁，2022年，8月28日初創(chuàng)時期布爾—英國數(shù)學(xué)家1847年，發(fā)表了《邏輯的數(shù)學(xué)分析，論演繹推理演算》，1854年出版了《思維法則的探討，作為邏輯與概率的數(shù)學(xué)理論的基礎(chǔ)》建立了“布爾代數(shù)”，并創(chuàng)造一套符號系統(tǒng)，利用符號來表示邏輯中的各種概念，這是一種新的邏輯。建立了一系列的運算法則，利用代數(shù)的方法研究邏輯問題，初步奠定了數(shù)理邏輯的基礎(chǔ)。GeorgeBoole1815-1864第十三頁，共六十二頁，2022年，8月28日初創(chuàng)時期耶芳斯使用相等記號來表示命題中的系詞布爾代數(shù)引入相容的或運算。文恩（英國邏輯學(xué)家）用圖解法表示布爾代數(shù)1881年提出符號邏輯麥柯爾(H．McColl)用字母及字母的組合表示整個命題；沿用流行的符號把“A或B”，“A且B“非A”表為A+B，AB，A’；引入了A蘊涵B的概念，表示為A:B。StanleyJevons1835-1882JohnVenn1834-1923第十四頁，共六十二頁，2022年，8月28日初創(chuàng)時期CharlesS.Peirce（1839-1914）皮爾斯1885年獨立地引進了量詞這個名稱，以及存在量詞∑x和全稱量詞∏x兩個符號。命題代數(shù)或命題演算．“既非…，又非”作為邏輯作為初始運算。在邏輯史上第一次全面、系統(tǒng)地建立了關(guān)系演算。皮爾斯和弗雷格都明確指出命題只有真假二值，命題的研究實質(zhì)上是真假值的研究。第十五頁，共六十二頁，2022年，8月28日奠基時期德國人，數(shù)學(xué)家，邏輯學(xué)家，哲學(xué)家1879年的《表意符號》引入和使用量詞與約束變元。1879年出版著作《概念文字：一種模仿算術(shù)語言構(gòu)造的純思維的形式語言》；第一次把謂詞演算形式化,完備地發(fā)展了命題演算和謂詞演算；歷史上第一個嚴格的關(guān)于邏輯規(guī)律的公理系統(tǒng)；這個系統(tǒng)共有三個基本概念：蘊涵、否定和全稱量詞，共有九條公理。第一個引入了符號’├’；接近于完成數(shù)理邏輯整個基礎(chǔ)，標志著數(shù)理邏輯的發(fā)展由創(chuàng)建時期進入奠基時期。弗雷格GottlobFrege1848-1925第十六頁，共六十二頁，2022年，8月28日奠基時期1899年意大利數(shù)理邏輯學(xué)家；提出了自然數(shù)算術(shù)的一個公理系統(tǒng)1894年出版《數(shù)學(xué)公式》，邏輯符號體系沿用至今；用邏輯演算表述數(shù)學(xué)、推導(dǎo)數(shù)學(xué)；區(qū)分集合論中的“屬于”關(guān)系和包含關(guān)系；關(guān)于自然數(shù)論的五個公理一直沿用到現(xiàn)在，成為自然數(shù)論的出發(fā)點。皮亞諾GiuseppePeano1858-1932第十七頁，共六十二頁，2022年，8月28日奠基時期羅素(B.Russell)，英國邏輯學(xué)家，哲學(xué)家；繼承皮亞諾的研究，完備了命題演算和謂詞演算的成果；以集合論為基礎(chǔ)，給出了自然數(shù)定義，證明了自然數(shù)滿足皮亞諾的五個公理；羅素總結(jié)了數(shù)理邏輯的成果，和懷特海合著了《數(shù)學(xué)原理》，他的成果匯集成為一本巨著，奠定了數(shù)理邏輯的基礎(chǔ)。BertrandRussell1872-1970第十八頁，共六十二頁，2022年，8月28日數(shù)學(xué)三次大危機數(shù)學(xué)曾發(fā)生三次大危機，它使數(shù)學(xué)基礎(chǔ)問題發(fā)生三次大爭論。第一次是古希臘時代無理數(shù)的發(fā)現(xiàn)畢達格拉斯學(xué)派以“只有可通約量”為信念。為了解釋無理數(shù)的存在，處理無理數(shù)，古希臘人發(fā)展了比例論，從而建立幾何公理系統(tǒng)。第二次是十七、八世紀關(guān)于微積分基礎(chǔ)的爭論，即關(guān)于無窮小的爭論，它一直延續(xù)到十九世紀，結(jié)果得出了極限論以及無理數(shù)的算術(shù)理論。第三次是集合論悖論的出現(xiàn)，從而導(dǎo)致數(shù)理邏輯的蓬勃發(fā)展。Pythagoras,572BC～497BC),古希臘第十九頁，共六十二頁，2022年，8月28日第一次數(shù)學(xué)危機歐幾里德，古希臘數(shù)學(xué)家；《幾何原本》是一個實質(zhì)公理系統(tǒng)，把點、線、面、角等分為原始定義概念（23）和可定義概念，把命題分為公設(shè)（5）、公理（5）和可由公理公設(shè)出發(fā)加以證明的定理（467）。從簡單到復(fù)雜，證明相當(dāng)嚴格。從而建立了歐幾里得幾何學(xué)的第一個公理化數(shù)學(xué)體系。在《幾何原本》所給的公理公設(shè)中，第五公設(shè)是關(guān)于平行線的，通常叫做平行公理。5．(平行公設(shè))若一直線與兩直線相交，且若同側(cè)所交兩內(nèi)角之和小于兩直角，則兩直線無限延長后必相交于該側(cè)的一點。EuclidofAlexandria325BC-265BC第二十頁，共六十二頁，2022年，8月28日無窮的大小1638年伽利略(Galileo){1，2，3，4，….}{1,4,9,16,……}伽利略(1564-1642)第二十一頁，共六十二頁，2022年，8月28日第二次數(shù)學(xué)危機牛頓和萊布尼茨提出微積分，計算非等速運動、不均勻密度的物體等物理現(xiàn)象引發(fā)微積分的基礎(chǔ)問題爭論達一百多年。極限論的說法中，有一條性質(zhì)，即“有界單調(diào)的數(shù)列必有極限”，是一切其它性質(zhì)的基礎(chǔ)，別的性質(zhì)都可由它推出。但這條性質(zhì)又從何推出呢?長期以來，人們以為可以由幾何性質(zhì)推出．但幾何公理中，根本末討論到連續(xù)的性質(zhì)，更未討論到極限。IsaacNewton1643-1727第二十二頁，共六十二頁，2022年，8月28日Augustin-LouisCauchy（1789–1857）柯西用“ε-δ”的數(shù)學(xué)形式對極限、收斂給出了嚴格的定義。第二十三頁，共六十二頁，2022年，8月28日魏爾斯特拉斯KarlTheodorWilhelmWeierstrass（1815–1897）19世紀下半葉，維爾斯特拉斯、戴德金、康托爾等數(shù)學(xué)家分別給實數(shù)作出了算術(shù)形式定義之后，實數(shù)理論建立在集合論基礎(chǔ)之上。第二十四頁，共六十二頁，2022年，8月28日非歐幾何18世紀初意大利數(shù)學(xué)家薩克利，用反證法，假設(shè)歐氏幾何五公設(shè)的否定命題，結(jié)果推出了一系列命題，始終沒有得到矛盾。俄國數(shù)學(xué)家羅巴切夫斯基發(fā)現(xiàn)了銳角非歐幾何。從直線外一點，至少可以做兩條直線和這條直線平行。1854年黎曼發(fā)現(xiàn)了鈍角非歐幾何。在同一平面內(nèi)任何兩條直線都有交點。第二十五頁，共六十二頁，2022年，8月28日非歐幾何1570年，德國數(shù)學(xué)家克萊因用微分幾何和射影幾何的研究成果，使非歐幾何在歐氏幾何中得到解釋。19世紀末，希爾伯特給出了簡單而完全的由二十條公理組成的公理系統(tǒng)幾何基礎(chǔ)，并在實數(shù)算術(shù)理論中為歐氏幾何建立了一個模型。第二十六頁，共六十二頁，2022年，8月28日幾何相容性非歐幾何相容性證明只能證明其相對相容性——相對于歐氏幾何的相容性，并不能證明非歐幾何的(絕對)相容性(即不矛盾性)；如果歐氏幾何沒有矛盾，那末非歐幾何亦沒有矛盾。歐氏幾何相容性證明借助于解析幾何，一切幾何命題都可以表示為代數(shù)(實數(shù)論上的）命題。如果歐氏幾何出現(xiàn)矛盾，那末表述為代數(shù)命題以后，也將得出兩條互相矛盾的（實數(shù)的)代數(shù)定理，即實數(shù)的代數(shù)也就出現(xiàn)矛盾了。歐氏幾何相對于(實數(shù))代數(shù)的相容性。第二十七頁，共六十二頁，2022年，8月28日集合論創(chuàng)立康托爾創(chuàng)立了一門嶄新的學(xué)科—集合論，亦稱為古典集合論或素撲集合論。外延原則與概括原則外延原則：一個集合由它的元素唯一地確定。概括原則：每一性質(zhì)(或謂詞)產(chǎn)生一個集合?？低袪柕谝淮慰茖W(xué)地應(yīng)用了“一一對應(yīng)”的概念來把握無窮集合的本質(zhì)?？低袪栍谩耙灰粚?yīng)”的概念解決了伽利略的“部分等于全體”的怪論，揭示了無窮集合的本質(zhì)以及無窮與有窮的本質(zhì)差別。康托爾的成果是人們對無窮集合認識道路上的第一塊里程碑。具有偉大歷史意義的證明：關(guān)于有理數(shù)集可數(shù)性的證明關(guān)于代數(shù)數(shù)可數(shù)的證明關(guān)于實數(shù)集不可數(shù)的證明康托爾創(chuàng)立的集合論是數(shù)學(xué)和數(shù)理邏輯發(fā)展史上的驚天動地的偉業(yè)，開辟了嶄新的數(shù)學(xué)領(lǐng)域，為數(shù)學(xué)奠定了初步基礎(chǔ)。GeorgCantor1845-1918第二十八頁，共六十二頁，2022年，8月28日相容性—實數(shù)、自然數(shù)、集合論狄德金(R.Dedekind)把實數(shù)定義為有理數(shù)的分劃，實質(zhì)上是有理數(shù)的(無窮)集合，也是自然數(shù)的(無窮)集合?？低?G.Cantor)則把實數(shù)定義為正規(guī)有理數(shù)無窮數(shù)列，實質(zhì)上仍可以化歸于自然數(shù)的(無窮)集合。實數(shù)論上的命題既可表示成自然數(shù)的集合的命題，如果實數(shù)論出現(xiàn)矛盾，勢必在自然數(shù)論和集合論上出現(xiàn)矛盾。實數(shù)論的相對相容性—相對于自然數(shù)論。弗雷格和狄德金等利用集合的概念而定義自然數(shù)，自然數(shù)論的相對相容性—相對于集合論的相容性便得到了證明。集合論的相容性又占著中心的、關(guān)鍵性的位置，是整個數(shù)學(xué)相容性的支柱。RichardDedekind1831-1916第二十九頁，共六十二頁，2022年，8月28日彭加勒宣言—數(shù)學(xué)成就1900年在巴黎召開的數(shù)學(xué)大會上，大數(shù)學(xué)家彭加勒(H.Poincare)宣稱“現(xiàn)在我們可以說，數(shù)學(xué)完全的嚴格性已經(jīng)達到了?！盚enriPoincaré1854-1912第三十頁，共六十二頁，2022年，8月28日羅素悖論集合論既占這么重要的位置，那么集合論具有相容性嗎？集合悖論：集合論是自相矛盾的，沒有相容性的！羅素悖論(1902)—“理發(fā)師悖論”某鄉(xiāng)村有一位理發(fā)師，有一天他宣布：只給不自己刮胡子的人刮胡子。那么就產(chǎn)生了一個問題：理發(fā)師究竟給不給自己刮胡子？如果他給自己刮胡子，他就是自己刮胡子的人，按照他的原則，他又不該給自己刮胡子；如果他不給自己刮胡子，那么他就是不自己刮胡子的人，按照他的原則，他又應(yīng)該給自己刮胡子。這就產(chǎn)生了矛盾。羅素悖論概念簡單，無法質(zhì)疑第三十一頁，共六十二頁，2022年，8月28日集合論的悖論經(jīng)典悖論布拉里—福蒂悖論（Borali-Forti1897）:最大序數(shù)的悖論康托爾悖論：最大基數(shù)的悖論（1899）、羅素悖論（1903）關(guān)系悖論語義悖論古希臘-歐布理得的說謊者悖論羅素把各種悖論加以分析歸納以后，認為“一切悖論……都有一個公共特征，即自己引證自己，或自反性”

第三十二頁，共六十二頁，2022年，8月28日公理集合論的建立在1908年，策梅羅發(fā)表論文《集合論基礎(chǔ)研究》，這標志著公理集合論的建立。外延性公理、初等集合公理、分離公理、冪集公理、并集公理、選擇公理l922年8月，著名的挪威數(shù)學(xué)家斯科倫(T.Skolem）在第五屆斯堪的納維亞數(shù)學(xué)家大會上發(fā)表了《對公理集合論的一些評論》的講演。他首先提到數(shù)理邏輯的五種運算(采用了施羅德的記法)合取、析取、否定、全稱量詞、存在量詞策梅羅一弗蘭克爾系統(tǒng)記為ZF系統(tǒng)外延性公理、無序?qū)怼⒖占怼⑻鎿Q公理模式、分離公理模式、冪集公理、并集公理、無窮公理、正則公理ZFC系統(tǒng)ZF系統(tǒng)+選擇公理。第三十三頁，共六十二頁，2022年，8月28日集合公理系統(tǒng)弗蘭克爾AdolfAbrahamHaleviFraenkel1891–1965策梅羅ErnstFriedrichFerdinandZermelo1871-1953第三十四頁，共六十二頁，2022年，8月28日公理集合論的建立在1923-1929年間，馮·諾意曼連續(xù)發(fā)表了6篇集合論論文。這些論文在公理集合論的發(fā)展史上具有重要意義。提出了一種新的序數(shù)理論論證了超窮歸納法的定義推廣了策梅羅和弗蘭克爾的集合論，構(gòu)造了一個新的公理集合論系統(tǒng)，并討論了相對一致性的問題。JohnvonNeumann1903-1957第三十五頁，共六十二頁，2022年，8月28日代數(shù)學(xué)公理化19世紀30年代，伽羅瓦給出了群的概念。群是滿足幾條運算規(guī)律的一個抽象系統(tǒng)，它概括了向量、矩陣、變換等研究對象。群的研究來源于高次方程求解的問題，但群的出現(xiàn)，導(dǎo)致了現(xiàn)代群論，環(huán)論，域論，交換代數(shù)，李代數(shù)以致同調(diào)代數(shù)，代數(shù)幾何等等公理化代數(shù)系統(tǒng)的驚人發(fā)展，在理論和實踐兩方面部取得了極豐富的成果。第三十六頁，共六十二頁，2022年，8月28日數(shù)理邏輯的三大流派以羅素為代表的邏輯主義派數(shù)學(xué)即邏輯，兩者之間沒有分界線?！稊?shù)學(xué)原理》羅素推演，以表明怎樣一步一步地從邏輯而過渡到數(shù)學(xué)；缺乏二公理：無窮公理和選擇公理。從邏輯過渡到數(shù)學(xué)時，必須發(fā)展集合論。以希爾柏特為代表的形式主義派數(shù)學(xué)的真理性體現(xiàn)在什么地方?邏輯規(guī)律的真理性以布魯維(L.E.J.Brouwer)為代表的直覺主義派強調(diào)能行性，因而對任何無窮集合都不認為是構(gòu)造完成的，而是在構(gòu)造中的。討論范圍限于數(shù)學(xué)命題：一命題真是指已證明其真，一命題假是指證明它為假，亦即當(dāng)假設(shè)它為真時可導(dǎo)致矛盾，因此反證法是可以用的，但只限于用以證明否定命題。排中律斷定每個命題或真或假，兩者必居其一．直覺主義不承認排中律第三十七頁，共六十二頁，2022年，8月28日形式公理與證明論希爾柏特（D.Hilbert）規(guī)劃直接證明數(shù)學(xué)理論的相容性數(shù)學(xué)理論徹底公理化一一規(guī)定數(shù)學(xué)基本概念一一列出基本概念的基本性質(zhì)(作為公理)，一一列出邏輯概念(如命題聯(lián)結(jié)詞和量詞等)一一列出邏輯概念的基本性質(zhì)(所謂邏輯法則)數(shù)學(xué)上的推導(dǎo)不但不必再依靠空間關(guān)系、不必再依靠直覺，而且不必再依靠邏輯法則，可以純粹機械地推演。每步推演表現(xiàn)為由某個邏輯式子變成另一個邏輯式子，逐步演算，便能夠由公理出發(fā)，最后達到定理．即數(shù)學(xué)的推演表現(xiàn)為一系列邏輯式子的演變。證明論的數(shù)學(xué)基礎(chǔ)是形式公理學(xué)證明數(shù)學(xué)理論的相容性，那便等于要求證明，在數(shù)學(xué)的推導(dǎo)中，只要從公理出發(fā)，絕不可能導(dǎo)出兩個互相反對的矛盾命題。希爾伯特l899年的《幾何基礎(chǔ)》是形式公理學(xué)的奠基著作，它不但給出了歐氏幾何的一個形式公理系統(tǒng)，而叢具體地解決了公理方法的一些邏輯理論問題。DavidHilbert1826-1943第三十八頁，共六十二頁，2022年，8月28日直覺主義邏輯LuitzenEgbertusJanBrouwer1881–1966布魯維第三十九頁，共六十二頁，2022年，8月28日塔爾斯基的語義學(xué)在1931年，塔斯基(ATarski)發(fā)表了論文《形式語言中真概念》,提出了形式系統(tǒng)真理論，開拓了邏輯語義學(xué)這一重要領(lǐng)域；塔爾斯基以現(xiàn)代邏輯為手段，用邏輯分析和語義分析的方法，給出了“真”概念實質(zhì)上適當(dāng)、形式上正確的定義；提出了著名的語言層次論，創(chuàng)建了現(xiàn)代意義上的系統(tǒng)的語義學(xué)；1954年，塔斯基建立了模型論；塔爾斯基證明不可判定性的一般方法。AlfredTarski1902-1983第四十頁，共六十二頁，2022年，8月28日哥德爾1931年發(fā)表了一篇論文《關(guān)于數(shù)學(xué)原理》一書，證明數(shù)理邏輯的不完全定理。在數(shù)理邏輯發(fā)展史上具有劃時代意義。哥德爾完全性定理哥德爾不完全性定理KurtG?del's1906-1978第四十一頁，共六十二頁，2022年，8月28日哥德爾定理哥德爾利用一種所謂原始遞歸函數(shù)的工具所使用的符號與式子對應(yīng)于自然數(shù)；推理過程，即式子到式子的變換，則對應(yīng)于原始遞歸函數(shù)(它是數(shù)到數(shù)的變換）；性質(zhì)能夠在自然數(shù)中反映出來，元定理也都可以表示為自然數(shù)論的定理。哥德爾不完全性定理如果公理包括有自然數(shù)理論為其一部分，那末可以找到一個式子A，使將只要該理論是不矛盾的，那末這個式子A及其否定(非A)都不能在該理論中推出。這個A便是所謂形式不可判定的語句。上述表明希爾伯特規(guī)劃不可能實現(xiàn)。第四十二頁，共六十二頁，2022年，8月28日StephenColeKleene1909-1994哥德爾-克林尼提出一般遞歸函數(shù)第四十三頁，共六十二頁，2022年，8月28日能行可計算性理論一般遞歸函數(shù)艾爾伯朗—哥德爾—克林哥德爾大量使用了原始遞歸函數(shù)。原始巡歸函數(shù)是能行可計算的證明論1936，堅欽(G.Gentzen)引用了一種超窮歸納法而證明了不加限制的自然數(shù)論的相容性。把整個理論、整個系統(tǒng)作為研究對象。模型論主要是對各種數(shù)學(xué)理論系統(tǒng)建立模型，研究各模型之間的關(guān)系、模型與數(shù)學(xué)系統(tǒng)之間的關(guān)系等等。Gerhard.Gentzen1909-1945第四十四頁，共六十二頁，2022年，8月28日能行可計算的函數(shù)一般遞歸函數(shù)作出一個形式系統(tǒng)，在其中利用代入及替換兩個極有力的運算而能夠計算該函數(shù)的值的，這個函數(shù)便叫做一船遞歸函數(shù)．圖靈機（）λ演算（A.Church）函數(shù)、自變量、替換規(guī)則Church理論能行可計算的函數(shù)與一般遞歸函數(shù)、圖靈機、λ演算相同波斯特的符號處理系統(tǒng)AlonsoChurch1903-1995第四十五頁，共六十二頁，2022年，8月28日ThoralfAlbertSkolem1887-1963斯科倫在1921年，波斯特證明了命題演算完全性第四十六頁，共六十二頁，2022年，8月28日計算機理論基礎(chǔ)圖靈機和可計算函數(shù)1936年，圖靈24歲時發(fā)表一篇論文《論數(shù)字計算在判決難題中的應(yīng)用》，提出著名的“圖靈機”的設(shè)想。這一思想奠定了現(xiàn)代計算機的基礎(chǔ)。美國計算機協(xié)會在圖靈去世12年后以他的名字命名了計算機領(lǐng)域的最高獎“圖靈獎”。艾倫·圖靈（1912－1954）第四十七頁，共六十二頁，2022年，8月28日數(shù)理邏輯的主要內(nèi)容數(shù)理邏輯可分成五大部分邏輯演算公理集合論證明論遞歸函數(shù)論模型論公理集合論、證明論、遞歸函數(shù)論和模型論都以邏輯演算(命題演算和謂調(diào)演算)為基礎(chǔ)。第四十八頁，共六十二頁，2022年，8月28日為什么學(xué)習(xí)數(shù)理邏輯？理論基礎(chǔ)集合論、圖論、代數(shù)系統(tǒng)、形式語言與自動機理論硬件基礎(chǔ)數(shù)字邏輯、計算機組成原理軟件基礎(chǔ)軟件證明、軟件驗證理論基礎(chǔ)、硬件基礎(chǔ)和軟件基礎(chǔ)能否用數(shù)理邏輯方法建立？第四十九頁，共六十二頁，2022年，8月28日理論基礎(chǔ)—集合論策梅羅一弗蘭克爾系統(tǒng)記為ZF系統(tǒng)外延性公理、無序?qū)?、空集公理、替換公理模式、分離公理模式、冪集公理、并集公理、無窮公理、正則公理ZFC系統(tǒng)ZF系統(tǒng)+選擇公理。第五十頁，共六十二頁，2022年，8月28日理論基礎(chǔ)—圖論G=<V,E>其中，V是頂點集合，E是邊的集合。第五十一頁，共六十二頁，2022年，8月28日理論基礎(chǔ)—群論（專用公理）設(shè)G是一個非空集合，°是它的—個代數(shù)運算，如果滿足以下條件：結(jié)合律：xyz((x°y)°z=x°(y°z))左單位元：x((x°e=x)(e°x=x))左逆元：xy((x°y=e)(y°x=e))則稱G對代數(shù)運算，作成一個群。第五十二頁，共六十二頁，2022年，8月28日理論基礎(chǔ)—形式語言與自動機理論形式文法喬姆斯基文法形式語言正則語言上下文無關(guān)語言上下文有關(guān)語言自動機理論有窮自動機下推自動機圖靈機第五十三頁，共六十二頁，2022年，8月28日硬件基礎(chǔ)數(shù)理邏輯建立邏輯描述的方法和能力，包括布爾邏輯及其變換、真值表的邏輯表示以及邏輯范式表示數(shù)字邏輯與數(shù)字部件設(shè)計數(shù)理邏輯是組合邏輯與時序邏輯原理基礎(chǔ)基于MIPS指令集，設(shè)計寄存器、加法器、移位器、控制器、多路選擇器、計數(shù)器、比較器計算機組成原理基于MIPS指令集，指令周期、數(shù)據(jù)通路、系統(tǒng)控制在部件設(shè)計基礎(chǔ)上，實現(xiàn)計算機硬件系統(tǒng)設(shè)計第五十四頁，共六十二頁，2022年，8月28日110110001110110110110111Y0Y1Y2Y3ABY0=ABY1=ABY2=ABY3=ABBAY3Y2Y1Y0數(shù)字邏