了得網自然科學_離散數學基礎及實驗教程（第3版）

編輯推薦

《離散數學基礎及實驗教程（第3版）》有以下特點：
(1) 簡單易學：隻要求學生學過高等數學，不需要更多的預備知識，寫作風格深入淺出，理論適中，實例豐富，便於自學。
(2) 實用性強：注重離散數學作為計算機科學專業的數學基礎，強調與本專業後續課程的關繫，所舉例子盡量與專業相關。
(3) 定位明確：適合地方二本院校和獨立學院學生使用。

內容簡介

本書對計算機類專業在本科階段*需要的離散數學基礎知識做了繫統的介紹，力求概念清晰，注重實際應用。全書共分8章，內容包括準備知識（集合、整數、序列和遞推關繫、矩陣），數理邏輯，計數（組合數學），關繫，布爾代數，圖論（圖、樹、圖和樹的有關算法）及對應的離散數學實驗等，並含有較多的與計算機類專業有關的例題和習題。
本書敘述簡潔、深入淺出、注重實踐和應用，主要面向地方院校和獨立學院計算機類專業的本科學生，也可以作為大學非計算機類專業學生的選修課教材和計算機應用技術人員的自學參考書。

目錄

第1章準備知識

1.1集合

1.1.1集合的基本概念

1.1.2集合的基本運算和性質

1.1.3集合的笛卡兒積
目錄

第1章準備知識

1.1集合

1.1.1集合的基本概念

1.1.2集合的基本運算和性質

1.1.3集合的笛卡兒積

1.1.4集合的計算機表示

1.2整數

1.2.1整除

1.2.2公約數和小公倍數

1.2.3模運算

1.3序列和遞推關繫

1.3.1序列

1.3.2序列求和

1.3.3遞推關繫

1.4矩陣

1.4.1矩陣的概念

1.4.2矩陣的運算

1.4.3布爾矩陣

習題1

第2章數理邏輯

2.1命題及聯結詞

2.1.1命題的概念

2.1.2命題聯結詞

2.2命題公式和分類

2.2.1和命題公式

2.2.2命題公式的賦值和真值表

2.2.3命題公式的類型

2.3等值演算與範式

2.3.1等價和基本等價式

2.3.2等值演算

2.3.3範式

2.4命題邏輯的推理理論

2.4.1推理的形式結構

2.4.2演繹法證明推理

2.5謂詞邏輯基礎

2.5.1謂詞邏輯的基本概念

2.5.2謂詞公式及其解釋

2.6謂詞邏輯等值式與範式

2.6.1謂詞邏輯等值式

2.6.2前束範式

2.7謂詞邏輯的推理理論

2.7.1有關量詞的基本蘊涵式

2.7.2有關量詞的推理規則

習題2

第3章計數

3.1基本計數、排列與組合

3.1.1基本的計數原則

3.1.2排列與組合

3.2排列組合的進一步討論

3.2.1圓周排列

3.2.2有重復的排列

3.2.3有重復的組合

3.3生成排列和組合

3.3.1生成排列

3.3.2生成組合

3.4生成函數及其應用

3.4.1生成函數的定義

3.4.2生成函數求解計數問題

3.4.3使用生成函數求解遞推關繫

3.5鴿巢原理

3.5.1一般的鴿巢原理

3.5.2推廣的鴿巢原理

3.6容斥原理

3.6.1容斥原理簡介

3.6.2容斥原理的應用

習題3

第4章關繫

4.1關繫定義及其表示

4.1.1關繫的基本概念

4.1關繫的表示

4.2關繫的運算

4.2.1關繫的合成

4.2.2逆運算

4.3關繫的性質

4.3.1自反性與反自反性

4.3.2對稱性與反對稱性

4.3.3傳遞關繫

4關繫及其應用

4.5關繫的閉包

4.5.1閉包的概念和求法

4.5.2Warshall算法

4.6等價關繫

4.6.1等價關繫與等價類

4.6.2等價關繫與劃分

4.7偏序關繫

4.7.1偏序關繫和哈斯圖

4.7.2極值和值

