定 價：30 元
叢書名：高等學校計算機專業(yè)教材精選·數(shù)理基礎(chǔ)
- 作者：周忠榮
- 出版時間：2007/12/1
- ISBN：9787302165743
- 出 版 社：清華大學出版社
- 中圖法分類：O158
- 頁碼：
- 紙張：膠版紙
- 版次：1
- 開本：16
本書系統(tǒng)闡述了離散數(shù)學的經(jīng)典內(nèi)容，包括命題邏輯、謂詞邏輯、集合、關(guān)系、代數(shù)系統(tǒng)、圖論等方面的基本知識。本書根據(jù)計算機科學各專業(yè)的需要選擇內(nèi)容、把握尺度，盡可能將離散數(shù)學知識和計算機科學中的實際問題相結(jié)合。本書編排新穎，每章通過定義、定理、實例、例等形式將內(nèi)容有機結(jié)合、融會貫通，達到學練兼顧的目的。本書加入了機上實現(xiàn)內(nèi)容，滿足了普通高校理工類本科生的實際需求。
本書書末還提供了離散數(shù)學常用符號、中英文名詞術(shù)語對照表、英中文名詞術(shù)語對照表以及習題答案與提示，能很好地幫助讀者理解和學習。
本書既可作為應用型本科和高職高專院校計算機科學各專業(yè)的教材，也可作為工程技術(shù)人員的參考書。
離散數(shù)學是研究離散量的結(jié)構(gòu)及相互關(guān)系的數(shù)學科學，是現(xiàn)代數(shù)學的一個重要分支。由于計算機只能處理離散的數(shù)量關(guān)系，所以離散數(shù)學是計算機科學各專業(yè)最重要的專業(yè)基礎(chǔ)課之一。隨著計算機科學的發(fā)展，離散數(shù)學作為計算機科學的一種數(shù)學工具，其作用日益重要。同時，離散數(shù)學還是計算機科學許多專業(yè)課程的基礎(chǔ)，其基本概念、基本理論和基本方法在數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、軟件工程、程序設(shè)計語言、算法設(shè)計與分析、計算機網(wǎng)絡(luò)、通信與接口、多媒體技術(shù)、數(shù)據(jù)庫管理系統(tǒng)、人工智能、形式語言與自動機、數(shù)字電路等課程中有廣泛的應用。
應用型本科培養(yǎng)計算機技術(shù)方面的應用型高級技術(shù)人才。這種類型的人才既需要懂得離散數(shù)學的基本概念和基本理論，更需要掌握離散數(shù)學的基本方法和實際應用。
由于各院校計算機專業(yè)培養(yǎng)目標不同，因而對離散數(shù)學知識有不同的要求。已經(jīng)出版的不同版本的離散數(shù)學教材不僅包含的數(shù)學分支不完全一樣，而且各部分的廣度差別較大，難度也顯著不同。本教材是在已出版的同類教材的基礎(chǔ)上繼續(xù)探索和創(chuàng)新的結(jié)果，相信會滿足不同讀者的需要。
本教材編者有著長期從事離散數(shù)學課程教學的豐富經(jīng)驗，熟悉多門計算機科學專業(yè)課程。為了編寫出有特色的高質(zhì)量教材，編者多次向計算機科學方面的專家、學者請教，深入了解計算機科學各專業(yè)所需的離散數(shù)學知識。在此基礎(chǔ)上確定了本教材的下列編寫原則：
(1) 根據(jù)計算機科學各專業(yè)對離散數(shù)學知識的基本要求確定內(nèi)容的廣度和深度。
本教材包括命題邏輯、謂詞邏輯、集合、關(guān)系、代數(shù)系統(tǒng)、圖論6個分支，涵蓋了離散數(shù)學的主要分支。每個分支都包括了基本內(nèi)容，并嚴格把握其廣度和深度。凡是重要的基本概念、基本方法不惜篇幅講透徹，例題和習題恰當?shù)乜刂屏穗y度和深度。
針對應用型本科的培養(yǎng)目標，本教材編寫了以下3個有特色的內(nèi)容： ①第1章介紹了離散數(shù)學必需的基礎(chǔ)知識； ②第8章介紹了幾個主要算法的偽代碼； ③附錄A、附錄B、附錄C收錄了離散數(shù)學的常用符號及中英文、英中文名詞術(shù)語對照表。這些內(nèi)容對應用型本科學生的學習很有幫助。
(2) 便于學生閱讀理解。
針對應用型本科學生的實際水平和認知能力，本教材在編寫方式上采取了以下3個措施，期望有助于讀者閱讀理解： ①盡可能先通過實例提出問題，再介紹有關(guān)定義、定理和概念，或者隨后附加實例對有關(guān)概念的各個方面進行補充說明； ②對較難理解的概念，充分利用圖形、圖像和通俗的語言予以說明； ③對基本概念、重要定理、重要公式和解題方法，不惜篇幅，敘述清楚。
(3) 與專業(yè)知識相結(jié)合。
各章節(jié)都盡可能編寫了本部分內(nèi)容在計算機科學中的實際應用，使離散數(shù)學親近專業(yè)。本教材突出培養(yǎng)學生運用離散數(shù)學知識解決與計算機科學相關(guān)的實際問題的能力。
本教材力求做到： 深入淺出、概念準確、知識結(jié)構(gòu)完整。
本教材采用了周忠榮編著、清華大學出版社出版的《計算機數(shù)學》中的相關(guān)內(nèi)容，特此說明。
為了便于讀者理解和注意，本教材使用了一些特殊的表達方式：
(1) 重要數(shù)學名詞在第一次出現(xiàn)時以黑體字標出。如： 集合.
(2) 重要的問題以【說明】的方式給出。
(3) 定理、推論、說明和一些重要結(jié)論都用楷體字表述。如： 一個關(guān)系可以既不是對稱的，也不是反對稱的。
本教材的編寫得到了廣州大學華軟軟件學院鄒婉玲副院長、徐祥副院長、教務處麥才淞處長、網(wǎng)絡(luò)技術(shù)系黃友謙主任、軟件工程系黃思曾主任的全力支持和指導，編者對他們表示感謝。
本教材由周忠榮（第5, 7, 8章和附錄），林偉初（第2章），江定漢（第6章），袁燕（第1, 4章），周志軒（第3章）編寫。周忠榮為全書擬訂了詳細的編寫提綱和要求，并負責統(tǒng)一修改、定稿。江定漢、周志軒審閱了部分章節(jié)的初稿，數(shù)學教研室的各位教師也給予了積極支持和幫助。
編者期望本教材能得到廣大教師和學生的歡迎，能對離散數(shù)學課程的改革做些貢獻。本教材雖經(jīng)多次修改，但因編寫時間緊迫、編者水平有限，書中疏漏、差錯難免，懇請讀者批評指正。希望本教材在廣大教師和學生的建議和幫助下得到不斷的改進和完善。編者的E-mail地址是：zzr@tsinghua.org.cn.
第1章 基礎(chǔ)知識1
1.1 集合的初步知識1
1.2 數(shù)學歸納法1
1.3 整數(shù)的基本性質(zhì)2
1.3.1 整除2
1.3.2 素數(shù)3
1.3.3 帶余除法4
1.3.4 最大公約數(shù)5
1.3.5 最小公倍數(shù)7
1.3.6 模運算8
1.3.7 同余的應用10
1.4 序列的基本知識11
1.4.1 序列11
1.4.2 典型的整數(shù)序列12
1.4.3 序列求和13
1.5 計數(shù)15
1.5.1 加法原理和乘法原理15
1.5.2 排列與組合17
1.5.3 二項式定理21
1.5.4 鴿巢原理22
1.6 矩陣的初步知識23
1.6.1 矩陣的概念23
1.6.2 矩陣的加法和數(shù)乘25
1.6.3 矩陣的乘法26
1.6.4 轉(zhuǎn)置矩陣和逆矩陣27
1.7 本章小結(jié)28
1.8 習題28
第2章 命題邏輯31
2.1 命題與聯(lián)結(jié)詞31
2.1.1 命題31
2.1.2 邏輯聯(lián)結(jié)詞33
2.1.3 聯(lián)結(jié)詞的優(yōu)先級37
2.1.4 命題符號化37
2.1.5 邏輯運算在計算機中的直接運用39
2.2 命題公式與等價演算41
2.2.1 命題公式及其層次41
2.2.2 命題公式的賦值42
2.2.3 等價式與等價演算45
2.2.4 等價演算的實際應用48
2.3 聯(lián)結(jié)詞的擴充與聯(lián)結(jié)詞完備集49
2.3.1 聯(lián)結(jié)詞的擴充49
2.3.2 與非、或非、異或的性質(zhì)51
2.3.3 聯(lián)結(jié)詞完備集52
2.4 范式53
2.4.1 析取范式與合取范式53
2.4.2 主析取范式與主合取范式57
2.4.3 主范式的作用62
2.4.4 用主范式解答實際問題63
2.5 命題邏輯推理66
2.5.1 推理的形式結(jié)構(gòu)66
2.5.2 推理的證明方法68
2.5.3 命題邏輯推理的實際應用71
2.6 本章小結(jié)72
2.7 習題73
第3章 謂詞邏輯76
3.1 謂詞邏輯的基本概念76
3.1.1 個體和謂詞76
3.1.2 量詞78
3.1.3 特性謂詞80
3.1.4 謂詞邏輯符號化81
3.2 謂詞公式與翻譯82
3.2.1 謂詞公式82
3.2.2 謂詞邏輯的翻譯83
3.3 變元的約束86
3.3.1 約束變元和自由變元86
3.3.2 約束變元的換名規(guī)則87
3.3.3 自由變元的代替規(guī)則88
3.4 謂詞公式的解釋與分類89
3.4.1 謂詞公式的解釋89
3.4.2 謂詞公式的分類90
3.5 謂詞邏輯的等價式和前束范式91
3.5.1 謂詞邏輯等價式91
3.5.2 前束范式94
3.6 謂詞邏輯推理95
3.6.1 推理定律95
3.6.2 推理規(guī)則97
3.6.3 謂詞邏輯推理例題98
3.7 程序正確性證明100
3.8 本章小結(jié)102
3.9 習題102
第4章 集合106
4.1 集合的基本概念106
4.1.1 集合及其表示方法106
4.1.2 集合間的關(guān)系108
4.1.3 特殊集合109
4.1.4 有限冪集元素的編碼表示110
4.2 集合的基本運算111
4.3 集合恒等式113
4.4 集合的劃分與覆蓋115
4.5 有窮集合的計數(shù)117
4.6 本章小結(jié)118
4.7 習題119
第5章 關(guān)系121
5.1 關(guān)系的概念與表示121
5.1.1 笛卡兒積121
5.1.2 二元關(guān)系的概念123
5.1.3 關(guān)系矩陣和關(guān)系圖125
5.2 復合關(guān)系和逆關(guān)系127
5.2.1 復合關(guān)系127
5.2.2 逆關(guān)系130
5.3 關(guān)系的性質(zhì)131
5.4 關(guān)系的閉包135
5.5 等價關(guān)系和偏序關(guān)系136
5.5.1 等價關(guān)系136
5.5.2 偏序關(guān)系138
5.5.3 字典排序和拓撲排序141
5.6 函數(shù)143
5.6.1 函數(shù)的基本概念143
5.6.2 復合函數(shù)和逆函數(shù)145
5.6.3 幾個重要的函數(shù)147
5.7 二元關(guān)系的應用148
5.7.1 等價關(guān)系的應用149
5.7.2 函數(shù)的應用149
5.8 多元關(guān)系及其應用149
5.8.1 多元關(guān)系149
5.8.2 關(guān)系數(shù)據(jù)庫151
5.9 本章小結(jié)153
5.10 習題153
第6章 代數(shù)系統(tǒng)155
6.1 二元運算及其性質(zhì)155
6.1.1 二元運算與一元運算155
6.1.2 二元運算的性質(zhì)與特殊元素157
6.1.3 代數(shù)系統(tǒng)簡介162
6.1.4 典型例題分析163
6.2 半群與群164
6.2.1 半群、獨異點與群164
6.2.2 冪167
6.2.3 群的性質(zhì)168
6.2.4 典型例題分析170
6.3 子群、循環(huán)群與置換群170
6.3.1 元素的周期170
6.3.2 子群171
6.3.3 循環(huán)群173
6.3.4 置換群176
6.4 陪集和正規(guī)子群178
6.4.1 陪集178
6.4.2 正規(guī)子群180
6.4.3 典型例題分析181
6.5 群的同態(tài)與同構(gòu)182
6.5.1 基本概念182
6.5.2 基本性質(zhì)183
6.6 環(huán)和域184
6.6.1 環(huán)184
6.6.2 域187
6.7 格187
6.7.1 格的定義187
6.7.2 格的性質(zhì)189
6.7.3 幾種特殊的格191
6.8 布爾代數(shù)193
6.8.1 布爾代數(shù)及其性質(zhì)193
6.8.2 布爾函數(shù)與布爾表達式196
6.9 應用實例196
6.9.1 門電路196
6.9.2 邏輯電路設(shè)計197
6.10 本章小結(jié)199
6.11 習題200
第7章 圖論204
7.1 圖的基本概念204
7.1.1 圖的定義204
7.1.2 特殊的圖207
7.1.3 子圖208
7.1.4 結(jié)點的度209
7.2 圖的連通性211
7.2.1 路徑和回路211
7.2.2 無向圖的連通性212
7.2.3 有向圖的連通性212
7.2.4 歐拉圖213
7.2.5 哈密頓圖217
7.2.6 帶權(quán)圖的最短路217
7.3 圖的矩陣表示219
7.3.1 無向圖的關(guān)聯(lián)矩陣219
7.3.2 有向圖的關(guān)聯(lián)矩陣220
7.3.3 有向圖的鄰接矩陣220
7.3.4 無向圖的鄰接矩陣221
7.4 樹222
7.4.1 無向樹與生成樹222
7.4.2 有向樹224
7.4.3 最優(yōu)二元樹226
7.4.4 前綴碼228
7.4.5 樹的遍歷230
7.5 本章小結(jié)231
7.6 習題232
第8章 算法與偽代碼234
8.1 算法概述234
8.2 判斷素數(shù)算法236
8.3 求最大數(shù)算法236
8.4 求最大公約數(shù)的歐幾里得算法237
8.5 求拓撲排序的算法237
8.6 求歐拉路的Fleury算法239
8.7 求最短路徑的Dijkstra算法240
8.8 求最小生成樹的Prim算法241
8.9 求最優(yōu)二元樹的Huffman算法243
附錄A 離散數(shù)學常用符號245
附錄B 中英文名詞術(shù)語對照表250
附錄C 英中文名詞術(shù)語對照表263
附錄D 習題答案與提示275
參考文獻286
書單推薦
