《離散數(shù)學》包括離散數(shù)學課程的標準內(nèi)容:數(shù)理邏輯中的命題邏輯、一階謂詞邏輯、集合論、代數(shù)系統(tǒng)、圖論等。特別是豐富了集合論的內(nèi)容,將數(shù)學歸納法、計數(shù)以及組合論中的一些廣泛應用的方法納入集合論中。另外,書末附錄中還講述了離散數(shù)學在關系數(shù)據(jù)庫中的應用。
《離散數(shù)學》力求做到簡潔明了、易懂易學,注重理論與實際的結合,注意與后續(xù)課程的銜接。適合作為普通高等院校數(shù)學、計算機科學與技術等專業(yè)的本科生教材,也可供高職高專院校的師生參考使用。
離散數(shù)學是現(xiàn)代數(shù)學的一個重要分支,是數(shù)學與應用數(shù)學、信息與計算科學及計算機科學與技術等專業(yè)的一門核心基礎課程. 旨在培養(yǎng)學生的抽象思維能力和邏輯推理能力,為后續(xù)課程打好扎實的基礎,在數(shù)學和計算機等專業(yè)領域中占有極其重要的地位.
本書的編寫是以最新的人才培養(yǎng)方案及課程大綱為依據(jù),以培養(yǎng)學生綜合能力為出發(fā)點,力求突出課程的實驗與實踐,更新課程的教學理念和方法,實現(xiàn)開拓學生創(chuàng)新能力的目的.本書包括7章及1個附錄,所涉及的內(nèi)容主要是數(shù)理邏輯、集合論、代數(shù)結構和布爾代數(shù)、圖論等四方面的內(nèi)容. 對于有些超出教學要求的內(nèi)容,均以“*”標志.限于篇幅和教學的要求,有些定理不予證明,但書后注明參考文獻以便查閱.同時,本書通過配備難度適中的典型例題,對重要概念、性質(zhì)、理論給予了比較詳細的說明,力圖把離散數(shù)學的經(jīng)典理論和思想介紹給學生. 本書還配備了適量的練習題,以培養(yǎng)學生解決問題的能力.
本書區(qū)別于其他同類書籍的鮮明特點是:將組合論、可計數(shù)理論的部分基礎知識放進本書中,從而在內(nèi)容上具有新穎性和實用性. 它既注重基礎與能力的結合、理論與實踐的結合,又關注當前與未來的結合、專業(yè)與普及的結合. 全書具有結構合理、內(nèi)容系統(tǒng)、闡釋新穎的特點. 本書是在所有編者兩年多的共同努力下,在多年教學講義的基礎上精心編寫而成,力求做到取材詳略得當,敘述清楚流暢,論證科學嚴謹,釋例、練習精選獨到.因此,全書具有較好的科學性、應用性和可讀性.
本書第1~3章由孫杰編寫,第4、5、7章及附錄由金玉蘋編寫,第6章由季丹丹編寫,王嵐和張型岱教授提供了全書基礎材料及最后的校對整理工作. 本書的出版得到了牡丹江師范學院教學建設經(jīng)費的資助,同時還得到了牡丹江師范學院教學改革項目(11-XJ12018)經(jīng)費的資助. 本書已經(jīng)被評為牡丹江師范學院“十二五”規(guī)劃教材的重點建設教材. 在此,編者向那些給予我們幫助的各級領導、老師、同事表示衷心的感謝!由于編者水平有限,疏漏之處在所難免,還請各位讀者不吝批評指正.
王 嵐2012年1月于牡丹江
第1章 集合論
1.1 集合的概念與運算
1.1.1 集合的概念
1.1.2 集合之間的關系
1.1.3 集合的運算
1.1.4 集合的運算性質(zhì)
1.1.5 序偶與笛卡兒積
1.2 二元關系
1.2.1 二元關系及其表示
1.2.2 二元關系的運算
1.3 關系的性質(zhì)
1.4 關系的閉包運算
1.5 序關系
1.6 等價關系
1.7 映射
1.8 數(shù)學歸納法
1.9 計數(shù)
1.9.1 帕斯卡三角形和二項式定理
1.9.2 鴿巢原理
1.9.3 乘法法則和加法法則
1.9.4 排列和組合
1.10 排列組合生成算法
1.11 離散概率簡介
習題1
第2章 命題邏輯
2.1 命題與聯(lián)結詞
2.1.1 命題與真值
2.1.2 命題聯(lián)結詞
2.2 命題公式、指派及真值表
2.2.1 命題公式
2.2.2 命題的符號化
2.2.3 公式的指派(賦值)及真值表
2.3 命題公式的等值式,蘊含關系式
2.3.1 命題公式的等值式
2.3.2 代入規(guī)則與替換規(guī)則
2.3.3 對偶式
2.3.4 蘊含關系式
2.4 主析取范式和主合取范式
2.4.1 合取范式與析取范式
2.4.2 主范式
2.5 聯(lián)結詞完備集
2.6 可滿足性問題與消解法
2.7 推理的形式結構
2.8 自然推理系統(tǒng)n中的形式證明
習題
第3章 謂詞邏輯
3.1 基本概念
3.1.1 個體詞、謂詞
3.1.2 量詞
3.2 一階邏輯公式及解釋
3.3 一階邏輯等值式
3.4 前束范式與斯科林范式
3.4.1 前束范式
3.4.2 斯科林范式
3.5 謂詞演算的推理理論
3.6 數(shù)理邏輯在計算機科學中的應用
3.6.1 “鑰匙在點火開關中”報警蜂鳴器
3.6.2 構造自鎖控制安全帶的電路
3.6.3 構造一個拿子游戲裝置
3.6.4 構造電路: 專用裝置和程序化計算機
習題3
第4章 公理系統(tǒng)下的形式證明
4.1 命題邏輯的公理推理系統(tǒng)
4.1.1 公理推理系統(tǒng)p
4.1.2 公理推理系統(tǒng)p的可靠性、和諧性和完備性
4.2 謂詞邏輯的公理系統(tǒng)
4.3 定理的機器證明
第5章 圖論
5.1 圖的基本概念
5.1.1 圖及其圖形表示
5.1.2 頂點的度
5.1.3 完全圖和補圖
5.1.4 子圖
5.1.5 圖的同構
5.2 通路、回路與連通性
5.2.1 通路和回路
5.2.2 無向圖的連通性
5.2.3 有向圖的連通性
5.2.4 門格定理
5.3 歐拉圖與中國郵遞員問題
5.3.1 哥尼斯堡七橋問題
5.3.2 歐拉圖
5.3.3 中國郵遞員問題
5.4 哈密爾頓圖與旅行售貨商問題
5.4.1 哈密爾頓圖
5.4.2 旅行售貨商問題
5.5 樹
5.5.1 樹的定義及其基本性質(zhì)
5.5.2 生成樹
5.5.3 最小生成樹問題
5.5.4 根樹及其應用
5.6 圖的矩陣表示
5.6.1 關聯(lián)矩陣
5.6.2 鄰接矩陣
5.6.3 可達矩陣
5.6.4 圖的運算
5.7 平面圖與圖的著色
5.7.1 平面圖
5.7.2 對偶圖與圖著色
習題5
第6章 代數(shù)系統(tǒng)
6.1 二元運算與代數(shù)系統(tǒng)
6.1.1 二元運算
6.1.2 代數(shù)系統(tǒng)
6.2 群和半群
6.2.1 群和半群的定義
6.2.2 關于逆元的性質(zhì)
6.2.3 群的幾個等價性質(zhì)
6.3 子群和元素的階
6.3.1 子群
6.3.2 元素的階
6.4 循環(huán)群和生成群、群的同構
6.4.1 循環(huán)群和生成群
6.4.2 群的同構
6.4.3 循環(huán)群的性質(zhì)
6.5 變換群和置換群、凱萊定理
6.5.1 置換群
6.5.2 凱萊定理
6.6 子群的陪集和拉格朗日定理
6.6.1 子群的陪集
6.6.2 子群的指數(shù)和拉格朗日定理
6.7 正規(guī)子群和商群
6.7.1 正規(guī)子群的概念
6.7.2 正規(guī)子群的性質(zhì)
6.7.3 商群
6.8 共軛元和共軛子群
6.8.1 中心和中心化子
6.8.2 共軛元和共軛類
6.8.3 共軛子群與正規(guī)化子
6.9 群的同態(tài)
6.9.1 群的同態(tài)定義
6.9.2 同態(tài)基本定理
6.10 環(huán)與域
6.11 代數(shù)系統(tǒng)在計算機科學中的應用
6.11.1 通信模型的基本概念
6.11.2 糾錯編碼的基本概念
6.11.3 線性分組碼和漢明碼
習題6
第7章 格與布爾代數(shù)
7.1 格
7.2 格同態(tài)
7.3 分配格和有補格
7.4 布爾代數(shù)
7.5 布爾函數(shù)及其表達式
習題7
附錄a 離散數(shù)學在關系數(shù)據(jù)庫中的應用
a.1 關系數(shù)據(jù)庫簡介
a.2 關系代數(shù)與數(shù)據(jù)子語言
參考文獻