4.7.3拓撲排序

4.8函數

4.8.1函數的定義

4.8.2函數的類型

4.8.3函數的運算

習題4

第5章布爾代數

5.1布爾函數

5.1.1布爾函數和布爾表達式

5.1.2布爾代數中的恆等式

5.2布爾函數的表示

5.2.1布爾函數的主析取範式

5.2.2函數完備性

5.3布爾代數的應用

5.3.1門電路

5.3.2卡諾圖

習題5

第6章圖

6.1圖的基本概念

6.1.1無向圖和有向圖

6.1.2握手定理

6.1.3圖的同構

6.2圖的連通性

6.2.1通路和回路

6.2.2無向圖的連通性

6.2.3有向圖的連通性

6.3圖的矩陣表示

6.3.1關聯矩陣

6.3.2鄰接矩陣

6.3.3有向圖的可達矩陣

6.4一些特殊的圖

6.4.1二部圖

6.4.2歐拉圖

6.4.3哈密爾頓圖

6.5帶權圖的短路徑

6.5.1Dijkstra算法

6.5.2Floyd算法

6.5.3旅行商問題

6.6平面圖

6.6.1平面圖的定義

6.6.2歐拉公式

6.6.3庫拉圖斯基定理

習題6

第7章樹

7.1無向樹

7.1.1無向樹的定義

7.1.2無向樹的應用例子

7.2生成樹

7.2.1生成樹的定義

7.2.2求小生成樹的算法

7.3根樹及應用

7.3.1根樹的定義及應用

7.3.2二叉樹和Huffman編碼

7.3.3二叉樹的遍歷

習題7

第8章離散數學實驗

8.1實驗一準備知識

8.1.1集合定義

8.1.2子集

8.1.3A-B

8.1.4集合相等

8.1.5笛卡兒積

8.1.6公約數與小公倍數

8.1.7餘數

8.1.8Fibonacci數列

8.1.9漢諾塔

8.1.10漢諾塔Ⅲ

8.1.11序列和

8.1.12有效編碼

8.1.13矩陣的和

8.1.14矩陣的布爾積

8.2實驗二數理邏輯

8.2.1命題聯結詞

8.2.2成真解釋

8.2.3公式類型

8.2.4主析取範式

8.2.5主合取範式

8.2.6派誰去進修的問題

8.2.7推理1

8.2.8推理2

8.2.9公式的真值1

8.2.10公式的真值2

8.3實驗三計數

8.3.1密碼

8.3.2圓周排列1

8.3.3圓周排列2

8.3.4有重復的組合

8.3.5生成排列

8.3.6生成組合

8.3.7上班問題

8.3.8解方程1

8.3.9解方程2

8.3.10工作組

8.4實驗四關繫

8.4.1關繫矩陣

8.4.2關繫的合成1

8.4.3關繫的合成2

8.4.4關繫的運算

8.4.5自反性

8.4.6對稱性

8.4.7對稱閉包

8.4.8傳遞閉包

8.4.9同餘

8.4.10等價類

8.4.11等價關繫

8.4.12哈斯圖

8.4.13極值

8.4.14值

8.4.15拓撲排序

8.5實驗五圖

8.5.1簡單圖1

8.5.2簡單圖2

8.5.3度數列1

8.5.4度數列2

8.5.5連通圖

8.5.6單向連通

8.5.7強連通

8.5.8二分圖

8.5.9歐拉圖

8.5.10半歐拉圖

8.5.11歐拉回路

8.5.12歐拉路

8.5.13單源正權短路徑

8.5.14短路徑

8.5.15平面圖1

8.5.16平面圖2

8.6實驗六樹

8.6.1無向樹

8.6.2小生成樹

8.6.3根樹

8.6.4Huffman編碼

參考文獻

前言

前言

本書以《離散數學基礎（第2版）》為基礎，在廣泛聽取廣大讀者的意見和建議的基礎上修改而成。本版主要對第2版中一些描述錯誤和印刷錯誤進行訂正，增加了第8章離散數學實驗等內容。前言

