1、數理邏輯Mathematical Logic 王書元 講師e-mail: wsy_生物數學教研室（外語學館411）緒 論課程之間的聯系 離散數學是計算機科學的核心基礎課程，它以離散量為研究對象；而數學分析（微積分）以連續函數為主要研究對象，屬于連續型數學。 離散數學在各學科領域，特別在計算機科學與技術領域有著廣泛的應用，同時離散數學的理論、方法直接為數據結構、操作系統、編譯原理、人工智能、程序設計等課程服務。課程之間的聯系離散數學數理邏輯集合論圖論代數結構組合數學課程之間的聯系什么是數理邏輯？ 邏輯通常指人們思考問題，從某些已知條件出發推出合理的結論的規律。 邏輯學是一門研究思維形式及思維規律

2、的科學。以推理形式為主要研究對象。現代的邏輯學與數學有非常密切的關系。邏輯學現代邏輯古典邏輯傳統邏輯數理邏輯什么是數理邏輯？傳統邏輯的局限：1. 討論范圍限于主賓式語句，即“S是P” 式的語句。2. 對量詞的研究非常有限，只能得出量 詞的一些次要性質。3. 表達形式停留在自然語言上，沒有專 門的邏輯符號來處理各類思維形式， 所以不夠精確。什么是數理邏輯？數理邏輯就是采用數學的方法來研究思維形式的邏輯結構及其規律的一門科學。所謂數學的方法就是用一套符號（即人工符號語言）的方法。什么是數理邏輯？數理邏輯與傳統邏輯的區別：1. 使用一整套符號語言，從而簡化了推理形式。2. 借助人工符號語言，使整個推

3、理形式化。3. 具有系統性。什么是數理邏輯？數理邏輯的歷史 數理邏輯的創始人是17世紀德國數學家和哲學家萊布尼茲，他把數學引入形式邏輯。1847年布爾實現了命題演算，1879年弗雷格建立了第一個謂詞演算系統。對建立這門學科做出貢獻的，還有美國人皮爾斯，他也在著作中引入了邏輯符號。從而使現代數理邏輯最基本的理論基礎逐步形成，成為一門獨立的學科。人物簡介n萊布尼茲q（Gottfried Wilhelm Leibniz，1646年7月1日1716年11月14日）德意志哲學家、數學家，歷史上少見的通才，被譽為17世紀的亞里士多德。q萊布尼茲曾在漢諾威生活和工作了近四十年，為了紀念他和他的學術成就，20

4、06年7月1日，也就是萊布尼茲360周年誕辰之際，漢諾威大學正式改名為漢諾威萊布尼茲大學。人物簡介q1646年7月1日萊布尼茲出生于神圣羅馬帝國的萊比錫。q他的著書約四成為拉丁文、約三成為法文、約一成五為德文。q現今在微積分領域使用的符號仍是萊布尼茲所提出的。在高等數學和數學分析領域，萊布尼茲判別法是用來判別交錯級數的收斂性的。q拓撲學、符號思維、單子論、數理邏輯。q1716年11月14日萊布尼茲于漢諾威孤獨地過世。直到去世前幾個月，才寫完一份關于中國人宗教思想的手稿：論中國人的自然神學。學習數理邏輯要達到的目的首先，培養嚴謹的邏輯推理能力。其次，培養抽象思維能力。再者，培養解決實際問題的能力

5、。本課程主要內容第一章 邏輯、集合和函數命題邏輯命題邏輯、謂詞邏輯謂詞邏輯、邏輯等價邏輯等價、集合、集合運算、函數、函數增長函數增長等第二章 算法、整數和矩陣算法算法、搜索算法搜索算法、算法的復雜性算法的復雜性、整數和除法（素數、最大公約數、最小公倍數、模運算等）、整數和算法、矩陣第三章 數學推理證明方法證明方法、數學歸納法數學歸納法、遞歸算法遞歸算法等第四章 關系關系及其性質關系及其性質、n元關系及應用元關系及應用、關系的表示關系的表示數理邏輯Mathematical Logic 第一章 邏輯、集合和函數Chapter 1 Logic、set and function邏輯：是所有數學推理的基

6、礎，邏輯規則給出數學語句的準確含義。集合：所有離散結構都從集合構造而來。如，表示對象之間相互關聯的關系（有序偶的集合），圖（頂點的集合、邊的集合）等。函數：離散數學中特別重要的概念。如，函數增長、遞歸函數等。1.1 命題邏輯Propositional Logic命題是一個非真即假（不可兼）的陳述句。 一、命題命題是一個陳述句，祈使句、疑問句和感嘆句都不是命題。所表述的內容可決定是真還是假，不能不真又不假，也不能又真又假。 具有兩種可能的取值（又稱真值），為真或為假，并且只能取其一。 通常用T（True）表示真值為真，用F（False）表示真值為假，有時也用1和0來表示。 因為只有兩種取值，所以

