離散結(jié)構(gòu)課程介紹和教學(xué)大綱

1、離散結(jié)構(gòu)課程簡介課程編號1240513001課程名稱離散結(jié)構(gòu)課程性質(zhì)必修學(xué) 時(shí)48學(xué) 分3學(xué)時(shí)分配授課：48   實(shí)驗(yàn)： 上機(jī)：   實(shí)踐：    實(shí)踐（周）：考核方式閉卷考試，平時(shí)成績占30% ，期末成績占70% 。開課學(xué)院信息工程學(xué)院更新時(shí)間適用專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程先修課程高等數(shù)學(xué)、線性代數(shù)課程內(nèi)容：離散結(jié)構(gòu)，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)中基礎(chǔ)理論的核心課程。它以研究離散量的結(jié)構(gòu)和相互之間的關(guān)系為主要目標(biāo)，其研究對象一般是有限個(gè)或可數(shù)個(gè)元素，因此它充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。本課程包括數(shù)理邏輯、集合論、代

2、數(shù)結(jié)構(gòu)，圖論等四個(gè)內(nèi)容。各個(gè)部分從不同的角度研究各種離散量的結(jié)構(gòu)和相互關(guān)系，它們既是獨(dú)立的又是相互有聯(lián)系的。Brief Introduction  Code1240513001TitleDiscrete MathematicsCourse natureRequiredSemester Hours48Credits3Semester Hour StructureLecture：48  Experiment：0  Computer Lab：0 Practice (Week)：AssessmentClosed book examination, usually resu

3、lts accounted for 30%, the final grade accounted for 70%.Offered bySchool of Information EngineeringDate2012-9forComputer Science and Technology, Software EngineeringPrerequisiteCalculus, Linear AlgebraCourse Description:Discrete structure, modern mathematics is an important branch of computer scien

4、ce is the theoretical foundation in the core curriculum. It discrete quantity to study the structure and the relationship between the main aim of their study is generally limited or a few elements, it fully describes the dispersion of Computer Science characteristics.The courses include mathematical

5、 logic and set theory, algebraic structures, graph theory, and so the four elements. Various parts from various different perspectives on the structure and dispersion of mutual relations, which is independent and is linked to each other.離散結(jié)構(gòu)課程教學(xué)大綱課程編號1240513001課程名稱離散結(jié)構(gòu)課程性質(zhì)必修學(xué) 時(shí)48學(xué) 分3學(xué)時(shí)分配授課：48  

6、 實(shí)驗(yàn)： 上機(jī)：  實(shí)踐：    實(shí)踐（周）：考核方式閉卷考試，平時(shí)成績占30% ，期末成績占70% 。開課學(xué)院信息工程學(xué)院更新時(shí)間適用專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程先修課程高等數(shù)學(xué)、線性代數(shù)一、教學(xué)內(nèi)容第一章 命題邏輯基本概念1.1 命題與聯(lián)結(jié)詞1.2 命題公式及其賦值教學(xué)重點(diǎn)： 簡單命題（既原子命題）與復(fù)合命題； 5種常用聯(lián)結(jié)詞，復(fù)合命題的符號化； “相容或”與“排斥或”； 命題公式的賦值、成真賦值、成假賦值。教學(xué)難點(diǎn)：“相容或”與“排斥或”的區(qū)別。第二章 命題邏輯等值演算2.1 等值式2.2 析取范式與合取范式2.3 聯(lián)結(jié)詞的完備集教學(xué)重點(diǎn)： 等值

7、式的定義； 基本等值式及置換規(guī)則進(jìn)行等值演算； 文字、簡單析取式、簡單合取式、析取范式，合取范式； 極小項(xiàng)、極大項(xiàng)的定義，名稱、下角標(biāo)與成真賦值的關(guān)系，主析取范式與主合取范式； 求主析取(主合取)范式的方法； 主析取范式求公式的成真賦值、成假賦值、判斷公式的類型、判斷兩個(gè)公式是否等值； 將任何命題公式等值地化成某聯(lián)結(jié)詞完備集中的公式。教學(xué)難點(diǎn)：求主析取(主合取)范式。第三章 命題邏輯的推理理論3.1 推理的形式結(jié)構(gòu)3.2 自然推理系統(tǒng)教學(xué)重點(diǎn)： 推理的不同方法，如真值表法、等值演算法、主析取范式法等； 各條推理規(guī)則的內(nèi)容及名稱； 在P系統(tǒng)中構(gòu)造證明的直接證明法、附加前提證明法、歸謬法。教學(xué)難點(diǎn)