本書以《離散數學基礎（第2版）》為基礎，在廣泛聽取廣大讀者的意見和建議的基礎上修改而成。本版主要對第2版中一些描述錯誤和印刷錯誤進行訂正，增加了第8章離散數學實驗等內容。
離散數學是計算機類專業的一門重要的專業基礎課，屬於現代數學的範疇，是隨著計算機科學的發展而逐步形成的一門新興的工具性學科。它在計算機類專業的許多後續課程中有著廣泛的應用，為計算機科學與技術提供數學基礎。國內已出版的離散數學教材不少，但特別適合地方院校和獨立學院計算機類專業使用的不多，主要的問題是理論性太強，大都是從純數學的角度討論問題，缺乏與計算機相關專業的聯繫。本書的寫作目的是從離散數學教學的實際現狀出發，克服目前國內教材普遍存在注重理論、忽視應用的問題，按照突出離散數學的實用性以及實用夠用的原則精選教學內容，突破傳統的離散數學的四大模塊內容，刪除部分大學階段用不到的內容，增加基礎知識、組合數學、布爾代數及離散數學實驗等內容，使教學內容更加易學實用。
本書第1章主要介紹本書所需的準備知識，包括集合及其在計算機中的表示、數論初步、序列和遞推關繫、一般矩陣和布爾矩陣的運算等。第2章主要介紹數理邏輯的基礎知識，包括命題邏輯和謂詞邏輯的基本概念、演算及推理等。第3章主要介紹組合數學中的計數理論和方法，包括計數原則、生成函數、鴿巢原理和容斥原理等。第4章主要介紹關繫理論，關繫基本概念和運算、等價關繫與劃分、偏序關關繫及應用、函數等。第5章主要介紹布爾代數的基本理論和應用，包括布爾運算、布爾表達式和布爾函數、積之和展開式（析取範式）、邏輯門電路表示和卡諾圖等。第6章主要介紹圖的基本理論和應用，包括圖論基礎、圖的矩陣表示、連通性理論、幾種特殊的圖、帶權圖的短路徑算法（Dijkstra算法和Floyd算法）等。第7章主要介紹樹及其應用，包括樹的定義，樹的應用（決策樹、前綴碼等），樹的遍歷算法，表達式表示，生成樹和小生成樹算法（Prim算法和Kruskal算法）等。第8章給出了離散數學實驗，每個實驗都針對書中理論部分的具體知識點，這樣使讀者既鞏固了前面所學的知識又提高了編程能力。
本書有以下特點。
(1) 簡單易學：隻要求學生學過高等數學，不需要更多的預備知識；書中內容深入淺出，理論適中，實例豐富，便於自學。
(2) 實用性強：注重離散數學作為計算機科學專業的數學基礎，強調與本專業後續課程的關繫，所舉例子盡量與專業相關。
(3) 定位明確：適合地方二本院校和獨立學院學生使用。
本書教學課時為72~90學時。教師可根據學時、專業和學生的實際情況對書中內容進行選講。
本書由謝勝利、虞銘財、王振宏編著。其中，第1章和第8章由虞銘財編寫，第2章由王振宏編寫，其餘章節由謝勝利編寫。全書由謝勝利統稿。
因為編者水平有限，難免存在疏漏之處，懇請讀者批評指正。

編者
2018年4月

在線試讀

第5章布爾代數
計算機和其他電子設備中的電路都有輸入和輸出，輸入的是0和1，輸出的也是0和1。電路可以用任何具有兩種不同狀態件來構造。1854年英國數學家喬治·布爾(George Boole，1815—1864)出版了他的不朽名著《思維規律的研究》，次給出了邏輯的基本規則。1938年克勞德·香農(Claude Elwood Shannon，1916—2001)創立了開關函數的代數，揭示怎樣用邏輯的基本規則來設計電路，這些規則形成了布爾代數的基礎。隨著半導體器件制造工藝的發展，各種具有良好開關性能的微電子器件不斷湧現，因而布爾代數已成為分析和設計現代電子邏輯電路不可缺少的數學工具。

5.1布爾函數

5.1.1布爾函數和布爾表達式

