本書從應用的角度介紹離散數(shù)學。全書共分6章，分別是命題邏輯、謂詞邏輯、集合與關(guān)系、代數(shù)結(jié)構(gòu)、圖和有向圖。全書體系嚴謹，敘述深入淺出，并配有大量與計算機科學相關(guān)的有實際背景的例題和習題。在每章最后增加了上機作業(yè)，可增強學生對課堂教學內(nèi)容的理解和掌握，提高學生的學習興趣和動手能力。這對于學生學習、理解和應用離散數(shù)學理論有很大的幫助。
本書可作為普通高等學校計算機科學與技術(shù)或相關(guān)專業(yè)的本科生教材。
從計算機應用的角度出發(fā)，講述離散數(shù)學理論在實際中的應用。
目錄
第1章命題邏輯1
1.1命題和邏輯連接詞2
1.1.1命題2
1.1.2邏輯連接詞與命題符號化4
習題1.17
1.2命題公式及其真值表8目錄
第1章命題邏輯1
1.1命題和邏輯連接詞2
1.1.1命題2
1.1.2邏輯連接詞與命題符號化4
習題1.17
1.2命題公式及其真值表8
1.2.1命題公式8
1.2.2真值表8
習題1.211
1.3命題公式的等價演算12
習題1.315
1.4命題公式的范式15
1.4.1析取范式與合取范式15
1.4.2標準析取范式和標準合取范式18
1.4.3利用真值表求解標準范式20
1.4.4標準析取范式和標準合取范式的關(guān)系22
習題1.423
1.5命題公式的推理演算25
1.5.1基本概念25
1.5.2演繹推理方法27
1.5.3附加前提法28
習題1.530
1.6邏輯門電路32
1.6.1門電路32
1.6.2邏輯電路設計33
習題1.635
第1章上機練習35
第2章謂詞邏輯37
2.1個體詞、謂詞與量詞37
2.1.1個體詞與謂詞37
2.1.2量詞38
習題2.140
2.2謂詞公式及其解釋42
2.2.1謂詞公式42
2.2.2謂詞公式的解釋43
習題2.246
2.3謂詞公式的等價演算47
習題2.349
2.4謂詞公式的推理演算50
2.4.1基本概念50
2.4.2演繹推理方法51
習題2.455
第2章上機練習56
第3章集合與關(guān)系58
3.1集合及其運算58
3.1.1基本概念58
3.1.2集合的運算60
3.1.3集合的計算機表示62
習題3.163
3.2二元關(guān)系及其運算65
3.2.1笛卡爾積65
3.2.2二元關(guān)系及其表示66
3.2.3二元關(guān)系的運算67
習題3.270
3.3二元關(guān)系的性質(zhì)與閉包71
3.3.1二元關(guān)系的性質(zhì)71
3.3.2二元關(guān)系的閉包73
習題3.375
3.4等價關(guān)系與劃分77
習題3.480
3.5偏序關(guān)系與拓撲排序80
3.5.1偏序關(guān)系80
3.5.2偏序集中的特殊元82
3.5.3拓撲排序84
習題3.585
3.6函數(shù)87
3.6.1基本概念87
3.6.2復合函數(shù)88
3.6.3逆函數(shù)90
習題3.691
3.7集合的等勢與基數(shù)92
習題3.793
3.8多元關(guān)系及其應用93
3.8.1多元關(guān)系93
3.8.2關(guān)系數(shù)據(jù)庫94
3.8.3數(shù)據(jù)庫的檢索95
3.8.4插入、刪除與修改96
習題3.897
第3章上機練習98
第4章代數(shù)結(jié)構(gòu)99
4.1代數(shù)運算99
4.1.1基本概念99
4.1.2二元運算的性質(zhì)100
4.1.3二元運算中的特殊元101
習題4.1103
4.2代數(shù)系統(tǒng)104
習題4.2106
4.3群107
4.3.1基本概念107
4.3.2冪運算109
4.3.3群的性質(zhì)110
習題4.3113
4.4子群與陪集114
4.4.1子群114
4.4.2陪集116
4.4.3正規(guī)子群與商群118
4.4.4群同態(tài)與同構(gòu)119
習題4.4120
4.5循環(huán)群、置換群121
4.5.1循環(huán)群121
4.5.2置換群122
習題4.5125
4.6環(huán)與域125
4.6.1環(huán)126
4.6.2整環(huán)與域127
習題4.6128
4.7格與布爾代數(shù)129
4.7.1格129
4.7.2幾種特殊的格130
4.7.3布爾代數(shù)132
習題4.7133
第4章上機練習134
第5章圖135
5.1基本概念135
5.1.1圖的定義135
5.1.2頂點的度137
習題5.1139
5.2圖的連通性139
5.2.1通路139
5.2.2連通圖141
5.2.3圖的矩陣表示144
習題5.2147
5.3歐拉圖與哈密爾頓圖148
5.3.1歐拉圖148
5.3.2哈密爾頓圖150
5.3.3旅行商問題151
習題5.3152
5.4最短通路153
5.4.1廣義優(yōu)先搜索153
5.4.2Dijkstra算法156
5.4.3中國郵遞員問題158
習題5.4159
5.5樹160
5.5.1基本概念160
5.5.2生成樹163
5.5.3深度優(yōu)先搜索165
5.5.4最小生成樹168
習題5.5171
5.6平面圖及圖的著色173
5.6.1平面圖173
5.6.2圖的著色176
習題5.6179
第5章上機練習180
第6章有向圖181
6.1有向圖概述181
6.1.1基本概念181
6.1.2有向圖的連通性182
6.1.3有向圖的矩陣表示184
習題6.1186
6.2根樹187
6.2.1基本概念187
6.2.2二叉搜索樹188
6.2.3最優(yōu)二叉樹190
習題6.2193
6.3網(wǎng)絡流194
6.3.1基本概念194
6.3.2最大流算法196
6.3.3最大流最小割定理202
習題6.3203
6.4匹配205
習題6.4207
第6章上機練習208
參考文獻209
書單推薦
