《離散數(shù)學(xué)》教學(xué)大綱48學(xué)時(shí)20170326-16級(jí)使用

1、離散數(shù)學(xué)課程教學(xué)大綱模板（黑體 小三號(hào) 居中）（以下標(biāo)題為黑體小四號(hào)，行距為18磅，內(nèi)容為宋體五號(hào)）課程名稱：離散數(shù)學(xué)/Discrete Mathematics課程編碼： 總學(xué)時(shí)數(shù)/學(xué)分?jǐn)?shù)：專業(yè)基礎(chǔ)課實(shí)驗(yàn)學(xué)時(shí)：0上機(jī)學(xué)時(shí)：0課程所屬部門：信息技術(shù)工程學(xué)院適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、軟件工程及相關(guān)專業(yè) 課程負(fù)責(zé)人：制定日期：2017年3月一、課程定位本課程的授課對(duì)象、課程的基本描述(課程的性質(zhì)、任務(wù)、與其它課程的關(guān)系等)和在人才培養(yǎng)過(guò)程中的地位和作用。離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)以及相關(guān)專業(yè)重要的專業(yè)基礎(chǔ)課。包括的主要內(nèi)容有：數(shù)理邏輯、集合論、二元關(guān)系、函數(shù)和圖論等。它以研究離散量的結(jié)構(gòu)和相互

2、關(guān)系為主要目標(biāo)，通過(guò)該課程的學(xué)習(xí)，培養(yǎng)學(xué)生抽象思維和嚴(yán)密的邏輯推理能力，為進(jìn)一步學(xué)習(xí)其它專業(yè)課打好基礎(chǔ)，并為學(xué)生今后處理離散信息，提高專業(yè)水平，從事計(jì)算機(jī)或者相應(yīng)專業(yè)以及實(shí)際工作提供必備的數(shù)學(xué)工具。二、教學(xué)目標(biāo)學(xué)生通過(guò)學(xué)習(xí)該課程后，在思維、知識(shí)和能力等方面應(yīng)達(dá)到的目標(biāo)。1. 有效地掌握該門課程中的所有概念。通過(guò)講課和布置一定數(shù)量的習(xí)題使學(xué)生能夠使用所學(xué)的概念對(duì)許多問(wèn)題作出正確的判斷。2. 通過(guò)課程中許多定理的證明過(guò)程復(fù)習(xí)概念，了解證明的思路，學(xué)會(huì)證明的方法，并使學(xué)生掌握定理的內(nèi)容和結(jié)果。3. 通過(guò)介紹各種做題的方法，啟發(fā)學(xué)生獨(dú)立思維的能力。創(chuàng)造性的提出自己解決問(wèn)題的方法，提高學(xué)生解決問(wèn)題的能力

3、。4.通過(guò)該門課程的學(xué)習(xí)使學(xué)生掌握邏輯思維和邏輯推理的能力，培養(yǎng)學(xué)生正規(guī)的邏輯思維方式。三、課程教學(xué)內(nèi)及要求教學(xué)內(nèi)容及學(xué)時(shí)教學(xué)要求實(shí)驗(yàn)（上機(jī)）項(xiàng)目及學(xué)時(shí)第一章 數(shù)理邏輯（16學(xué)時(shí)）1. 命題2. 重言式3. 范式4. 推理規(guī)則和證明方法5. *謂詞和量詞了解：命題與真值；原子命題、復(fù)合命題；命題常元與變?cè)宦?lián)結(jié)詞；真值表；原子公式與命題公式；邏輯等價(jià)式；重言式（或永真式）、永假式（或矛盾式）、可滿足式；恒等式；永真蘊(yùn)含式；代入與替換規(guī)則；基本積，基本和；極小與極大項(xiàng)；主析取與主合取范式；推理；前提；有效結(jié)論；證明；*個(gè)體常元與變?cè)?謂詞常元與變?cè)?論述域； *全總個(gè)體域；*量詞與轄域；*全

4、稱與存在量詞；*特性謂詞；*原子公式；*謂詞公式；*自由與約束變?cè)?改名規(guī)則。理解：命題P的否定式；命題P和Q的合取、析取、蘊(yùn)含以及等值式；求給定公式的或真或或假的賦值；判斷給定公式的類型；熟練求已給公式的極小與極大項(xiàng)、進(jìn)而求主析取與主合取范式的主要步驟；每個(gè)公式都有唯一主合取與主析取范式；推理正確的定義；證明中常用的推理規(guī)則；間接證明法；反證法及CP規(guī)則法；*特性謂詞的加入規(guī)則；*命題與謂詞之間的相互聯(lián)系；*量詞的量化作用；*正確判斷量詞的轄域、指明相應(yīng)的自由與約束變?cè)?。掌握：運(yùn)用五個(gè)常用聯(lián)結(jié)詞將命題符號(hào)化；熟練的構(gòu)造給定公式的真值表，并用于判斷某復(fù)合命題的真假；用真值表判斷給定公式的類型

