《離散數(shù)學(xué)》教學(xué)大綱

1、離散數(shù)學(xué)教學(xué)大綱（高職高專）一 課程的性質(zhì) 本課程是為高職高專院校計(jì)算機(jī)類專業(yè)開設(shè)的專業(yè)基礎(chǔ)課。離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)中基礎(chǔ)理論的核心課程，是學(xué)習(xí)專業(yè)理論不可少的數(shù)學(xué)工具。離散數(shù)學(xué)是以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對象一般地是有限個(gè)和可數(shù)個(gè)元素，充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。在計(jì)算機(jī)科學(xué)中，離散數(shù)學(xué)與數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、邏輯設(shè)計(jì)、算法分析、編譯原理、人工智能、系統(tǒng)結(jié)構(gòu)等課程聯(lián)系緊密。掌握集合論、數(shù)理邏輯和圖論等離散數(shù)學(xué)的基本概念和基本原理，為學(xué)習(xí)計(jì)算機(jī)專業(yè)各后續(xù)課程做好必要的知識(shí)準(zhǔn)備。進(jìn)一步提高學(xué)生的抽象思維和邏輯推理能力，為從事計(jì)算機(jī)的應(yīng)用提供必

2、要的描述工具和理論基礎(chǔ)。二 課程的教學(xué)目的和要求 在計(jì)算機(jī)科學(xué)教學(xué)中，離散數(shù)學(xué)主要是為專業(yè)服務(wù)的基礎(chǔ)理論課，是一門概念較多、理論性較強(qiáng)，應(yīng)用性較廣的課程。本課程主要教授數(shù)理邏輯、集合論、代數(shù)系統(tǒng)、圖論方面的基礎(chǔ)知識(shí)，是計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)中一些后續(xù)課程學(xué)習(xí)的基礎(chǔ)和工具。通過本課程的學(xué)習(xí)，要使學(xué)生掌握離散數(shù)學(xué)的基本概念和基本原理，以現(xiàn)代數(shù)學(xué)的觀點(diǎn)和方法，初步掌握處理離散結(jié)構(gòu)所必須的描述工具和方法。同時(shí)，也要培養(yǎng)學(xué)生抽象思維、慎密概括、邏輯推理的能力，從而使學(xué)生具有良好的開拓專業(yè)理論的素質(zhì)和使用所學(xué)知識(shí)，分析和解決實(shí)際問題的能力。三 課程的主要教學(xué)內(nèi)容 1.命題邏輯: 命題與聯(lián)結(jié)詞、邏輯等價(jià)和永真

3、蘊(yùn)含式；推理理論，范式。2.謂詞邏輯: 謂詞與量詞，謂詞公式與變元約束，謂詞演算的等價(jià)式與永真蘊(yùn)含式；前束范式；謂詞邏輯的推理理論。3.集 合 論：集合的基本概念，集合的運(yùn)算，包含排斥原理。4.二元關(guān)系與函數(shù)：集合的笛卡爾乘積，關(guān)系的定義，關(guān)系的表示法，特殊關(guān)系，復(fù)合關(guān)系和逆關(guān)系，關(guān)系的閉包運(yùn)算，函數(shù)的定義，特殊函數(shù)，復(fù)合函數(shù)和逆函數(shù)。5.代數(shù)結(jié)構(gòu)：代數(shù)系統(tǒng)，特殊運(yùn)算和特殊元素；同構(gòu)概念，半群、群；子群，循環(huán)群，置換群；陪集和拉格朗日定理。環(huán)、域；格與布爾代數(shù)。6.圖論：圖的基本概念，通路、回路及圖的連通性，賦權(quán)圖的最短通路，圖與矩陣表示、歐拉圖與哈密頓圖、平面圖與二部圖、無向樹，有向樹及其應(yīng)

