離散數學是現代數學的一個重要分支，也是計算機科學與技術的理論基礎。離散數學是計算機專業的許多專業課程的基礎，是數據結構、編譯原理、程序設計語言、數據庫原理、操作系統、人工智能、算法分析與設計等課程必不可少的前行課程。通過對離散數學的學習，不僅使學生掌握進一步學習其他課程所必需的離散量的結構及其相互關系的數學知識，同時還培養了學生的抽象思維能力和嚴密的邏輯推理能力，另外還增強了學生使用學過的離散數學知識進行分析問題和解決問題的能力。

本書是在編者多年“離散數學”教學經驗的基礎上編寫而成的。在編寫過程中，結合高職高專學生的培養特點和21世紀人才培養需要，不僅考慮了理論體系的完整性與一致性，也很好地體現了高職高專教育的教學要求。本書中的理論以夠用為主，不注重理論的推導，有的定理只給出結論，加強了理論與實際的聯系，培養學生分析問題、解決問題的能力。在本書的編寫過程中，力求通俗易懂、簡明扼要，書中除了提供典型實例外，每章后還配有適量的習題供讀者練習。

全書共分9章，第1、2章為數理邏輯部分，包括命題邏輯和謂詞邏輯等內容。第3～6章為集合論部分，包括集合的基本概念與運算、二元關系、函數、集合的基數等內容。第7章為圖論部分，包括圖的基本概念、圖的矩陣表示、歐拉圖、哈密爾頓圖、樹、平面圖等內容。第8、9章為代數系統部分，包括代數系統、半群、獨異點、群、環、域、格、有補格、分配格與布爾代數等內容。

本書由賈振華主編，王學軍、賈建文、郭輝任副主編。其中，第1章由李建義編寫，第2章由賈建文編寫，第4，7章由賈振華編寫，第3，5，6章由郭輝編寫，第8，9章由王學軍編寫。劉立媛、莊連英、邵溫參加了部分章節的習題編寫和校對，鄒澎濤負責了部分圖形的繪制。另外，參加編寫的還有李建新、趙輝、李杰、劉俊新等同志。在本書的編寫過程中，始終得到安志遠教授的幫助，在此表示最真摯的感謝。

在編寫本書過程中，我們參考了大量的離散數學教材和資料，在此向有關作者表示衷心的感謝。

由于作者水平有限，書中難免出現一些疏漏和不妥之處，敬請讀者批評指正。E-mail：jiazh@nciae.edu.cn。

編者

2003年12月