5、；牢記并靈活運(yùn)用重要的恒等式和永真蘊(yùn)含式；用等值演算法判斷二公式是否等價(jià)；用定值觀察法及等值演算法證明一蘊(yùn)含式是否為永真蘊(yùn)含式；運(yùn)用真值表法或填滿變?cè)ㄊ炀毜厍蠼o定公式的主范式；主析取與主合取范式之間的緊密聯(lián)系及轉(zhuǎn)化；熟練的掌握判斷有效結(jié)論的方法：真值表法、*直接證明法、*間接證明法（含反證法及CP規(guī)則法）；*用推理規(guī)則構(gòu)造推理的證明；*較熟練的進(jìn)行不太復(fù)雜的自然語(yǔ)言與謂詞公式之間的簡(jiǎn)單翻譯；*掌握量詞與聯(lián)結(jié)詞之間的轉(zhuǎn)化關(guān)系。應(yīng)用：XXXX第二章 集合論（4學(xué)時(shí)）1. 集合論的基本概念2. 集合上的運(yùn)算3. 集合的笛卡爾乘積了解：集合的并、交、差、補(bǔ)；*對(duì)稱差集；冪集；序偶； n重組；笛卡爾乘

6、積。理解：兩集合相等、全集的相對(duì)性；含有集合作為元素的特殊集；常用的集合恒等式；*對(duì)稱差運(yùn)算及其性質(zhì)；用文式圖表示集合的運(yùn)算及之間關(guān)系；序偶中元素的次序是重要的；笛卡爾乘積運(yùn)算的性質(zhì)。掌握：集合的兩種表示法；正確區(qū)別“屬于”與“包含”之不同；證明集合相等的兩類方法；證明集合恒等式；求給定集合的冪集；熟練地求集合的笛卡爾乘積。第三章 二元關(guān)系（10學(xué)時(shí)）1. 基本概念2. 關(guān)系的合成3. *關(guān)系上的閉包運(yùn)算4. 次序關(guān)系5. 等價(jià)關(guān)系與劃分了解：關(guān)系與二元關(guān)系（含A到B的關(guān)系及A上的關(guān)系）；空關(guān)系、全域關(guān)系；A上的恒等關(guān)系；關(guān)系R的定義域與值域；*關(guān)系矩陣；關(guān)系圖；A上的關(guān)系的五種特性；關(guān)系的合

7、成；關(guān)系的冪運(yùn)算；*逆關(guān)系；*關(guān)系的閉包；偏序（集合）、擬序（集合）、線序（集合）及良序（集合）；哈斯圖；最大、最小、極大、極小元素；上界、下界、最小上界與最大下界；等價(jià)關(guān)系；等價(jià)類；模K等價(jià)；*劃分；*塊；*秩。理解：一個(gè)關(guān)系的三種描述形式（即序偶、*關(guān)系矩陣、關(guān)系圖表示）；通過(guò)關(guān)系圖確定關(guān)系的特性；關(guān)系經(jīng)合成后所得新關(guān)系與原關(guān)系的聯(lián)系；*關(guān)系經(jīng)求逆后所得新關(guān)系與原關(guān)系的聯(lián)系；偏序與擬序之間的關(guān)系；偏序與線序、良序之間的關(guān)系；上、下界與最小上界及最大下界；*等價(jià)關(guān)系與劃分之間的一一對(duì)應(yīng)關(guān)系。掌握：求給定關(guān)系的定義域和值域；判斷給定關(guān)系的性質(zhì)；由給定關(guān)系求合成關(guān)系；*由給定關(guān)系求逆關(guān)系；*關(guān)系

8、的閉包；判斷某給定關(guān)系R是否為偏序、線序或良序關(guān)系；熟練的畫出偏序集合的哈斯圖，并求出某子集的各種特異元素；判定某給定關(guān)系是否為等價(jià)關(guān)系；*判斷集合A的子集構(gòu)成的集合是否是A上的劃分；*搞清并牢記集合A上的等價(jià)關(guān)系與其上的劃分的相互誘導(dǎo)。第四章 函數(shù)（4學(xué)時(shí)）1. 函數(shù)的基本概念2. 特殊函數(shù)類3. *逆函數(shù)了解：函數(shù)；恒等函數(shù)；合成函數(shù)；逆函數(shù)單射、滿射與雙射；集合A的特征函數(shù)；*逆函數(shù)。理解：函數(shù)是滿足單值性的特殊關(guān)系；正確區(qū)別函數(shù)的合成與關(guān)系的合成在記法上的不同；單、滿射與雙射的性質(zhì)，如單（滿、雙）射和單（滿、雙）射的合成仍是單（滿、雙）射；集合A的特征函數(shù)的性質(zhì)；*只有雙射才有逆函數(shù)。

