2005級(jí)-離散數(shù)學(xué)(1)教案-李占山,于海鴻,盧欣華VIP

1、課程編碼：（參考本科培養(yǎng)計(jì)劃）離散數(shù)學(xué)I課程教案 2008 2009 學(xué)年第 1 學(xué)期任課教師： 李占山 于海鴻 盧欣華吉林大學(xué)計(jì)算機(jī)學(xué)院課程名稱： 離散數(shù)學(xué)I 課程英文名稱：discreted mathematics學(xué)時(shí)： 64學(xué)分：授課對(duì)象： 計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè) 2007級(jí)1-14班教學(xué)目的：（參照教學(xué)大綱）教學(xué)方式：板書 多媒體 投影教材：孫吉貴等離散數(shù)學(xué)高等教育出版社，2002教學(xué)參考書：孫吉貴等離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答高等教育出版社，2003耿素云集合論與圖論 北京大學(xué)出版社，1998 授課題目11集合的基本概念授課學(xué)時(shí)4授課時(shí)間第1周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：1集合、子集、超

2、集、空集、冪集、集合族的概念。兩個(gè)集合間相等和包含關(guān)系的定義和性質(zhì)，利用定義證明兩個(gè)集合相等。常用的集合表示方法。2集合的基本運(yùn)算：并、交、余、差、直乘積，對(duì)稱差的定義以及集合運(yùn)算滿足的基本算律，利用它們來證明更復(fù)雜的集合等式。教學(xué)難點(diǎn)：1如何去證明兩個(gè)集合相等與包含；2笛卡兒積的深入理解與實(shí)際應(yīng)用。教學(xué)要點(diǎn)：1集合及集合相關(guān)概念2集合的分類：有窮集（有限集）、無窮集。3空集和全集的定義。4給出集合的關(guān)系：集合相等和包含關(guān)系。5冪集的定義及性質(zhì)。6集合族的定義。7集合的運(yùn)算：差、并、余（補(bǔ)）與交運(yùn)算8笛卡兒積的定義及性質(zhì)。9集合的算律。10集合的表示方法主要有3種：描述法；列舉法；文氏圖法(J

3、ohn Venn) 講述方法：本節(jié)在講述基本概念時(shí)要引入大量的實(shí)例，讓學(xué)生充分理解定義的內(nèi)涵與外延；在給出集合相等定義的同時(shí)要引導(dǎo)學(xué)生思考如何去證明兩個(gè)集合相等以及兩個(gè)集合的包含關(guān)系；在講解集合的算律時(shí)要講、練結(jié)合，將書中所給的算律充分融入到習(xí)題中，讓學(xué)生通過練習(xí)來掌握算律，而不是死記硬背。參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解·精練 黃健斌 西安電子科技大學(xué)出版社集合論與圖論 耿素云 北京大學(xué)出版社 作業(yè)安排：教材中習(xí)題1.1中的第1、2題。答疑時(shí)間：另行安排授課題目12 關(guān)系授課學(xué)時(shí)6授課時(shí)間第2、3周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)

4、：1關(guān)系、二元關(guān)系、空關(guān)系、全域關(guān)系、相等關(guān)系、逆關(guān)系的概念以及關(guān)系的性質(zhì)：自反性、對(duì)稱性、反對(duì)稱性、傳遞性。會(huì)做關(guān)系的乘積。了解關(guān)系的閉包運(yùn)算：自反閉包、對(duì)稱閉包、傳遞閉包。2等價(jià)關(guān)系、等價(jià)類、商集的概念，了解等價(jià)關(guān)系和劃分的內(nèi)在聯(lián)系。3部分序關(guān)系、部分序集、全序關(guān)系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、極大元、極小元、上確界、下確界的定義。能畫出有限部分序集的Hasse圖，并根據(jù)圖討論部分序集的某些性質(zhì)。教學(xué)難點(diǎn)：1等價(jià)關(guān)系與等價(jià)類的理解；2部分序集的理解教學(xué)要點(diǎn)：1關(guān)系的基本概念及其性質(zhì)關(guān)系的定義及特點(diǎn)講授方法：通過例1.2.1 來引導(dǎo)學(xué)生理解關(guān)系的定義并總結(jié)出其特點(diǎn)。

