離散數學基礎（簡體書）

前 言

離散數學(discretemathematics)是以可枚舉(enumerable)的數量或形狀作為研究物件的數學分支。這裡可枚舉的含義是指離散數學研究的物件與物件之間有清晰明確的界限，從而可以一一羅列出來，或者用數學語言說，可枚舉的物件與若幹自然數可以有一一對應的關係。當前現有的計算機只能處理可枚舉的信息，因此離散數學在計算機科學中有著廣泛的應用。

“離散數學基礎”課程是計算機專業學生的核心基礎課程，提供包括邏輯(logic)、集合(set)、算法(algorithm)、圖論(graphtheory)和代數(algebra)在內的數學語言描述可枚舉的數學物件，使得人們在利用計算機求解問題時可建立合適的數學模型並對其進行分析。

編寫新工科建設背景下計算機專業的離散數學教材，應注重離散數學在利用計算機求解問題時的應用。建立離散模型通常是利用計算機求解問題的第一步。因此，我們認為“離散數學基礎”課程的核心目標應該是培養學生具備初步的離散建模能力。在這種課程目標的指導下，與傳統的離散數學教材不同，我們力圖將邏輯、集合、算法、圖論和代數的相關知識從離散模型描述語言的角度進行闡述，重點將它們作為表達和交流的工具，基於描述離散模型的需要，討論這些語言的核心詞匯和核心問題。

在這些語言中，邏輯語言主要用於描述模型的性質和約束，其核心詞匯是“命題”和“真值”，核心問題是如何確定命題的真值以及命題之間的真值關係；集合語言用於描述模型的元素與結構，核心詞匯是“集合”“函數”與“關係”，核心問題是如何確定集合的元素以及不同集合之間元素的對應關係；算法語言用於描述模型的行為和實現，核心詞匯是“指令”“輸入”和“輸出”，核心問題是如何利用順序、分支和循環三種結構組合一些基本操作，即基本指令，描述如何從輸入得到期望的輸出；圖論語言可用於可視化地描述模型結構，核心詞匯是“頂點”“邊”和“關聯”，核心問題是滿足條件的頂點、邊或子圖的搜索與構造；代數語言可用於描述模型的結構與約束，核心詞匯是“運算”“代數”和“同態”，核心問題是利用基本運算刻畫代數的性質以及代數之間的關係。

在進行離散數學建模時，人們還運用關係思維、邏輯思維、計算思維、量化思維和遞歸思維等去組織和運用離散數學語言，找到建模的切入點，並使得自己的思考更為周密、嚴謹。關係思維引導人們建模時去分析事物之間的關鍵關係；邏輯思維強調對模型性質與約束應使用嚴謹的邏輯語言表達，並考查模型元素之間的邏輯關係；計算思維強調關注模型的可實現性；量化思維強調關注模型的規模以及模型動態行為的效率；遞歸思維引導人們關注模型在結構或行為方面的自相似性，思考如何將大規模的模型結構或行為歸結為小規模的模型結構或行為。

為構建有利於計算機自動實現的“好”模型，人們在離散建模時應具備離散化、模塊化、層次化、公理化和系統化的計算機專業意識。離散化意識使得人們在建模時思考如何將復雜問題進行分解，並清晰地羅列和枚舉模型的元素、結構、行為和約束；模塊化意識使得人們在建模時思考模型元素間關係的緊密程度，盡量將要考慮的範圍局部化，從而更好地把握住復雜的問題；層次化意識告訴人們在對復雜問題進行分解時應逐步求精和細化，形成不同的抽象層次；公理化意識引導人們在繁雜的模型元素、結構、行為或約束中找到最基本的構件，利用基本的構件和一些通用的規則去構造和描述復雜的模型元素、結構、行為或約束；系統化意識引導人們將模型的元素、結構、行為或約束從某種角度進行系統化思考，形成有機的整體，從而做到不遺漏、不重復，使得模型能在某種程度上全面地刻畫要解決的問題。

本書作為“離散數學基礎”課程的教材，從描述離散數學模型的需要出發，給出有關邏輯語言、集合語言、算法語言、圖論語言和代數語言的基礎知識，培養學生運用這些離散數學語言和包括關係思維、邏輯思維、計算思維、量化思維和遞歸思維在內的思維方式建立離散數學模型的初步能力，並逐步樹立離散化、模塊化、層次化、公理化和系統化的計算機專業意識。本書的核心內容是關於邏輯、集合、算法、圖論和代數5種離散數學語言的基礎知識，引導讀者運用這些離散數學語言表達要利用計算機進行求解的問題。圖1給出了本書章節內容的整體框架結構。

