離散數(shù)學(xué)

前言

顧名思義，離散數(shù)學(xué)是研究離散對(duì)象及其相互間關(guān)系的一個(gè)數(shù)學(xué)分支，它的基本內(nèi)容已出現(xiàn)在現(xiàn)代科學(xué)技術(shù)的各個(gè)領(lǐng)域。例如，計(jì)算機(jī)科學(xué)、程序設(shè)計(jì)、計(jì)算機(jī)網(wǎng)絡(luò)、信息論與編碼、通信理論、現(xiàn)代密碼學(xué)、數(shù)字信號(hào)處理和形式語言等都與離散數(shù)學(xué)密切相關(guān)。正因?yàn)槿绱?，離散數(shù)學(xué)在國際上已受到高度重視，在我國也已成為理工科高等院校各專業(yè)的重要基礎(chǔ)課，尤其是計(jì)算機(jī)和應(yīng)用數(shù)學(xué)專業(yè)。離散數(shù)學(xué)的內(nèi)容非常廣泛，它至少包含了數(shù)理邏輯、集合論、代數(shù)學(xué)、組合數(shù)學(xué)、數(shù)論、圖論、計(jì)算理論和復(fù)雜性理論、復(fù)雜網(wǎng)絡(luò)以及協(xié)同網(wǎng)絡(luò)計(jì)算等內(nèi)容。這些內(nèi)容里面又細(xì)分了許多個(gè)分支學(xué)科，包含了當(dāng)前國際前沿的數(shù)學(xué)和科學(xué)技術(shù)理論研究課題。在已出版的眾多離散數(shù)學(xué)教科書及其習(xí)題解答中，大部分都是介紹那些應(yīng)用廣泛且易理解、可接受的基本知識(shí)和方法。我們也出版了一本《離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)》，該書的寫作風(fēng)格類似于國外流行的Schaum’s Outline Series教材，在內(nèi)容上則增加了“密碼學(xué)”或“信息安全理論”的數(shù)學(xué)基礎(chǔ)內(nèi)容，使離散數(shù)學(xué)的基本內(nèi)容有了一些擴(kuò)展。而本書是在《離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)》的基礎(chǔ)上編寫的一本適應(yīng)面廣、內(nèi)容適中的離散數(shù)學(xué)教材。全書共五篇，依次為數(shù)理邏輯、集合論、代數(shù)系統(tǒng)、組合分析與算法數(shù)論、圖論，分成14章：命題邏輯，謂詞邏輯，集合，關(guān)系，函數(shù)，半群、語言和自動(dòng)機(jī)，群、環(huán)和域，格與布爾代數(shù)，組合分析，算法數(shù)論，無向圖，平面圖與圖著色，有向圖，樹。各章都盡量安排了“應(yīng)用”，試圖讓學(xué)生學(xué)以致用。其中，有些應(yīng)用是對(duì)科技進(jìn)步產(chǎn)生重要作用的，例如，自動(dòng)定理證明、數(shù)字電路、語言與有限自動(dòng)機(jī)、基于身份的密碼設(shè)計(jì)等；有些應(yīng)用在科學(xué)理論上意義重大，例如，超越數(shù)無窮的集合論證明等。另外，第10章（算法數(shù)論）還引進(jìn)了最新的研究成果，特別是近幾年才產(chǎn)生的“雙線性配對(duì)與基于身份的密碼”，供讀者選學(xué)。

內(nèi)容概要

　　全書共14章，第1～2章為數(shù)理邏輯，第3～5章為集合論，第6～8章為代數(shù)系統(tǒng)，第9～10章為組合分析與算法數(shù)論，第11～14章為圖論。每部分內(nèi)容盡量由淺人深，同時(shí)都盡量安排了“應(yīng)用”，試圖讓讀者懂得“學(xué)以致用”。其中有些應(yīng)用對(duì)科技進(jìn)步產(chǎn)生重要作用，有些應(yīng)用在科學(xué)理論上意義重大。　　本書內(nèi)容豐富翔實(shí)，條理清晰，可作為高等院校計(jì)算機(jī)、電類及相關(guān)專業(yè)“離散數(shù)學(xué)”課程的教材，也可作為相關(guān)科研人員的參考書。

作者簡(jiǎn)介