5、關(guān)系的運(yùn)算關(guān)系的并、交、差、余等運(yùn)算。講授方法：通過引導(dǎo)學(xué)生思考子關(guān)系的定義基礎(chǔ)上，給出關(guān)系的并、交、差、余的運(yùn)算。注：（1）集合的并、交、差、余運(yùn)算性質(zhì)對(duì)關(guān)系運(yùn)算也成立。（2）作為關(guān)系時(shí)，余運(yùn)算是對(duì)全域關(guān)系而言的，即A´B作為全集E。關(guān)系的性質(zhì)自反性；對(duì)稱性；傳遞性；反自反、反對(duì)稱及遞講授方法：在講關(guān)系的性質(zhì)時(shí)，可以引入一些日常生活中的實(shí)例讓學(xué)生理解關(guān)系的性質(zhì)。2關(guān)系的乘法關(guān)系的乘法定義及定理1.2.1至1.2.43關(guān)系的閉包。關(guān)系的閉包定義及求解方法（定理1.2.5）4等價(jià)關(guān)系 等價(jià)關(guān)系、等價(jià)類的定義；商集的定義； 等價(jià)關(guān)系、等價(jià)類的計(jì)算（求解即定理1.2.6至1.2.8） 講授

6、方法：通過1.2.2至1.2.5等例子來講解。讓學(xué)生逐步理解等價(jià)關(guān)系、等價(jià)類和商集的定義，并求解集合上等價(jià)關(guān)系和等價(jià)類，引導(dǎo)學(xué)生思考定理的局限性。5部分序關(guān)系。 部分序關(guān)系的定義及部分序集的定義集合的最大、最小元素、極大、極小元素部分序集的哈斯圖的畫法講授方法：通過具體的例子來講解該部分內(nèi)容。作業(yè)安排：教材中習(xí)題1.2中的第9、10題。答疑時(shí)間：另行安排授課題目13映射授課學(xué)時(shí)4授課時(shí)間第3、4周教學(xué)重點(diǎn)、難點(diǎn)：1掌握映射、映像、1-1映射等概念，會(huì)做映射的乘積。2了解可數(shù)集合的概念，掌握可數(shù)集合的判定方法。教學(xué)難點(diǎn)：1判斷集合的可數(shù)、不可數(shù)2證明集合的可數(shù)、不可數(shù)教學(xué)要點(diǎn)：1映射的基本概念映

7、射的定義；單射、滿射的定義；1-1映射的定義；映射的復(fù)合定義；逆映射的定義；講授方法：通過大量的示意圖來讓學(xué)生理解這些基本概念。2集合的基數(shù)集合基數(shù)的定義，表示形式；兩個(gè)集合基數(shù)相等的定義；集合間基數(shù)的比較；講授方法：本部分內(nèi)容的講解可以結(jié)合一些具體的例子特別是自然數(shù)，學(xué)生較好理解。3可數(shù)集合可數(shù)集合的定義；判斷集合可數(shù)的方法；講授方法：通過給出可數(shù)集合的概念，以及講解定理證明的過程，引導(dǎo)學(xué)生逐步掌握集合可數(shù)的判斷方法。4不可數(shù)集合不可數(shù)集合的定義；判斷集合不可數(shù)的方法；講授方法：通過定理1.3.6證明過程的講解，讓學(xué)生掌握康托爾對(duì)角線法；通過定理1.3.8的證明過程講解，引導(dǎo)學(xué)生逐步掌握構(gòu)造

8、性證明方法，以及反證法的應(yīng)用。5本章內(nèi)容小結(jié)參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解·精練 黃健斌 西安電子科技大學(xué)出版社集合論與圖論 耿素云 北京大學(xué)出版社 作業(yè)安排：教材中習(xí)題1.3中的第1、2題。答疑時(shí)間：另行安排授課題目2.1 命題以及邏輯聯(lián)結(jié)詞授課學(xué)時(shí)1.5授課時(shí)間第4周教學(xué)重點(diǎn)：掌握命題、簡(jiǎn)單命題、復(fù)合命題的概念，掌握命題真假的判斷方法教學(xué)難點(diǎn)：理解蘊(yùn)涵命題為真為假的前提條件教學(xué)要點(diǎn)：1命題的基本概念。命題的定義；理解和掌握簡(jiǎn)單命題和復(fù)合命題；講授方法：首先給出定義，然后通過例子理解和掌握定義，并且要求學(xué)生區(qū)分出簡(jiǎn)單命題