8、： 基本推理方法：等值演算法、主析取范式法等； 基本證明方法：直接證明法、附加前提證明法、歸謬法。第四章 一階邏輯基本概念4.1 一階邏輯命題符號化4.2 一階邏輯公式及解釋教學(xué)重點(diǎn)： 一階邏輯公式，永真式、矛盾式、可滿足式的概念及其判別方法； 閉式的概念及閉式的性質(zhì)； 給定的解釋會判斷給定公式的類型。教學(xué)難點(diǎn)：給定的解釋會判斷給定公式的類型。第五章 一階邏輯等值演算與推理5.1 一階邏輯等值式與置換規(guī)則5.2 一階邏輯前束范式5.3 一階邏輯的推理理論教學(xué)重點(diǎn)： 一階邏輯中的重要的等值式； 置換規(guī)則、換名規(guī)則、代替規(guī)則； 求出給定公式的前束范式； 自然推理系統(tǒng)F中的各條推理規(guī)則； 對于給定的

9、推理，要求正確地給出它的證明。教學(xué)難點(diǎn)：自然推理系統(tǒng)F中的各條推理規(guī)則，求正確地給出它的證明。第六章 集合代數(shù)6.1 集合的基本概念6.2 集合的運(yùn)算6.3 集合恒等式教學(xué)重點(diǎn)： 集合的兩種表示法； 集合之間的包含、相等、真包含等關(guān)系； 集合的基本運(yùn)算（寡集運(yùn)算，普通運(yùn)算和廣義運(yùn)算）； 有窮集合的計(jì)數(shù)方法；證明集合等式或者包含關(guān)系的基本方法。教學(xué)難點(diǎn)：有窮集合的計(jì)數(shù)方法，證明集合等式或者包含關(guān)系的基本方法。第七章 二元關(guān)系教學(xué)內(nèi)容：7.1 有序?qū)εc笛卡兒積7.2 二元關(guān)系7.3 關(guān)系的運(yùn)算7.4 關(guān)系的性質(zhì)7.5 關(guān)系的閉包7.6 等價(jià)關(guān)系與劃分7.7 偏序關(guān)系教學(xué)重點(diǎn)： 有序?qū)Α⒍P(guān)系、集

10、合A到B的關(guān)系、集合A上的關(guān)系(包含空關(guān)系、全域關(guān)系、小于等于關(guān)系、整除關(guān)系、包含關(guān)系等)的定義掌握笛卡兒積的運(yùn)算和性質(zhì)； 關(guān)系表達(dá)式、關(guān)系矩陣、關(guān)系圖的表示法； 關(guān)系的定義域、值域、逆、右復(fù)合、限制、像、冪的計(jì)算方法； 集合A上關(guān)系R的自反閉包、對稱閉包和傳遞閉包； 關(guān)系運(yùn)算的集合恒等式或者包含式； 判斷關(guān)系五種性質(zhì)的方法，并能對關(guān)系的自反、對稱、反對稱、傳遞性給出證明； 等價(jià)關(guān)系、等價(jià)類、商集、劃分的概念，以及等價(jià)關(guān)系與劃分的對應(yīng)性質(zhì)； 偏序關(guān)系、偏序集、哈斯圖、偏序集中的特定元素等概念。教學(xué)難點(diǎn)：關(guān)系的閉包運(yùn)算，等價(jià)關(guān)系、等價(jià)類；偏序關(guān)系、偏序集、哈斯圖。第八章 函數(shù)8.1 函數(shù)的定義與