9、掌握：判斷一個(gè)關(guān)系是否是函數(shù)；求兩個(gè)給定函數(shù)的合成函數(shù)； 判斷一函數(shù)是否為單射、滿射、雙射；*判斷一個(gè)函數(shù)是否有逆函數(shù)；求出逆函數(shù)。第五章 圖論（14學(xué)時(shí)）1. 圖的基本概念2. 路徑和回路3. 幾種特殊圖4. *樹(shù)了解：無(wú)向圖與有向圖；鄰接；關(guān)聯(lián)；多重邊、平行邊；路徑與回路；圖中頂點(diǎn)之間的可達(dá)關(guān)系；路徑與回路的長(zhǎng)度；兩點(diǎn)間的距離；歐拉路徑（回路）及歐拉圖；哈密爾頓路徑（回路）；二部圖，完全二部圖；平面圖、平面圖的面；*無(wú)向樹(shù)、*樹(shù)葉、*分支點(diǎn)、*森林；*生成樹(shù)；*樹(shù)枝與弦；*最小生成樹(shù)。理解：零圖、底圖、（，）圖；多重圖、線圖與簡(jiǎn)單圖；頂點(diǎn)的次數(shù)、有向圖中頂點(diǎn)的引入次數(shù)和引出次數(shù)；圖的同構(gòu)；

10、子圖、生成子圖；完全圖；補(bǔ)圖；路徑（回路）的分類：簡(jiǎn)單及基本路徑（回路）；無(wú)向連通圖以及連通分支；三種有向連通圖：強(qiáng)、單項(xiàng)及弱連通圖；強(qiáng)（單向、弱）分圖；賦權(quán)圖；無(wú)向及有向圖為歐拉圖的充要條件；歐拉公式及其推論；*無(wú)向樹(shù)的幾個(gè)等價(jià)定義；*無(wú)向樹(shù)中邊數(shù)等于頂點(diǎn)數(shù)減一；*任一連通無(wú)向圖至少有一棵生成樹(shù)。掌握：靈活運(yùn)用無(wú)向圖中關(guān)于頂點(diǎn)的次數(shù)的重要結(jié)論；能判斷兩個(gè)簡(jiǎn)單的圖是否同構(gòu)；判斷無(wú)向或有向圖中路徑及回路的類型；判斷一個(gè)圖是否為歐拉圖；*利用定義、定理判斷一個(gè)圖是否為平面圖；*利用圖的次數(shù)定理以及樹(shù)的有關(guān)性質(zhì)，由已知樹(shù)中某些頂點(diǎn)的次數(shù)求其它頂點(diǎn)的次數(shù)（或求具有指定次數(shù)的某種頂點(diǎn)數(shù)）；*求連通圖的生

11、成樹(shù)；*用Kruskal法求最小生成樹(shù)。說(shuō)明：1. 實(shí)驗(yàn)和上機(jī)內(nèi)容只填寫項(xiàng)目名稱及學(xué)時(shí)，具體內(nèi)容和要求見(jiàn)實(shí)驗(yàn)大綱。2. 教學(xué)要求分章節(jié)按“了解”、“理解”、“掌握”三個(gè)層次編寫教學(xué)內(nèi)容及要求?！傲私狻笔侵笇W(xué)生應(yīng)能辨認(rèn)的科學(xué)事實(shí)、概念、原則、術(shù)語(yǔ)，知道事物的分類、過(guò)程及變化傾向，包括必要的記憶；“理解”是指學(xué)生能用自己的語(yǔ)言把學(xué)過(guò)的知識(shí)加以敘述、解釋、歸納，并能把某一事實(shí)或概念分解為若干部分，指出它們之間的內(nèi)在聯(lián)系或與其它事物的相互關(guān)系；“掌握”是指學(xué)生能根據(jù)不同情況對(duì)某些概念、定律、原理、方法等在正確理解的基礎(chǔ)上結(jié)合事例加以運(yùn)用，包括分析和綜合?！皯?yīng)用”指學(xué)生運(yùn)用已獲得的知識(shí)去解決新的練習(xí)性課題或?qū)嶋H問(wèn)題，要求以語(yǔ)言或?qū)嶋H操作的方式把所學(xué)得的知識(shí)具體化并應(yīng)用到社會(huì)實(shí)踐中去。四、教材、參考書和閱讀材料(1)教材：離散數(shù)學(xué)（第三版） 方世昌 西安電子科技大學(xué)出版社 2009(2)參考書：離散數(shù)學(xué)（第2版） 屈婉玲 高等教育出版社 2015離散數(shù)學(xué)左孝陵 上?？茖W(xué)技術(shù)文獻(xiàn)出版社1982Discrete Mathematics and Its Applications （美）Kenneth