9、和復(fù)合命題。2命題的真值 命題的真值有兩種：0（假），1（真）講授方法：首先要求學(xué)生明確定義，然后給出一些命題要求學(xué)生判斷真假值。從而讓學(xué)生進(jìn)一步明確命題的定義（引申）。3常用的聯(lián)結(jié)詞 聯(lián)結(jié)詞的定義：五種常用的聯(lián)結(jié)詞符號(hào)：Ø（否）Ú（析?。?#217;（合?。?#174;（蘊(yùn)含）«（等價(jià)）聯(lián)結(jié)詞的運(yùn)算表聯(lián)結(jié)詞的運(yùn)算優(yōu)先級(jí)聯(lián)結(jié)詞的含義以及自然語言描述參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解·精練 黃健斌 西安電子科技大學(xué)出版社作業(yè)安排：教材中習(xí)題2.1中的第3題。答疑時(shí)間：另行安排授課題目2.2 命題公式

10、授課學(xué)時(shí)2.5授課時(shí)間第4、5周教學(xué)重點(diǎn)：掌握命題公式的概念，理解命題公式的解釋的定義教學(xué)難點(diǎn)：給定一個(gè)公式，判定其是否為恒真公式或恒假公式教學(xué)要點(diǎn)： 1公式的基本概念。原子的定義；命題邏輯中的公式定義；講授方法：給出命題邏輯中的公式定義，逐步引導(dǎo)學(xué)生領(lǐng)會(huì)遞歸定義的方法。2解釋的定義解釋的定義；例子； 講授方法：回顧命題的相關(guān)知識(shí)，給出一個(gè)命題公式，進(jìn)行賦值，判斷其真、假值，引出解釋的定義。3真值表 真值表的定義：真值表的畫法；記住一個(gè)結(jié)論：n個(gè)不同原子的公式，共有2n個(gè)解釋。講授方法：通過一具體例子，教會(huì)學(xué)生會(huì)畫真值表，并引導(dǎo)學(xué)生學(xué)會(huì)利用真值表來判斷公式是否恒真、恒假、可滿足。4公式G恒真的

11、定義；公式G恒假的定義；公式G可滿足的定義。5如何判斷一個(gè)公式恒真、恒假、可滿足。 參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解·精練 黃健斌 西安電子科技大學(xué)出版社作業(yè)安排：習(xí)題2.2.4 答疑安排：另行通知授課題目2.3 命題公式的等價(jià)關(guān)系和蘊(yùn)涵關(guān)系授課學(xué)時(shí)4授課時(shí)間第5、6周教學(xué)重點(diǎn)：掌握命題公式的等價(jià)的相關(guān)概念；掌握命題公式蘊(yùn)涵的相關(guān)概念；掌握演繹的相關(guān)概念和有關(guān)定理；掌握基本蘊(yùn)涵式；理解公式蘊(yùn)涵的證明方法。教學(xué)難點(diǎn)：公式蘊(yùn)涵的證明方法；區(qū)別公式蘊(yùn)涵和命題蘊(yùn)涵的差異。教學(xué)要點(diǎn)：1公式的等價(jià)相關(guān)概念。公式等價(jià)的定義；公式G、H等價(jià)

12、的充要條件；基本等價(jià)式；完備集的定義以證明。講授方法：給出公式等價(jià)的定義及一些基本等價(jià)式（要求學(xué)生通過上節(jié)課所學(xué)內(nèi)容可以證明）。 2公式的蘊(yùn)涵相關(guān)概念及相關(guān)定理公式的蘊(yùn)涵的定義；公式G蘊(yùn)涵公式H的充要條件；定理2.3.1 講授方法：通過一個(gè)例子給出公式蘊(yùn)涵的定義（注意區(qū)別Þ和=），給出定理2.3.1利用基本等價(jià)公式證明。3演繹的相關(guān)概念及相關(guān)定理 演繹的定義：引理定理2.3.2定理2.3.3一些基本蘊(yùn)涵式4公式蘊(yùn)涵的證明方法講授方法：通過回憶的方法逐一引導(dǎo)學(xué)生思考如何證明公式G蘊(yùn)涵H。 參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解