7、這樣的命題邏輯稱為二值邏輯。 一、命題下列語句哪些是命題：華盛頓是美國的首都。1+1=3。好大的雪啊！雪是白的。我學英語，或者我學日語。 一、命題下列語句哪些是命題：幾點了？如果劉翔腳沒傷，那么他能在奧運會上打破世界紀錄。全體起立！ x+1=3. 一、命題下列語句哪些是命題：今天是星期一。嚴格地說，含有可變時間、地點、人物的語句不是命題，除非假定了一個確定的時間、地點、人物。 一、命題命題表示法：命題常用字母表示，就像用字母表示變量那樣。習慣上用來表示命題的字母是p、q、r、s 一、命題簡單命題和復合命題：簡單命題又稱原子命題，不能分解成更簡單的命題。如，今天是星期一并且有數理邏輯課。可分解為

8、：今天是星期一。今天有數理邏輯課。復合命題又稱分子命題，由原子命題用邏輯運算符組合起來的命題。 一、命題邏輯運算符也稱為聯結詞，它是復合命題中的重要組成部分，體現了復合命題中各個原子命題之間的運算關系，為了便于書寫和推演，必須對聯結詞做出明確的規定并符號化。二、命題聯結詞及真值表否定（定義）：令p為一命題，則語句“不是p所說的情形。”是另一個命題，稱為p的否定。用p表示，讀作“非p”。二、命題聯結詞及真值表否定（例題）：p：今天是星期一。p：今天不是星期一。不能說今天星期二、星期三等。p：昨天張三看球賽了。p：昨天張三沒有去看球賽。二、命題聯結詞及真值表否定（真值表）：ppTFFT二、命題聯結

9、詞及真值表合取（定義）：令p和q為命題，用pq表示的命題“p而且q”是這樣的一個命題：當p和q均為真時它成真，否則為假。命題pq稱為p和q的合取。二、命題聯結詞及真值表合取（例題）：p：今天是星期一。q：今天有數理邏輯課。pq：今天是星期一并且有數理邏輯課。p：1+1=2。 q：雪是白的。pq：1+1=2并且雪是白的。邏輯語言中僅考慮命題與命題之間的形式關系，并不顧及自然語言中是否有此說法。二、命題聯結詞及真值表合取（真值表）：pqpqTTTTFFFTFFFF二、命題聯結詞及真值表析取（定義）：令p和q為命題，用pq表示的命題“p或q”是這樣的一個命題：它的真值在p和q均為假時為假，否則成真。

10、命題pq稱為p和q的析取。二、命題聯結詞及真值表析取（例題）：選修過微積分或計算機科學的學生可以選修本課程。同或 異或他現在在301房間或302房間。二、命題聯結詞及真值表析取（真值表）：pqpqTTTTFTFTTFFF二、命題聯結詞及真值表異或（定義）：令p和q為命題，p和q的異或，用 表示，是這樣的一個命題：當p和q中恰有一個成真時它成真，否則它為假。pq二、命題聯結詞及真值表異或（真值表）：pqTTFTFTFTTFFFpq二、命題聯結詞及真值表蘊含（定義）：令p和q為命題，蘊含pq是這樣一個命題：在p成真而q為假時它為假，否則成真。其中p稱為假設（前項、前提），q稱為結論（或后果）。二、

11、命題聯結詞及真值表蘊含（例題）：p：n3（n是整數）。q：n29。pq：如果n3，那么n29。p：劉翔的腳沒有受傷。q：劉翔在奧運會上打破了世界紀錄。pq：如果劉翔的腳沒有受傷，那么劉翔在奧運會上打破了世界紀錄。二、命題聯結詞及真值表蘊含（真值表）：pqpqTTTTFFFTTFFT二、命題聯結詞及真值表蘊含（術語）：“如果p，那么q”“p是q的充分條件”“ p蘊含q” “q如果p”“如果p，q” “q每當p”“p僅當q” “q是p的必要條件”二、命題聯結詞及真值表蘊含：逆蘊含：命題qp稱為pq的逆蘊含。逆否命題（倒置命題）： pq的逆否命題是命題qp二、命題聯結詞及真值表雙蘊含（定義）：令p和q為命題，雙蘊含 是這樣一個命題：其真值只有在p和q有同樣真值時為真，否則為假。雙蘊含恰在pq和qp均為真時為真。pq二、命題聯結詞及真值表雙蘊含：“p當且僅當q”“p是q的充分必要條件”“如果p，那么q；反之亦然。”二、命題聯結詞及真值表雙蘊含（真值表）：pqTTTTFFFTFFFTpq二、命題聯結詞及真值表運算順序： 、 pq(p)q二、