4、用。四課程的教學(xué)要求層次教學(xué)要求中，有關(guān)定義、定理、性質(zhì)、特征等內(nèi)容要求，由低到高分“知道、了解、理解”三個(gè)層次；有關(guān)計(jì)算、解法、公式、法則等方法的內(nèi)容要求，由低到高分“會(huì)、掌握、熟練掌握”三個(gè)層次。五教學(xué)時(shí)數(shù)安排 本課程可安排為72學(xué)時(shí)。學(xué)時(shí)分配如下表：教學(xué)時(shí)數(shù)分配表 章、節(jié) 教 學(xué) 內(nèi) 容 教 學(xué) 時(shí) 數(shù)第一章命題邏輯14第二章謂詞邏輯10第三章集合8第四章二元關(guān)系和函數(shù)12第五章代數(shù)系統(tǒng)簡介8第六章圖的基本概念10第七章一些特殊的圖10 合 計(jì) 72教 學(xué) 內(nèi) 容一命題邏輯（一）教學(xué)內(nèi)容：1. 命題與聯(lián)結(jié)詞，復(fù)合命題與命題公式；2. 真值表與邏輯等價(jià)：命題公式的真值表和常用的邏輯等價(jià)公式

5、。3. 永真蘊(yùn)含式概念和常用的永真蘊(yùn)含公式。4命題演算的推理理論。（二）教學(xué)目的：數(shù)理邏輯是用數(shù)學(xué)方法來研究推理規(guī)律的方法。本章和下一章介紹數(shù)理邏輯最基本的內(nèi)容：命題邏輯和謂詞邏輯，是后續(xù)相關(guān)課程學(xué)習(xí)的工具。通過這兩章學(xué)習(xí)，要求學(xué)生熟悉真值表及其應(yīng)用，熟悉命題和謂詞的概念；熟悉命題公式和謂詞公式的演算；掌握命題的公式符號化應(yīng)用；領(lǐng)會(huì)推理理論及其規(guī)則；掌握推理演算方法。（三）教學(xué)知識(shí)點(diǎn)及基本要求1. 理解命題的概念，會(huì)判斷語句是否命題，會(huì)將命題符號化；2. 掌握六個(gè)聯(lián)結(jié)詞的真值表，掌握命題公式真值表的構(gòu)造法；3. 掌握命題的常用邏輯等價(jià)公式，熟練掌握對命題公式進(jìn)行邏輯等價(jià)變換的方法。4. 掌握命

6、題演算的永真蘊(yùn)含式以及命題邏輯的推理演算方法?！局攸c(diǎn)】 命題符號化，命題公式真值表的構(gòu)造法，對命題公式進(jìn)行邏輯等價(jià)變換，命題邏輯的推理演算?！倦y點(diǎn)】命題符號化，命題邏輯的推理演算二謂詞邏輯（一）教學(xué)內(nèi)容：1謂詞與個(gè)體，量詞；2謂詞公式、自由變元和約束變元;3謂詞演算的等價(jià)式和永真蘊(yùn)含式；4. 前束范式；5. 謂詞演算的推理理論。（二）教學(xué)知識(shí)點(diǎn)及基本要求1理解謂詞、量詞、變元、個(gè)體域等概念；掌握用謂詞、量詞、聯(lián)結(jié)詞構(gòu)造謂詞公式的方法；2掌握謂詞公式在給定解釋下求真值的方法。3會(huì)將謂詞邏輯化為前束范式；4會(huì)將謂詞邏輯作為工具，將命題符號化，并能用推理規(guī)則進(jìn)行邏輯證明?！局攸c(diǎn)】謂詞與量詞，前束范式