圖1 本書章節內容的整體框架結構

第1 章“基礎知識”介紹有關邏輯語言、集合語言、圖論語言、代數語言和算法語言的基礎知識。這些基礎知識大部分在中學學習中已經接觸過，是對高中數學知識的銜接。這一章介紹這些離散數學語言的基本概念，並盡早地引入集合的歸納定義法、圖的基本概念、代數運算的基本概念以及算法的描述方法和算法的遞歸調用。這些內容在後面的章節中到處出現，是學習後面內容的準備，後面要學習的內容則是這一章內容的拓展與深入。

第2章“命題邏輯”、第3章“一階邏輯”和第4章“證明方法”屬於邏輯語言的深入介紹。邏輯語言使用命題描述事物的性質和事物之間的關係，核心的問題是確定命題的真值以及命題真值之間的關係，包括邏輯等值和邏輯推理關係。第2章學習命題邏輯的基本概念、命題邏輯公式的語法和真值確定、命題邏輯公式的等值演算和基於命題邏輯公式的推理系統。第3章介紹有關一階邏輯的基本概念、一階邏輯公式的語法和真值確定、一階邏輯公式的等值演算和基於一階邏輯公式的推理。第4章介紹基本的證明方法，包括直接證明與間接證明、分情況證明、構造性與非構造性存在證明、數學歸納法、集合的歸納定義與結構歸納法。通過第4章的學習，讀者不僅可熟悉基本的數學證明方法和思路，提高自己的數學證明能力，而且可進一步體會邏輯語言的嚴謹性。

第5章“集合”、第6章“關係”和第7章“函數”屬於集合語言的深入介紹。集合語言是現代數學的基本語言，使用集合、關係、函數等描述所要研究的數學物件以及它們之間的聯系。第5章介紹集合的基本概念、集合運算、集合等式和子集關係證明。第6章介紹關係的基本概念、關係的運算、關係的性質、關係的閉包，以及兩種特殊的關係——等價關係和偏序關係。第7章介紹函數的基本概念、函數的性質和函數的運算，並介紹集合等勢、有窮集和無窮集、可數集和不可數集的基礎知識，討論函數的增長及其在算法效率分析方面的應用和一些關於算法復雜度的基礎知識。

邏輯語言和集合語言是學習組合計數、圖論語言和代數語言的基礎。第8章“計數與組合”介紹基本的組合計數原理、排列與組合、二項式定理及二項式系數恒等式的證明、遞推關係的構建與線性遞推關係式的求解。第2~4章，特別是第4章的證明體現邏輯思維的運用，而第5~7章，特別是第6章的關係和第7章的函數體現關係思維，第8章展示量化思維的運用，不僅討論集合元素的計數，而且進一步討論算法效率的分析，特別是遞歸算法和分治算法的效率分析。

第9 章“圖與樹”對圖論語言做比較深入的介紹，在總結圖和樹的基本概念的基礎上，對圖的連通性、圖的遍歷、樹的遍歷，以及帶權圖的頂點間最短距離、最優二叉樹、圖的最小生成樹等做更多的討論，並對一些特殊的圖，包括平面圖、歐拉圖、哈密頓圖做簡單的介紹。

第10章“代數系統”對代數語言做比較深入的介紹，在定義運算及其性質的基礎上，介紹代數系統的基本概念、代數的構造（子代數、同餘關係和商代數）、代數同態和同構，並介紹代數系統的例子，包括群、格與布爾代數的一些基礎知識。

第11章“結束語”總結全書的內容，介紹可以進一步學習的離散數學相關知識，並給出一些推薦閱讀的參考文獻。

本書沒有單列一章介紹算法的相關內容，但第1章的“基礎知識”有一節專門介紹算法語言的基礎知識，包括算法的基本概念和基本特點，結合例子給出了如何使用結構化自然語言描述算法的順序結構、選擇結構和循環結構，以及算法調用的方法，並盡早引入了遞歸調用和遞歸算法的概念。計算機專業的學生在學習離散數學時應注意思考如何利用計算機輔助求解離散數學的問題，因此算法語言的使用和計算思維、遞歸思維的運用應該貫穿對邏輯、集合、圖論和代數的學習，相關的章節也會給出許多算法的例子。另外，第7章對函數的介紹會討論函數的增長及其在算法效率分析中的應用，第8章的“計數與組合”會介紹遞推關係式及其在算法效率分析中的應用。