13、83;精練 黃健斌 西安電子科技大學(xué)出版社離散數(shù)學(xué) 耿素云等 高等教育出版社 作業(yè)安排：習(xí)題2.3.1、8 答疑安排：另行通知授課題目2.4 范式授課學(xué)時(shí)4授課時(shí)間第6、7周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：1析取范式、合取范式、極大項(xiàng)、極小項(xiàng)、主析取范式、主合取范式的概念和性質(zhì)。2掌握求各種范式的方法，能夠用等價(jià)演算法和真值表法求命題公式的主析取范式、主合取范式。3了解一個(gè)命題公式的主合取范式與主析取范式的關(guān)系。教學(xué)難點(diǎn)：1命題公式的析取范式與合取范式的轉(zhuǎn)化；2命題公式恒真、恒假的判斷。教學(xué)要點(diǎn)： 1范式的概念 文字的定義；子句的定義；短語的定義。 提醒學(xué)生注意：一個(gè)文字既可稱為是一個(gè)子句，也可稱為

14、是一個(gè)短語。 析取范式的定義；合取范式的定義 提醒學(xué)生注意：一個(gè)文字既可稱為是一個(gè)合取范式，也可稱為是一個(gè)析取范式。一個(gè)子句，一個(gè)短語既可看做是合取范式，也可看做是析取范式。 講授方法：講解時(shí)可以通過一個(gè)具體的例子來展示定義的內(nèi)涵。 對(duì)于任意命題公式，都存在等價(jià)于它的析取范式和合取范式。2主析取范式和主合取范式 極小（大）項(xiàng)的定義； 結(jié)論：n個(gè)不同原子的公式，有2n個(gè)不同的極?。ù螅╉?xiàng)。主析取范式的概念；主合取范式的概念。 對(duì)于命題公式G，都存在等價(jià)于它的主析取范式。 設(shè)公式G，H是關(guān)于原子P1，Pn的兩個(gè)主析取范式。 如果G，H不完全相同，則G，H不等價(jià)。 對(duì)于任意公式G，存在唯一一個(gè)與G等

15、價(jià)的主析取范式。講授方法：講解本部分內(nèi)容可以做這樣的教學(xué)設(shè)計(jì)：給出一個(gè)公式G，它的范式是不唯一的，能否有唯一的標(biāo)準(zhǔn)形式呢? （提出問題）答案是有（引導(dǎo)學(xué)生分析問題），引出主析取范式和主合取范式的概念。（解決問題）3恒真恒假性的判定 解決判定問題的方法：短語是恒假的當(dāng)且僅當(dāng)至少有一個(gè)原子及其否定(也稱互補(bǔ)對(duì))同時(shí)在此短語中出現(xiàn)。命題公式G是恒假的當(dāng)且僅當(dāng)在等價(jià)于它的析取范式中，每個(gè)短語均至少包含一個(gè)原子及其否定。 把公式化成主析取范式：公式恒假時(shí)，主析取范式?jīng)]有極小項(xiàng)；公式恒真時(shí)，主析取范式有全部極小項(xiàng)。 一種判定算法：對(duì)任給要判定的命題公式G，設(shè)其中有原子P1，P2，Pn，令P1取1值，求G的

16、真值，或?yàn)?，或?yàn)?，或成為新公式G1且其中只有原子P2，Pn，再令P1取0值，求G真值，如此繼續(xù)，到最終只含0或1為止，若最終結(jié)果全為1，則公式G恒真，若最終結(jié)果全為0，則公式G恒假，若最終結(jié)果有1，有0，則是可滿足的。4本章內(nèi)容小結(jié)作業(yè)安排：教材中習(xí)題2.4中的第4、5題。授課題目3.1 謂詞邏輯的基本概念授課學(xué)時(shí)2授課時(shí)間第7周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：謂詞、全稱量詞、存在量詞等概念，學(xué)會(huì)使用它們符號(hào)化一些命題并構(gòu)成一些較復(fù)雜的命題。約束變量、自由變量的概念，能夠正確使用改名規(guī)則。教學(xué)難點(diǎn)：n元謂詞的理解；存在量詞或全稱量詞限定的公式真值的理解 教學(xué)要點(diǎn)：1謂詞和量詞謂詞定義、量詞定義量