7、，命題符號化，謂詞邏輯的推理理論?！倦y點(diǎn)】前束范式，謂詞邏輯的推理理論。命題符號的方法。三集合（一） 教學(xué)內(nèi)容：1 集合的概念與表示法，集合間的關(guān)系和特殊集合，冪集。2 集合代數(shù)。3 包含排斥原理。（二） 教學(xué)目的 集合論是現(xiàn)代數(shù)學(xué)各學(xué)科的基礎(chǔ)。本章介紹集合論的基礎(chǔ)知識(shí)，以作為后續(xù)相關(guān)課程學(xué)習(xí)的工具。通過本章學(xué)習(xí)，要求學(xué)生熟悉集合的概念、性質(zhì)及其運(yùn)算。（三） 教學(xué)知識(shí)點(diǎn)及基本要求1 掌握集合的兩種表示法；2 理解集合的包含與相等，冪集等基本概念；3 熟練掌握集合的交、并、補(bǔ)、差、對稱差運(yùn)算，并通過文氏圖加深理解。4 會(huì)求集合的冪集；5 理解包含排斥原理，掌握其簡單應(yīng)用?！局攸c(diǎn)】 集合概念、集合

8、的運(yùn)算，包含排斥原理。四二元關(guān)系和函數(shù)（一） 教學(xué)內(nèi)容：1 集合中的笛卡爾乘積；2 二元關(guān)系的定義；關(guān)系的三種表示法；3 復(fù)合關(guān)系與逆關(guān)系；4 關(guān)系的基本類型（自反、反自反、對稱、反對稱、傳遞等關(guān)系）及判別方法； 5 關(guān)系上的閉包運(yùn)算；6 等價(jià)關(guān)系與劃分：等價(jià)關(guān)系、等價(jià)類和劃分，商集；7 偏序關(guān)系：偏序關(guān)系和全序關(guān)系，哈斯圖，極大（極小）元素，最大（最小）元素，上界（下界），上（下）確界；8 函數(shù)的定義與特殊函數(shù)；9 復(fù)合函數(shù)與逆函數(shù)。（二）教學(xué)目的 本章主要要求領(lǐng)會(huì)集合上二元關(guān)系的概念、性質(zhì)，以及集合上的特殊關(guān)系：等價(jià)關(guān)系，偏序關(guān)系的概念；掌握函數(shù)的概念，掌握滿射，單射，雙射函數(shù)的概念，并會(huì)

9、判別之；理解復(fù)合函數(shù)與逆函數(shù)。（三）教學(xué)知識(shí)點(diǎn)及基本要求1 理解二元關(guān)系的概念及其性質(zhì)；2 掌握二元關(guān)系的表格表示，關(guān)系矩陣和關(guān)系圖的畫法；3 掌握關(guān)系的自反、反自反、對稱、反對稱、傳遞等性質(zhì)；4 理解關(guān)系閉包概念，會(huì)求關(guān)系的自反閉包，對稱閉包，傳遞閉包。5 理解等價(jià)關(guān)系、等價(jià)類和商集的概念，會(huì)求等價(jià)類，會(huì)判別等價(jià)關(guān)系理解偏序關(guān)系的有關(guān)概念，會(huì)畫偏序關(guān)系的哈斯圖；了解極大（極?。┰兀畲螅ㄗ钚。┰兀辖纾ㄏ陆纾?，上（下）確界的定義。6 掌握函數(shù)的概念，會(huì)判斷滿射，單射，雙射函數(shù)，會(huì)求復(fù)合函數(shù)與逆函數(shù)【重點(diǎn)】 關(guān)系概念及性質(zhì)，等價(jià)關(guān)系和偏序關(guān)系，復(fù)合函數(shù)與逆函數(shù)?！倦y點(diǎn)】 二元關(guān)系概念，等價(jià)

10、類和商集的概念，極大（極小）元素，最大（最小）元素，上界（下界），上（下）確界的概念。五代數(shù)系統(tǒng)簡介（一） 教學(xué)內(nèi)容：1. 代數(shù)系統(tǒng)：二元運(yùn)算、代數(shù)系統(tǒng)概念；2. 特殊運(yùn)算和特殊元素：代數(shù)系統(tǒng)常見的性質(zhì)(結(jié)合律、交換律、分配律 ，單位元素、逆元素、零元素)；3. 代數(shù)系統(tǒng)的同構(gòu)；4. 群的定義與性質(zhì)；5. 子群；6. 循環(huán)群。（二）教學(xué)目的： 代數(shù)系統(tǒng)是由集合上定義的若干運(yùn)算而組成的系統(tǒng)，是一類特殊的數(shù)學(xué)結(jié)構(gòu)。人們研究、考察現(xiàn)實(shí)世界的事物、現(xiàn)象，往往要借助某些數(shù)學(xué)工具，因此，針對某個(gè)具體問題，需要選用適宜的數(shù)學(xué)結(jié)構(gòu)去進(jìn)行較為確切的描述。代數(shù)系統(tǒng)的概念和方法則是計(jì)算機(jī)科學(xué)研究中使用的主要工具之一