不少離散數學教材有關於數論的基礎知識，我們沒有單列一章介紹有關數論，但不少內容，包括簡單的算法例子、數學問題的證明、計數與組合中都有涉及整數性質的例子。這些例子會給出一些重要的數論基礎知識，包括最大公因數及其歐幾裡得算法、素數及素數的無窮性、兩整數最大公因數的貝祖定理(Bézout’sTheorem)等。

本書每章的定義、定理和例子都分別按章跨節編號。我們只將能夠嚴格使用數學語言定義，並且對於“離散數學基礎”課程學習非常重要的概念作為定義，定義的正文使用楷體以與其他正文區別，其中被定義的概念使用黑體。定理、引理和推論都沿用定理的編號，給出每章最重要的結論。我們精心挑選每一知識模塊所需的定義和定理，使得它們能形成一個相對完整的整體，但不至於有太多、太散的概念和結論需要讀者記憶和學習。

我們將例子進一步分為例子和問題，所以例子和問題進行了統一編號，一起按章跨節編號。例子主要用於進一步解釋定義給出的概念或定理給出的結論，問題則偏向定義和定理的應用，給出的問題在形式上與這一章的習題及運用離散數學要求解的實際問題相同，並且除給出參考的【解答】或【證明】外，通常在解答前有【分析】部分介紹求解問題的思路和切入點，在解答後有【討論】部分補充解答的一些注意事項以及可能的啟發。因此，不少問題也適合用於翻轉課堂教學模式中在學生自學章節主要內容之後進行的討論式教學。

本書每一章除給出大量例子和問題外，還給出了“本章小結”，總結這一章的主要概念、主要結論，以及學習這一章之後讀者應該了解、熟悉的概念和應該能求解的問題。每章的習題在這章的最後一節給出，其中大部分習題用於鞏固學習的內容，與這章中給出的問題十分類似，但也給出了一些擴展性的、有一定難度的習題，供基礎好的讀者練習，其中標記星號“*”的習題是推薦的習題，可作為課後作業布置給學生完成。經過登記和驗證的課程任課教師，可以通過郵箱bailj@tup.tsinghua.edu.cn獲得習題的參考答案。

本書只假定學生有中學數學知識，如果已經接觸過矩陣的基礎知識，以及使用某門程序設計語言編寫過計算機程序則更好。本書可作為高等院校計算機相關專業本科一、二年級72~108 學時的“離散數學基礎”課程的教材，或者作為離散數學相關課程的參考書，也可供從事計算機專業相關工作的科研人員、工程技術人員及其他有關人員參考。表1給出了參考的課程學習計劃和學時建議，其中列①針對周學時為4學時（總學時為72學時①）的課程，列②針對周學時為6學時（總學時為108學時①）的課程（每學期上課周數設為18周），任課教師可根據情況選用。本書對應表中列出的每個教學單元的起始點給出了二維碼，掃描該二維碼可獲得該教學單元的課件和視頻講解等教學資源。

表1 課程學習計劃和學時建議

序號教學單元主要內容選講或略講內容..

基礎知識：邏輯語言、集合1.3圖論語言1 第1 章語言、算法語言1.4代數語言34

2.1 節、2.2節、命題邏輯的基本概念、命2.2.2命題邏輯公式的語法性

2 2.3節題邏輯公式的語法和語義質23

32.4節命題邏輯的等值演算2.4.3命題邏輯公式的範式23

2.5.3 構造驗證推理有效性的

4 2.5 節命題邏輯的推理理論論證23

52.6節命題邏輯的應用2.6.3算法性質的邏輯分析23

3.1 節、3.2節、一階邏輯的基本概念、一

6 3.3 節階邏輯公式的語法和語義3.3.1 一階邏輯公式的解釋34

73.4節一階邏輯的等值演算3.4.3一階邏輯的前束範式23

8 3.5 節 一階邏輯的推理理論 3.5.2 量詞公式的推理規則 2 4

9 3.6 節 一階邏輯的應用 3.6.3 算法性質的邏輯分析 2 3

10 4.1節、4.2節 直接證明、間接證明、分情況證明、存在性證明 4.2.4 基本證明策略 3 4