序
前言
第一部分 數理邏輯
第1章 命題邏輯 1
本章學習目標 1
1.1 命題及其表示法 1
1.1.1 命題的概念 1
1.1.2 命題的表示 3
1.2 命題聯結詞 3
1.2.1 否定聯結詞 3
1.2.2 合取聯結詞 4
1.2.3 析取聯結詞 4
1.2.4 條件聯結詞 5
1.2.5 雙條件聯結詞 6
1.2.6 與非聯結詞 7
1.2.7 或非聯結詞 8
1.3 命題公式、翻譯與解釋 8
1.3.1 命題公式 8
1.3.2 命題的翻譯 9
1.3.3 命題公式的解釋 10
1.4 真值表與等價公式 10
1.4.1 真值表 10
1.4.2 命題公式的分類 12
1.4.3 等價公式 12
1.4.4 置換規則 15
1.5 對偶與范式 17
1.5.1 對偶 17
1.5.2 范式 19
1.5.3 主范式 20
1.6 公式的蘊涵 25
1.6.1 蘊涵的概念 25
1.6.2 基本蘊涵式 26
1.7 其他聯結詞與最小聯結詞組 27
1.7.1 其他聯結詞 27
1.7.2 最小聯結詞組 28
1.8 命題邏輯推理理論 28
1.8.1 命題邏輯推理理論 28
1.8.2 推理規則 30
1.8.3 推理常用方法 30
本章小結 34
習題 34
第2章 謂詞邏輯 37
本章學習目標 37
2.1 謂詞邏輯命題的符號化 37
2.2 謂詞邏輯公式與解釋 41
2.2.1 謂詞邏輯的合式公式 41
2.2.2 約束變元與自由變元 42
2.2.3 謂詞邏輯公式的解釋 43
2.3 謂詞邏輯約束公式的等價與蘊涵 44
2.3.1 謂詞邏輯的等價公式 44
2.3.2 謂詞邏輯的蘊涵公式 48
2.3.3 多個量詞的使用 49
2.4 前束范式 50
2.5 謂詞演算的推理理論 51
本章小結 55
習題 55
第二部分 集合論
第3章 集合 59
本章學習目標 59
3.1 集合的概念與表示 59
3.1.1 集合的基本概念 59
3.1.2 集合的表示 60
3.2 集合之間的關系 61
3.3 集合的運算 63
3.3.1 集合的并運算 63
3.3.2 集合的交運算 64
3.3.3 集合的補 65
3.3.4 集合的對稱差 66
3.4 包含排斥原理 67
本章小結 70
習題 71
第4章 關系 74
本章學習目標 74
4.1 序偶與笛卡兒積 74
4.1.1 有序n元組 74
4.1.2 笛卡兒積的概念 75
4.1.3 笛卡兒積的性質 75
4.2 二元關系及其表示 77
4.2.1 二元關系的概念 77
4.2.2 二元關系的表示 78
4.3 關系的運算 80
4.3.1 關系的交、并、差、補運算 80
4.3.2 關系的復合運算 80
4.3.3 關系的逆運算 84
4.4 關系的性質 85
4.4.1 自反性和反自反性 85
4.4.2 對稱性和反對稱性 86
4.4.3 傳遞性 87
4.4.4 關系性質的判定 87
4.5 關系的閉包 93
4.6 等價關系與集合的劃分 97
4.6.1 等價關系 97
4.6.2 等價類 98
4.6.3 集合的劃分 99
4.7 相容關系 101
4.7.1 相容關系 101
4.7.2 覆蓋 103
4.8 偏序關系 105
4.8.1 偏序關系 105
4.8.2 哈斯圖 106
4.8.3 全序關系 108
4.8.4 良序關系 110
本章小結 110
習題 110
第5章 函數 114
本章學習目標 114
5.1 函數的概念 114
5.1.1 函數的基本概念 114
5.1.2 幾種特殊的函數 115
5.2 復合函數與逆函數 116
5.2.1 復合函數 116
5.2.2 逆函數 117
本章小結 119
習題 119
第6章 集合的基數 120
本章學習目標 120
6.1 基數的概念 120
6.2 可數集和不可數集 121
6.3 基數的比較 123
本章小結 125
習題 125
第三部分 圖論
第7章 圖論 126
本章學習目標 126
7.1 圖的基本概念 127
7.1.1 圖的基本類型 127
7.1.2 圖中結點的度數 129
7.1.3 完全圖 131
7.1.4 圖的同構 132
7.1.5 補圖 134
7.1.6 子圖 138
7.2 路與回路 139
7.2.1 通路與回路 139
7.2.2 圖的連通性 140
7.2.3 賦權圖的最短通路 144
7.2.4 關鍵路徑 147
7.3 圖的矩陣表示 149
7.3.1 圖的鄰接矩陣表示 149
7.3.2 圖的關聯矩陣表示 153
7.4 歐拉圖 155
7.4.1 歐拉圖的定義 155
7.4.2 歐拉圖的判定 156
7.5 哈密爾頓圖 159
7.5.1 哈密爾頓圖 159
7.5.2 哈密爾頓圖的判定 160
7.6 樹 163
7.6.1 無向樹 163
7.6.2 有向樹 166
7.6.3 周游算法 169
7.6.4 前綴碼與最優樹 171
7.7 二部圖和平面圖 175
7.7.1 二部圖 175
7.7.2 平面圖 179
本章小結 187
習題 187
第四部分 代數系統
第8章 代數結構 191
本章學習目標 191
8.1 二元運算及其性質 191
8.2 代數系統 196
8.3 半群和獨異點 197
8.4 群與子群 199
8.4.1 群 199
8.4.2 群的性質 200
8.4.3 子群 201
8.5 阿貝爾群和循環群 203
8.5.1 阿貝爾群 203
8.5.2 循環群 204
8.6 置換群與伯恩賽德定理 206
8.6.1 置換群 206
8.6.2 伯恩賽德定理（Burnside） 207
8.7 陪集和拉格朗日定理 210
8.7.1 陪集 210
8.7.2 拉格朗日定理 211
8.8 同態與同構 212
本章小結 215
習題 215
第9章 格與布爾代數 220
本章學習目標 220
9.1 格的定義和性質 220
9.1.1 格的定義 220
9.1.2 格的性質 221
9.1.3 格與代數系統的對應 223
9.2 分配格和有補格 224
9.2.1 分配格 224
9.2.2 有補格 226
9.3 布爾代數 228
9.3.1 布爾代數的概念 228
9.3.2 布爾代數的性質 228
9.3.3 布爾表達式 230
本章小結 231
習題 232
參考文獻 236

1. 離散數學（第二版） [主編 賈振華]
2. 離散數學（第二版） [主編 邱曉紅]
3. 離散數學基礎 [主 編 陳華峰 楊 勇]
4. 離散數學 [鐘國亮 編著]
5. 離散數學同步輔導及習題全解 [焦艷芳]
6. 離散數學 [邱曉紅 主編]
7. 離散數學 [賈振華 主編]