《離散數(shù)學(xué)》課程教學(xué)大綱-64學(xué)時課程編號：** 適用專業(yè)：計算機科學(xué)與技術(shù)、信息安全、軟件工程學(xué)時數(shù)：64 學(xué)分數(shù)：4 開課學(xué)期：第2學(xué)期先修課程：線性代數(shù)、高級語言程序設(shè)計(C語言)執(zhí)筆者：編寫日期： 審核人（教學(xué)副院長）：一、課程性質(zhì)和目標授課對象：本科生課程類別：學(xué)科基礎(chǔ)課教學(xué)目標：離散數(shù)學(xué)是一門理論兼實際應(yīng)用的綜合性學(xué)科，既具有嚴備的理論基礎(chǔ)，又具備應(yīng)用科學(xué)的特點。它是計算機科學(xué)和其他應(yīng)用科學(xué)的基礎(chǔ)理論課。在課堂教學(xué)中，不僅要求學(xué)生掌握離散數(shù)學(xué)的基本理論與方法，更重要的是強調(diào)離散數(shù)學(xué)課程的思想。通過本課程學(xué)習(xí)，培養(yǎng)和訓(xùn)練學(xué)生的抽象的離散思維能力、嚴格的邏輯推理的能力，以及獲取知識、應(yīng)用知識和創(chuàng)新的能力；培養(yǎng)和訓(xùn)練學(xué)生的離散建模能力；培養(yǎng)和學(xué)生能有條理、明確和系統(tǒng)地描述問題、分析和求解問題的能力。通過本課程學(xué)習(xí)，使學(xué)生了解離散數(shù)學(xué)在計算機學(xué)科和日常生活中的作用，為學(xué)生今后處理離散信息以及用計算機處理大量的日常事物和科研項目，從事計算機科學(xué)和應(yīng)用打下堅實基礎(chǔ)，特別是對那些從事計算機科學(xué)與理論研究的高層次計算機人員來說，更是一門必不可少的基礎(chǔ)理論工具。同時，提煉課程內(nèi)容中的思政元素，培養(yǎng)學(xué)生正確的價值觀、人生觀以及精益求精的工匠精神。二、教學(xué)內(nèi)容安排及基本要求（一）課時安排章節(jié)64學(xué)時第1章集合論21.1-1.42第2章命題邏輯102.1，2.2.12.2.2-2.3.12.3.2，2.3.32.42.5第3章謂詞邏輯83.1-3.2.223.2.3-3.323.42章節(jié)64學(xué)時3.52作業(yè)講評第4章二元關(guān)系64.14.24.34.4，4.5第5章特殊關(guān)系65.225.325.4，5.52第6章圖86.126.2，6.326.426.52第7章特殊圖87.1，7.227.3，7.427.527.6，7.72第8章代數(shù)系統(tǒng)48.1-8.2.128.2.2-8.42第9章群環(huán)域89.129.229.3，9.429.5，9.62第10章格與布爾代數(shù)410.1，10.2210.3，10.42（二）教學(xué)內(nèi)容、要求及教學(xué)方法第1章集合論2學(xué)時教學(xué)方法：課堂面授教學(xué)目的：集合是數(shù)學(xué)的基礎(chǔ)，通過本章的學(xué)習(xí)，要求學(xué)生能熟悉集合的表示、運算與證明，為以后各章的學(xué)習(xí)奠定基礎(chǔ)?；緝?nèi)容：集合相關(guān)的基本概念及性質(zhì)、集合間的各種運算及運算性質(zhì)、幾個特殊的集合、集合的證明、無限集和與集合相關(guān)的應(yīng)用。教學(xué)重點：集合的概念及集合間關(guān)系的證明；集合的表示方法：列舉法、描述法和文氏圖；集合運算及定律和冪集P(A)的計算。教學(xué)難點：從集合與元素兩個角度去分析集合；集合與集合關(guān)系的證明和無限集基數(shù)的理解。第2章命題邏輯10學(xué)時教學(xué)方法：課堂面授教學(xué)目的：正確理解命題的概念，掌握五個命題聯(lián)結(jié)詞，熟練證明公式之間的等價關(guān)系及將公式化為標準形式。幫助學(xué)生建立命題邏輯的基本概念，通過例題掌握正確解決問題的方法，并初步學(xué)習(xí)使用命題邏輯的方法建立符號體系。為推理打下基礎(chǔ)?；緝?nèi)容：命題與命題聯(lián)結(jié)詞、命題公式、解釋、真值表、命題公式的分類、命題公式的基本等價關(guān)系、命題聯(lián)結(jié)詞的完備集、公式的標準型——范式（析取范式和合取范式、主析取范式和主合取范式）、命題邏輯的推理理論。命題聯(lián)結(jié)詞的應(yīng)用、命題公式的應(yīng)用、范式的應(yīng)用、命題邏輯的推理理論的應(yīng)用。教學(xué)重點：命題聯(lián)結(jié)詞、真值規(guī)定及真值表的構(gòu)建；自然語言的命題符號化；等價定律的運用；主合（析）取范式的計算和命題邏輯的推理。教學(xué)難點：自然語言的命題符號化；極大（?。╉椌幋a的理解；命題公式的等價變形和推理有效性的判別方法。第3章謂詞邏輯8學(xué)時教學(xué)方法：課堂面授教學(xué)目的：正確理解謂詞、量詞的概念，掌握謂詞的語言翻譯，熟練證明合式公式之間的等價關(guān)系。能熟練使用各種推理規(guī)則和推理方法，培養(yǎng)學(xué)生的邏輯思維能力和提高證明問題的技巧?；緝?nèi)容：謂詞邏輯的基本概念與表示（謂詞、量詞、謂詞的語言翻譯）、謂詞公式、自由變元與約束變元、謂詞公式的解釋、謂詞公式的分類、謂詞公式的基本等價定律、謂詞公式的標準型：前束范式、Skolem范式、謂詞邏輯的推理理論和謂詞邏輯的應(yīng)用。教學(xué)重點：自然語言的謂詞符號化、謂詞公式的解釋、特性謂詞識別與翻譯、基本等價規(guī)律、量詞去掉/添加規(guī)則和謂詞邏輯的推理。教學(xué)難點：自然語言的謂詞符號化、謂詞邏輯與命題邏輯的聯(lián)系與區(qū)別、謂詞翻譯的兩條原則、合式公式的解釋和量詞去掉/添加規(guī)則的正確使用。第4章二元關(guān)系6學(xué)時教學(xué)方法：課堂面授教學(xué)目的：正確理解關(guān)系是一種特殊的集合，從集合的觀點理解關(guān)系的基本概念，基本運算和基本性質(zhì)，掌握關(guān)系的運算、關(guān)系的性質(zhì)的判斷，熟練使用按定義法證明關(guān)系的性質(zhì)，為特殊關(guān)系的證明打下基礎(chǔ)?；緝?nèi)容：二元關(guān)系的定義、二元關(guān)系的表示方法、二元關(guān)系的復(fù)合運算、二元關(guān)系的逆運算、二元關(guān)系的冪運算、二元關(guān)系性質(zhì)的定義、二元關(guān)系性質(zhì)的判斷與證明、二元關(guān)系性質(zhì)的保守性、二元關(guān)系的閉包和二元關(guān)系的應(yīng)用。教學(xué)重點：二元關(guān)系的概念和表示；關(guān)系的復(fù)合與逆運算和關(guān)系性質(zhì)的判定與證明。教學(xué)難點：笛卡爾積和二元關(guān)系都是特殊的集合；復(fù)合運算的理解與計算和關(guān)系性質(zhì)的判定與證明。第5章特殊關(guān)系6學(xué)時教學(xué)方法：課堂面授教學(xué)目的：正確理解特殊關(guān)系的本質(zhì)是同時具有某幾個特殊性質(zhì)的關(guān)系，以及特殊關(guān)系之間的區(qū)別與聯(lián)系；能根據(jù)定義熟練判定和證明偏序關(guān)系和等價關(guān)系；會求偏序關(guān)系的8個特殊元；從關(guān)系的角度去理解函數(shù)的定義，函數(shù)的復(fù)合運算；能將特殊關(guān)系的知識用于解決實際問題，培養(yǎng)學(xué)生的抽象思維能力。基本內(nèi)容：相容關(guān)系的定義及集合的覆蓋，等價關(guān)系、等價類、商集、集合的劃分等概念，等價關(guān)系與劃分的相關(guān)定理；偏序關(guān)系、擬序關(guān)系、全序關(guān)系、良序關(guān)系，偏序關(guān)系的哈斯圖、最大元、最小元、極大元、極小元、上界、下界、上確界和下確界以及與這8個特殊元素相關(guān)的定理，函數(shù)的定義和復(fù)合運算、逆運算及其相應(yīng)的定理，函數(shù)的類型，特殊關(guān)系的應(yīng)用。教學(xué)重點：特殊關(guān)系的判定與證明；等價類和商集的計算；8個特殊元的判定；復(fù)合函數(shù)的計算。教學(xué)難點：相容關(guān)系與覆蓋的聯(lián)系；等價關(guān)系與集合劃分的聯(lián)系；特殊關(guān)系的判定與證明；8個特殊元的判定和函數(shù)類型的證明。第6章圖8學(xué)時教學(xué)方法：課堂面授教學(xué)目的：圖是一類具有廣泛實際問題背景的數(shù)學(xué)模型，有著極其豐富的內(nèi)容，是數(shù)據(jù)結(jié)構(gòu)等課程的先修內(nèi)容。學(xué)習(xí)時應(yīng)掌握好圖論的基本概念、基本方法和基本算法，善于把實際問題抽象為圖論的問題，然后用圖論的方法去解決。正確理解圖是兩個集合，從集合的觀點理解圖的基本概念，基本運算和基本性質(zhì)，掌握圖的連通性，熟練使用握手定理證明圖的性質(zhì)?；緝?nèi)容：圖的概念：圖的定義、圖的表示、圖的操作、圖的分類、子圖與補圖、圖的同構(gòu)等；結(jié)點的度數(shù)、圖的基本定理（握手定理）；通路與回路及其長度、特殊通路（回路）、短程線和距離、可達與可達性矩陣；無向連通圖與連通分支、強（單向、弱）連通圖與強（單向、弱）分圖；圖的應(yīng)用。教學(xué)重點：圖的基本概念及分類，握手定理的理解與運用，鄰接矩陣的理解與運用，通路與回路的理解與運用，圖的連通性的判斷與計算，連通分支的判斷與計算。教學(xué)難點：圖同構(gòu)的判斷與證明，單向連通圖的判斷和連通分支的計算。第7章特殊圖8學(xué)時教學(xué)方法：課堂面授教學(xué)目的：正確理解樹、歐拉圖、哈密爾頓圖、偶圖、平面圖的基本概念和基本性質(zhì)，掌握基本判定方法及基本算法?；緝?nèi)容：幾個特殊圖的基本概念、基本性質(zhì)及判定方法；偶圖的匹配、圖的著色；與樹相關(guān)的概念及樹的基本性質(zhì)；樹的基本算法及特殊圖的應(yīng)用。教學(xué)重點：無向樹的定義與性質(zhì)、生成樹與最小生成樹及其求解算法；根樹的定義與分類、歐拉圖及其判定，F(xiàn)leury算法，哈密爾頓圖及其判定，偶圖及其判定，匹配，平面圖及其判定，歐拉公式，庫拉托夫斯基定理。教學(xué)難點：哈密爾頓圖的判定，平面圖的判定，庫拉托夫斯基定理。第8章代數(shù)系統(tǒng)4學(xué)時教學(xué)方法：課堂面授教學(xué)目的：正確理解代數(shù)系統(tǒng)的定義，運算定律及特殊元，培養(yǎng)學(xué)生的抽象思維能力?；緝?nèi)容：代數(shù)系統(tǒng)（代數(shù)運算、代數(shù)系統(tǒng)、子代數(shù)）、代數(shù)系統(tǒng)的基本運算和性質(zhì)（代數(shù)運算的性質(zhì)：交換律、結(jié)合律、分配律、冪等律、吸收律、消去律；代數(shù)系統(tǒng)中的特殊元素：單位元、零元、逆元、冪等元）、同態(tài)和同構(gòu)。教學(xué)重點：代數(shù)運算與子代數(shù)，二元運算律，特殊元及同臺與同構(gòu)。教學(xué)難點：特殊元的計算，運算律的驗證，同態(tài)與同構(gòu)的證明。第9章群、環(huán)、域8學(xué)時教學(xué)方法：課堂面授教學(xué)目的：正確理解群、環(huán)、域這三種特殊代數(shù)系統(tǒng)分類方法，掌握群、環(huán)、域的基本概念，以及群的證明方法?；緝?nèi)容：半群與含幺半群（半群和含幺半群、子半群和子含幺半群、循環(huán)半群與循環(huán)含幺半群的概念、性質(zhì)與判斷）、群及其性質(zhì)（群的定義、元素的周期、子群及其判定條件、群同態(tài)與同構(gòu)）、特殊群（交換群、循環(huán)群）、陪集與拉格朗日定理、不變子群與商群，環(huán)、整環(huán)、除環(huán)和域的定義，子環(huán)、理想和商環(huán)，環(huán)的同態(tài)同構(gòu)定義及計算。教學(xué)重點：群和子群的判定及證明，與各類特殊群和元素階相關(guān)的綜合證明，與陪集和拉格朗日定理相關(guān)的綜合證明，環(huán)和域的證明。教學(xué)難點：各類群、環(huán)、域的判定和證明問題，各類子代數(shù)、子群等的判定與證明，同態(tài)與同構(gòu)相關(guān)的證明，循環(huán)群生成元的尋找，置換群的輪換表示，奇偶性和類型判定，陪集計算及拉格朗日定理的應(yīng)用。第10章格與布爾代數(shù)4學(xué)時教學(xué)方法：課堂面授教學(xué)目的：正確理解格的兩種定義方法及基本性質(zhì)，掌握格的定義及性質(zhì)，子格與格同態(tài)，幾種特殊格的定義及判定方法?；緝?nèi)容：格的基本定義，子格，同態(tài)的基本定義，同構(gòu)意義下不同格的個數(shù)，特殊格及布爾代數(shù)。教學(xué)重點：格的定義及性質(zhì)，子格與格同態(tài)，特殊格和布爾代數(shù)，格中運算定律的驗證，格中運算定律的綜