離散數(shù)學(xué)及應(yīng)用

前言

　　離散數(shù)學(xué)是計(jì)算機(jī)及相關(guān)專業(yè)的一門重要核心、基礎(chǔ)課，是計(jì)算機(jī)科學(xué)與技術(shù)的基礎(chǔ)理論之一。它隸屬于現(xiàn)代數(shù)學(xué)的范疇，研究的對(duì)象是離散數(shù)據(jù)結(jié)構(gòu)及相互關(guān)系。它在數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)、程序設(shè)計(jì)、形式語(yǔ)言、自動(dòng)機(jī)、人工智能、操作系統(tǒng)、編譯原理、語(yǔ)言學(xué)等領(lǐng)域都有著重要的應(yīng)用。通過(guò)離散數(shù)學(xué)課程的學(xué)習(xí)，可以培養(yǎng)學(xué)生的數(shù)學(xué)抽象思維和嚴(yán)格的推理能力，使學(xué)生掌握信息技術(shù)領(lǐng)域中的一些基本數(shù)學(xué)工具和方法，為將來(lái)從事軟、硬件開發(fā)打下堅(jiān)實(shí)基礎(chǔ)?！　∪珪卜譃?篇16章，內(nèi)容安排如下。　　第1篇為集合論部分，包括第1～3章。第1章為集合的總體概述，介紹了有關(guān)集合的運(yùn)算、有限集合的計(jì)算以及集合的各種運(yùn)算定律；第2章為關(guān)系，由笛卡爾積引入關(guān)系的概念，介紹了關(guān)系的表示方法、關(guān)系的各種運(yùn)算、關(guān)系的性質(zhì)、關(guān)系的閉包、等價(jià)關(guān)系、相容關(guān)系以及偏序關(guān)系等；第3章為函數(shù)，主要介紹了函數(shù)的基本概念、一些特殊的函數(shù)、函數(shù)的運(yùn)算以及集合的基數(shù)等?！　〉?篇為圖論部分，包括第4～7章。第4章介紹了圖的基本概念以及圖的操作和運(yùn)算；第5章介紹了幾類特殊的圖形，主要有歐拉圖、漢密爾頓圖、二部圖、平面圖等；第6章和第7章分別介紹了無(wú)向樹和有向樹，主要有無(wú)向樹和有向樹涉及的基本概念、最小生成樹、最優(yōu)二叉樹及其遍歷等。第3篇為數(shù)理邏輯部分，包括第8和第9章。第8章介紹了命題邏輯，包括命題、命題公式與賦值、命題公式類型、命題的等價(jià)、命題的范式以及在命題邏輯中的推理理論；第9章為謂詞邏輯部分，包括謂詞公式與解釋、謂詞公式類型、謂詞公式的等價(jià)、謂詞公式的范式以及在謂詞邏輯中的推理理論等?！　〉?篇為代數(shù)結(jié)構(gòu)部分，包括第10～12章。第10章介紹了群的基本定義、交換群、置換群、循環(huán)群、子群、商群等，并介紹了群的同態(tài)與同構(gòu)等；第11章介紹了環(huán)和理想，包括環(huán)的基本概念、多項(xiàng)式環(huán)、歐幾里德環(huán)、商環(huán)等：第12章介紹了域，包括擴(kuò)域、代數(shù)元、超越元以及有限域、本原元、本原多項(xiàng)式等?！　〉?篇為離散數(shù)學(xué)的應(yīng)用部分，包括第13～16章。第13章介紹了數(shù)理邏輯的應(yīng)用，介紹了命題邏輯在簡(jiǎn)化電路、簡(jiǎn)化計(jì)算機(jī)程序、簡(jiǎn)化邏輯網(wǎng)絡(luò)圖以及在繼電器控制開關(guān)中的應(yīng)用，并介紹了謂詞邏輯在人工智能領(lǐng)域、在邏輯程序設(shè)計(jì)語(yǔ)言等方面的應(yīng)用；第14章介紹了關(guān)系的應(yīng)用，主要有關(guān)系及運(yùn)算在關(guān)系型數(shù)據(jù)庫(kù)中的應(yīng)用、關(guān)系的閉包、等價(jià)關(guān)系、序關(guān)系等的應(yīng)用實(shí)例；第15章介紹了圖論的應(yīng)用，主要包括平面圖與著色的應(yīng)用、圖的通路的應(yīng)用、歐拉圖和漢密爾頓圖的應(yīng)用、樹的應(yīng)用以及網(wǎng)絡(luò)流等問(wèn)題；第16章介紹了文法、有限自動(dòng)機(jī)、語(yǔ)言等內(nèi)容?！　∪珪鴥?nèi)容深入淺出，圖文并茂，各篇章之間既有聯(lián)系，又相對(duì)獨(dú)立，讀者可根據(jù)需要選擇閱讀。每章后面都附有作者精心挑選的思考題，可幫助讀者進(jìn)一步鞏固所學(xué)的知識(shí)?！　”緯杀本┪镔Y學(xué)院信息學(xué)院郭鍵、李俊韜、譚加博編寫。

