計(jì)算機(jī)科技專(zhuān)業(yè)《離散數(shù)學(xué)》教學(xué)大綱

《離散數(shù)學(xué)》教學(xué)大綱安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院二OO六年六月

前言《離散數(shù)學(xué)》課程是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)高等教育的專(zhuān)業(yè)基礎(chǔ)課程?！峨x散數(shù)學(xué)》是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是學(xué)習(xí)計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)理論必不可少的數(shù)學(xué)工具。本課程主要研究離散對(duì)象的結(jié)構(gòu)及相互關(guān)系，對(duì)提高學(xué)生的抽象思維與邏輯推理能力有重要作用。設(shè)置本課程的目的是：培養(yǎng)學(xué)生的數(shù)學(xué)思維能力，使學(xué)生得到良好的數(shù)學(xué)訓(xùn)練，提高學(xué)生的抽象思維和邏輯推理能力，并使學(xué)生掌握處理離散結(jié)構(gòu)所必須的描述工具和方法，為其從事計(jì)算機(jī)的應(yīng)用提供堅(jiān)實(shí)的理論基礎(chǔ)。學(xué)習(xí)本課程的要求是：通過(guò)本課程的學(xué)習(xí)，學(xué)生應(yīng)正確理解和熟練掌握基本概念、基本定理及其證明方法，提高運(yùn)用基本理論分析和解決實(shí)際問(wèn)題的能力，為在后續(xù)專(zhuān)業(yè)課和實(shí)際工作中運(yùn)用本課程的基本知識(shí)打下基礎(chǔ)。先修課程要求：高等數(shù)學(xué)。本課程計(jì)劃144學(xué)時(shí)，7學(xué)分，分兩學(xué)期完成，分別稱(chēng)為離散數(shù)學(xué)（上）和離散數(shù)學(xué)（下）。離散數(shù)學(xué)（上）計(jì)劃72學(xué)時(shí)，3.5學(xué)分；離散數(shù)學(xué)（下）計(jì)劃72學(xué)時(shí)，3.5學(xué)分。選用教材：《離散數(shù)學(xué)》，方世昌，西安電子科技大學(xué)出版社，2000出版。教學(xué)手段：多媒體教學(xué)?？己朔椒ǎ嚎荚嚒＝虒W(xué)進(jìn)程安排表：離散數(shù)學(xué)（上）周次學(xué)時(shí)數(shù)教學(xué)主要內(nèi)容教學(xué)方法備注14命題、邏輯聯(lián)結(jié)詞及真值表、命題符號(hào)化命題公式的概念及命題公式的基本等值式講授24命題演算的規(guī)則和對(duì)偶原理析取范式與合取范式的概念及計(jì)算講授34主析取范式與主合取范式的概念及計(jì)算聯(lián)結(jié)詞的擴(kuò)充與歸約講授44命題邏輯的推理規(guī)則命題邏輯的證明方法講授54個(gè)體、謂詞和量詞等概念、謂詞符號(hào)化謂詞公式和自由變?cè)然靖拍钪v授64謂詞演算的基本等值式謂詞演算的推理規(guī)則及證明方法講授74第一章習(xí)題課集合的基本概念習(xí)題課講授84集合上的基本運(yùn)算、文氏圖集合的歸納定義及數(shù)學(xué)歸納法講授94序偶和集合的笛卡爾乘積第二章習(xí)題課講授習(xí)題課104二元關(guān)系的基本概念、關(guān)系矩陣和關(guān)系圖二元關(guān)系的特性講授114關(guān)系的合成及合成關(guān)系的矩陣表達(dá)逆關(guān)系、關(guān)系的閉包運(yùn)算講授124偏序關(guān)系及其哈斯圖表示偏序集中的特殊元素、擬序、良序和線序講授134等價(jià)關(guān)系的概念和性質(zhì)、等價(jià)類(lèi)劃分的概念、劃分的積與和講授144第三章習(xí)題課函數(shù)的基本概念及函數(shù)的合成習(xí)題課講授154函數(shù)的性質(zhì)、特殊函數(shù)類(lèi)逆函數(shù)的概念及性質(zhì)、單側(cè)逆函數(shù)講授164第四章習(xí)題課有限與無(wú)限集合、可數(shù)與不可數(shù)集合等概念習(xí)題課講授174可數(shù)與不可數(shù)集合的性質(zhì)基數(shù)的比較、無(wú)限集合的特性講授184第五章習(xí)題課總復(fù)習(xí)習(xí)題課離散數(shù)學(xué)（下）周次學(xué)時(shí)數(shù)教學(xué)主要內(nèi)容教學(xué)方法備注14代數(shù)的構(gòu)成和分類(lèi)、么元和零元概念及性質(zhì)逆元的概念及性質(zhì)、子代數(shù)講授24代數(shù)同態(tài)和同構(gòu)的概念及性質(zhì)同余關(guān)系的概念及判定講授34商代數(shù)和積代數(shù)的概念及性質(zhì)半群和獨(dú)異點(diǎn)的概念及性質(zhì)講授44群的定義及性質(zhì)置換群和循環(huán)群的概念及性質(zhì)講授54子群的定義及判定、群同態(tài)的概念陪集和拉格朗日定理講授64正規(guī)子群和商群環(huán)、整環(huán)和域的概念講授74子環(huán)和理想第六章習(xí)題課講授習(xí)題課84作為偏序集的格的定義及性質(zhì)作為代數(shù)系統(tǒng)的格的定義及性質(zhì)講授94子格、格同態(tài)、格的積代數(shù)分配格和有界格的定義、判定及性質(zhì)講授104有補(bǔ)格和有補(bǔ)分配格的定義及性質(zhì)布爾代數(shù)的定義及性質(zhì)、子布爾代數(shù)講授114有限布爾代數(shù)的原子表示布爾表達(dá)式和布爾函數(shù)講授124第七章習(xí)題課圖的基本概念、結(jié)點(diǎn)次數(shù)、圖的同構(gòu)和運(yùn)算習(xí)題課講授134子圖與補(bǔ)圖、路徑和回路連通圖的概念及性質(zhì)、賦權(quán)圖的最短路徑講授144歐拉路徑（回路）、哈密爾頓路徑（回路）圖的矩陣表示講授154二部圖的概念、判定及應(yīng)用平面圖和歐拉公式講授164對(duì)偶圖和五色原理無(wú)向樹(shù)的定義及性質(zhì)講授174生成樹(shù)及最小生成樹(shù)有向樹(shù)的定義及性質(zhì)、搜索樹(shù)和決策樹(shù)講授184第八章習(xí)題課總復(fù)習(xí)習(xí)題課第一章數(shù)理邏輯一、學(xué)習(xí)目的通過(guò)本章的學(xué)習(xí)，理解命題、聯(lián)結(jié)詞、命題公式、（主）析/合取范式、個(gè)體、謂詞、量詞、謂詞公式、指派等概念；掌握公式真值表的構(gòu)造及命題符號(hào)化方法、常用的基本等值式及其應(yīng)用、常用的永真蘊(yùn)涵式及其在邏輯推理中的應(yīng)用、（主）析/合取范式的計(jì)算、命題演算和謂詞演算的推理規(guī)則和證明方法。第一章計(jì)劃26學(xué)時(shí)。二、課程內(nèi)容1.1命題（一）命題的概念。（二）命題聯(lián)結(jié)詞及其真值表。（三）命題符號(hào)化。（四）命題變?cè)兔}公式的概念。1.2重言式（一）指派、重言式、邏輯恒等式、永真蘊(yùn)含式等基本概念。（二）常見(jiàn)的邏輯恒等式和永真蘊(yùn)含式。（三）邏輯恒等式和永真蘊(yùn)含式的基本性質(zhì)。（四）命題演算的基本規(guī)則：代入規(guī)則、替換規(guī)則。（五）命題演算中的對(duì)偶原理。1.3范式（一）基本積與基本和的概念。（二）析取范式與合取范式的概念。（三）析取范式與合取范式的計(jì)算。（四）極小項(xiàng)與極大項(xiàng)的概念。（五）主析取范式與主合取范式的概念。（六）主析取范式與主合取范式的計(jì)算。（七）主析取范式與主合取范式的個(gè)數(shù)。1.4聯(lián)結(jié)詞的擴(kuò)充與歸約（一）與非、或非、異或(排拆或)、蘊(yùn)含否定的定義。（二）與非、或非、異或(排拆或)、蘊(yùn)含否定的基本性質(zhì)。（三）聯(lián)結(jié)詞完備集的概念。（四）聯(lián)結(jié)詞完備集的判定。1.5推理規(guī)則和證明方法（一）推理的有效性的概念。（二）推理規(guī)則：T規(guī)則（前提引入）、P規(guī)則（結(jié)論引入）等。（三）形式推理的表上作業(yè)。（四）證明方法：演繹法、歸謬法等。1.6謂詞和量詞（一）個(gè)體和謂詞的概念。（二）全稱(chēng)量詞和存在量詞的概念。（三）謂詞符號(hào)化。（四）量化斷言與命題的關(guān)系。（五）謂詞公式的概念。（六）自由變?cè)c約束變?cè)母拍?。（七）謂詞公式中的改名規(guī)則。1.7謂詞演算的永真公式（一）謂詞公式的解釋。（二）謂詞演算的基本永真公式。（三）謂詞演算的幾條規(guī)則：代入規(guī)則、替換規(guī)則和對(duì)偶原理。1.8謂詞演算的推理規(guī)則（一）術(shù)語(yǔ)“A(x)對(duì)y是自由的”的意義。（二）全稱(chēng)指定規(guī)則（US）（全稱(chēng)量詞消去規(guī)則）。（三）存在指定規(guī)則(ES)（存在量詞消去規(guī)則）。（四）存在推廣規(guī)則(EG)（存在量詞引入規(guī)則）。（五）全稱(chēng)推廣規(guī)則（UG）（全稱(chēng)量詞引入規(guī)則）。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）本章的重點(diǎn)是各個(gè)概念、公式演算和推理方法的教學(xué)。（二）本章的難點(diǎn)是謂詞符號(hào)化和應(yīng)用公式進(jìn)行邏輯推理。四、思考與練習(xí)（一）簡(jiǎn)單命題與符合命題的區(qū)分。（二）可兼或和排斥或的聯(lián)系和區(qū)別。（三）含有n個(gè)命題變?cè)拿}公式有多少不同的指派？（四）關(guān)于n個(gè)命題變?cè)梢詷?gòu)造多少個(gè)真值表？（五）如何構(gòu)造結(jié)論形式為P→Q→R或（P→Q）→R的證明。（六）如何用存在量詞和全稱(chēng)量詞來(lái)表示存在唯一？第二章集合一、學(xué)習(xí)目的通過(guò)本章的學(xué)習(xí)，了解自然數(shù)的歸納定義；理解數(shù)學(xué)歸納法第一原理及第二原理；掌握集合的基本概念、基本運(yùn)算的相關(guān)性質(zhì)和文氏圖表示、冪集的概念、有限集的計(jì)數(shù)方法、集合的歸納定義、n元組和笛卡兒乘積等概念和性質(zhì)。第二章計(jì)劃10學(xué)時(shí)。二、課程內(nèi)容2.1集合論的基本概念（一）集合的基本概念。（二）集合的表示方法。（三）羅素悖論。（四）集合間的包含關(guān)系。2.2集合上的運(yùn)算（一）集合上的交、并、差、補(bǔ)、環(huán)和與環(huán)積等運(yùn)算的定義和性質(zhì)。（二）集合上的交和并運(yùn)算的擴(kuò)展。（三）集合運(yùn)算的文氏圖表示。（四）冪集合的概念。（五）有限集的基數(shù)公式及應(yīng)用。2.3歸納法和自然數(shù)（一）集合的歸納定義法。（二）自然數(shù)的歸納定義和皮亞諾(Peano)公設(shè)。（三）數(shù)學(xué)歸納法第一原理和第二原理。2.5集合的笛卡兒乘積（一）序偶和n重組的概念。（二）集合的笛卡兒乘積的概念。（三）集合的笛卡兒乘積的性質(zhì)。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）本章的重點(diǎn)是集合的基本概念和運(yùn)算、集合的歸納定義和笛卡兒乘積。（二）本章的難點(diǎn)是集合的交和并運(yùn)算的推廣、自然數(shù)的歸納定義。四、思考與練習(xí)（一）集合論中的包含和屬于關(guān)系的區(qū)別。（二）數(shù)學(xué)歸納法第一原理和第二原理的聯(lián)系和區(qū)別。第三章二元關(guān)系一、學(xué)習(xí)目的通過(guò)本章的學(xué)習(xí)，理解關(guān)系的合成及逆關(guān)系的概念、等價(jià)關(guān)系和劃分的聯(lián)系；掌握關(guān)系的基本概念、二元關(guān)系的關(guān)系矩陣和關(guān)系圖表示、關(guān)系的特性、關(guān)系的閉包運(yùn)算、偏序關(guān)系及其哈斯圖表示、等價(jià)關(guān)系和等價(jià)類(lèi)的概念和性質(zhì)、劃分的概念。第三章計(jì)劃18學(xué)時(shí)。二、課程內(nèi)容3.1基本概念（一）關(guān)系的概念。（二）空關(guān)系、全域關(guān)系、恒等關(guān)系等一些特殊的關(guān)系。（三）二元關(guān)系的表示：集合表示法、關(guān)系圖、關(guān)系矩陣。（四）二元關(guān)系的特性：自反性、反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性、傳遞性。3.2關(guān)系的合成（一）關(guān)系的合成運(yùn)算的概念。（二）關(guān)系的合成運(yùn)算的性質(zhì)。（三）關(guān)系的冪的概念。（四）關(guān)系的冪運(yùn)算的性質(zhì)。（五）合成關(guān)系的矩陣表達(dá)。3.3關(guān)系的閉包運(yùn)算（一）逆關(guān)系的概念。（二）逆關(guān)系的性質(zhì)。（三）關(guān)系的閉包運(yùn)算的概念。（四）構(gòu)造關(guān)系的閉包的方法。（五）關(guān)系的閉包運(yùn)算的性質(zhì)。3.4次序關(guān)系（一）偏序關(guān)系和偏序集合的概念。（二）偏序集合的哈斯圖表示。（三）偏序集中的特殊元素。（四）擬序集合、線序集合、良序集合的概念。（五）偏序、擬序、線序、良序的性質(zhì)。3.5等價(jià)關(guān)系（一）等價(jià)關(guān)系和等價(jià)類(lèi)的概念。（二）等價(jià)關(guān)系的性質(zhì)。（三）劃分的概念。（四）等價(jià)關(guān)系與劃分的聯(lián)系：等價(jià)關(guān)系與化分可相互誘導(dǎo)且保持一致性。（五）劃分的積與和的概念。（六）劃分的積與和的性質(zhì)。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）本章的重點(diǎn)是各種關(guān)系的基本概念、性質(zhì)及其聯(lián)系；關(guān)系的閉包運(yùn)算。（二）本章的難點(diǎn)是關(guān)系的特性的判定、閉包運(yùn)算、等價(jià)關(guān)系與劃分的聯(lián)系。四、思考與練習(xí)（一）空關(guān)系具有哪些特性？（二）關(guān)系的合成運(yùn)算保持哪些關(guān)系的特性？（三）在交、并、差、補(bǔ)等運(yùn)算下，關(guān)系的哪些特性仍保持？（四）偏序集合中最小元素與極小元素的聯(lián)系和區(qū)別。（五）n元集合上可定義多少個(gè)不同的二元關(guān)系、偏序關(guān)系、等價(jià)關(guān)系？第四章函數(shù)一、學(xué)習(xí)目的通過(guò)本章的學(xué)習(xí)，了解一些特殊的函數(shù)；理解映射、單射、滿射、雙射等概念；掌握單射、滿射、雙射的判別方法，函數(shù)的合成運(yùn)算、逆函數(shù)的概念及性質(zhì)。第四章計(jì)劃8學(xué)時(shí)。二、課程內(nèi)容4.1函數(shù)的基本概念（一）函數(shù)和映象等基本概念。（二）函數(shù)的合成。（三）函數(shù)的歸納定義。（四）偏函數(shù)的概念。（五）函數(shù)前域的擴(kuò)大與縮小。4.2特殊函數(shù)類(lèi)（一）單射、滿射、雙射的概念。（二）單射、滿射、雙射的性質(zhì)。（三）一些特殊的函數(shù)。（四）特征函數(shù)的概念及性質(zhì)。4.3逆函數(shù)（一）逆函數(shù)的概念。（二）逆函數(shù)的性質(zhì)。（三）逆像和規(guī)范映射（自然映射）的概念。（四）單側(cè)逆函數(shù)的概念。（五）單側(cè)逆函數(shù)的性質(zhì)。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）本章的重點(diǎn)是函數(shù)的基本概念和基本性質(zhì)。（二）本章的難點(diǎn)是逆函數(shù)與單側(cè)逆函數(shù)的定義和性質(zhì)。四、思考與練習(xí)（一）函數(shù)與關(guān)系的聯(lián)系和區(qū)別。（二）逆函數(shù)與逆關(guān)系的聯(lián)系和區(qū)別。第五章無(wú)限集合一、學(xué)習(xí)目的通過(guò)本章的學(xué)習(xí)，了解可數(shù)與不可數(shù)集合的概念，理解集合基數(shù)的概念及比較，掌握一些常見(jiàn)的無(wú)限集合所屬類(lèi)別的判定方法。第五章計(jì)劃10學(xué)時(shí)。二、課程內(nèi)容5.1可數(shù)和不可數(shù)集合（一）有限集合和無(wú)限集合的概念（二）可數(shù)集合的概念。（三）可數(shù)集合的性質(zhì)。（四）基數(shù)c的概念。5.2基數(shù)的比較（一）集合的等勢(shì)和優(yōu)勢(shì)的概念。（二）集合等勢(shì)的性質(zhì)。（三）無(wú)限集合的特性。（四）基數(shù)的無(wú)限性和連續(xù)統(tǒng)假設(shè)。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）本章的重點(diǎn)是對(duì)無(wú)限集合的理解和區(qū)分。（二）本章的難點(diǎn)是可數(shù)無(wú)限集合與不可數(shù)集合的區(qū)別和判定。四、思考與練習(xí)（一）自然數(shù)集合、整數(shù)集合、有理數(shù)集合、實(shí)數(shù)集合等基數(shù)的大小關(guān)系。（二）集合A、A的冪集合和{0,1}A這三個(gè)集合的基數(shù)的關(guān)系。第六章代數(shù)一、學(xué)習(xí)目的通過(guò)本章的學(xué)習(xí)，了解商代數(shù)和積代數(shù)的構(gòu)造；掌握代數(shù)系統(tǒng)的概念和有關(guān)性質(zhì)、代數(shù)的同態(tài)和同構(gòu)概念、代數(shù)系統(tǒng)的同余關(guān)系、一些重要代數(shù)系統(tǒng)（半群、群、環(huán)、域等）的概念及其性質(zhì)。第六章計(jì)劃28學(xué)時(shí)。二、課程內(nèi)容6.1代數(shù)結(jié)構(gòu)（一）代數(shù)的構(gòu)成：載體、運(yùn)算、代數(shù)常數(shù)。（二）一元運(yùn)算與二元運(yùn)算的概念及性質(zhì)。（三）代數(shù)的分類(lèi)。（四）么元、零元和逆元的概念。（五）么元、零元和逆元的性質(zhì)。6.2子代數(shù)（一）運(yùn)算封閉的概念。（二）子代數(shù)的概念及性質(zhì)。6.3同態(tài)（一）同態(tài)的概念。（二）單一同態(tài)、滿同態(tài)、同構(gòu)的概念。（三）同構(gòu)的性質(zhì)。（四）同態(tài)的性質(zhì)。6.4同余關(guān)系（一）等價(jià)關(guān)系的置換性質(zhì)。（二）同余關(guān)系的概念。（三）同余關(guān)系的性質(zhì)。6.5商代數(shù)和積代數(shù)（一）商代數(shù)的概念。（二）商代數(shù)的性質(zhì)。（三）積代數(shù)的概念。（四）積代數(shù)的性質(zhì)。6.6半群和獨(dú)異點(diǎn)（一）半群、獨(dú)異點(diǎn)、子半群、子獨(dú)異點(diǎn)的概念。（二）半群和獨(dú)異點(diǎn)中元素的冪的概念。（三）半群和獨(dú)異點(diǎn)的性質(zhì)。（四）循環(huán)半群和循環(huán)獨(dú)異點(diǎn)的概念。（五）循環(huán)半群和循環(huán)獨(dú)異點(diǎn)的性質(zhì)。（六）半群與獨(dú)異點(diǎn)的直積的概念。（七）半群與獨(dú)異點(diǎn)同態(tài)的概念。6.7群（一）群、群中元素的冪、群的階、群中元素的階等基本概念。（二）群的基本性質(zhì)。（三）置換群和循環(huán)群的概念。（四）子群的定義及判定。（五）群同態(tài)的概念及性質(zhì)。（六）陪集和拉格朗日定理。（七）正規(guī)子群的概念、性質(zhì)及判定。（八）商群的概念。6.8環(huán)和域（一）環(huán)的概念。（二）域的概念。（三）子環(huán)的概念。（四）環(huán)同態(tài)的概念。（五）理想的概念。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）本章的重點(diǎn)是代數(shù)系統(tǒng)的建立及各種代數(shù)的關(guān)系、群的概念及運(yùn)算。（二）本章的難點(diǎn)是代數(shù)的同態(tài)與同構(gòu)的概念。群的相關(guān)概念和性質(zhì)。四、思考與練習(xí)（一）給定集合上的任意二元運(yùn)算的幺元與零元能否相同？（二）教材中關(guān)于同態(tài)性質(zhì)的定理6.3-3中，A’’能否換成A’？（三）群的階和群中元素的階的聯(lián)系和區(qū)別。（四）如何求出循環(huán)群中的所有生成元？（五）列舉并證明一些判定子群的充要條件。（六）證明階小于6的群都是阿貝爾群。（七）列舉并證明一些域的等價(jià)定義。第七章格與布爾代數(shù)一、學(xué)習(xí)目的通過(guò)本章的學(xué)習(xí)，理解布爾表達(dá)式的概念及運(yùn)算；掌握格和子格等概念及其性質(zhì)，分配格、有界格、有補(bǔ)格的概念、性質(zhì)及判定，布爾代數(shù)的基本概念和運(yùn)算性質(zhì)。第七章計(jì)劃18學(xué)時(shí)。二、課程內(nèi)容7.1格（一）格作為偏序集的定義。（二）格的基本性質(zhì)。7.2格是代數(shù)系統(tǒng)（一）格作為代數(shù)系統(tǒng)的定義。（二）子格的概念及判定。（三）格同態(tài)的概念。（四）格同態(tài)的性質(zhì)。7.3特殊的格（一）分配格的概念及判定。（二）分配格的性質(zhì)。（三）全下界和全上界、有界格的概念。（四）有界格的性質(zhì)。（五）補(bǔ)元、有補(bǔ)格、有補(bǔ)分配格的概念。（六）有補(bǔ)分配格的的性質(zhì)。7.4布爾代數(shù)（一）布爾代數(shù)作為格的定義。（二）布爾代數(shù)作為代數(shù)系統(tǒng)的定義。（三）布爾代數(shù)的性質(zhì)。（四）子布爾代數(shù)和布爾同態(tài)的概念。（五）原子的概念及性質(zhì)。（六）有限布爾代數(shù)的原子表示。（七）布爾代數(shù)的積代數(shù)的概念及性質(zhì)。（八）布爾表達(dá)式和布爾函數(shù)的概念。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）本章的重點(diǎn)是格和作為特殊格的布爾代數(shù)的體系的建立。（二）本章的難點(diǎn)是布爾代數(shù)和布爾表達(dá)式。四、思考與練習(xí)（一）舉例說(shuō)明一般的格中保交和保聯(lián)運(yùn)算不一定滿足分配律。（二）正整數(shù)的正因子集關(guān)于最大公約數(shù)和最小公倍數(shù)能否構(gòu)成布爾代數(shù)？（三）給出并證明n元布爾函數(shù)的個(gè)數(shù)。（四）布爾函數(shù)與布爾表達(dá)式的聯(lián)系和區(qū)別。第八章圖論一、學(xué)習(xí)目的通過(guò)本章的學(xué)習(xí)，了解對(duì)偶圖和五色問(wèn)題及應(yīng)用、搜索樹(shù)和決策樹(shù)等概念；理解平面圖歐拉公式的證明及應(yīng)用；掌握?qǐng)D論的基本概念，圖的路徑和回路、圖的連通性、賦權(quán)圖的最短路徑等基本概念和性質(zhì)，歐拉路徑和歐拉回路、哈密爾路徑和回路的基本概念、性質(zhì)、判定及應(yīng)用，圖的矩陣表示（鄰接矩陣和可達(dá)矩陣），二部圖和平面圖的定義及判斷方法，樹(shù)的等價(jià)定義，最小生成樹(shù)的概念及生成方法，有向樹(shù)、最優(yōu)樹(shù)等概念及其應(yīng)用。第八章計(jì)劃26學(xué)時(shí)。二、課程內(nèi)容8.1圖的基本概念（一）無(wú)向圖、有向圖、簡(jiǎn)單圖、賦權(quán)圖、頂點(diǎn)的度數(shù)等基本概念。（二）圖的基本性質(zhì)。（三）圖的同構(gòu)的概念及性質(zhì)。（四）圖的運(yùn)算：并、交、差、環(huán)和、刪除結(jié)點(diǎn)或邊。（五）子圖、導(dǎo)出子圖、完全圖與補(bǔ)圖等概念。8.2路徑與回路（一）路徑和回路的概念及性質(zhì)。（二）無(wú)向圖的連通性和連通分圖的概念。（三）有向圖的連通性，強(qiáng)連通分圖、單向連通分圖、弱連通分圖的概念。（四）賦權(quán)圖中的最短路徑。（五）歐拉路徑和歐拉回路、歐拉圖的概念。（六）歐拉圖的判定及應(yīng)用。（七）哈密爾頓路徑和哈密爾頓回路、哈密爾頓圖的概念。（八）哈密爾頓圖的必要條件和充分條件。（九）貨郎擔(dān)問(wèn)題：最近鄰算法。8.3圖的矩陣表示（一）有向線圖、無(wú)向線圖和賦權(quán)圖的鄰接矩陣的概念。（二）有向線圖的鄰接矩陣的性質(zhì)。（三）可達(dá)矩陣的概念。（四）可達(dá)矩陣的計(jì)算。8.4二部圖