11、性質(zhì)8.2 函數(shù)的復(fù)合與反函數(shù)教學(xué)重點(diǎn)： 函數(shù)的概念，會判斷給定集合是否為函數(shù)、是否為從A到B的函數(shù)； 計(jì)算函數(shù)的值、像、完全原像； 單射、滿射、雙射的性質(zhì)、構(gòu)造從A到B的雙射函數(shù)； 復(fù)合函數(shù)、雙射函數(shù)的反函數(shù)。教學(xué)難點(diǎn)：復(fù)合函數(shù)、雙射函數(shù)的反函數(shù)。第九章 代數(shù)系統(tǒng)9.1 二元運(yùn)算及其性質(zhì)9.2 代數(shù)系統(tǒng)教學(xué)重點(diǎn)：代數(shù)運(yùn)算的概念； 代數(shù)運(yùn)算的表示方法； 二元運(yùn)算定律 特異元素；代數(shù)系統(tǒng)的概念，同類型的代數(shù)系統(tǒng)，子代數(shù)的概念。教學(xué)難點(diǎn)：同類型的代數(shù)系統(tǒng)。第十章 半群和群10.1 半群與獨(dú)異點(diǎn)10.2 群的定義與性質(zhì)10.3 子群10.4 陪集與拉格朗日定理10.5 正規(guī)子群與商群10.6 群的同

12、態(tài)與同構(gòu)10.7 循環(huán)群與置換群教學(xué)重點(diǎn)：半群和獨(dú)異點(diǎn)的概念及性質(zhì)；群的定義及性質(zhì)；子群的概念，子群判定定理； 陪集的概念，拉格朗日定理，正規(guī)子群的概念，正規(guī)子群的性質(zhì)及判定；群的同態(tài)概念； 循環(huán)群的概念，循環(huán)群的性質(zhì)； 置換群的概念，置換群的性質(zhì)。教學(xué)難點(diǎn)：子群判定定理，正規(guī)子群的性質(zhì)及判定，群的同態(tài)概念。第十一章 環(huán)與域11.1 環(huán)的定義與性質(zhì)11.2 整環(huán)與域教學(xué)重點(diǎn)：環(huán)的概念及性質(zhì)； 域的概念及性質(zhì)。教學(xué)難點(diǎn)：域。第十二章 格與布爾代數(shù)12.1 格的定義與性質(zhì)12.2 子格與格同態(tài)12.3 分配格與有補(bǔ)格12.4 布爾代數(shù)教學(xué)重點(diǎn)：格的概念與性質(zhì)；子格的概念 布爾代數(shù)的概念。教學(xué)難點(diǎn)：

13、布爾代數(shù)。第十三章 圖的基本概念13.1 圖13.2 通路與回路13.3 圖的連通性13.4 圖的矩陣表示13.5 圖的運(yùn)算教學(xué)重點(diǎn)： 圖的定義； 握手定理； 同構(gòu)，簡單圖，完全圖，正則圖，子圖，補(bǔ)圖，二部圖等概念及其它們的性質(zhì)和相互關(guān)系； 通路與回路的定義，相互關(guān)系及其分類，掌握通路與回路的各種不同的表示方法； 無向圖的連通性，連通分支等概念； 無向圖的點(diǎn)連通度、邊連通度等概念及其之間的關(guān)系； 用有向圖的鄰接矩陣及各次冪求圖中通路與回路數(shù)的方法； 有向圖的關(guān)聯(lián)矩陣、距離矩陣、可達(dá)矩陣。教學(xué)難點(diǎn)：無向圖的連通性，連通分支；無向圖的點(diǎn)連通度、邊連通度。第十四章 歐拉圖與哈密爾頓圖14.1 歐拉圖

