離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，也是計(jì)算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)。離散數(shù)學(xué)是計(jì)算機(jī)專(zhuān)業(yè)的許多專(zhuān)業(yè)課程的基礎(chǔ)，是數(shù)據(jù)結(jié)構(gòu)、編譯原理、程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)庫(kù)原理、操作系統(tǒng)、人工智能、算法分析與設(shè)計(jì)等課程必不可少的前行課程。通過(guò)對(duì)離散數(shù)學(xué)的學(xué)習(xí)，不僅使學(xué)生掌握進(jìn)一步學(xué)習(xí)其他課程所必需的離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)知識(shí)，同時(shí)還培養(yǎng)了學(xué)生的抽象思維能力和嚴(yán)密的邏輯推理能力，另外還增強(qiáng)了學(xué)生使用學(xué)過(guò)的離散數(shù)學(xué)知識(shí)進(jìn)行分析問(wèn)題和解決問(wèn)題的能力。

本書(shū)是在編者多年“離散數(shù)學(xué)”教學(xué)經(jīng)驗(yàn)的基礎(chǔ)上編寫(xiě)而成的。在編寫(xiě)過(guò)程中，結(jié)合高職高專(zhuān)學(xué)生的培養(yǎng)特點(diǎn)和21世紀(jì)人才培養(yǎng)需要，不僅考慮了理論體系的完整性與一致性，也很好地體現(xiàn)了高職高專(zhuān)教育的教學(xué)要求。本書(shū)中的理論以夠用為主，不注重理論的推導(dǎo)，有的定理只給出結(jié)論，加強(qiáng)了理論與實(shí)際的聯(lián)系，培養(yǎng)學(xué)生分析問(wèn)題、解決問(wèn)題的能力。在本書(shū)的編寫(xiě)過(guò)程中，力求通俗易懂、簡(jiǎn)明扼要，書(shū)中除了提供典型實(shí)例外，每章后還配有適量的習(xí)題供讀者練習(xí)。

全書(shū)共分9章，第1、2章為數(shù)理邏輯部分，包括命題邏輯和謂詞邏輯等內(nèi)容。第3～6章為集合論部分，包括集合的基本概念與運(yùn)算、二元關(guān)系、函數(shù)、集合的基數(shù)等內(nèi)容。第7章為圖論部分，包括圖的基本概念、圖的矩陣表示、歐拉圖、哈密爾頓圖、樹(shù)、平面圖等內(nèi)容。第8、9章為代數(shù)系統(tǒng)部分，包括代數(shù)系統(tǒng)、半群、獨(dú)異點(diǎn)、群、環(huán)、域、格、有補(bǔ)格、分配格與布爾代數(shù)等內(nèi)容。

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

在編寫(xiě)本書(shū)過(guò)程中，我們參考了大量的離散數(shù)學(xué)教材和資料，在此向有關(guān)作者表示衷心的感謝。

由于作者水平有限，書(shū)中難免出現(xiàn)一些疏漏和不妥之處，敬請(qǐng)讀者批評(píng)指正。E-mail：jiazh@nciae.edu.cn。

編者

2003年12月

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

1. 離散數(shù)學(xué)（第二版） [主編 賈振華]
2. 離散數(shù)學(xué)（第二版） [主編 邱曉紅]
3. 離散數(shù)學(xué)基礎(chǔ) [主 編 陳華峰 楊 勇]
4. 離散數(shù)學(xué) [鐘國(guó)亮 編著]
5. 離散數(shù)學(xué)同步輔導(dǎo)及習(xí)題全解 [焦艷芳]
6. 離散數(shù)學(xué) [邱曉紅 主編]
7. 離散數(shù)學(xué) [賈振華 主編]