全書共8章，首先通過"命題邏輯和"謂詞邏輯建立基本的邏輯思維體系，進而以嚴(yán)謹(jǐn)?shù)姆栠壿嬂斫?集合的基本概念與運算，并作為其他知識的基礎(chǔ)。"關(guān)系、"函數(shù)不僅擴充了集合的應(yīng)用范圍，也更體現(xiàn)了集合的重要應(yīng)用。在此基礎(chǔ)上，利用"運算與代數(shù)系統(tǒng)、"環(huán)、域、格和布爾代數(shù)介紹了近世代數(shù)的基本理論與結(jié)果。*后為"圖論。全書的內(nèi)容可在70個學(xué)時左右講完。
前 言
離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的一門學(xué)科，是由邏輯學(xué)、集合論、關(guān)系理論、圖論、抽象代數(shù)、布爾代數(shù)甚至算法設(shè)計、組合分析、離散概率和計算模型等匯集起來的一門綜合學(xué)科。由于數(shù)字電子計算機是一個離散結(jié)構(gòu)，只能處理離散的或離散化了的數(shù)量關(guān)系和數(shù)學(xué)模型，這正是離散數(shù)學(xué)的主要內(nèi)容，因此，離散數(shù)學(xué)構(gòu)成了計算機相關(guān)學(xué)科的基礎(chǔ)學(xué)科。為此，《中國計算機科學(xué)與技術(shù)學(xué)科教程2002》將其界定為計算機科學(xué)與技術(shù)專業(yè)的核心基礎(chǔ)課程，美國IEEE＆ACM也確定其為計算機專業(yè)的核心課程。
應(yīng)該說，計算機及其相關(guān)專業(yè)的絕大部分課程，都是直接以離散數(shù)學(xué)作為理論基礎(chǔ)的，也可以說是離散數(shù)學(xué)的直接運用，或者說需要依靠離散數(shù)學(xué)課程中建立的觀點、方法和邏輯思維能力去解決具體問題。因此，離散數(shù)學(xué)課程的教學(xué)目的就是要建立邏輯（數(shù)學(xué)）推理能力、了解重要的離散對象與結(jié)構(gòu)、構(gòu)建和應(yīng)用解決離散問題的模型、具備算法思維等。
存在著一些相當(dāng)成功的離散數(shù)學(xué)教材，如Kenneth H. Rosen的《Discrete mathematics and its applications》、左孝凌的《離散數(shù)學(xué)》和屈婉玲的《離散數(shù)學(xué)》等。在近30年的教學(xué)實踐中，我們采用這些教材取得過一定的成功，但也存在著諸多問題，且這些問題隨著形勢的發(fā)展變得越來越突出，以至于形成了一些尖銳的矛盾。概括地說，這些教材大而全，更關(guān)注理論與系統(tǒng)的完整性，這與教材的定位甚至國家對精品教材、規(guī)劃教材、優(yōu)秀教材等的要求和評價標(biāo)準(zhǔn)不無關(guān)聯(lián)，缺乏對學(xué)習(xí)對象本身的情況和層次、學(xué)時的減少以及工程教學(xué)目的變化等實實在在因素的關(guān)注。這些問題在湖南大學(xué)的張洪圣等老師編寫的同名教材中已經(jīng)部分提及，我們深有同感。舉例說，普通工科高校在我國高校中占大多數(shù)，但它們的學(xué)生與985、211高校存在著很大的差異，以學(xué)術(shù)研究為目標(biāo)的教材和教學(xué)內(nèi)容上的趨同不僅達不到拔高的目標(biāo)，反而使學(xué)生過早喪失了學(xué)習(xí)興趣，形成一系列不良的連鎖反應(yīng)。又如，在僅有48至64學(xué)時的教學(xué)時間里，我們不能期望把類似數(shù)論、離散概率、組合設(shè)計、形式語言、自動機等內(nèi)容都灌輸給普通院校的學(xué)生。
本書的寫作目的是為一般的而非拔尖的普通工科高校的計算機、軟件工程及其相關(guān)專業(yè)提供一本通俗、易于理解、易于自學(xué)、有一定工程應(yīng)用背景和實際問題引導(dǎo)的教材。因此，本書不追求體系的完整、內(nèi)容的全面和對理論的深入探討，也不關(guān)注競賽、考研等問題。為了達到目標(biāo)，體現(xiàn)自身的特點，我們注重如下問題并采取了我們認(rèn)為適當(dāng)?shù)淖龇ǎ?br />? 內(nèi)容按教學(xué)實際取舍。舍棄中學(xué)學(xué)過的簡單組合計數(shù)、前文提到的離散概率、數(shù)論、組合設(shè)計、形式語言等內(nèi)容，以及數(shù)據(jù)結(jié)構(gòu)等課程中涵蓋的算法，不使內(nèi)容過于膨脹，并盡量避免與后續(xù)課程重復(fù)。
? 次序編排突出邏輯思維。以邏輯學(xué)而不是集合論為出發(fā)點，用命題邏輯和謂詞邏輯主導(dǎo)解決后續(xù)所有問題的思維，以便強化分析、解決問題的邏輯性和能力。
? 對問題平實、透徹講解。離散數(shù)學(xué)也是數(shù)學(xué)，內(nèi)容抽象。通過身邊和計算機領(lǐng)域?qū)嵗栴}引導(dǎo)、分析、評價、辨析等步驟，將問題講解透徹，避免讀者自身需要花過長的時間思考或借助參考書才能讀懂，甚至利用理解標(biāo)簽予以提示并展示應(yīng)理解的程度。特別地，對大量值得注意或認(rèn)真分析的關(guān)鍵問題，都通過辨析標(biāo)簽給出討論和警示。
? 概括、突出問題核心。對解決一類問題的核心內(nèi)容給予總結(jié)、概括和突出，說明此類問題的實質(zhì)和解決方法的關(guān)鍵而不是一個具體題目的解法。
? 適當(dāng)引入工程問題。選取領(lǐng)域中有代表性的工程應(yīng)用實踐問題作為示例或習(xí)題，消除學(xué)生總認(rèn)為學(xué)理論與實際脫節(jié)的誤解，激發(fā)其學(xué)習(xí)課程和解決實際問題的興趣。
? 對思考和應(yīng)用進行引導(dǎo)。作為教材，對于新的成果、大量的相關(guān)問題及其解決方案不可能全部囊括，僅是一斑。對于很多問題，通過延伸標(biāo)簽指出其發(fā)展方向、實際應(yīng)用案例、存在的解決方法等，并列出可供參考的論文等素材，以引導(dǎo)學(xué)生自己探索。當(dāng)然，這些內(nèi)容作為課堂的延伸，以輔助學(xué)習(xí)和思考為主，研究為輔。因此，列出的論文都不是專門研究理論而是程度較淺的應(yīng)用型文章、教學(xué)論文乃至?xí)?br />? 洗練定理與習(xí)題。過多羅列已有的結(jié)果令人眼花繚亂，還會誤導(dǎo)學(xué)生機械記憶而不是由基本概念出發(fā)進行主動思考，探究和發(fā)現(xiàn)結(jié)果。同時，盡管多做習(xí)題有助于問題的理解，但需要大量的時間和精力，過多習(xí)題也容易使人恐懼并產(chǎn)生排斥心理。為此，盡量精簡了定理與習(xí)題。相反，基于概念（定義）對內(nèi)容理解和題目求解的極端重要作用，故將重要概念納入習(xí)題，直接提醒學(xué)生弄懂并記住這些定義。
使本書體現(xiàn)上述特點源自于學(xué)生的實際情況、教學(xué)上的要求以及人才培養(yǎng)工程化的形勢變化等因素。我們認(rèn)為，在把更多的時間、思考、總結(jié)、發(fā)現(xiàn)任務(wù)交給學(xué)生時，教師要能使學(xué)生學(xué)會學(xué)習(xí)，教材要有助于學(xué)生自主學(xué)習(xí)。教材既不能包羅萬象，求深求全，也不能只是干巴巴的綱，更不應(yīng)連一節(jié)中有幾個重要概念、主要方法之類的總結(jié)都由教材代替。考慮到目前離散數(shù)學(xué)課程多在一年級中開設(shè)，我們沒有對算法的描述以及程序?qū)崿F(xiàn)提出過多要求，以免徒增額外負(fù)擔(dān)且沖淡主題。此外，還對重要名詞配以英文對照，以期可以輔助對專業(yè)外文詞匯的掌握。
全書分為8章，分別是命題邏輯、謂詞邏輯、集合的基本概念與運算、關(guān)系、函數(shù)、運算與代數(shù)系統(tǒng)、環(huán)、域、格和布爾代數(shù)、圖論。這種安排次序的目的是期望以嚴(yán)密的邏輯思維貫穿各部分內(nèi)容，以使思考和推理更富有理論依據(jù)。全書的內(nèi)容可在70個學(xué)時左右講完。
本書的幾位作者都具有20多年的課程教學(xué)經(jīng)驗，且未間斷地從事本科離散數(shù)學(xué)課程的教學(xué)工作。無論是對課程內(nèi)容、體系、教學(xué)方法和安排，還是工程教育的發(fā)展方向與工科學(xué)生的實際情況均有著深刻的理解，這使得本書的寫作更有針對性。我們期望通過本書使離散數(shù)學(xué)的內(nèi)容更容易理解、學(xué)習(xí)和掌握，促進課程教學(xué)質(zhì)量的提高，但囿于個人見解，仍會存在諸多缺憾，歡迎讀者指出其不足，也期待能與讀者做更多的交流（niulq@sut.edu.cn）。
此外，本書的出版得到了沈陽工業(yè)大學(xué)和學(xué)校諸多老師的支持和幫助，作者深表感謝！
作 者
牛連強，男，沈陽工業(yè)大學(xué)軟件學(xué)院院長、教授二是余年來，長期從事高等學(xué)校計算機領(lǐng)域的教學(xué)和科研工作，教學(xué)經(jīng)驗豐富、科研項目成果豐富，并出版了多部教材和專著，發(fā)表論文40余篇。
目 錄
第1章 命題邏輯1
1.1 命題1
思考與練習(xí)1.13
1.2 邏輯聯(lián)結(jié)詞3
1.2.1 基本聯(lián)結(jié)詞3
1.2.2 其他聯(lián)結(jié)詞6
思考與練習(xí)1.26
1.3 命題公式與真值表7
1.3.1 命題公式7
1.3.2 真值表8
思考與練習(xí)1.39
1.4 命題翻譯9
1.4.1 合取命題9
1.4.2 可兼與不可兼析取命題10
1.4.3 條件命題10
1.4.4 多聯(lián)結(jié)詞命題11
思考與練習(xí)1.413
1.5 命題公式的值與等價14
1.5.1 命題公式的分類14
1.5.2 命題公式的等價14
1.5.3 聯(lián)結(jié)詞的功能完備集17
1.5.4 由德?摩根律到對偶原理17
思考與練習(xí)1.518
1.6 范式19
1.6.1 簡單的范式19
1.6.2 小項與大項20
1.6.3 主析取范式與主合取范式21
思考與練習(xí)1.623
1.7 推理理論24
1.7.1 蘊含與論證24
1.7.2 自然推理系統(tǒng)26
思考與練習(xí)1.733
第2章 謂詞邏輯34
2.1 謂詞、個體詞與量詞34
2.1.1 個體詞與謂詞34
2.1.2 量詞與量化36
思考與練習(xí)2.137
2.2 謂詞邏輯中的命題翻譯38
2.2.1 特殊化個體詞的命題38
2.2.2 量詞量化的命題39
思考與練習(xí)2.242
2.3 量詞約束與謂詞公式的解釋42
2.3.1 量詞對個體詞變元的作用42
2.3.2 謂詞公式的解釋與求值43
2.3.3 量詞與聯(lián)結(jié)詞的搭配44
思考與練習(xí)2.345
2.4 謂詞邏輯中的基本等價和蘊含
關(guān)系46
2.4.1 基本等價與蘊含關(guān)系46
2.4.2 利用等價關(guān)系計算前束范式49
思考與練習(xí)2.450
2.5 謂詞演算的推理理論50
思考與練習(xí)2.556
第3章 集合論基礎(chǔ)58
3.1 集合的概念與表示方法58
3.1.1 集合描述58
3.1.2 集合的包含與相等59
3.1.3 空集與全集60
3.1.4 集合的冪集62
思考與練習(xí)3.163
3.2 集合運算64
3.2.1 基本運算64
3.2.2 多集合的交與并66
思考與練習(xí)3.268
3.3 集合運算的性質(zhì)與證明方法69
3.3.1 集合運算的性質(zhì)與演算證明69
3.3.2 基于定義的集合運算證明
方法70
思考與練習(xí)3.373
3.4 序偶與笛卡爾積73
3.4.1 序偶與元組74
3.4.2 笛卡爾積74
思考與練習(xí)3.477
第4章 關(guān)系78
4.1 二元關(guān)系的含義與表示78
4.1.1 二元關(guān)系78
4.1.2 關(guān)系的矩陣和圖表示法80
思考與練習(xí)4.181
4.2 關(guān)系運算81
4.2.1 關(guān)系求逆與復(fù)合82
4.2.2 關(guān)系運算的性質(zhì)83
4.2.3 利用關(guān)系圖與關(guān)系矩陣實現(xiàn)
關(guān)系運算85
4.2.4 多關(guān)系的復(fù)合87
思考與練習(xí)4.289
4.3 關(guān)系的主要性質(zhì)89
4.3.1 自反與反自反關(guān)系89
4.3.2 對稱與反對稱關(guān)系90
4.3.3 傳遞關(guān)系92
4.3.4 特殊關(guān)系的判定92
思考與練習(xí)4.394
4.4 關(guān)系的閉包95
4.4.1 閉包的概念95
4.4.2 閉包計算96
思考與練習(xí)4.499
4.5 相容關(guān)系與等價關(guān)系100
4.5.1 集合的覆蓋與劃分100
4.5.2 相容與等價101
4.5.3 相容關(guān)系產(chǎn)生的完全覆蓋102
4.5.4 等價關(guān)系產(chǎn)生的劃分103
4.5.5 由覆蓋、劃分生成相容關(guān)系
和等價關(guān)系105
思考與練習(xí)4.5106
4.6 序關(guān)系107
4.6.1 體現(xiàn)部分次序的偏序關(guān)系107
4.6.2 哈斯圖107
4.6.3 偏序集的特殊元素110
思考與練習(xí)4.6112
第5章 函數(shù)114
5.1 從關(guān)系到函數(shù)114
5.1.1 函數(shù)的概念114
5.1.2 函數(shù)集115
5.1.3 特殊函數(shù)116
思考與練習(xí)5.1118
5.2 函數(shù)的逆與復(fù)合119
5.2.1 雙射的反函數(shù)119
5.2.2 函數(shù)的復(fù)合119
5.2.3 函數(shù)運算的性質(zhì)121
思考與練習(xí)5.2122
5.3 集合的基數(shù)123
5.3.1 集合等勢123
5.3.2 有限集與無限集124
5.3.3 可數(shù)集與不可數(shù)集124
5.3.4 基數(shù)比較126
思考與練習(xí)5.3127
第6章 運算與代數(shù)系統(tǒng)129
6.1 運算及其性質(zhì)129
6.1.1 n元運算129
6.1.2 二元運算的主要性質(zhì)130
思考與練習(xí)6.1132
6.2 二元運算中的特殊元素132
6.2.1 幺元132
6.2.2 零元133
6.2.3 逆元134
思考與練習(xí)6.2135
6.3 代數(shù)系統(tǒng)135
6.3.1 代數(shù)與子代數(shù)135
6.3.2 同態(tài)與同構(gòu)136
思考與練習(xí)6.3138
6.4 半群與獨異點138
思考與練習(xí)6.4140
6.5 群與子群140
6.5.1 群的概念140
6.5.2 群的性質(zhì)141
6.5.3 子群142
思考與練習(xí)6.5144
6.6 循環(huán)群與置換群145
6.6.1 循環(huán)群145
6.6.2 置換群146
思考與練習(xí)6.6148
6.7 群的陪集分解149
6.7.1 陪集149
6.7.2 拉格朗日定理150
思考與練習(xí)6.7151
第7章 環(huán)、域、格和布爾代數(shù)152
7.1 環(huán)和域152
7.1.1 環(huán)152
7.1.2 域153
思考與練習(xí)7.1154
7.2 格155
7.2.1 格與其誘導(dǎo)的代數(shù)系統(tǒng)155
7.2.2 子格157
7.2.3 特殊格157
思考與練習(xí)7.2160
7.3 布爾代數(shù)161
7.3.1 布爾格誘導(dǎo)的布爾代數(shù)161
7.3.2 典型的布爾代數(shù)162
思考與練習(xí)7.3164
第8章 圖165
8.1 圖的基本概念165
8.1.1 圖的認(rèn)知165
8.1.2 結(jié)點的度與握手定理166
8.1.3 完全圖與正則圖168
8.1.4 子圖、補圖與圖同構(gòu)169
思考與練習(xí)8.1170
8.2 圖的連通性171
8.2.1 路與回路171
8.2.2 無向圖的連通性172
8.2.3 有向圖的連通性173
思考與練習(xí)8.2174
8.3 圖的矩陣表示174
8.3.1 鄰接矩陣174
8.3.2 關(guān)聯(lián)矩陣176
思考與練習(xí)8.3177
8.4 二部圖、歐拉圖與漢密爾頓圖177
8.4.1 二部圖177
8.4.2 歐拉圖179
8.4.3 漢密爾頓圖181
思考與練習(xí)8.4183
8.5 平面圖183
8.5.1 平面圖與歐拉定理183
8.5.2 平面圖的對偶圖186
8.5.3 平面圖的著色187
思考與練習(xí)8.5188
8.6 樹188
8.6.1 無向樹188
8.6.2 生成樹190
8.6.3 根樹192
思考與練習(xí)8.6195
附錄A 符號索引197
參考文獻199
新書資訊