11、。通過本章學(xué)習(xí)，要求學(xué)生熟悉代數(shù)系統(tǒng)的概念、性質(zhì)及其運(yùn)算；領(lǐng)會(huì)群的概念、性質(zhì)。（三）教學(xué)知識(shí)點(diǎn)及基本要求：1 知道代數(shù)系統(tǒng)、代數(shù)系統(tǒng)的性質(zhì)、以及代數(shù)系統(tǒng)的特殊元素；2 了解同構(gòu)概念；3 掌握二元運(yùn)算的性質(zhì)：結(jié)合律、交換律、分配律、冪等律、吸收律。4 掌握求集合上代數(shù)運(yùn)算的單位元和逆元的方法。5 了解交換群、置換群和循環(huán)群的概念，掌握其判別方法?！局攸c(diǎn)】 代數(shù)系統(tǒng)及其性質(zhì)，群的概念，交換群和循環(huán)群?！倦y點(diǎn)】 判別群的同構(gòu)，置換群和循環(huán)群的概念和判別方法。六圖的基本概念（一）教學(xué)內(nèi)容：1. 圖的基本概念，圖的同構(gòu);2. 通路和賦權(quán)圖的最短通路：通路和回路，賦權(quán)圖的最短通路的Dijkstra算法。3

12、. 圖與矩陣：圖的鄰接矩陣，可達(dá)性矩陣；（二）教學(xué)目的：本章僅介紹圖的一些基本概念和定義，以及一些典型的應(yīng)用實(shí)例。為在以后的計(jì)算機(jī)相關(guān)學(xué)科學(xué)習(xí)、研究時(shí)，以圖論的基本知識(shí)為工具。通過本章學(xué)習(xí)，要求學(xué)生：熟悉圖的基本概念及其性質(zhì)；掌握圖的矩陣表示，學(xué)會(huì)賦權(quán)圖的最短通路的Dijkstra算法。（三）教學(xué)知識(shí)點(diǎn)及基本要求：1. 理解有關(guān)圖的基本概念，掌握圖的頂點(diǎn)和邊的關(guān)系定理，理解圖的同構(gòu)。2. 理解簡單通（回）路、基本通（回）路的概念，理解圖的連通性，掌握其判別方法;會(huì)求賦權(quán)圖的最短通路。3. 掌握圖的矩陣表示方法，會(huì)通過可達(dá)性矩陣求圖的強(qiáng)分支?！局攸c(diǎn)】 圖的概念，頂點(diǎn)度數(shù)和邊關(guān)系的定理，圖的矩陣表示?！倦y點(diǎn)】 判別圖的同構(gòu)，利用圖的矩陣判別圖的性質(zhì)和連通性。七一些特殊的圖（一）教學(xué)內(nèi)容：1二部圖：二部圖及其判別；2歐拉圖；3哈密頓圖；4平面圖；平面圖的概念，歐拉公式，平面圖和非平面圖的判別。5. 無向樹：樹的定義，樹的性質(zhì)6. 有向樹：有向樹的基本概念，前綴碼與最優(yōu)樹（二）教學(xué)目的：會(huì)判別二部圖、歐拉圖、哈密頓圖、平面圖；掌握樹的概念及其性質(zhì)；了解樹的典型實(shí)例及其應(yīng)用。（三）教學(xué)知識(shí)點(diǎn)及基本要求：【重點(diǎn)】歐拉圖和哈密頓圖；樹