定 價(jià):79 元
叢書名:重點(diǎn)大學(xué)計(jì)算機(jī)教材
- 作者:張瑞勛,邵秀麗 ,任明明
- 出版時(shí)間:2021/8/1
- ISBN:9787111678205
- 出 版 社:機(jī)械工業(yè)出版社
- 中圖法分類:O158
- 頁(yè)碼:
- 紙張:膠版紙
- 版次:
- 開本:16開
本書針對(duì)本科離散數(shù)學(xué)課程的要點(diǎn)和關(guān)鍵問(wèn)題,深入淺出地介紹了數(shù)理邏輯、集合論、圖論、代數(shù)結(jié)構(gòu)和布爾代數(shù)、網(wǎng)絡(luò)模型、組合數(shù)學(xué)理論和算法等與計(jì)算機(jī)科學(xué)密切相關(guān)的問(wèn)題,既著重于各部分內(nèi)容之間的緊密聯(lián)系,又深入探討各部分內(nèi)容的概念、理論、算法和實(shí)際應(yīng)用,本書敘述嚴(yán)謹(jǐn),推演詳盡。各章配有習(xí)題,可為讀者迅速掌握有關(guān)知識(shí)提供有效的幫助。
離散數(shù)學(xué)是計(jì)算機(jī)及相關(guān)專業(yè)的重要數(shù)學(xué)基礎(chǔ)之一,它是以離散型變量、離散數(shù)量關(guān)系和離散結(jié)構(gòu)模型為研究對(duì)象,以研究離散型變量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)的一門學(xué)科,內(nèi)容包括數(shù)理邏輯、抽象代數(shù)、古典概率、組合學(xué)、圖論、集合論、數(shù)論、自動(dòng)機(jī)和形式語(yǔ)言、可計(jì)算性和可判定性、離散幾何等.
18世紀(jì)以前,數(shù)學(xué)基本上是研究離散對(duì)象的數(shù)量和空間關(guān)系的科學(xué).天文學(xué)、物理學(xué)的發(fā)展,如牛頓三大力學(xué)定律等的研究,極大地推動(dòng)了連續(xù)數(shù)學(xué)的發(fā)展.在這個(gè)時(shí)期,除了抽象代數(shù)外,屬于離散數(shù)學(xué)范圍的組合學(xué)(包括圖論)、數(shù)理邏輯等一直處于相對(duì)停滯的狀態(tài).但自20世紀(jì)30年代起,隨著圖靈提出計(jì)算機(jī)的理論模型圖靈機(jī),以及電子計(jì)算機(jī)的迅猛發(fā)展,離散數(shù)學(xué)重新煥發(fā)青春.
由于電子計(jì)算機(jī)是一個(gè)離散結(jié)構(gòu),它只能處理離散的或離散化了的數(shù)量關(guān)系,因此,無(wú)論計(jì)算機(jī)科學(xué)本身,還是與計(jì)算機(jī)科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域,都面臨著如何對(duì)離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型,以及如何將已用連續(xù)數(shù)量關(guān)系建立起來(lái)的數(shù)學(xué)模型離散化,從而可由計(jì)算機(jī)進(jìn)行處理等問(wèn)題.于是離散數(shù)學(xué)的地位不斷攀升,成為近代數(shù)學(xué)的一個(gè)重要分支.
本書系統(tǒng)地介紹了離散數(shù)學(xué)各個(gè)分支的基本概念、基本理論和基本方法.這些概念、理論以及方法大量地應(yīng)用在數(shù)字電路、編譯原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)、算法的分析與設(shè)計(jì)、人工智能、計(jì)算機(jī)網(wǎng)絡(luò)等專業(yè)課程中,為學(xué)生提高專業(yè)理論水平打下堅(jiān)實(shí)的基礎(chǔ).同時(shí),本書著重培養(yǎng)學(xué)生的抽象概括能力、邏輯思維能力、歸納構(gòu)造能力,有益于培養(yǎng)學(xué)生嚴(yán)謹(jǐn)、規(guī)范的科學(xué)態(tài)度.
本書在構(gòu)思、編寫過(guò)程中參考了一些書籍和文獻(xiàn)(已在本書的參考文獻(xiàn)中列出),在此對(duì)這些文獻(xiàn)的作者表示感謝.
本書共10章,內(nèi)容包括:命題邏輯、謂詞邏輯、集合及其運(yùn)算、二元關(guān)系、函數(shù)、代數(shù)結(jié)構(gòu)、格和布爾代數(shù)、圖論、樹、計(jì)數(shù)方法和分類原理.每章均有豐富的例題,幫助讀者理解知識(shí)點(diǎn);每章后配有相關(guān)習(xí)題,可供讀者鞏固知識(shí)點(diǎn).
本書第1、2、4、7、9、10章由邵秀麗完成,習(xí)題由邵秀麗和任明明完成,第3、5、6、8章由張瑞勛完成,任明明負(fù)責(zé)全書的終統(tǒng)稿,全書經(jīng)過(guò)三人共同討論和修改完稿.
本書依據(jù)作者在南開大學(xué)一直使用的課程講義整理而成,但由于作者經(jīng)驗(yàn)所限,書中難免會(huì)有疏漏和錯(cuò)誤之處,希望讀者給予批評(píng)和指正.
作者
2020年于南開大學(xué)
前言
第1章 命題邏輯1
1.1 引言1
1.2 命題與命題聯(lián)結(jié)詞1
1.2.1 命題的概念1
1.2.2 命題標(biāo)識(shí)符和命題分類3
1.2.3 命題聯(lián)結(jié)詞3
1.3 翻譯、命題公式和真值表7
1.3.1 翻譯7
1.3.2 命題公式9
1.3.3 真值情況和真值表10
1.4 永真式、永假式和等價(jià)關(guān)系12
1.5 等價(jià)式和蘊(yùn)涵式14
1.5.1 等價(jià)公式14
1.5.2 等價(jià)定律公式14
1.5.3 子公式15
1.5.4 證明兩個(gè)公式等價(jià)的方法16
1.5.5 蘊(yùn)涵式19
1.5.6 永真蘊(yùn)涵關(guān)系的判斷20
1.6 其他聯(lián)結(jié)詞22
1.6.1 其他聯(lián)結(jié)詞的定義22
1.6.2 與非聯(lián)結(jié)詞的性質(zhì)23
1.6.3 或非聯(lián)結(jié)詞的性質(zhì)23
1.6.4 異或聯(lián)結(jié)詞的性質(zhì)24
1.6.5 小聯(lián)結(jié)詞組25
1.7 對(duì)偶與范式26
1.7.1 對(duì)偶27
1.7.2 范式29
1.7.3 主析取范式31
1.7.4 主合取范式35
1.7.5 主范式的應(yīng)用37
1.8 命題演算的推理理論39
1.8.1 推理的基本概念39
1.8.2 判斷有效結(jié)論的方法和規(guī)則41
本章習(xí)題48
第2章 謂詞邏輯53
2.1 謂詞的基本概念53
2.2 個(gè)體、謂詞及表達(dá)式54
2.3 命題函數(shù)57
2.4 量詞59
2.5 謂詞公式與翻譯62
2.5.1 謂詞公式62
2.5.2 謂詞邏輯的翻譯63
2.6 變?cè)募s束65
2.7 謂詞公式的永真式、永假式、等價(jià)式和蘊(yùn)涵式68
2.7.1 判定方法和基本公式69
2.7.2 謂詞等價(jià)式和蘊(yùn)涵式70
2.7.3 謂詞公式的范式72
2.7.4 多個(gè)量詞的使用74
2.8 謂詞演算的推理理論76
2.8.1 4個(gè)與量詞有關(guān)的推理規(guī)則76
2.8.2 謂詞邏輯中推理的論證78
2.8.3 演算中常見的錯(cuò)誤83
本章習(xí)題84
第3章 集合及其運(yùn)算86
3.1 集合的概念與表示86
3.1.1 集合的概念86
3.1.2 集合的表示87
3.1.3 集合的相等或包含關(guān)系88
3.1.4 集合的基數(shù)90
3.2 集合的運(yùn)算90
3.3 基本的集合運(yùn)算律93
3.4 包含排斥原理99
本章習(xí)題103
第4章 二元關(guān)系105
4.1 序偶和笛卡兒乘積105
4.2 關(guān)系及其表示108
4.3 復(fù)合關(guān)系和逆關(guān)系112
4.4 關(guān)系的性質(zhì)118
4.5 關(guān)系的閉包124
4.6 等價(jià)關(guān)系132
4.7 序關(guān)系135
本章習(xí)題139
第5章 函數(shù)141
5.1 函數(shù)的概念141
5.2 函數(shù)的類型143
5.3 復(fù)合函數(shù)147
5.4 逆函數(shù)149
本章習(xí)題153
第6章 代數(shù)結(jié)構(gòu)155
6.1 代數(shù)系統(tǒng)的一般概念155
6.2 代數(shù)系統(tǒng)的運(yùn)算性質(zhì)157
6.3 代數(shù)系統(tǒng)的同態(tài)和同構(gòu)164
6.4 半群和獨(dú)異點(diǎn)168
6.5 子半群和子獨(dú)異點(diǎn)172
6.6 群和子群173
6.7 交換群和循環(huán)群181
6.8 子群的陪集及拉格朗日定理184
6.9 置換群188
6.10 環(huán)和域190
本章習(xí)題196
第7章 格和布爾代數(shù)199
7.1 格的基本概念199
7.2 格的基本性質(zhì)202
7.3 幾種特殊的格207
7.4 有界格和有補(bǔ)格212
7.5 布爾代數(shù)214
本章習(xí)題216
第8章 圖論219
8.1 圖的基本定義及相關(guān)術(shù)語(yǔ)219
8.1.1 圖的概念219
8.1.2 圖的邊點(diǎn)之間的關(guān)系221
8.1.3 圖的分類222
8.2 結(jié)點(diǎn)的度數(shù)及其計(jì)算224
8.3 子圖、補(bǔ)圖和圖的同構(gòu)227
8.3.1 子圖的概念227
8.3.2 補(bǔ)圖的概念229
8.3.3 圖的同構(gòu)概念230
8.4 通路、回路和連通性232
8.4.1 通路和回路的概念232
8.4.2 簡(jiǎn)單有向圖的連通性235
8.4.3 無(wú)向圖的連通性238
8.5 圖的矩陣表示241
8.5.1 無(wú)向圖與有向圖的關(guān)聯(lián)矩陣241
8.5.2 圖的鄰接矩陣242
8.5.3 有向圖的可達(dá)矩陣244
8.6 歐拉圖與哈密頓圖245
8.6.1 歐拉圖245
8.6.2 哈密頓圖251
8.7 路徑和關(guān)鍵路徑257
8.7.1 路徑的概念257
8.7.2 路徑在實(shí)際中的應(yīng)用259
8.7.3 歐拉圖的應(yīng)用中國(guó)郵路問(wèn)題259
8.7.4 哈密頓回路和貨郎擔(dān)問(wèn)題260
8.8 平面圖262
8.8.1 平面圖的概念262
8.8.2 平面圖的面263
8.8.3 平面圖的判定264
8.9 對(duì)偶與著色269
8.9.1 對(duì)偶的基本概念269
8.9.2 平面圖的對(duì)偶圖的做法269
8.9.3 對(duì)偶圖的性質(zhì)270
8.9.4 圖的著色271
8.9.5 地圖的著色與平面圖的點(diǎn)著色272
本章習(xí)題273
第9章 樹277
9.1 無(wú)向樹及其性質(zhì)277
9.1.1 樹的基本概念277
9.1.2 無(wú)向樹的性質(zhì)277
9.2 生成樹和小生成樹280
9.3 有向樹、根樹和二叉樹285
9.3