17、詞限定公式的真值變量和命題函數(shù)中的變量區(qū)別量詞的作用域教學(xué)方法：通過邏輯學(xué)中的著名的三段論案例，讓學(xué)生理解命題邏輯的局限性，以及研究謂詞邏輯的必要性，從而引出謂詞邏輯的基本概念。2改名規(guī)則 變量的約束與自由的含義改名規(guī)則教學(xué)方法：通過一些例子的練習(xí)讓學(xué)生正確理解與掌握改名規(guī)則及其使用。參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解·精練 黃健斌 西安電子科技大學(xué)出版社離散數(shù)學(xué) 耿素云等 高等教育出版社 作業(yè)安排：教材中習(xí)題3.1中的第3題。答疑時(shí)間：另行安排授課題目3.2 謂詞公式 授課學(xué)時(shí)2授課時(shí)間第8周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：謂詞公

18、式、解釋的概念，能夠求出一給定公式在某一解釋下的真值。恒真公式、恒假公式、可滿足公式等概念，了解與命題邏輯判定問題可解不同的是：謂詞邏輯判定問題不可解，但謂詞邏輯是半可判定的。教學(xué)難點(diǎn)：函數(shù)符號(hào)的理解謂詞公式的解釋教學(xué)要點(diǎn)：1 謂詞公式四種符號(hào)：常量符號(hào)、變量符號(hào)、函數(shù)符號(hào)、謂詞符號(hào)項(xiàng)的定義公式的定義教學(xué)方法：通過例子進(jìn)一步理解謂詞邏輯的遞歸定義，讓學(xué)生分析對(duì)比這些概念與命題邏輯中相關(guān)知識(shí)的區(qū)別與聯(lián)系，從而提高分析問題解決問題的能力2 解釋解釋的定義解釋包含的內(nèi)容與形式結(jié)構(gòu)公式的恒真、恒假以及可滿足的定義教學(xué)方法：通過一些具體案例的講解也可結(jié)合實(shí)際應(yīng)用問題進(jìn)行講解，讓學(xué)生領(lǐng)會(huì)解釋的實(shí)際含義，并

19、學(xué)會(huì)對(duì)具體公式給出滿足或弄假公式的解釋參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解·精練 黃健斌 西安電子科技大學(xué)出版社離散數(shù)學(xué) 耿素云等 高等教育出版社 作業(yè)安排：教材中習(xí)題3.2中的第2、3題答疑時(shí)間：另行安排授課題目3.3 謂詞公式的等價(jià)關(guān)系和蘊(yùn)含關(guān)系授課學(xué)時(shí)2授課時(shí)間第8周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：謂詞公式的等價(jià)、蘊(yùn)涵等概念，熟記基本的等價(jià)式、蘊(yùn)涵式，會(huì)證明更復(fù)雜的等價(jià)式、蘊(yùn)涵式。教學(xué)難點(diǎn)：謂詞演算的推理方法的掌握教學(xué)要點(diǎn)：1謂詞公式的等價(jià)關(guān)系 謂詞公式等價(jià)的定義謂詞公式等價(jià)的充要條件教學(xué)方法；通過例子的講解使學(xué)生能夠分析對(duì)比謂

20、詞公式等價(jià)與命題公式等價(jià)的區(qū)別和聯(lián)系，從而加深學(xué)生對(duì)問題的理解2謂詞公式的蘊(yùn)涵關(guān)系 謂詞公式蘊(yùn)涵的定義謂詞公式蘊(yùn)涵的充要條件基本蘊(yùn)涵式教學(xué)方法；通過三段論例子的進(jìn)一步講解使學(xué)生能夠分析對(duì)比謂詞公式蘊(yùn)涵與命題公式蘊(yùn)涵的區(qū)別和聯(lián)系，從而加深學(xué)生對(duì)問題的理解，并看到謂詞邏輯的不足，引導(dǎo)和啟發(fā)學(xué)生深入思考一些相關(guān)問題3謂詞演算的推理方法謂詞演算規(guī)則演算規(guī)則的使用規(guī)則錯(cuò)誤使用的識(shí)別教學(xué)方法；通過例子的講解過程使學(xué)生掌握這些規(guī)則和推理方法的具體運(yùn)用，并能夠識(shí)別推理過程中的規(guī)則使用錯(cuò)誤參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解·精練 黃健斌 西安電