布爾代數或稱邏輯代數。它雖然和普通代數一樣也用字母表示變量，但變量的值隻有“1”和“0”兩種。所謂邏輯“1”和邏輯“0”，代表兩種相反的邏輯狀態。在布爾代數中隻有布爾積(“與”運算)、布爾和(“或”運算)和布爾補(“非”運算)3種運算。
1. 布爾和

表達式： F=A＋B。
運算規則： 0＋0=0，0＋1=1，1＋0=1，1＋1=1。
2. 布爾積
表達式： F=A·B (在不引起混淆的情況下，可以刪去運算符，就像寫代數積一樣)。
運算規則： 0·0=0，0·1=0，1·0=0，1·1=1。第5章布爾代數
計算機和其他電子設備中的電路都有輸入和輸出，輸入的是0和1，輸出的也是0和1。電路可以用任何具有兩種不同狀態件來構造。1854年英國數學家喬治·布爾(George Boole，1815—1864)出版了他的不朽名著《思維規律的研究》，次給出了邏輯的基本規則。1938年克勞德·香農(Claude Elwood Shannon，1916—2001)創立了開關函數的代數，揭示怎樣用邏輯的基本規則來設計電路，這些規則形成了布爾代數的基礎。隨著半導體器件制造工藝的發展，各種具有良好開關性能的微電子器件不斷湧現，因而布爾代數已成為分析和設計現代電子邏輯電路不可缺少的數學工具。

5.1布爾函數

5.1.1布爾函數和布爾表達式

布爾代數或稱邏輯代數。它雖然和普通代數一樣也用字母表示變量，但變量的值隻有“1”和“0”兩種。所謂邏輯“1”和邏輯“0”，代表兩種相反的邏輯狀態。在布爾代數中隻有布爾積(“與”運算)、布爾和(“或”運算)和布爾補(“非”運算)3種運算。
1. 布爾和

表達式： F=A＋B。
運算規則： 0＋0=0，0＋1=1，1＋0=1，1＋1=1。
2. 布爾積
表達式： F=A·B (在不引起混淆的情況下，可以刪去運算符，就像寫代數積一樣)。
運算規則： 0·0=0，0·1=0，1·0=0，1·1=1。
3. 布爾補
表達式： F=(布爾補運算符用上畫線表示)。

運算規則： 0=1，1=0。
它們運算的優先級從高到低依次為布爾補、布爾積和布爾和。
例5.1計算(0 1)·0·1的值。
解：根據布爾和、布爾積和布爾補的運算規則，得

(0 1)·0·1=1·0=1·1=1

布爾和、布爾積和布爾補分別對應於第2章中的邏輯算子
∨、∧和
。有關布爾代數的結果可以直接翻譯成有關命題的結果，同樣，有關命題的結果也可以翻譯成關於布爾代數的命題。

設B={0，1}，如果變量x隻取B中的值，則稱x為一個布爾變量。
定義5.1如果n∈Z ，則Bn={(b1，b2，…，bi,…,bn)|bi∈B，1≤i≤n}，函數f： Bn→B稱為具有n個變量的(或n度的)布爾函數。布爾函數也稱開關函數。
通過寫成f(x1，x2，…，xi,…,xn)的形式來強調這n個變量，其中每一個變量xi，都是一個布爾變量。
布爾函數也可以用由布爾變量和布爾運算構成的表達式來表示。關於布爾變量x1，x2，…，xi,…,xn的布爾表達式可以遞歸地定義如下。
定義5.2(1) 0，1，x1，x2，…，xi,…,xn是布爾表達式。
(2) 如果E1和E2是布爾表達式，則1，(E1 E2)和(E1 E2)是布爾表達式。
每個布爾表達式都表示一個布爾函數，此函數的值是通過在表達式中用0和1替換布爾變量得到的。
例5.2令
f： B3→B，其中
f(x，y，z)=xy z，按如下規則確定這個布爾函數：對變量x，y，z的8組可能賦值分別計算函數f的值，如表5.1所示。

商品搜索

商品分类

【醫學】

【各大出版社】