11 4.3 節 數學歸納法、良序原理、歸納定義、結構歸納法、遞歸算法、歸納證明 4.3.1數學歸納法與良序原理4.3.3遞歸算法與歸納證明 3 4

12 5.1節、5.2節 集合的基本概念、集合運算 5.1.3文氏圖與成員關係表5.2.5集合運算的算法 3 3

13 5.3 節 集合等式 2 3

14 6.1 節 關係的定義、關係的表示、關係的運算 2 3

15 6.2 節 關係的性質 6.2.4 關係性質與關係運算 2 3

16 6.3 節 關係的閉包 2 4

17 6.4 節 特殊關係舉例 2 3

18 7.1 節 函數的基本概念、性質和函數運算 7.1.3 函數運算與函數的性質 2 3

19 7.2 節 集合等勢、無窮集、可數集 7.2.2 有窮集與無窮集 2 3

20 7.3 節 函數的增長、算法效率分析 7.3.3 算法復雜度基礎知識 2 3

21 8.1 節 加法原理、乘法原理、容斥原理、鴿籠原理 8.1.3 鴿籠原理 3 4

. 表1 中列. 和列. 分別留2 學時和3 學時的機動時間。

(續表1)

序號教學單元主要內容選講或略講內容..

22 8.2.1節、8.2.2排列與組合、二項式定理、2 節組合等式

8.2.3 節、8.2.4允許重復的排列與組合、

23容斥原理及其應用、排列8.2.5排列與組合的生成算法3

節、8.2.5節與組合的生成算法

遞推關係式及其求解、分

24 8.3 節 治算法與遞推關係式2

圖的基本概念、圖的連通

259.1節性、圖的表示、無向圖的遍9.1.4無向圖的遍歷2歷

269.2節樹的基礎知識23

279.3節帶權圖及其應用24

289.4節平面圖、歐拉圖、哈密頓圖23

10.1 節、10.2運算及其性質、代數及同

29 節 態10.2.2 同餘關係與商代數3

30 10.3 節 群、子群、陪集、正規子群、商群 10.3.2群元素的階10.3.5群同態 2 3

31 0.4 節 格與布爾代數 10.4.2 分配格與有界格 2 3

總學時數 70 105

在本書的編寫過程中，參考了許多國內外同類教材，得到了許多領導和老師的支持，在此對這些教材的編者以及支持我們的領導和老師表示衷心的感謝。教材於2020年2—7月在中山大學數據科學與計算機學院計算機大類四個教學班進行了試用，非常感謝參與的老師和學生在試用過程中提出的許多寶貴意見和建議。這裡還要特別感謝清華大學出版社的編輯，特別是白立軍老師，沒有他們的耐心和支持，本書不可能得以出版。

在新工科建設背景下，基於培養計算機專業學生離散建模能力，編寫一本與計算機專業其他課程，特別是與程序設計課程內容緊密結合的離散數學教材是我們努力嘗試的方向，但限於編者的水平，不一定能達到預期的目標。書中可能存在不少的疏漏和不妥之處，懇請廣大讀者批評指正。

作者

2020 年7 月

① 表1中列?和列?分別留2學時和3學時的機動時間。

