吉林大學(xué)離散數(shù)學(xué)串講ppt

1、2021年11月26日星期五1 離散數(shù)學(xué)吉大吉大 11春學(xué)期考前串講春學(xué)期考前串講2第一章第一章 集合論基礎(chǔ)集合論基礎(chǔ)1.掌握集合、子集、差集、空集、冪集、集合族的概念。懂得兩個(gè)集合間相等和包含關(guān)系的定義和性質(zhì)，能夠利用定義證明兩個(gè)集合相等。熟悉常用的集合表示方法。2.掌握集合的基本運(yùn)算：并、交、余、差、直乘積、對(duì)稱差的定義以及集合運(yùn)算滿足的基本算律，能夠利用它們來(lái)證明更復(fù)雜的集合等式。3.掌握關(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ì)稱閉包、傳遞閉包。4.掌握等價(jià)關(guān)系、等價(jià)類、商集

2、的概念，了解等價(jià)關(guān)系和劃分的內(nèi)在聯(lián)系。5.掌握部分序關(guān)系、部分序集、全序關(guān)系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、極大元、極小元、上確界、下確界的定義。能畫出有限部分序集的Hasse圖，并根據(jù)圖討論部分序集的某些性質(zhì)。6.掌握映射、映像、1-1映射等概念，會(huì)做映射的乘積。了解可數(shù)集合的概念，掌握可數(shù)集合的判定方法。400-810-6736 3400-810-6736 4第二章第二章 命題邏輯命題邏輯1.掌握命題、邏輯聯(lián)結(jié)詞等概念，能夠?qū)⒚}符號(hào)化。2.掌握命題公式、解釋、恒真公式、恒假公式等概念。能夠判斷一命題公式是恒真、恒假，還是可滿足。3.掌握公式的等價(jià)、蘊(yùn)涵等概念，熟記

3、基本的等價(jià)式、蘊(yùn)涵式，會(huì)證明更復(fù)雜的等價(jià)式、蘊(yùn)涵式。4.掌握聯(lián)結(jié)詞的功能完備集的概念，能夠判別一個(gè)聯(lián)結(jié)詞集合是否為聯(lián)結(jié)詞的功能完備集。5.掌握演繹方法，能夠使用演繹方法進(jìn)行有效推理。6.掌握析取范式、合取范式、極大項(xiàng)、極小項(xiàng)、主析取范式、主合取范式的概念和性質(zhì)。掌握求各種范式的方法，能夠用等價(jià)演算法和真值表法求命題公式的主析取范式、主合取范式。400-810-6736 5400-810-6736 6第三章第三章 謂詞邏輯謂詞邏輯1.掌握謂詞、全稱量詞、存在量詞等概念，學(xué)會(huì)使用它們符號(hào)化一些命題并構(gòu)成一些較復(fù)雜的命題。2.掌握約束變量、自由變量的概念，能夠正確使用改名規(guī)則。3.掌握謂詞公式、解釋

4、的概念，能夠求出一給定公式在某一解釋下的真值。4.掌握恒真公式、恒假公式、可滿足公式等概念，了解與命題邏輯判定問(wèn)題可解,不同的是：謂詞邏輯判定問(wèn)題不可解，但謂詞邏輯是半可判定的。 5.掌握謂詞公式的等價(jià)、蘊(yùn)涵等概念，熟記基本的等價(jià)式、蘊(yùn)涵式，會(huì)證明更復(fù)雜的等價(jià)式、蘊(yùn)涵式。6.掌握前束范式、Skolem范式等概念，能夠?qū)⒁恢^詞公式化成與之等價(jià)的前束范式，并進(jìn)一步化為Slolem范式。400-810-6736 7400-810-6736 8第四章第四章 圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò)1.掌握?qǐng)D、有限圖、母圖、子圖、支撐子圖、完全圖、補(bǔ)圖等概念，了解有限圖中點(diǎn)的度的性質(zhì)，掌握?qǐng)D的矩陣表示：關(guān)聯(lián)矩陣、鄰接矩陣。2.

5、掌握路、簡(jiǎn)單路、回路、連通圖等概念。3.理解Dijkstra算法，并能夠在已知權(quán)圖中使用該算法求出任意兩點(diǎn)間的最短路。4.掌握樹(shù)、支撐樹(shù)的概念以及圖是樹(shù)的幾個(gè)等價(jià)命題。5.理解Kruskal算法，并能夠應(yīng)用它求已知加權(quán)連通圖的最優(yōu)樹(shù)。了解求最優(yōu)樹(shù)的Prim算法，會(huì)總結(jié)Sollin算法。6.掌握有向圖、有向子圖、有向路、簡(jiǎn)單有向路、有向回路等概念。7.掌握有向圖的強(qiáng)連通性和有向圖的根的概念，了解二者的關(guān)系。8.掌握Euler路、Euler圖的概念，掌握有向圖中和無(wú)向圖中Euler圖的充要條件，并能利用判斷某圖是否為Euler圖。了解從Euler路得出有向支撐樹(shù)以及從有向支撐樹(shù)得出Euler路的方