內(nèi)容概要

本書共分為5篇：集合論、圖論、數(shù)理邏輯、代數(shù)結(jié)構(gòu)及綜合應(yīng)用。集合論部分介紹了集合、關(guān)系、函數(shù)等；圖論部分介紹了圖的基本概念及特殊圖；數(shù)理邏輯包括命題邏輯和謂詞邏輯；代數(shù)系統(tǒng)介紹了群、環(huán)、域等；最后詳細(xì)介紹了這四部分在計(jì)算機(jī)中的實(shí)際應(yīng)用。本書在編寫過(guò)程中，盡量將離散數(shù)學(xué)的各個(gè)部分有機(jī)地結(jié)合起來(lái)，力求條理清楚、深入淺出，通過(guò)該課程的學(xué)習(xí)，可使讀者掌握必備的離散數(shù)學(xué)知識(shí)，并提高其利用離散數(shù)學(xué)知識(shí)分析和解決實(shí)際問(wèn)題的能力。    本書可作為高等院校計(jì)算機(jī)科學(xué)技術(shù)等相關(guān)專業(yè)的本科生和研究生的教學(xué)用書，也可作為計(jì)算機(jī)工程技術(shù)和研究人員學(xué)習(xí)離散數(shù)學(xué)的參考用書。

書籍目錄

前言第1篇  集合論  第1章  集合    1.1  集合的基本概念及性質(zhì)      1.1.1  集合的基本概念      1.1.2  集合的表示形式      1.1.3  集合的基本性質(zhì)      1.1.4  集合之間的關(guān)系    1.2  集合的運(yùn)算      1.2.1  集合的交運(yùn)算      1.2.2  集合的并運(yùn)算      1.2.3  集合的補(bǔ)運(yùn)算      1.2.4  集合的對(duì)稱差運(yùn)算      1.2.5  集合的廣義交和廣義并運(yùn)算    1.3  有限集合的計(jì)數(shù)      1.3.1  鴿巢原理      1.3.2  包容排斥原理    1.4  集合的運(yùn)算定律    思考與練習(xí)題  第2章  關(guān)系    2.1  笛卡爾積概念      2.1.1  序偶      2.1.2  笛卡爾積    2.2  二元關(guān)系及其表示方法      2.2.1  二元關(guān)系的定義      2.2.2  二元關(guān)系的表示方法    2.3  二元關(guān)系的運(yùn)算      2.3.1  關(guān)系的基本運(yùn)算      2.3.2  關(guān)系的復(fù)合運(yùn)算      2.3.3  關(guān)系的冪運(yùn)算      2.3.4  關(guān)系的逆運(yùn)算      2.3.5  關(guān)系的限制和像    2.4  二元關(guān)系的性質(zhì)      2.4.1  自反性與反自反性      2.4.2  對(duì)稱性、反對(duì)稱性、非對(duì)稱性      2.4.3  傳遞性      2.4.4  關(guān)系性質(zhì)的保持性    2.5  二元關(guān)系的閉包      2.5.1  關(guān)系閉包定義      2.5.2  關(guān)系閉包涉及的定理      2.5.3  關(guān)系閉包的求解方法總結(jié)    2.6  等價(jià)關(guān)系      2.6.1  等價(jià)關(guān)系定義      2.6.2  等價(jià)類與商集      2.6.3  等價(jià)類與劃分    2.7  相容關(guān)系與覆蓋      2.7.1  相容關(guān)系與覆蓋的定義      2.7.2  最大相容類    2.8  序關(guān)系      2.8.1  偏序關(guān)系      2.8.2  全序關(guān)系與良序關(guān)系      2.8.3  擬序關(guān)系    思考與練習(xí)題  第3章  函數(shù)    3.1  函數(shù)的基本概念      3.1.1  函數(shù)的引入      3.1.2  函數(shù)的定義及特點(diǎn)    3.2  特殊函數(shù)      3.2.1  單射、滿射與雙射      3.2.2  常用函數(shù)    3.3  函數(shù)的運(yùn)算      3.3.1  函數(shù)的復(fù)合運(yùn)算      3.3.2  函數(shù)的逆運(yùn)算    3.4  集合的基數(shù)      3.4.1  基數(shù)的定義      3.4.2  丁數(shù)集的定義及性質(zhì)      3.4.3  集合基數(shù)的比較    思考與練習(xí)題第2篇  圖論  第4章  圖的基本概念  第5章  特殊圖  第6章  無(wú)向樹  第7章  有向樹第3篇  數(shù)理邏輯  第8章  命題邏輯  第9章  謂詞邏輯第4篇  代數(shù)結(jié)構(gòu)  第10章  群  第11章  環(huán)與理想  第12章  域第5篇  綜合應(yīng)用  第13章  數(shù)理邏輯的應(yīng)用實(shí)例  第14章  關(guān)系的應(yīng)用實(shí)例  第15章  圖論的應(yīng)用實(shí)例  第16章  有限自動(dòng)機(jī)與語(yǔ)言參考文獻(xiàn)