第1章 基礎知識
1.1 邏輯語言
1.2 集合語言
1.3 圖論語言
1.4 代數語言
1.5 算法語言
1.6 本章小結
1.7 習題
第2章 命題邏輯
2.1 命題邏輯的基本概念
2.1.1 命題與真值
2.1.2 原子命題與復合命題
2.2 命題邏輯公式的語法
2.2.1 命題邏輯公式的定義
2.2.2 命題邏輯公式的語法性質
2.2.3 命題邏輯公式的簡寫
2.3 命題邏輯公式的語義
2.3.1 命題邏輯公式的真值定義
2.3.2 命題邏輯公式的真值表
2.3.3 命題邏輯公式的分類
2.4 命題邏輯的等值演算
2.4.1 命題邏輯公式的邏輯等值
2.4.2 基本邏輯等值式
2.4.3 命題邏輯公式的範式
2.5 命題邏輯的推理理論
2.5.1 推理的有效性
2.5.2 命題邏輯的自然推理系統
2.5.3 構造驗證推理有效性的論證
2.6 命題邏輯的應用
2.6.1 自然語言命題的符號化
2.6.2 普通邏輯問題的符號化分析
2.6.3 算法性質的邏輯分析
2.7 本章小結
2.8 習題
第3章 一階邏輯
3.1 一階邏輯的基本概念
3.2 一階邏輯公式的語法
3.2.1 一階邏輯公式的符號
3.2.2 一階邏輯公式的定義
3.2.3 自由變量和約束變量
3.3 一階邏輯公式的語義
3.3.1 一階邏輯公式的解釋
3.3.2 一階邏輯公式的真值
3.3.3 一階邏輯公式的分類
3.4 一階邏輯的等值演算
3.4.1 一階邏輯公式的邏輯等值
3.4.2 量詞公式的基本等值式
3.4.3 一階邏輯的前束範式
3.5 一階邏輯的推理理論
3.5.1 一階邏輯推理的有效性
3.5.2 量詞公式的推理規則
3.5.3 一階邏輯的自然推理舉例
3.6 一階邏輯的應用
3.6.1 自然語言命題的符號化
3.6.2 自然語言推理有效性的驗證
3.6.3 算法性質的邏輯分析
3.7 本章小結
3.8 習題
第4章 證明方法
4.1 數學證明導引
4.2 基本證明方法與策略
4.2.1 直接證明與間接證明
4.2.2 分情況證明
4.2.3 存在性證明
4.2.4 基本證明策略
4.3 歸納定義與歸納證明
4.3.1 數學歸納法與良序原理
4.3.2 歸納定義與結構歸納法
4.3.3 遞歸算法與歸納證明
4.4 本章小結
4.5 習題
第5章 集合
5.1 集合的基本概念
5.1.1 集合的基本術語
5.1.2 定義集合的基本方法
5.1.3 文氏圖與成員關係表
5.2 集合運算
5.2.1 集合交
5.2.2 集合並
5.2.3 集合差與補
5.2.4 集合的冪集
5.2.5 集合運算的算法
5.3 集合等式
5.3.1 基於定義證明集合等式
5.3.2 集合等式演算
5.3.3 子集關係與集合等式
5.4 本章小結
5.5 習題
第6章 關係
6.1 關係的基本概念
6.1.1 集合的笛卡兒積
6.1.2 關係的定義
6.1.3 關係的表示
6.1.4 關係的運算
6.2 關係的性質
6.2.1 關係的自反性與反自反性
6.2.2 關係的對稱性與反對稱性
6.2.3 關係的傳遞性
6.2.4 關係性質與關係運算
6.3 關係的閉包
6.3.1 關係閉包的定義
6.3.2 關係閉包的計算
6.3.3 Warshall算法
6.4 特殊關係舉例
6.4.1 等價關係
6.4.2 偏序關係
6.5 本章小結
6.6 習題
第7章 函數
7.1 函數的基礎知識
7.1.1 函數的基本概念
7.1.2 函數的性質
7.1.3 函數運算與函數的性質
7.2 集合基數的基礎知識
7.2.1 集合等勢
7.2.2 有窮集與無窮集
7.2.3 可數集與不可數集
7.3 函數的增長與算法效率分析
7.3.1 函數的增長
7.3.2 算法效率分析基礎
7.3.3 算法復雜度基礎知識
7.4 本章小結
7.5 習題
第8章 計數與組合
8.1 組合計數的基本原理
8.1.1 加法原理和乘法原理
8.1.2 容斥原理
8.1.3 鴿籠原理
8.2 排列與組合
8.2.1 排列與組合的基本定義
8.2.2 二項式定理與組合等式
8.2.3 允許重復的排列與組合
8.2.4 再論容斥原理及其應用
8.2.5 排列與組合的生成算法
8.3 遞推關係式
8.3.1 計數問題的遞推關係式建模
8.3.2 線性遞推關係式求解
8.3.3 分治算法與遞推關係式
8.4 本章小結
8.5 習題
第9章 圖與樹
9.1 圖的基礎知識
9.1.1 圖的基本概念
9.1.2 圖的連通性
9.1.3 圖的表示與存儲
9.1.4 無向圖的遍歷
9.2 樹的基礎知識
9.2.1 無向樹的定義
9.2.2 根樹的定義
9.2.3 樹的遍歷
9.3 帶權圖及其應用
9.3.1 帶權圖的最短距離
9.3.2 帶權圖的最小生成樹
9.3.3 哈夫曼樹
9.4 一些特殊的圖
9.4.1 平面圖
9.4.2 歐拉圖
9.4.3 哈密頓圖
9.5 本章小結
9.