21、子科技大學(xué)出版社離散數(shù)學(xué) 耿素云等 高等教育出版社 數(shù)理邏輯 王捍貧 北京大學(xué)出版社作業(yè)安排：教材中習(xí)題3.3中的第1題。答疑時(shí)間：另行安排授課題目34 范 式授課學(xué)時(shí)2授課時(shí)間第9周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：1掌握前束范式、Skolem范式等概念；2掌握將謂詞公式化成與之等價(jià)的前束范式，并進(jìn)一步化為Slolem范式。教學(xué)難點(diǎn)：公式與其Slolem范式可滿足性的等價(jià)性證明。教學(xué)要點(diǎn)：1范式的概念前束范式的定義； 等價(jià)公式；對(duì)任意公式G，都存在與其等價(jià)的前束范式；改名公式在謂詞邏輯中的應(yīng)用；公式的等價(jià)前束范式求解方法；教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意提出問題，引導(dǎo)學(xué)生去思考求解問題的方法。例如

22、為什么提出改名，它的意義在哪里？2Skolem范式的概念Skolem范式的定義及理解；公式G的Skolem函數(shù)定義；設(shè)S是公式G的Skolem范式，于是，公式G是恒假的充要條件是公式S是恒假的；公式G與它的Skolem范式S可滿足性是等價(jià)的；教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意提出問題，引導(dǎo)學(xué)生去思考求解問題的方法。例如為什么提出Skolem范式？它的意義在哪里？是否存在更好的解決方案？最后讓學(xué)生了解謂詞邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用。3本章內(nèi)容小結(jié)參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解·精練 黃健斌 西安電子科技大學(xué)出版社離散數(shù)學(xué) 耿素

23、云等 高等教育出版社 數(shù)理邏輯 王捍貧 北京大學(xué)出版社作業(yè)安排：教材中習(xí)題3.4中的第2、3題。答疑時(shí)間：另行安排授課題目41 圖授課學(xué)時(shí)4授課時(shí)間第9、10周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：1掌握?qǐng)D的概念。2理解Dijkstra算法，并能夠在已知權(quán)圖中使用該算法求出任意兩點(diǎn)間的最短路教學(xué)難點(diǎn)：Dijkstra算法的正確性證明。教學(xué)要點(diǎn)：1圖的概念圖的定義； 子圖的定義；圖的矩陣表示：相鄰矩陣和關(guān)聯(lián)矩陣；有限圖中點(diǎn)的度；教學(xué)方法：在講解本部分內(nèi)容時(shí)多舉例子，讓學(xué)生對(duì)于圖有一個(gè)直觀的理解。2權(quán)圖和Dijkstra算法權(quán)圖的定義；Dijkstra算法；Dijkstra算法的執(zhí)行過程；Dijkstra算法

24、的正確性證明；教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意提出問題，引導(dǎo)學(xué)生去思考算法的本質(zhì)。例如Dijkstra算法的原理是什么？它主要適合那些問題？有沒有更好的方法？并鼓勵(lì)學(xué)生通過編程實(shí)現(xiàn)算法加深對(duì)于算法的理解。參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社集合論與圖論 耿素云 北京大學(xué)出版社 網(wǎng)絡(luò)優(yōu)化 謝金星 邢文訓(xùn) 清華大學(xué)出版社作業(yè)安排：教材中習(xí)題4.1中的第7題。答疑時(shí)間：另行安排授課題目42 樹授課學(xué)時(shí)4授課時(shí)間第10、11周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：1掌握樹、支撐樹的概念以及圖是樹的幾個(gè)等價(jià)命題。2理解Kruskal算法，并能夠應(yīng)用它求已知加權(quán)連通圖的最優(yōu)樹。了解求最優(yōu)

