離散數學

本書系統地介紹了離散數學的基本內容。全書共分10章，主要由4部分組成：數理邏輯，包括命題邏輯和一階邏輯；集合論，包括集合的基本概念和運算及二元關係和函數；代數結構，包括代數系統的基本概念、幾個典型的代數系統及格和布爾代數；圖論基礎，包括圖的基本概念、樹和幾類典型圖。各章備有例題選解和較多的習題，便於讀者自學。

本書可作為計算機等相關專業的離散數學教材，可供一般本科院校教學使用，也可作為其他類院校離散數學課程的教材和教學參考書。

離散數學是以離散型變數為研究對象的一門科學，它以研究離散型變數的結構和相互間的關係為主要目標。

在現實世界中，變數總是可以分成離散型和連續型兩類，離散型就是變數的變化是可數的（包括有限或無限），與之相對的就是連續型變數。例如自然數0，1，2，3，4，…是離散量，而一天內的溫度變化則是一個連續型的變數。

從人類歷史的發展過程來看，人們最初接觸的量是離散型的，反映到數學領域上則屬於離散數學的範疇，所以，按照離散數學的定義，人們最早熟悉的數學就是離散數學。隨著數學理論的不斷發展和對無限概念的深入探討，同時由於處理離散型數量關係的數學工具在刻畫物體運動方面無能為力，近代出現了連續的數量概念——實數，出現了處理連續型數量關係的數學工具——微積分。因此，近代數學主要研究連續型變數關係及其數學結構、數學模型，並且取得了極其輝煌的成績。近代數學的這一特徵，一直延續至今，仍在現代數學中佔據主導地位。

然而隨著計算機科學的迅猛發展，由於計算機本身是一個離散結構，它只能處理離散型的或離散化了的數量關係，因此，在計算技術、計算機系統功能和計算機應用等各個領域中提出了許多有關離散量的理論問題，迫切需要用適當的數學工具來描述和深化，於是離散數學作為一門學科應運而生，並成為近代數學的一個重要分支。

離散數學課程是介紹離散數學各分支的基本概念、基本理論和基本研究方法、研究工具的基礎課程。它所涉及的概念、方法和理論，大量地應用在數字電路、編譯原理、數據結構、操作系統、資料庫系統、演演算法的分析與設計、軟體工程、人工智慧、計算機網路等專業課程及信息管理、信號處理等相關課程中。它著重培養訓練學生的抽象思維能力、邏輯推理能力和歸納構造能力，為學生提高專業理論水平打下紮實的數學基礎，為後續專業課程的學習做好準備。

本書於2003年6月出版了第一版，受到廣大讀者歡迎，先後多次重印。許多教師、學生和其他讀者在支持鼓勵的同時，對本教材提出了許多寶貴的意見和建議。根據專家的意見和讀者在使用中提出的合理建議，並結合筆者本人的教學實踐，在第一版的基礎上對本書進行了修訂。這次修訂在保持原版風格和基本內容的基礎上，將代數結構部分的環和域內容分開，增加了環、域和有限域的內容，以適應後續有關信息安全課程的需求，讀者可以適當選取該部分內容；圖論部分增加了實用性較強的帶權圖和最短路徑。同時筆者對原有不當的地方進行了必要的修改，調整了部分習題內容，以便於讀者更好地學習和掌握。

根據國家教委頒布的計算機專業教學基本要求，本書包含了4部分內容：數理邏輯、集合與關係、代數結構和圖論。全書體系結構嚴謹、敘述深入淺出，並配有大量習題，可作為普通高等學校計算機或相關專業的本科生教材。根據我們的經驗，本書可在90~110學時內完成教學計劃，如果課時不夠，可適當刪去代數結構中的部分內容和有星號的內容。

本書的數理邏輯和圖論部分（第一、二章，第八、九、十章）由劉均梅編寫，集合與關係和代數結構部分（第三章至第七章）由蔡英編寫。在編寫過程中，夏倫進副教授曾與我們討論本書的內容、觀點，使我們受益匪淺。另外，在編寫過程中，筆者還參閱了大量的離散數學書籍和資料，在此一併向有關作者表示衷心的感謝。同時，我們衷心感謝西安電子科技大學出版社對本書的出版所給予的大力支持。

最後，希望本書的修訂能給讀者學習離散數學帶來一些幫助，感謝讀者選擇和使用本書，誠懇地期待讀者的批評、指正以及提出修改意見，筆者將不勝感激。

蔡英　劉均梅

2008年3月於北京

第一章 命題邏輯 3

1.1 命題符號化及聯結詞 3

1.2 命題公式及分類 8

1.3 等值演算 11

1.4 聯結詞全功能集 14

1.5 對偶與範式 18

1.6 推理理論 26

*1.7 命題演算的自然推理形式系統N 32

1.8 例題選解 36

習題一 39

第二章 一階邏輯 43

2.1 一階邏輯的基本概念 43

2.2 一階邏輯公式及解釋 47

2.3 等值演算和前束範式 53

2.4 一階邏輯推理理論 56

2.5 例題選解 59

習題二 62

第三章 集合的基本概念和運算 67

3.1 集合的基本概念與表示 67

3.2 集合的基本運算 71

3.3 集合元素的計數 76

3.4 例題選解 78

習題三 80

第四章 二元關係和函數 82

4.1 序偶與笛卡兒積 82

4.2 關係及表示 85

4.3 關係的運算 88

4.4 關係的性質 94

4.5 關係的閉包 99

4.6 等價關係和劃分 104

4.7 序關係 108

4.8 函數的定義和性質 115

4.9 函數的複合和反函數 120

4.10 集合的基數 124

4.11 例題選解 130

習題四 135

第五章 代數系統的基本概念 143

5.1 二元運算及其性質 143

5.2 代數系統 149

5.3 代數系統的同態與同構 150

5.4 例題選解 154

習題五 155

第六章 幾個典型的代數系統 158

6.1 半群與群 158

6.2 子群 165

6.3 循環群和置換群 167

6.4 陪集與拉格朗日定理 171

6.5 正規子群、商群和同態基本定理 174

6.6 環 176

6.7 域 181

6.8 有限域 184

6.9 例題選解 187

習題六 190

第七章 格和布爾代數 195

7.1 格與子格 195

7.2 特殊格 201

7.3 布爾代數 205

7.4 例題選解 209

習題七 211

第八章 圖的基本概念 215

8.1 圖的定義及相關術語 215

8.2 通路迴路圖的連通性 220

8.3 圖的矩陣表示 226

8.4 帶權圖與最短路徑 230

8.5 例題選解 232

習題八 233

第九章 樹 236

9.1 無向樹 236

9.2 根樹及其應用 242

9.3 例題選解 249

習題九 252

第十章 幾種典型圖 254

10.1 歐拉圖 254

10.2 哈密頓圖 258

10.3 平面圖 262

10.4 二分圖 270

10.5 例題選解 275

習題十 277

參考文獻 280