董曉蕾，2001年在哈爾濱工業(yè)大學(xué)獲理學(xué)博士學(xué)位，同年到上海交通大學(xué)做博士后，2003年出站留校。主要研究數(shù)論、密碼學(xué)和可信計(jì)算等，發(fā)表40余篇學(xué)術(shù)論文，其中SCI和EI檢索的論文有30余篇（次）。主持國家自然科學(xué)基金等多項(xiàng)科研項(xiàng)目，獲得教育部和上海市自然科學(xué)一、二等獎(jiǎng)各一項(xiàng)。曾赴日本筑波大學(xué)和香港浸會(huì)大學(xué)訪問研究。曹珍富，上海交通大學(xué)電信學(xué)院一級(jí)責(zé)任教授、博士生導(dǎo)師。中科院青年獎(jiǎng)勵(lì)研究基金、國家杰出青年基金和國務(wù)院政府特殊津貼獲得者。主要研究數(shù)論、密碼學(xué)和通信網(wǎng)安全等。1981年以來發(fā)表300多篇期刊論文，被SCI和EI檢索的分別超過100和130篇，出版5部著作。主持國家和省部級(jí)科研項(xiàng)目40余項(xiàng)，獲得省部級(jí)獎(jiǎng)7項(xiàng)。曾6次去日本、中國香港和中國臺(tái)灣等地的大學(xué)訪問研究或講學(xué)。

書籍目錄

出版者的話序言前言教學(xué)建議第一篇 數(shù)理邏輯第1章 命題邏輯1.1 命題與聯(lián)結(jié)詞1.1.1 命題基本概念1.1.2 命題聯(lián)結(jié)詞1.1.3 復(fù)合命題1.2 命題公式1.2.1 定義1.2.2 賦值1.2.3 真值表技術(shù)1.3 等值演算1.3.1 基本等值式1.3.2 等值演算過程1.3.3 對(duì)偶公式和內(nèi)否公式1.4 命題公式的范式1.4.1 析取范式和合取范式1.4.2 主范式1.5 聯(lián)結(jié)詞的功能完全集1.5.1 真值函數(shù)1.5.2 功能完全集1.6 永真蘊(yùn)涵式1.6.1 基本永真蘊(yùn)涵式1.6.2 證明永真蘊(yùn)涵式的方法1.7 命題邏輯推理1.8 命題邏輯歸結(jié)推理法1.9 命題邏輯推理的機(jī)械化方法第2章 謂詞邏輯2.1 謂詞邏輯的基本概念2.1.1 謂詞的概念2.1.2 量詞的概念2.2 謂詞邏輯公式2.2.1 合式公式2.2.2 約束變?cè)妥杂勺冊(cè)?.2.3 賦值2.2.4 換名規(guī)則和替換規(guī)則2.3 謂詞邏輯的等值演算與前束范式2.3.1 基本等值式2.3.2 前束范式2.4 Skolem 標(biāo)準(zhǔn)型2.4.1 前束范式2.4.2 無前束范式2.5 謂詞邏輯的推理理論2.5.1 基本永真蘊(yùn)涵式2.5.2 推理規(guī)則2.5.3 推理實(shí)例2.6 謂詞邏輯的歸結(jié)推理法2.6.1 歸結(jié)證明過程2.6.2 歸結(jié)證明實(shí)例第二篇 集合論第3章 集合3.1 集合的定義3.2 集合的基本運(yùn)算3.3 有限集合的計(jì)數(shù)3.4 集合表達(dá)式的相等與包含3.5 集合的特征函數(shù)第4章 關(guān)系4.1 二元關(guān)系4.2 二元關(guān)系的表示及按性質(zhì)分類4.2.1 二元關(guān)系的關(guān)系矩陣和關(guān)系圖表示4.2.2 二元關(guān)系的按性質(zhì)分類4.3 二元關(guān)系的運(yùn)算4.4 二元關(guān)系的合成4.5 關(guān)系的閉包4.6 等價(jià)關(guān)系和偏序關(guān)系4.6.1 等價(jià)關(guān)系4.6.2 偏序關(guān)系第5章 函數(shù)5.1 函數(shù)的基本概念5.2 函數(shù)的性質(zhì)5.3 函數(shù)的復(fù)合與反函數(shù)5.4 可逆函數(shù)集與置換5.5 二元運(yùn)算5.6 基數(shù)第三篇 代數(shù)系統(tǒng)第6章 半群、語言和自動(dòng)機(jī)6.1 半群與語言6.2 語言和文法6.3 有限狀態(tài)機(jī)6.4 有限狀態(tài)自動(dòng)機(jī)6.5 語言與自動(dòng)機(jī)的關(guān)系第7章 群、環(huán)和域7.1 群的基本概念7.2 子群7.3 群的同態(tài)與同構(gòu)7.4 子群的陪集7.5 對(duì)稱群、置換群、正規(guī)性與商群7.6 群在集合上的作用7.7 同態(tài)基本定理與同構(gòu)定理7.8 環(huán)的基本概念7.9 子環(huán)、理想與商環(huán)7.10 交換環(huán)中的因子分解7.11 多項(xiàng)式環(huán)7.12 多項(xiàng)式環(huán)的因子分解7.13 域的基本概念7.14 分裂域7.15 有限域第8章 格與布爾代數(shù)8.1 格的概念8.2 分配格8.3 有補(bǔ)格8.4 布爾代數(shù)8.5 布爾表達(dá)式8.6 數(shù)字電路與最小化第四篇 組合分析與算法數(shù)論第9章 組合分析9.1 計(jì)數(shù)9.2 排列與組合9.3 遞推序列9.4 抽屜原理9.5 生成函數(shù)第10章 算法數(shù)論10.1 整數(shù)論10.2 與整數(shù)有關(guān)的典型算法10.3 素性測(cè)試、因數(shù)分解與公鑰密碼學(xué)10.3.1 素性測(cè)試10.3.2 因數(shù)分解10.3.3 公鑰密碼10.4 有限域上的橢圓曲線算術(shù)和ECC10.5 配對(duì)和基于身份的公鑰密碼體制10.5.1 雙線性配對(duì)10.5.2 基于身份的密碼第五篇 圖論第11章 無向圖11.1 無向圖的基本概念11.2 無向圖的表示11.3 無向圖的連通性11.4 歐拉圖與哈密頓圖11.4.1 歐拉圖11.4.2 哈密頓圖11.5 最短通道問題第12章 平面圖與圖著色12.1 平面圖的基本概念12.2 歐拉公式和極大平面圖12.3 平面圖的對(duì)偶圖12.4 圖著色第13章 有向圖13.1 有向圖的基本概念13.2 有向圖的連通性第14章 樹14.1 基本定義和性質(zhì)14.2 生成樹與最小生成樹14.3 有根樹14.4 二叉樹和哈夫曼樹參考文獻(xiàn)