25、樹的Prim算法，會(huì)總結(jié)Sollin算法。教學(xué)難點(diǎn)：樹的等價(jià)命題；Kruskal算法的正確性證明。教學(xué)要點(diǎn)：1樹及其等價(jià)命題數(shù)和森林的定義； 引理1；樹的等價(jià)命題；定理4.2.1 如果G是圖，則下列諸命題等價(jià)：1） G是樹。2） G連通并且刪去G的任意一邊，所得之圖都不連通。3） 對(duì)G中任意兩點(diǎn)v，v(v¹v)，恰有一條從v到v的簡(jiǎn)單路。如果G還是有限圖，設(shè)P(G)元數(shù)為n，則下列命題也與上面命題等價(jià)：4） G不含回路，并且G有（n-1）條邊。5） G連通，并且G有（n-1）條邊。教學(xué)方法：在講解定理4.2.1時(shí)，注意讓學(xué)生領(lǐng)會(huì)證明方法，并著重強(qiáng)調(diào)反證法的作用2最優(yōu)樹和Kruskal

26、算法 最優(yōu)樹定義及理解；Kruskal算法；Kruskal算法的正確性證明；了解求最優(yōu)樹的其他算法教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意提出問題，引導(dǎo)學(xué)生去思考求解問題的方法。在講授Kruskal算法的時(shí)候注意讓學(xué)生理解算法的原理，并剖析其“閉圈法”的本質(zhì)，同時(shí)鼓勵(lì)學(xué)生上機(jī)編程實(shí)現(xiàn)。參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社集合論與圖論 耿素云 北京大學(xué)出版社 網(wǎng)絡(luò)優(yōu)化 謝金星 邢文訓(xùn) 清華大學(xué)出版社作業(yè)安排：教材中習(xí)題4.2中的第4題。答疑時(shí)間：另行安排授課題目43 有向圖 Euler路授課學(xué)時(shí)6授課時(shí)間第11、12周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：1 掌握有向圖、有向子圖、有向

27、路、簡(jiǎn)單有向路、有向回路等概念。2. 掌握有向圖的強(qiáng)連通性和有向圖的根的概念，了解二者的關(guān)系。3. 掌握有向樹的概念以及有向樹與樹的轉(zhuǎn)化定理。4. 掌握Euler路、Euler圖的概念，掌握有向圖中和無向圖中Euler圖的充要條件，并能利用判斷某圖是否為Euler圖。了解從Euler路得出有向支撐樹以及從有向支撐樹得出Euler路的方法。教學(xué)難點(diǎn)：轉(zhuǎn)化定理的證明；無孤立點(diǎn)有限有向圖中有Euler路的充分必要條件；教學(xué)要點(diǎn)：1有向圖與有向樹的相關(guān)定義有向圖的定義；有向路的定義；有向圖的強(qiáng)連通性和有向圖的根的概念；有向樹的概念；轉(zhuǎn)化定理：對(duì)有向樹G，若無視各弧之方向，則得一樹G0；反之，若G0是樹

28、，可選取任一點(diǎn)做根，并適當(dāng)指定各邊之方向，則得一有向樹G。教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意聯(lián)系直觀，尤其是對(duì)于轉(zhuǎn)化定理，能給學(xué)生以直觀的方式，這樣能夠加深對(duì)于證明方法以及定理本身的理解。2Euler路Euler路和Euler圖的概念；有向圖中和無向圖中Euler圖的充要條件以應(yīng)用：設(shè)G是無孤立點(diǎn)的有限有向圖。于是，G有Euler路當(dāng)且僅當(dāng)G是平衡的，并且強(qiáng)連通。Euler路得出有向支撐樹以及從有向支撐樹得出Euler路的方法教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意避免把著眼點(diǎn)局限在證明上，要多舉例子和講授證明的方法，以加深學(xué)生對(duì)于復(fù)雜證明的理解。參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高

29、等教育出版社集合論與圖論 耿素云 北京大學(xué)出版社 網(wǎng)絡(luò)優(yōu)化 謝金星 邢文訓(xùn) 清華大學(xué)出版社作業(yè)安排：教材中習(xí)題4.3中的第1題。答疑時(shí)間：另行安排授課題目44 Hamilton圖授課學(xué)時(shí)4授課時(shí)間第13周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：1掌握Hamilton路、Hamilton回路、Hamilton圖的概念以及Hamilton圖的必要條件和若干充分條件。2了解流動(dòng)推銷員問題和求解Hamilton路的逼近算法。教學(xué)難點(diǎn)：Hamilton圖的必要條件和若干充分條件的證明。教學(xué)要點(diǎn)：1Hamilton路的相關(guān)概念Hamilton路的提出； Hamilton路的定義；Hamilton圖的定義；Hamilto