6、法。10. 掌握Hamilton路、Hamilton回路、Hamilton圖的概念以及Hamilton圖的必要條件和若干充分條件。400-810-6736 9400-810-6736 10第六章第六章 群與環(huán)群與環(huán)1.掌握二元代數(shù)運(yùn)算、代數(shù)系統(tǒng)的定義，能夠判斷一運(yùn)算是否為二元代數(shù)運(yùn)算，運(yùn)算是否滿足交換律、結(jié)合律、分配律、冪等律、吸收律、消去律。2.掌握半群、群的定義以及群的性質(zhì)，能夠判斷一代數(shù)系統(tǒng)是否為半群或群。3.掌握交換群的定義以及交換群中的三個(gè)指數(shù)律。4.掌握置換、輪換、不相雜輪換、對(duì)換等概念，會(huì)做置換的乘法，會(huì)將任意置換寫成不相雜輪換的乘積。了解置換的順向圈表示。5.掌握奇置換、偶置換

7、的概念，了解置換的定性數(shù)與置換的圖型及奇偶性的關(guān)系。6.掌握n次對(duì)稱群、n次交代群的概念，會(huì)寫出其中的元素。7.掌握子群的定義以及子群的判別條件。掌握周期、循環(huán)群的定義和乘法群、加法群中周期的性質(zhì)以及循環(huán)群中一元素作為生成元的充要條件。8.掌握群中合同、右陪集的定義。了解子群在大群中的右陪集的一些性質(zhì)。掌握正規(guī)子群的概念以及一子群為大群的正規(guī)子群的充要條件。掌握并會(huì)正確應(yīng)用Lagrange定理。400-810-6736 11第六章第六章 群與環(huán)群與環(huán)9.掌握同態(tài)映射、同構(gòu)映射、自同構(gòu)映射的概念以及同態(tài)定理。會(huì)判斷一個(gè)群與一乘法系統(tǒng)間的映射是否為同態(tài)映射、同構(gòu)映射或自同構(gòu)映射。10. 掌握同態(tài)核

8、的概念，了解若是群G到G上的同態(tài)映射，則其核N為一正規(guī)子群。反過(guò)來(lái)，設(shè)N是G的一個(gè)正規(guī)子群，則有一個(gè)群G以及一個(gè)G到G上的同態(tài)映射，使N為的核。掌握并會(huì)正確應(yīng)用聯(lián)系同態(tài)與同構(gòu)的基本定理。了解為群G到G上的同態(tài)映射時(shí)，G中子群與G中子群的關(guān)系。11. 掌握環(huán)、交換環(huán)、含壹環(huán)、消去環(huán)的定義及其性質(zhì)，會(huì)判斷。12.掌握整區(qū)、體、域、子環(huán)、子體、子域等概念，以及環(huán)的子集作成子環(huán)的充要條件。13. 掌握并會(huì)應(yīng)用理想、主理想的定義，掌握環(huán)中合同關(guān)系、剩余類的定義以及環(huán)中合同關(guān)系的性質(zhì)。14. 掌握環(huán)同態(tài)映射、同構(gòu)映射、剩余環(huán)的定義，了解與群論中平行的環(huán)中的關(guān)于同態(tài)映射、同構(gòu)映射的一些定理。15. 掌握單純

9、環(huán)與極大理想的定義，以及二者的關(guān)系，了解一個(gè)環(huán)是域的充要條件。 400-810-6736 12400-810-6736 13第八章第八章 格與布爾代數(shù)格與布爾代數(shù)1.掌握半序格、半序子格、代數(shù)格、代數(shù)子格的定義，了解半序格和代數(shù)格的定義是等價(jià)的。2.掌握互相對(duì)偶的兩個(gè)關(guān)系、互相對(duì)偶的兩個(gè)格的定義，了解二者關(guān)系。掌握格中表達(dá)式、對(duì)偶格中的對(duì)偶表達(dá)式、本格中的對(duì)偶表達(dá)式的定義，掌握并會(huì)應(yīng)用對(duì)偶原理1及對(duì)偶原理2。3.了解格的其它性質(zhì)，如格的保序性、分配不等式、模不等式等。4.掌握并會(huì)應(yīng)用格同態(tài)映射、格的自同態(tài)映射、格同構(gòu)映射的定義。了解格的同態(tài)映射一定是保序映射，同構(gòu)映射的逆映射也是同構(gòu)映射等結(jié)論。5. 掌握有界格、有余格、分配格以及模格的定義以及相關(guān)的結(jié)論。了解一個(gè)格為模格的充要條件。6.掌握布爾代數(shù)的定義及其16個(gè)性質(zhì)，掌握并會(huì)應(yīng)用Huntington公理來(lái)判定一代數(shù)系統(tǒng)是否為布爾代數(shù)。了解電路代數(shù)、集合代數(shù)、命題代數(shù)、開(kāi)關(guān)代數(shù)。掌握并會(huì)應(yīng)用布爾代數(shù)的子集是其子代數(shù)的充要條件。400-810-6736 14第八章第八章 格與布爾代數(shù)格與布爾代數(shù)7.掌握可唯一表示布爾代數(shù)中元素的基底的定義及其性質(zhì)。掌握極小元的定義及其性質(zhì)。掌握布爾代數(shù)的生成、極小項(xiàng)、多項(xiàng)式、多項(xiàng)范式、布爾代數(shù)中一組元素互相獨(dú)立等概念，了解