14、14.2 哈密頓圖14.3 帶權(quán)圖與貨郎擔(dān)問題教學(xué)重點(diǎn)： 歐拉圖與半歐拉圖的定義及判別定理； 哈密頓圖及半哈密頓圖的定義； 分清哈密頓圖的必要條件和充分條件； 對于完全帶權(quán)圖K4和K5能準(zhǔn)確地求出最短的哈密頓回路教學(xué)難點(diǎn)：歐拉圖與半歐拉圖的判別定理；哈密頓圖及半哈密頓圖的判別定理。第十五章 樹15.1 無向樹及其性質(zhì)15.2 生成樹15.3 根樹及其應(yīng)用教學(xué)重點(diǎn)： 無向樹的定義及性質(zhì)； 畫出階數(shù)n較小的所有非同構(gòu)的無向樹； 基本回路，基本回路系統(tǒng)，基本割集，基本割集系統(tǒng)； Kruskal算法求最小生成樹； 根樹及其分類，階數(shù)n較小(如1n5)所有非同構(gòu)的根樹； Huffman算法，并用它求最佳

15、前綴碼； 波蘭符號法及逆波蘭符號法的算法； 波蘭符號法及逆波蘭符號法的算法教學(xué)難點(diǎn)：n階樹的所有非同構(gòu)的無向樹；Kruskal算法求最小生成樹；Huffman算法，并用它求最佳前綴碼；二、教學(xué)要求第一章 命題邏輯基本概念教學(xué)要求：掌握命題簡單命題（既原子命題）與復(fù)合命題；掌握5種常用聯(lián)結(jié)詞的涵義，應(yīng)用它們將基本復(fù)合命題及復(fù)合命題符號化；掌握“相容或”與“排斥或”； 掌握命題公式的賦值、成真賦值、成假賦值，判斷出公式的類型。第二章 命題邏輯等值演算教學(xué)要求：掌握等值式的定義，公式之間的等值關(guān)系具有自反性、對稱性、傳遞性；等值式的名稱及它們的內(nèi)容；應(yīng)用基本等值式及置換規(guī)則進(jìn)行等值演算；掌握文字、簡

16、單析取式、簡單合取式、析取范式，合取范式等概念；極小項(xiàng)、極大項(xiàng)的定義，名稱、下角標(biāo)與成真賦值的關(guān)系，主析取范式與主合取范式；掌握求主析取(主合取)范式的方法；理解用主析取范式求公式的成真賦值、成假賦值、判斷公式的類型、判斷兩個(gè)公式是否等值；理解將任何命題公式等值地化成某聯(lián)結(jié)詞完備集中的公式。第三章 命題邏輯的推理理論教學(xué)要求：掌握推理形式結(jié)構(gòu)的兩種形式；判斷推理是否正確的不同方法，如真值表法、等值演算法、主析取范式法等；掌握系統(tǒng)中各條推理規(guī)則的內(nèi)容及名稱；掌握在P系統(tǒng)中構(gòu)造證明的直接證明法、附加前提證明法、歸謬法；將日常生活中、社會活動(dòng)中、科學(xué)領(lǐng)域中的某些推理形式化，即寫出符號化形式的前提、結(jié)

17、論，并能判斷推理是否正確，對于正確的推理能在P系統(tǒng)中給出證明。第四章 一階邏輯基本概念教學(xué)要求：將給定命題符號化；分清在41節(jié)中給出(1)(7)或更多種的符號化形式，特別要注意兩個(gè)基本公式中量詞與聯(lián)結(jié)詞的搭配情況，理解其實(shí)(5)、(6)、(7)等都是兩個(gè)基本公式(3)與(4)的應(yīng)用；永真式、矛盾式、可滿足式的概念及其判別方法；掌握閉式的概念及閉式的性質(zhì)(閉式在任何解釋下都是命題)；掌握給定的解釋會判斷給定公式是否成為命題，對是命題的能判斷出是真命題，還是假命題。第五章 一階邏輯等值演算與推理教學(xué)要求：理解一階邏輯中的重要的等值式，并能準(zhǔn)確而熟練地應(yīng)用他們；使用置換規(guī)則、換名規(guī)則、代替規(guī)則；求出