30、n圖的必要條件；教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意提出問題，引導(dǎo)學(xué)生去思考求解問題的方法。2Hamilton圖的若干充分條件教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意讓學(xué)生對(duì)于定理應(yīng)用的掌握，同時(shí)通過講授巧妙的證明過程，使得學(xué)生能夠理解找到判定Hamilton圖充分必要條件的困難，并激發(fā)學(xué)生探索的精神3. 本章小結(jié)參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社集合論與圖論 耿素云 北京大學(xué)出版社 網(wǎng)絡(luò)優(yōu)化 謝金星 邢文訓(xùn) 清華大學(xué)出版社作業(yè)安排：由于課后習(xí)題比較難，選擇部分作為例題講授答疑時(shí)間：另行安排授課題目51 整除性 輾轉(zhuǎn)相除授課學(xué)時(shí)2.5授課時(shí)間第14周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重

31、點(diǎn)：1掌握整除、因數(shù)、倍數(shù)等概念，記住并會(huì)應(yīng)用整除的性質(zhì)。2. 掌握最高公因數(shù)的概念，能夠使用輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最高公因數(shù)并表示為它們的倍數(shù)和。會(huì)利用數(shù)的數(shù)碼特征判別某些整除性教學(xué)難點(diǎn)：輾轉(zhuǎn)相除法的原理和應(yīng)用。教學(xué)要點(diǎn)：1整除的相關(guān)定義整除的定義；整除的性質(zhì)教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意提出問題，引導(dǎo)學(xué)生去思考求解問題的方法。例如為什么要研究整除，它的意義在哪里？2輾轉(zhuǎn)相除輾轉(zhuǎn)相除求兩個(gè)數(shù)最高公因的證明；輾轉(zhuǎn)相除的運(yùn)用教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意強(qiáng)調(diào)對(duì)于知識(shí)的應(yīng)用和掌握基本的方法。例如對(duì)于輾轉(zhuǎn)相除法，要讓學(xué)生理解它的原理，操作步驟。并讓學(xué)生了解它在數(shù)論中的地位。參考文獻(xiàn)： 離散數(shù)學(xué)

32、學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解·精練 黃健斌 西安電子科技大學(xué)出版社初等數(shù)論 閔嗣鶴 嚴(yán)士健 人民教育出版社 作業(yè)安排：教材中習(xí)題5.1中的第2題。答疑時(shí)間：另行安排授課題目52 互質(zhì) 質(zhì)因數(shù)分解授課學(xué)時(shí)1.5授課時(shí)間第14周教學(xué)重點(diǎn)、難點(diǎn)：教學(xué)重點(diǎn)：1 掌握互質(zhì)的概念和質(zhì)數(shù)的性質(zhì)。2 掌握質(zhì)數(shù)、合數(shù)的概念以及算術(shù)基本定理、歐幾里得定理。教學(xué)難點(diǎn)：算數(shù)基本定理。教學(xué)要點(diǎn)：1掌握互質(zhì)的概念和質(zhì)數(shù)的性質(zhì)互質(zhì)的定義； 質(zhì)數(shù)的性質(zhì)；教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意提出問題，引導(dǎo)學(xué)生去思考求解問題的方法。例如為什么要研究質(zhì)數(shù)，它的意義在哪里？合數(shù)的定義2算術(shù)基本定理、歐幾里得定理算術(shù)基本定理；歐幾里得定理教學(xué)方法：在講解本部分內(nèi)容時(shí)要注意提出問題，引導(dǎo)學(xué)生去思考求解問題的方法。同時(shí)掌握定理證明的思想，如在歐幾里得定理證明質(zhì)數(shù)無窮多時(shí)對(duì)于反證法的應(yīng)用。參考文獻(xiàn)： 離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解答 孫吉貴等 高等教育出版社離散數(shù)學(xué)精講·精解