章節(jié)摘錄

　　在有限集A中，A的基數(shù)lAl就是集合A中元素的個(gè)數(shù)。在計(jì)算和證明中，常常會(huì)遇到從有限集A中取若干元素的問(wèn)題，或者給定有限集A與B，求AUB和AnB等?！　?.3.1 鴿巢原理　　有一種搶位子的游戲，當(dāng)座位少人多時(shí)，就會(huì)發(fā)生幾個(gè)人同時(shí)擠在同一個(gè)位子上的情況。同樣的道理，只要一年里出生的人數(shù)超過(guò)366個(gè)，那么必可得出這樣的結(jié)論：至少有兩人是同年同月同日出生的?！　▲澇苍恚≒igeonhole Principle，又稱抽屜原理、鴿舍原理）：若有n+1只鴿子住進(jìn)n個(gè)鴿巢，則至少有1個(gè)鴿巢住進(jìn)2只鴿子。　　證明（反證法）假設(shè)每個(gè)鴿巢至多住進(jìn)1只鴿子，則n個(gè)鴿巢至多住進(jìn)n只鴿子，這與有，z+1只鴿子矛盾。故至少有1只鴿巢至少住進(jìn)2只鴿子?！　　纠?-9】月黑風(fēng)高穿襪子。某晚你房間的電燈忽然間壞了，伸手不見五指，而你又要出去，于是就摸床底下的襪子。你有三雙分別為紅、白、藍(lán)顏色的襪子，可是你平時(shí)做事隨便，一脫襪就亂扔，在黑暗中不能知道哪一雙是顏色相同的。你想拿最少數(shù)目的襪子出去，在外面借街燈配成同顏色的一雙。問(wèn)需要拿的最少數(shù)目應(yīng)該是多少？　　解如果懂得鴿巢原理，就會(huì)知道只需拿出去四只襪子就行了。因?yàn)槿绻覀儗⑦@三雙襪子分別放人三個(gè)盒子中，則要抽出4只襪子，至少有一個(gè)盒子的襪子全被拿出來(lái)，則這個(gè)盒子的襪子必然是同色的，可以拿來(lái)穿?！　?.3.2 包容排斥原理　　我們可以利用有限集合中元素的個(gè)數(shù)來(lái)進(jìn)行計(jì)數(shù)。在做這類計(jì)數(shù)運(yùn)算時(shí)，被包含的公共子集常被重復(fù)計(jì)數(shù)，需要排除掉這部分的重復(fù)計(jì)數(shù)，而在排除時(shí)，由于包含關(guān)系又發(fā)生重復(fù)排除，需要再加回被重復(fù)排除的部分，如此容、斥、容、斥……，直至不再容或斥。這就是計(jì)數(shù)中的包容排斥原理（又稱容斥原理）。

圖書封面

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

---

    離散數(shù)學(xué)及應(yīng)用 PDF格式下載

---