18、給定公式的前束范式；掌握自然推理系統(tǒng)F的定義，牢記F中的各條推理規(guī)則，特別是要正確使用UI、UG、EG、EI 4條推理規(guī)則；對于給定的推理，要求正確地給出它的證明。第六章 集合代數(shù)教學(xué)要求：掌握集合的兩種表示法；判別元素是否屬于給定的集合；掌握判別兩個(gè)集合之間是否存在包含、相等、真包含等關(guān)系；掌握集合的基本運(yùn)算（寡集運(yùn)算，普通運(yùn)算和廣義運(yùn)算）并能化簡集合表達(dá)式；理解有窮集合的計(jì)數(shù)方法；理解證明集合等式或者包含關(guān)系的基本方法。第七章 二元關(guān)系教學(xué)要求：掌握有序?qū)?、二元關(guān)系、集合A到B的關(guān)系、集合A上的關(guān)系(包含空關(guān)系、全域關(guān)系、小于等于關(guān)系、整除關(guān)系、包含關(guān)系等)的定義掌握笛卡兒積的運(yùn)算和性質(zhì)；

19、掌握關(guān)系表達(dá)式、關(guān)系矩陣、關(guān)系圖的表示法；掌握關(guān)系的定義域、值域、逆、右復(fù)合、限制、像、冪的計(jì)算方法；計(jì)算集合A上關(guān)系R的自反閉包、對稱閉包和傳遞閉包；掌握證明含有上述關(guān)系運(yùn)算的集合恒等式或者包含式；理解判斷關(guān)系五種性質(zhì)的方法，對關(guān)系的自反、對稱、反對稱、傳遞性給出證明；等價(jià)關(guān)系、等價(jià)類、商集、劃分的概念，以及等價(jià)關(guān)系與劃分的對應(yīng)性質(zhì)；理解偏序關(guān)系、偏序集、哈斯圖、偏序集中的特定元素等概念；用上述關(guān)系模型處理簡單的實(shí)際問題。第八章 函數(shù)教學(xué)要求：理解函數(shù)的基本概念，判斷給定集合是否為函數(shù)、是否為從A到B的函數(shù)；理解計(jì)算函數(shù)的值、像、完全原像；理解判斷和證明函數(shù)的單射、滿射、雙射的性質(zhì)；給定集合

20、A和B，會構(gòu)造從A到B的雙射函數(shù)；理解計(jì)算復(fù)合函數(shù)、雙射函數(shù)的反函數(shù)。第九章 代數(shù)系統(tǒng)教學(xué)要求：理解代數(shù)運(yùn)算的概念，各種特異元素；理解代數(shù)運(yùn)算定律的概念，并能熟練應(yīng)用；理解代數(shù)系統(tǒng)的概念；了解同類型的代數(shù)系統(tǒng)；子代數(shù)的概念。第十章 半群和群教學(xué)要求：掌握半群和獨(dú)異點(diǎn)的概念及性質(zhì)；掌握群的定義及性質(zhì)；掌握子群的概念，子群判定定理；理解陪集的概念，拉格朗日定理；掌握正規(guī)子群的概念，正規(guī)子群的性質(zhì)及判定；掌握群的同態(tài)概念；理解循環(huán)群的概念，循環(huán)群的性質(zhì)，應(yīng)用相關(guān)定理；掌握置換群的概念，置換群的性質(zhì)。第十一章 環(huán)與域教學(xué)要求：理解環(huán)的概念及性質(zhì)；理解域的概念及性質(zhì)。第十二章 格與布爾代數(shù)教學(xué)要求：掌握格的概念與性質(zhì)；掌握子格的概念；掌握布爾代數(shù)的概念。第十三章 圖的基本概念教學(xué)要求：掌握圖的定義有關(guān)的諸多概念，以及它們之間的相互關(guān)系；理解圖同構(gòu)，簡單圖，完全圖，正則圖，子圖，補(bǔ)圖，二部圖等概念及其它們的性質(zhì)和相互關(guān)系，并能熟練地應(yīng)用這些性質(zhì)和關(guān)系；深刻理解通路與回路的定義，相互關(guān)系及其分類，掌握通路與回路的各種不同的表示方法；無向圖的連通性，連通分支等概