章節(jié)摘錄

第1章 命題邏輯本章介紹命題邏輯的基本知識(shí)、基本思想和方法。命題邏輯又稱命題演算，是以命題為研究對(duì)象、以推理中前提和結(jié)論之間的形式關(guān)系為研究目的的邏輯學(xué)科，包括命題與聯(lián)結(jié)詞、命題公式（特別是真值表技術(shù)）、等值演算、命題公式的范式、聯(lián)結(jié)詞的功能完全集、永真蘊(yùn)涵式、命題邏輯的推理理論、命題邏輯推理的機(jī)械化方法等。1.1 命題與聯(lián)結(jié)詞1.1.1 命題基本概念命題對(duì)于命題邏輯來說是一個(gè)原始的概念，因此不能在命題邏輯的范圍內(nèi)給出它的精確定義，只能描述它的性質(zhì)?！径x1.1】在經(jīng)典命題邏輯中，把能判斷真假但不能既真又假的陳述句的內(nèi)容稱為命題。命題必須為陳述句的內(nèi)容，而不是陳述語句。有關(guān)語句的介紹可見第6章。為了說明命題是陳述語句的內(nèi)容，通常在陳述語句外面加引號(hào)來表示命題。例如，陳述語句：3是素?cái)?shù)。構(gòu)成的命題是“3是素?cái)?shù)”，即3是素?cái)?shù)是語句（不是命題），“3是素?cái)?shù)”是命題。命題必須具有真假值。疑問句、祈使句、感嘆句的內(nèi)容沒有真假之分，所以它們不是命題。例如，“北京是中國的首都”是命題；“關(guān)門！”，“你上哪里？”這種命令和問話語句其內(nèi)容不能判斷真假，所以不是命題；“太陽系外有外星人”，目前人類尚無法確定其真假，但從事物的本質(zhì)而論，該語句的內(nèi)容是可分辨真假的，所以它也是命題。

編輯推薦

《離散數(shù)學(xué)》具有以下特點(diǎn)：講解透徹：深入淺出地介紹離散數(shù)學(xué)所包含的基本知識(shí)。內(nèi)容新穎：融合了作者自己的理解、體會(huì)、方法和結(jié)果。注重應(yīng)用：介紹了一些相關(guān)知識(shí)在現(xiàn)代科學(xué)技術(shù)領(lǐng)域的應(yīng)用。〈br〉習(xí)題適中：便于學(xué)生鞏固所學(xué)知識(shí)、加深理解，學(xué)以致用。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    離散數(shù)學(xué) PDF格式下載

---