《離散數(shù)學(xué)》課程教學(xué)大綱課程代碼：ABXX0502課程中文名稱:離散數(shù)學(xué)課程英文名稱：DiscreteMathematics課程性質(zhì)：必修課程學(xué)分?jǐn)?shù)：2.5課程學(xué)時(shí)數(shù)：40授課對(duì)象：信息與計(jì)算科學(xué)本課程的前導(dǎo)課程：高等數(shù)學(xué)、線性代數(shù)一、課程簡(jiǎn)介離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的重要分支，是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論，是信息與計(jì)算科學(xué)專業(yè)的基礎(chǔ)課。本課程著重討論數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論四個(gè)方面的內(nèi)容。通過(guò)本課程的學(xué)習(xí)，能為后續(xù)相關(guān)專業(yè)理論課的學(xué)習(xí)以及將來(lái)從事軟、硬件開(kāi)發(fā)和應(yīng)用研究打下堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)和提供必要的數(shù)學(xué)工具，也能培養(yǎng)學(xué)生的抽象思維能力和嚴(yán)格邏輯推理能力，提高學(xué)生分析問(wèn)題和解決問(wèn)題的能力。二、教學(xué)基本內(nèi)容和要求第一部分命題邏輯課程教學(xué)內(nèi)容：本章是本門課程的重點(diǎn)內(nèi)容之一。命題符號(hào)化及聯(lián)結(jié)詞、命題公式及分類、聯(lián)結(jié)詞全功能集、推理理論。課程的重點(diǎn)：命題符號(hào)化、判斷有效結(jié)論的構(gòu)造推理證明方法。課程的難點(diǎn)：判斷有效結(jié)論的構(gòu)造推理證明方法。課程教學(xué)要求：熟練掌握常用聯(lián)結(jié)詞、命題符號(hào)化、合式公式、公式分類、推理規(guī)則、推理定律、判斷有效結(jié)論的構(gòu)造推理證明方法；掌握命題，公式解釋，真值表，代入規(guī)則，替換規(guī)則，公式的標(biāo)準(zhǔn)型（析取范式、合取范式、主析取范式、主合取范式），判斷有效結(jié)論的真值表法和間接證法；了解聯(lián)結(jié)詞的擴(kuò)充。第二部分一階邏輯課程教學(xué)內(nèi)容：本章是本門課程的重點(diǎn)內(nèi)容之一。一階邏輯基本概念、一階邏輯合式公式及解釋、一階邏輯等值式與前束范式。課程的重點(diǎn)：一階邏輯公式的翻譯，判斷有效結(jié)論的構(gòu)造推理證明方法。課程的難點(diǎn)：量詞的消去和產(chǎn)生規(guī)則，判斷有效結(jié)論的構(gòu)造推理證明方法。課程教學(xué)要求：掌握一階邏輯合式公式的定義、公式的翻譯、約束變?cè)母拿?guī)則；掌握邏輯有效公式、等價(jià)式、量詞的消去和產(chǎn)生規(guī)則和判斷有效結(jié)論的構(gòu)造推理證明方法；理解謂詞、個(gè)體、量詞、指導(dǎo)變?cè)?、轄域、約束變?cè)?、自由變?cè)?、解釋、公式范式等概念。第三部分集合論課程教學(xué)內(nèi)容：本章是本門課程的重點(diǎn)內(nèi)容之一。集合的基本概念、集合的基本運(yùn)算、集合中元素的計(jì)數(shù)。課程的重點(diǎn)：集合的并、交、差和冪集等的運(yùn)算；集合恒等式的證明。課程的難點(diǎn)：集合恒等式的證明。課程教學(xué)要求：理解集合、元素、空集、子集和冪集的定義；熟練掌握集合的幾種運(yùn)算（并、交、差）；掌握文氏圖的方法集中相等，子集合，集合的基數(shù)的定義；掌握冪集，集合的并，交，差運(yùn)算；掌握集合的恒等式以及相等的證明方法。第四部分關(guān)系與函數(shù)課程教學(xué)內(nèi)容：本章是本門課程的重點(diǎn)內(nèi)容之一。集合的笛卡兒積與二元關(guān)系、等價(jià)關(guān)系和偏序關(guān)系、函數(shù)的定義和性質(zhì)。課程的重點(diǎn)：關(guān)系的性質(zhì)，等價(jià)關(guān)系和函數(shù)。課程的難點(diǎn)：偏序關(guān)系和劃分。課程教學(xué)要求：熟練掌握笛卡爾積、關(guān)系的定義、關(guān)系的運(yùn)算、關(guān)系的性質(zhì)、等價(jià)關(guān)系、等價(jià)類、劃分、函數(shù)的定義、函數(shù)的復(fù)合、反函數(shù)、滿射函數(shù)、單射函數(shù)、雙射函數(shù)，掌握關(guān)系的閉包、偏序關(guān)系、極小元、最小元、極大元、最大元和偏序集；掌握關(guān)系矩陣、關(guān)系圖、恒等關(guān)系、恒等函數(shù)和特征函數(shù)；了解線序關(guān)系和線序集。第五部分代數(shù)結(jié)構(gòu)的基本概念及其性質(zhì)課程教學(xué)內(nèi)容：二元運(yùn)算及其性質(zhì)、代數(shù)系統(tǒng)、代數(shù)系統(tǒng)的同態(tài)與同構(gòu)。課程的重點(diǎn)：代數(shù)結(jié)構(gòu)的定義與性質(zhì)。課程的難點(diǎn)：判斷結(jié)構(gòu)是否為代數(shù)結(jié)構(gòu)。課程教學(xué)要求：掌握代數(shù)結(jié)構(gòu)的定義、子代數(shù)的定義；掌握代數(shù)結(jié)構(gòu)的性質(zhì)：交換律、分配律、幺元、零元、逆元、吸收律、等冪律，可約律、可約元等。第六部分群與環(huán)課程教學(xué)內(nèi)容：群的定義及其性質(zhì)、循環(huán)群與置換群、環(huán)與域。課程的重點(diǎn)：群的定義與定理。課程的難點(diǎn)：判定給定的代數(shù)結(jié)構(gòu)是否為群。課程教學(xué)要求：掌握代生成元，群的定義的定義與定理，循環(huán)群與置換群特征。第七部分格與布爾代數(shù)課程教學(xué)內(nèi)容：群的定義及其性質(zhì)、循環(huán)群與置換群、環(huán)與域。課程的重點(diǎn)：格的定義與性質(zhì)、分配格、有補(bǔ)格與布爾代數(shù)。課程的難點(diǎn)：與格有關(guān)定理的證明、布爾代數(shù)相關(guān)定理的證明。課程教學(xué)要求：掌握格的定義和布爾代數(shù)的概念；掌握與格有關(guān)的幾個(gè)定理，掌握分配格和有補(bǔ)格的概念以及與它們相關(guān)的定理，掌握布爾代數(shù)相關(guān)定理。第八部分圖論課程教學(xué)內(nèi)容：圖的基本概念、特殊的圖、樹(shù)。課程的重點(diǎn)：圖的矩陣表示形式，最小生成樹(shù)和哈夫曼算法樹(shù)。課程的難點(diǎn)：圖的矩陣表示形式，最小生成樹(shù)和哈夫曼算法樹(shù)。課程教學(xué)要求：掌握?qǐng)D定義；掌握結(jié)點(diǎn)、邊、結(jié)點(diǎn)的度的定義；了解始結(jié)點(diǎn)，長(zhǎng)度，簡(jiǎn)單鏈，基本鏈，簡(jiǎn)單圈，基本圈，結(jié)點(diǎn)的連通度，鄰接矩陣的相乘；掌握無(wú)向樹(shù)的概念與相關(guān)的定理，掌握生成樹(shù)的概念，了解相關(guān)定理，熟練掌握最小生成樹(shù)的求法，掌握根樹(shù)的概念，熟練掌握哈夫曼算法樹(shù)。三、實(shí)驗(yàn)教學(xué)內(nèi)容及基本要求無(wú)四、教學(xué)方法與手段1.課程概念多、抽象、涉及面廣，教學(xué)形式以講授方式為主+多媒體輔助。2.課程概念多、比較抽象，算法分析有一定難度，為了學(xué)生進(jìn)一步理解課堂教學(xué)內(nèi)容，擬布置一定數(shù)量習(xí)題為宜，教師批改作業(yè)本的1/3,并安排時(shí)間上習(xí)題課。五、教學(xué)學(xué)時(shí)分配章節(jié)與內(nèi)容課時(shí)作業(yè)量備注一命題邏輯8二一階邏輯61課時(shí)習(xí)題課三集合論4四關(guān)系與函數(shù)61課時(shí)習(xí)題課五代數(shù)結(jié)構(gòu)的基本概念及其性質(zhì)2六群與環(huán)2七格與布爾代數(shù)4八圖論61課時(shí)習(xí)題可合計(jì)40六、考核方式與成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)1、考核方法：考試。2、成績(jī)?cè)u(píng)定：總評(píng)成績(jī)=期終成績(jī)（70%）+平時(shí)成績(jī)（30%），平時(shí)成績(jī)不合格者取消考試資格。七、教學(xué)參考資源參考書(shū)目：（1）屈婉玲，耿素