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

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

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

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

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

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

6、積。理解：兩集合相等、全集的相對性；含有集合作為元素的特殊集；常用的集合恒等式；*對稱差運算及其性質(zhì)；用文式圖表示集合的運算及之間關(guān)系；序偶中元素的次序是重要的；笛卡爾乘積運算的性質(zhì)。掌握：集合的兩種表示法；正確區(qū)別“屬于”與“包含”之不同；證明集合相等的兩類方法；證明集合恒等式；求給定集合的冪集；熟練地求集合的笛卡爾乘積。第三章 二元關(guān)系（10學時）1. 基本概念2. 關(guān)系的合成3. *關(guān)系上的閉包運算4. 次序關(guān)系5. 等價關(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)系的冪運算；*逆關(guān)系；*關(guān)系的閉包；偏序（集合）、擬序（集合）、線序（集合）及良序（集合）；哈斯圖；最大、最小、極大、極小元素；上界、下界、最小上界與最大下界；等價關(guān)系；等價類；模K等價；*劃分；*塊；*秩。理解：一個關(guān)系的三種描述形式（即序偶、*關(guān)系矩陣、關(guān)系圖表示）；通過關(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)系；上、下界與最小上界及最大下界；*等價關(guān)系與劃分之間的一一對應關(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)系是否為等價關(guān)系；*判斷集合A的子集構(gòu)成的集合是否是A上的劃分；*搞清并牢記集合A上的等價關(guān)系與其上的劃分的相互誘導。第四章 函數(shù)（4學時）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、掌握：判斷一個關(guān)系是否是函數(shù)；求兩個給定函數(shù)的合成函數(shù)； 判斷一函數(shù)是否為單射、滿射、雙射；*判斷一個函數(shù)是否有逆函數(shù)；求出逆函數(shù)。第五章 圖論（14學時）1. 圖的基本概念2. 路徑和回路3. 幾種特殊圖4. *樹了解：無向圖與有向圖；鄰接；關(guān)聯(lián)；多重邊、平行邊；路徑與回路；圖中頂點之間的可達關(guān)系；路徑與回路的長度；兩點間的距離；歐拉路徑（回路）及歐拉圖；哈密爾頓路徑（回路）；二部圖，完全二部圖；平面圖、平面圖的面；*無向樹、*樹葉、*分支點、*森林；*生成樹；*樹枝與弦；*最小生成樹。理解：零圖、底圖、（，）圖；多重圖、線圖與簡單圖；頂點的次數(shù)、有向圖中頂點的引入次數(shù)和引出次數(shù)；圖的同構(gòu)；

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

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