1、離散數(shù)學(xué)答疑庫1、什么是計算學(xué)科？答：計算學(xué)科（Computing Science）即我們所熟悉的計算機(jī)科學(xué)與技術(shù)(Computer Science and Technology)。計算學(xué)科是對描述和變換信息的算法過程，包括其理論、分析、設(shè)計、效率分析、實現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究的一門學(xué)科。它涉及計算過程的分析如可計算性、算法，研究有關(guān)計算機(jī)的各種現(xiàn)象、揭示其規(guī)律與本質(zhì)如計算機(jī)的設(shè)計和使用、可計算性硬件和軟件的實際實現(xiàn)問題。計算學(xué)科的基本問題是能行與效率的問題,即它的核心問題是“能行”問題(Practicability)： 1)、什么是（實際）可計算的？ 什么是（實際）不可計算的？ 2)、如何

2、保證計算的自動性、有效性及正確性？ 2、計算科學(xué)是一門什么樣的學(xué)科？是計算機(jī)科學(xué)是科學(xué)還是工程學(xué)科?答：計算學(xué)科（通常也稱作計算機(jī)科學(xué)與技術(shù)）作為現(xiàn)代技術(shù)的標(biāo)志，已成為世界各國經(jīng)濟(jì)增長的主要動力。但如何認(rèn)識這門學(xué)科，它究竟屬于理科還是工科，屬于科學(xué)還是屬于工程的范疇，這是困擾國內(nèi)外計算機(jī)科學(xué)界很長時間且爭論不休的問題。計算學(xué)科誕生于20世紀(jì)40年代初，它的理論基礎(chǔ)可以說在這之前就已經(jīng)建立起來了。正是電子數(shù)字計算機(jī)的問世才這一門學(xué)科的在發(fā)展。世人一般公認(rèn)1946年2月14日研制成功的ENIAC（電子數(shù)字積分器和計算器，Electronic Numerical Integrator and Cal

3、culator）是世界上第一臺通用電子數(shù)字計算機(jī)（事實上，早在1943年，英國數(shù)學(xué)家圖靈領(lǐng)導(dǎo)制造出了一臺名叫“巨人”（Colossus）的電子計算機(jī)，它專門用于譯碼。由于英國政府的保密制度，故人們對它的成就了解甚少。）。美國的普渡大學(xué)于1962年開設(shè)了最早的計算機(jī)科學(xué)學(xué)位課程。在計算機(jī)產(chǎn)生之初及隨后的一、二十年時間里，計算機(jī)主要用于數(shù)值計算。大多數(shù)科學(xué)家認(rèn)為使用計算機(jī)僅為編程問題，不需作任何深刻的科學(xué)思考，計算機(jī)從本質(zhì)上說是一種職業(yè)而一門學(xué)科。到了20世紀(jì)70、80年代，計算技術(shù)得到了迅猛的發(fā)展和廣泛的應(yīng)用，并開始滲透到大多數(shù)科學(xué)領(lǐng)域。這時人們普遍爭論的問題是：計算機(jī)科學(xué)是否作為一門學(xué)科？它是

4、科學(xué)還是工程？它屬于理科還是工科？或者只是一門技術(shù)、一個計算商品的研制者或銷售者？科學(xué)是關(guān)于自然、社會和思維的發(fā)展和變化規(guī)律的知識體系，它主要解決認(rèn)識世界的問題，是創(chuàng)造知識的研究活動，回答“是什么”和“為什么”。它得出假設(shè)，作出基于假設(shè)的斷言，收集數(shù)據(jù)并分析數(shù)據(jù)以證實或推翻假設(shè)。技術(shù)泛指根據(jù)科學(xué)原理和生產(chǎn)實踐經(jīng)驗發(fā)展而成的各種工藝操作方法、技能和技藝。它主要解決改造世界的問題，回答“做什么”和“怎樣做”的問題。工程則指將科學(xué)原理應(yīng)用到實際領(lǐng)域中而形成的各門學(xué)科的總稱?？茖W(xué)探索未知，進(jìn)行發(fā)現(xiàn)，帶有自由研究的性質(zhì)。技術(shù)則發(fā)明、綜合應(yīng)用知識?？茖W(xué)成果主要以知識形態(tài)存在，而技術(shù)成果除以知識形態(tài)存在之外

5、，還具有一定的物質(zhì)形態(tài)?？茖W(xué)對經(jīng)濟(jì)的作用不太確定，可能在較長時間內(nèi)才能體現(xiàn)出來，而技術(shù)對經(jīng)濟(jì)的作用則確定而直接。1985年春，ACM（美國計算機(jī)協(xié)會）和IEEECS（國際電子電氣工程師學(xué)會計算機(jī)分會）組成聯(lián)合攻關(guān)小組，開始了對“計算作為一門學(xué)科”的存在性證明。1989年1月，該小組提交了計算作為一門學(xué)科（Computing as a discipline）的報告。第一次給出了計算學(xué)科一個透徹的定義，回答了計算學(xué)科中長期以來一直爭論的一些問題，完成了計算學(xué)科的“存在性”證明，還提出了未來計算科學(xué)教育必須解決的二個重大問題整個學(xué)科核心課程詳細(xì)設(shè)計及整個學(xué)科綜述性導(dǎo)引課程的構(gòu)建。1991年，在這報告

6、的基礎(chǔ)上提交了關(guān)于計算學(xué)科教學(xué)計劃CC1991（Computing Curricula 1991）。2001年12月，提交了最終的CC2001報告。計算作為一門學(xué)科報告及CC1991、CC2001一起解決了三個重要問題：第一個重大問題（計算作為一門學(xué)科的存在性證明）的解決。對學(xué)科本身的發(fā)展至關(guān)重要。如果在眾多分支領(lǐng)域都取得了重大成果并已得到廣泛應(yīng)用的“計算”，連作為一門學(xué)科的地位都不清楚，那么它的發(fā)展勢必要受到很大的限制。第二個重大問題（整個學(xué)科核心課程詳細(xì)設(shè)計）的解決，將為高校制定計算機(jī)教學(xué)計劃奠定基礎(chǔ)。確定一個公認(rèn)的本科生應(yīng)該掌握的核心內(nèi)容，將避免教學(xué)計劃設(shè)計中的隨意性，從而為我們科學(xué)地制

7、定教學(xué)計劃奠定基礎(chǔ)。第三個重大問題（整個學(xué)科綜述性導(dǎo)引課程的構(gòu)建）的解決，將使人們對整個學(xué)科的認(rèn)知科學(xué)化、系統(tǒng)化和邏輯化。如果人們對計算學(xué)科的認(rèn)知能建立在公理化的基礎(chǔ)之上，則該學(xué)科可被認(rèn)為是嚴(yán)謹(jǐn)?shù)目茖W(xué)、成熟的學(xué)科，從而有助于它的發(fā)展，并將由此而得到人們的尊重。攻關(guān)小組的結(jié)論是：計算學(xué)科所研究的根本問題是能行問題（什么能被（有效地）自動進(jìn)行）。計算學(xué)科的基本原理已納入理論、抽象和設(shè)計這3個具有科學(xué)技術(shù)方法意義的過程中。學(xué)科的各分支領(lǐng)域正是通過這3個過程來實現(xiàn)它們各自的目標(biāo)。而這3個過程要解決的都是計算過程中的“能行性”和“有效性”問題。這兩個問題滲透在包括硬件和軟件在內(nèi)的理論、方法、技術(shù)的研究和

8、應(yīng)用的研究和開發(fā)之中，且學(xué)科的方法論的主要理論基礎(chǔ)以離散數(shù)學(xué)為代表的構(gòu)造性數(shù)學(xué)與能行性問題形成了天然的一致。因此，計算機(jī)科學(xué)各個分支學(xué)科的理論、技術(shù)理論和計算機(jī)工程的各學(xué)科的工程（含開發(fā)方法）和工程技術(shù)（含技藝和技巧）常常既有理論特征，又有技術(shù)特征，二者之間的界限往往不很清楚。它們本質(zhì)上都是從不同的角度和層面對各種問題的能行性及其求解方法和過程的描述。相對而言，計算機(jī)科學(xué)側(cè)重于理論和抽象，而計算機(jī)工程則側(cè)重于抽象和設(shè)計，計算機(jī)科學(xué)與工程則居中。因此不能簡單地將計算學(xué)科歸屬于理科或工科。ACM和IEEECS聯(lián)合攻關(guān)小組將計算機(jī)科學(xué)、計算機(jī)工程、計算機(jī)科學(xué)與工程、計算機(jī)信息學(xué)以及其它類似名稱的及其

9、研究范疇統(tǒng)稱為計算學(xué)科。3、計算科學(xué)與數(shù)學(xué)的關(guān)系是什么？為什么計算機(jī)技術(shù)專業(yè)的學(xué)生要學(xué)習(xí)數(shù)學(xué)？答：數(shù)學(xué)是現(xiàn)代科學(xué)的重要基礎(chǔ)，當(dāng)然也是計算科學(xué)的主要基礎(chǔ)。數(shù)學(xué)方法在現(xiàn)代科技的發(fā)展中已經(jīng)成為一種必不可少的認(rèn)識手段。它的主要作用是為科技研究提供：（1）簡潔精確的形式化語言；（2）數(shù)量分析和計算的方法；（3）邏輯推理的工具。人們公認(rèn)高技術(shù)本質(zhì)上就是數(shù)學(xué)技術(shù)，而計算學(xué)科（即我們所熟悉的計算機(jī)科學(xué)與技術(shù)）也離不開數(shù)學(xué)。從數(shù)學(xué)的角度出發(fā)，數(shù)學(xué)本身可分為連續(xù)數(shù)學(xué)和離散數(shù)學(xué)。離散和連續(xù)是現(xiàn)實世界中物質(zhì)運動對立統(tǒng)一的兩個方面，離散數(shù)學(xué)和連續(xù)數(shù)學(xué)是描述、刻畫現(xiàn)實物質(zhì)世界的重要工具。最早的數(shù)學(xué)本質(zhì)上是一種離散型的數(shù)學(xué)

10、，但隨著微積分的出現(xiàn)，對整個數(shù)學(xué)的研究發(fā)生了深刻的影響。人們以一種連續(xù)的觀點研究數(shù)學(xué)，描述自然科學(xué)研究中的各種具體問題，從而形成了現(xiàn)在占統(tǒng)治地位的連續(xù)數(shù)學(xué)。隨著現(xiàn)代科學(xué)技術(shù)的發(fā)展，特別是計算機(jī)科學(xué)技術(shù)的興起，離散數(shù)學(xué)又重新找到了它自己原有的位置?！澳苄行浴边@個計算學(xué)科的根本問題決定了計算機(jī)本身的結(jié)構(gòu)和它處理的對象都是離散型的，甚至許多連續(xù)型問題也必須在轉(zhuǎn)化為離散型問題以后才能被計算機(jī)處理。所以計算機(jī)科學(xué)與技術(shù)本質(zhì)上是一門離散數(shù)學(xué)技術(shù)。在計算科學(xué)中，無論是理論研究還是技術(shù)研究的成果，最終目標(biāo)要體現(xiàn)在計算機(jī)軟件產(chǎn)品的程序指令系統(tǒng)應(yīng)能機(jī)械地、嚴(yán)格地按照程序指令執(zhí)行，決不能無故出錯。計算機(jī)系統(tǒng)的這一客

11、觀屬性和特點決定了計算機(jī)的設(shè)計、制造、以及各種軟件系統(tǒng)開發(fā)的每一步都應(yīng)該是嚴(yán)密的、精確無誤的。就目前基于圖靈機(jī)這一理論計算模型和存儲程序式思想設(shè)計制造的計算機(jī)而言，它們只能處理離散問題或可用構(gòu)造性方式描述的問題，而且這些問題必須對給定的論域存在有窮表示。至于非離散的連續(xù)性問題，如實數(shù)域上的函數(shù)計算，方程求根等還只能用近似的逼近方法。于是，由于計算模型的非連續(xù)性特點，使得以嚴(yán)密、精確著稱的數(shù)學(xué)尤其是以離散數(shù)學(xué)為代表的應(yīng)用數(shù)學(xué)成為描述計算學(xué)科理論、方法和技術(shù)的主要工具。數(shù)學(xué)與電子科學(xué)（特別是微電子技術(shù)）構(gòu)成了計算學(xué)科的基礎(chǔ)。與數(shù)學(xué)相比，電子技術(shù)的重要性對計算科學(xué)而言不如數(shù)學(xué)，因為數(shù)學(xué)提供了計算科學(xué)

12、最重要的學(xué)科思想和方法論基礎(chǔ)，而電子技術(shù)只提供了電子計算機(jī)的實現(xiàn)技術(shù)，它僅僅只是對計算科學(xué)許多思想和方法的一種當(dāng)前最現(xiàn)實、最有效的實現(xiàn)技術(shù)手段而已。當(dāng)科學(xué)技術(shù)的手段提到發(fā)展時，完全有可能有某一項新技術(shù)歸結(jié)為有效地取代電子技術(shù)（如光技術(shù)、生物技術(shù)等等），但計算科學(xué)的數(shù)學(xué)基礎(chǔ)可能變化不大。從事計算科學(xué)的人都知道，計算科學(xué)中不僅許多理論是用數(shù)學(xué)描述的，而且許多技術(shù)也是用數(shù)學(xué)描述的。大多數(shù)計算科學(xué)理論不僅僅是對研究對象變化規(guī)律的陳述，而且由于能行性這一本質(zhì)的核心問題和特點的作用，理論描述中常通過方法折射出技術(shù)的思想和步驟，而從理論通過方法跨越到技術(shù)則完全取決于理論的深刻認(rèn)識和理解。一個人如果看懂了以形

13、式化方法描述的技術(shù)文獻(xiàn)，自然明白技術(shù)上應(yīng)該怎樣去做。至于計算機(jī)技術(shù)專業(yè)的學(xué)生為何要學(xué)習(xí)數(shù)學(xué)這個問題的答案，了解了上面所講的計算學(xué)科與數(shù)學(xué)的關(guān)系后就不言而喻了：計算機(jī)科學(xué)植根于數(shù)學(xué)，從而數(shù)學(xué)是必須掌握的基礎(chǔ)知識；另外如果我們已經(jīng)擁有牢固的數(shù)學(xué)基礎(chǔ)，則能大大提高我們本身的邏輯推理能力、抽象思維能力和形式化思維能力，從而今后在學(xué)習(xí)任何一門計算機(jī)科學(xué)的專業(yè)主干課程時，都不會遇上任何思維理解上的困難。4、離散數(shù)學(xué)這門課程在計算機(jī)科學(xué)技術(shù)學(xué)科中有什么樣的作用？答：離散數(shù)學(xué)（Discrete Mathematics）研究離散（變）量的結(jié)構(gòu)及其相互關(guān)系，是計算機(jī)科學(xué)的理論基礎(chǔ)。在整個課程的學(xué)習(xí)過程中，由于要經(jīng)

14、常強(qiáng)調(diào)具有構(gòu)造性特點的一系列問題解決方法，因此它非常重視“能行性”(Practicability)問題的研究：即要解決一個問題，不光要證明該問題解的存在性（連續(xù)數(shù)學(xué)只要做到這一步就基本上算解決問題了），還要給出解決該問題的解的步驟來。 我們知道在計算科學(xué)研究中，存在這樣一條規(guī)律：一個問題，當(dāng)它的描述及其求解方法或求解過程可以用構(gòu)造性數(shù)學(xué)描述，而且該問題所涉及的論域為有窮，或雖為無窮但存在有窮表示時，那么該問題一定能用計算機(jī)來求解；反過來，凡是能用計算機(jī)求解的問題，也一定能將該問題的求解過程數(shù)學(xué)化，而且這種數(shù)學(xué)化是構(gòu)造性的。從而計算學(xué)科的基本問題是“能行性”問題。凡是與“能行性”有關(guān)的討論，都是

15、處理離散對象的。因為非離散對象（即連續(xù)對象），是很難進(jìn)行“能行”處理的。因此，“能行性”這個計算學(xué)科的根本問題決定了計算機(jī)本身的結(jié)構(gòu)和它處理的對象都是離散型的，甚至許多連續(xù)型問題也必須在轉(zhuǎn)化為離散型問題以后才能被計算機(jī)處理。正是構(gòu)造數(shù)學(xué)的構(gòu)造性和離散性特征保證了計算方法的能行性，所以計算機(jī)科學(xué)與技術(shù)本質(zhì)上是一門離散數(shù)學(xué)技術(shù)。離散數(shù)學(xué)是計算機(jī)科學(xué)和技術(shù)的重要理論基礎(chǔ)之一，為計算學(xué)科各分支領(lǐng)域解決其基本問題提供了強(qiáng)有力的數(shù)學(xué)工具，在計算機(jī)科學(xué)與技術(shù)中有十分廣泛的應(yīng)用。1998年秋，IEEECS和ACM聯(lián)手組成任務(wù)組，開始了關(guān)于計算學(xué)科教學(xué)計劃的CC2001（Computing Curricula

16、2001）的起草工作。經(jīng)過3年多的工作，任務(wù)組于2001年12月提交了最終報告。CC2001將計算學(xué)科劃分為14個主領(lǐng)域：離散結(jié)構(gòu)(Discrete Structures)、程序設(shè)計基礎(chǔ)(Programming Fundamentals)、算法與復(fù)雜性(Algorithms and Complexity)、體系結(jié)構(gòu)(Architecture and Organization)、操作系統(tǒng)(Operating Systems)、網(wǎng)絡(luò)計算(Net-Centric Computing)、程序設(shè)計語言(Programming Languages)、人機(jī)交互(Human-Computer Interact

17、ion)、圖形學(xué)與可視化計算(Graphics and Visual Computing)、智能系統(tǒng)(Intelligent Systems)、信息管理(Information Management)、軟件工程(Software Engineering)、社會和職業(yè)的問題(Social and Professional Issues)和科學(xué)計算(Computational Science)。CC2001的一個特別之處是將離散數(shù)學(xué)從預(yù)備知識部分獨立出來，列為學(xué)科的第一個主領(lǐng)域，以強(qiáng)調(diào)計算學(xué)科對它的依賴性。離散數(shù)學(xué)所涉及的概念、方法和理論，大量地應(yīng)用在“數(shù)字電路”、“編譯原理”、“數(shù)據(jù)結(jié)構(gòu)”、“操

18、作系統(tǒng)”、“數(shù)據(jù)庫系統(tǒng)”、“系統(tǒng)結(jié)構(gòu)”、“容錯判斷”、“算法的分析與設(shè)計”、“邏輯程序設(shè)計”、“軟件工程”、“人工智能”、“多媒體技術(shù)”、“計算機(jī)網(wǎng)絡(luò)”、“信息管理”、“信號處理”、“模式識別”、“數(shù)據(jù)加密”、 “機(jī)器定理證明”、 “形式語言與自動機(jī)”等計算科學(xué)的相關(guān)專業(yè)課程中，為這些專業(yè)課程的學(xué)習(xí)提供了重要的數(shù)學(xué)理論基礎(chǔ)。更重要的是計算學(xué)科各專業(yè)的學(xué)生通過學(xué)習(xí)離散數(shù)學(xué)，可以使他們熟悉和習(xí)慣抽象的符號表示和演算形式，培養(yǎng)和訓(xùn)練我們掌握使用數(shù)學(xué)語言或符號系統(tǒng)處理問題的基本方法，提高我們的抽象思維和邏輯推理的能力。數(shù)學(xué)系畢業(yè)的學(xué)生到軟件企業(yè)中大多做軟件設(shè)計與分析工作，而計算機(jī)系畢業(yè)的學(xué)生則以做程序

19、員的居多，原因就在于數(shù)學(xué)系畢業(yè)的學(xué)生有很強(qiáng)的分析推理能力。這充分說明了抽象思維和邏輯推理能力的重要性。計算機(jī)系的學(xué)生學(xué)習(xí)離散數(shù)學(xué)的目的應(yīng)該是：將抽象的理論再應(yīng)用于實踐，不但要掌握題目的解題方法，更要掌握解題思想；對于定理的學(xué)習(xí)：不是簡單的應(yīng)用，而是掌握證明過程即掌握定理的由來，訓(xùn)練自己的推理能力。只有這樣才達(dá)到了學(xué)習(xí)這門課程的目的：通過嚴(yán)格的訓(xùn)練，逐步實現(xiàn)思維方式的數(shù)學(xué)化。5、離散數(shù)學(xué)這門課程的特點和內(nèi)容有哪些？答：離散數(shù)學(xué)由多門數(shù)學(xué)分支組成，每一分支可以看成是一門獨立的學(xué)科，它們從不同的角度出發(fā)，研究各種離散量之間數(shù)與形的關(guān)系。它充分地描述了計算機(jī)與技術(shù)離散性的特點，從而成了計算科學(xué)的主要工

20、具。它的數(shù)學(xué)內(nèi)容并不是新的，是隨著計算科學(xué)的興起，才成為一門獨立的課程。隨著計算科學(xué)的出現(xiàn)，一些以前獨立的數(shù)學(xué)分支以它們的某些方面的共性以及在計算科學(xué)中的不斷應(yīng)用突然變得日益重要起來。人們發(fā)現(xiàn)，這些分支處理的數(shù)學(xué)對象和方法與傳統(tǒng)的分析有明顯的區(qū)別：分析研究的問題描述和解決方案都是連續(xù)的，因而微分、積分成為基本的運算手段；而這些分支研究的對象是離散的，一般是有限個或可數(shù)個，從而我們稱這些分支為“離散數(shù)學(xué)”?！半x散數(shù)學(xué)”的名字越來越響亮，最后導(dǎo)致以分析為中心的傳統(tǒng)數(shù)學(xué)被相對稱為“連續(xù)數(shù)學(xué)”。 經(jīng)過多年的發(fā)展，離散數(shù)學(xué)的內(nèi)容基本上穩(wěn)定下來。一般認(rèn)為，離散數(shù)學(xué)包含以下部分 ：1) 集合論(Sets)2

21、）二元關(guān)系(Binary Relations)3）數(shù)理邏輯（包括命題邏輯和謂詞邏輯）Mathematical Logic4）抽象代數(shù)（包括代數(shù)結(jié)構(gòu)、半群、群、環(huán)、域和布爾代數(shù)）(Abstract Algebra)5）圖論(Graph Theory)6）數(shù)論和組合數(shù)學(xué)(Number Theory and Combinatorics)6、學(xué)習(xí)離散數(shù)學(xué)要達(dá)到什么樣的目的？答：通過學(xué)習(xí)本課程，不僅掌握離散數(shù)學(xué)在計算科學(xué)中的應(yīng)用，為計算機(jī)專業(yè)后續(xù)專業(yè)課程的學(xué)習(xí)和科研工作（軟、硬件開發(fā)和應(yīng)用研究）的參與打下良好的數(shù)學(xué)理論基礎(chǔ)，而且學(xué)到一種證明問題的方法，培養(yǎng)學(xué)生抽象思維、嚴(yán)格的邏輯推理和創(chuàng)新能力，進(jìn)而提高

22、學(xué)生分析問題解決問題的能力。離散數(shù)學(xué)的學(xué)習(xí)所提供的訓(xùn)練，十分有益于學(xué)生概括抽象能力、邏輯思維能力、歸納構(gòu)造能力的提高，十分有益于學(xué)生嚴(yán)謹(jǐn)、完整、規(guī)范的科學(xué)態(tài)度的培養(yǎng)。這些能力與態(tài)度是一切軟、硬件計算機(jī)科學(xué)工作者所不可缺少的。離散數(shù)學(xué)課程所傳授的思想和方法，廣泛地體現(xiàn)在計算機(jī)科學(xué)技術(shù)從科學(xué)計算到信息處理，從理論計算機(jī)科學(xué)到計算機(jī)應(yīng)用技術(shù)，從計算機(jī)軟件到計算機(jī)硬件，從人工智能到分布式系統(tǒng)及相關(guān)專業(yè)的諸領(lǐng)域中。7、在離散數(shù)學(xué)中，集合論的具體內(nèi)容有什么？在計算科學(xué)中有什么應(yīng)用？答：集合論是現(xiàn)代數(shù)學(xué)的基礎(chǔ)，是現(xiàn)代數(shù)學(xué)不可或缺的基本描述工具?？梢赃@樣講，現(xiàn)代數(shù)學(xué)（包括離散數(shù)學(xué)）的“大廈”是建立在集合論的基

23、礎(chǔ)之上的。從而集合論也是計算科學(xué)的基礎(chǔ)。集合論主要研究：集合及其表示、集合的運算及其性質(zhì)、集合的基數(shù)、有限集與無限集、有序?qū)图系牡芽柗e。集合不僅可以用來表示數(shù)及其運算，還可以用于非數(shù)值信息的表示和處理（如數(shù)據(jù)的增加、刪除、修改、排序及數(shù)據(jù)間關(guān)系的描述等）。集合論在編譯原理、開關(guān)理論、信息檢索、形式語言、數(shù)據(jù)庫與知識庫、專家系統(tǒng)、CAD、CAI、人工智能等各個領(lǐng)域中有十分廣泛的應(yīng)用。8、在離散數(shù)學(xué)中，關(guān)系理論的具體內(nèi)容有什么？在計算科學(xué)中有什么應(yīng)用？答：關(guān)系是一種被廣泛使用的概念，如日常生活中的父子關(guān)系、朋友關(guān)系、債主與債戶關(guān)系，自然科學(xué)中的函數(shù)關(guān)系、相似關(guān)系、對稱關(guān)系。我們介紹集合時，并

24、不關(guān)心集合的成員之間有什么關(guān)系。而事實上客觀世界是由各種各樣的事物組成的，事物之間存在著一定的相互作用、相互聯(lián)系和相互制約的關(guān)系。集合的元素并不是烏合之眾。因此我們既有必要研究集合元素的個性、共性，更有必要研究元素之間的關(guān)系。關(guān)系理論主要研究：關(guān)系的定義與表示、關(guān)系的性質(zhì)（自反性、反自反性、對稱性、反對稱性和傳遞性）、關(guān)系的運算、等價關(guān)系、等價類與劃分、序關(guān)系（偏序關(guān)系、全序關(guān)系和良序關(guān)系）。在計算機(jī)科學(xué)中關(guān)系理論的應(yīng)用特別普遍：如關(guān)系數(shù)據(jù)庫中數(shù)據(jù)特性關(guān)系、程序的輸入與輸出關(guān)系、計算機(jī)語言的字符關(guān)系、OOP編程中的類繼承關(guān)系、結(jié)構(gòu)化程序設(shè)計中的函數(shù)或子程序調(diào)用關(guān)系、程序的串行與并行運算關(guān)系。9

25、、在離散數(shù)學(xué)中，數(shù)理邏輯的具體內(nèi)容有什么？在計算科學(xué)中有什么應(yīng)用？答：數(shù)理邏輯又稱符號邏輯，是用數(shù)學(xué)的方法研究思維規(guī)律和推理過程的一門學(xué)科。人的思維的形式結(jié)構(gòu)包括概念、判斷和推理之間和結(jié)構(gòu)和聯(lián)系。其中概念是思維的基本單位；通過概念對事物描述是否具有某種屬性進(jìn)行肯定或否定的回答，這個過程就是判斷；由一個或幾個判斷推出另一個判斷的思維形式就是推理。研究推理的方法很多，用引進(jìn)一套符號體系、乘簡潔地表示出各種推理的邏輯關(guān)系的數(shù)學(xué)方法研究推理的就稱為數(shù)理邏輯。數(shù)理邏輯主要研究：邏輯演算(命題邏輯和謂詞邏輯)（包括命題的概念、命題的真值、命題聯(lián)結(jié)詞、命題符號化、合式公式(命題公式)、子公式和指派、真值表、

26、公式分類與永真式、邏輯恒等式和永真蘊(yùn)含式、證明方法、對偶原理、合(析)取范式、極大(小)項、主合(析)取范式、命題邏輯的推理理論、個體、個體域、謂詞、命題的謂詞形式、量詞（稱量詞、存在量詞）、量詞的轄域、自由變元、約束變元、合式公式）、公理化集合論、模型論、構(gòu)造主義與證明論。最基本的內(nèi)容是命題邏輯和謂詞邏輯。數(shù)理邏輯在電子線路、機(jī)器證明、自動化系統(tǒng)、編譯理論、算法設(shè)計方法、自動程序設(shè)計、CAD方面有著廣泛的應(yīng)用。10、在離散數(shù)學(xué)中，抽象代數(shù)的具體內(nèi)容有什么？在計算科學(xué)中有什么應(yīng)用？答：代數(shù)的概念與方法是研究計算機(jī)科學(xué)和工程的重要數(shù)學(xué)工具。眾所周知，在許多實際問題的研究中都離不開數(shù)學(xué)模型，而構(gòu)造

27、數(shù)學(xué)模型就要用到某種數(shù)學(xué)結(jié)構(gòu)，而抽象代數(shù)研究的中心問題是代數(shù)系統(tǒng)的結(jié)構(gòu)：半群、群、環(huán)、域、格與布爾代數(shù)等等。因此抽象代數(shù)的基本概念、方法和結(jié)果已成為計算機(jī)科學(xué)與工程領(lǐng)域中研究人員的基本工具。抽象代數(shù)主要研究：代數(shù)運算與代數(shù)系統(tǒng)、代數(shù)運算的性質(zhì)（交換律、結(jié)合律、分配律等）、特殊元素（單位元、零元、逆元、冪等元等）、代數(shù)系統(tǒng)的同態(tài)和同構(gòu)、半群、獨異點、子半群和子獨異點、群、元素的階、子群和子群的判定條件、群同態(tài)和群同構(gòu)、特殊群（可交換群、循環(huán)群和變換群）、子群的陪集與拉格朗日定理、不變子群、商群與群同態(tài)基本定理、環(huán)（可交換環(huán)、有單位元環(huán)、有零因子環(huán)、無零因子環(huán)、整環(huán)）、理想、商環(huán)、環(huán)同態(tài)、多項式環(huán)

28、、有限域、格（偏序格和代數(shù)格）、格同態(tài)、特殊格（完全格、有界格、有補(bǔ)格、模格（泰特金格）、分配格、有補(bǔ)分配格）、布爾代數(shù)、子布爾代數(shù)、布爾同態(tài)、有限布爾代數(shù)。抽象代數(shù)在研究形式語言與自動機(jī)理論、編碼理論、關(guān)系數(shù)據(jù)庫理論、抽象數(shù)據(jù)類型與表示理論、算法理論、網(wǎng)絡(luò)與通信理論、Petri網(wǎng)理論中，在描述機(jī)器可計算的函數(shù)、研究可計算性與計算復(fù)雜性、刻畫抽象數(shù)據(jù)結(jié)構(gòu)、研究程序設(shè)計學(xué)中的形式語義學(xué)中有著十分廣泛的應(yīng)用。特別地，半群在形式語言和自動機(jī)理論中有著重要的應(yīng)用，有限域理論是編碼理論的數(shù)學(xué)基礎(chǔ)，在通訊中發(fā)揮了重要作用。而電子線路設(shè)計、電子計算機(jī)硬件設(shè)計和通訊系統(tǒng)設(shè)計更是離不開布爾代數(shù)。11、在離散數(shù)學(xué)

29、中，圖論的具體內(nèi)容有什么？在計算科學(xué)中有什么應(yīng)用？答：圖論起源于歐拉解決的哥尼斯堡七橋問題。在自然界和人類社會的實際生活中，用圖形來描述和表示某些事物之間的關(guān)系既方便又直觀。例如用工藝流程圖來描述某項工程中各工序之間的先后關(guān)系，用網(wǎng)絡(luò)圖來描述某通訊系統(tǒng)中各通訊站之間信息傳遞關(guān)系，用開關(guān)電路圖來描述IC中各元件電路導(dǎo)線連接關(guān)系等等。圖的理論在開始時似乎價值不大，因為所討論的內(nèi)容多為娛樂性的一些難題， 但計算學(xué)科的興起和發(fā)展改變了這一切。圖論研究由線連成的點集的理論。一個圖中的結(jié)點表示對象，兩點之間的連線表示兩對象之間具有某種特定關(guān)系(先后關(guān)系、勝負(fù)關(guān)系、傳遞關(guān)系和連接關(guān)系等)。事實上，任何一個包

30、含了某種二元關(guān)系的系統(tǒng)都可以用圖形來模擬。由于我們感興趣的是兩個對象之間是否有某種特定關(guān)系，所以圖形中兩點之間連接與否最重要，而連接線的曲直長短則無關(guān)緊要。由此經(jīng)數(shù)學(xué)抽象產(chǎn)生了圖的概念。圖論主要研究：圖的基本概念（頂點、邊、度、無向圖、有向圖）、端點、鄰接頂點、孤立點、平行邊、自回路、多重圖、線圖、零圖、平凡圖、簡單圖、有限圖、Euler握手定理、子圖、生成子圖、誘導(dǎo)子圖、完全圖、補(bǔ)圖、圖的同構(gòu)、通路（回路）、簡單通路（簡單回路）、基本通路（基本回路）、頂點間的可達(dá)性、連通性、連通分支、有向圖的強(qiáng)連通性、單向連通性、弱連通性、圖的矩陣表示（鄰接矩陣、可達(dá)矩陣）、歐拉圖、哈密爾頓圖、平面圖、面、

31、歐拉公式、無向樹、生成樹、最小生成樹、有向樹、二元樹、最優(yōu)樹、前綴碼、二部圖（偶圖）、匹配、圖的著色問題、網(wǎng)絡(luò)。由于生產(chǎn)管理、軍事、交通運輸、計算機(jī)和通訊網(wǎng)絡(luò)等方面的大量問題的出現(xiàn)，大大促進(jìn)了圖論的應(yīng)用。特別是電子計算機(jī)的大量應(yīng)用，更使大規(guī)模圖論問題的求解成為可能。實際問題如電網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電路設(shè)計、數(shù)據(jù)結(jié)構(gòu)以及社會科學(xué)中的問題所涉及到的圖形都是很復(fù)雜的，需要計算機(jī)的幫助才有可能進(jìn)行分析和解決。目前圖論在電信網(wǎng)絡(luò)、開關(guān)理論、編碼理論、可靠性理論、計算機(jī)程序設(shè)計、故障診斷、人工智能、印刷電路板的設(shè)計、圖案識別、地圖著色等計算科學(xué)的學(xué)科領(lǐng)域都有十分廣泛的應(yīng)用。12、在離散數(shù)學(xué)中，數(shù)論和組合數(shù)學(xué)的

32、具體內(nèi)容有什么？在計算科學(xué)中有什么應(yīng)用？答：數(shù)論是研究數(shù)的規(guī)律、特別是整數(shù)性質(zhì)的數(shù)學(xué)分支。它與幾何學(xué)一樣，是最古老的而又始終活躍著的數(shù)學(xué)研究領(lǐng)域。素數(shù)分布是數(shù)論最早的研究課題，歐幾里得就曾證明過素數(shù)有無窮多個。歷史上的絕大多數(shù)數(shù)學(xué)家都進(jìn)行過數(shù)論方面的研究。組合數(shù)學(xué)也叫組合分析， 組合數(shù)學(xué)也是一個古老而又年輕的數(shù)學(xué)分支。數(shù)論可分為初等數(shù)論（整數(shù)的整除、因子、倍數(shù)、素數(shù)、合數(shù)、最大公因子、最小公倍數(shù)、同余）解析數(shù)論、代數(shù)數(shù)論、幾何數(shù)論。組合數(shù)學(xué)主要研究和按照一定的規(guī)則來安排一些事物有關(guān)的問題，研究這種安排的存在性問題、構(gòu)造性問題以及最優(yōu)化問題（組合學(xué)問題的算法）。主要研究的內(nèi)容有：鴿巢原

33、理、排列與組合、二項式系數(shù)容斥原理及應(yīng)用，遞推關(guān)系和生成函數(shù)、特殊計數(shù)序列、二分圖中的匹配、組合設(shè)計。計數(shù)（Counting）是組合數(shù)學(xué)領(lǐng)域的重要課題，高中階段數(shù)學(xué)課程中的排列、組合及二項式定理等教學(xué)內(nèi)容，皆屬于計數(shù)這一范疇。計數(shù)技術(shù)廣泛應(yīng)用于事件概率的計算,以及計算機(jī)算法的復(fù)雜性研究。關(guān)于算法設(shè)計，歷史上已經(jīng)總結(jié)出了若干帶有普遍意義的方法和技術(shù)，包括動態(tài)規(guī)劃、回溯法、分支限界法、分治法、貪心法等。應(yīng)用是相當(dāng)廣泛的,比如旅行商問題、圖著色問題、整數(shù)規(guī)劃問題。由于計算機(jī)只能處理有限數(shù)和有限個數(shù)，無論什么問題都必須離散化后才能在計算機(jī)上進(jìn)行數(shù)值計算，所以離散數(shù)學(xué)顯得日益重要，而離散數(shù)學(xué)的基礎(chǔ)之一就

34、是數(shù)論和組合數(shù)學(xué)。計算機(jī)的計算模型、硬件體系結(jié)構(gòu)的設(shè)計與實現(xiàn)、代數(shù)編碼、軟件設(shè)計與實現(xiàn)、計算機(jī)通信與密碼學(xué)等都廣泛使用了整數(shù)數(shù)論及組合數(shù)學(xué)，因此使這兩門古老的學(xué)科又得到了廣泛的應(yīng)用。一般四年制本科的離散數(shù)學(xué)課不講這些內(nèi)容，即使講也只講整數(shù)哪一部分。13、學(xué)習(xí)離散數(shù)學(xué)，有哪些較好的中、英文參考書籍？答：離散數(shù)學(xué)的網(wǎng)上講授以劉玉珍，劉詠梅編著，武漢大學(xué)出版社2003年8月印刷的離散數(shù)學(xué)為主。其余的中英文參考書目為：離散數(shù)學(xué)，倪子偉，蔡經(jīng)球著，科學(xué)出版社；離散數(shù)學(xué)，陳莉、劉曉霞著，高等教育出版社；離散數(shù)學(xué)，孫吉貴、楊鳳杰、歐陽丹彤、李占山著，高等教育出版社；離散數(shù)學(xué)及其應(yīng)用，傅彥、顧小豐著，電子工業(yè)

35、出版社；離散數(shù)學(xué)，左孝凌著，上?？萍嘉墨I(xiàn)出版社；離散數(shù)學(xué)，方世昌著，西安電子科大出版社；離散數(shù)學(xué)導(dǎo)論，王元元、張桂蕓，科學(xué)出版社；計算機(jī)科學(xué)中的離散結(jié)構(gòu)，王元元、張桂蕓，機(jī)械工業(yè)出版社；離散數(shù)學(xué)及其應(yīng)用，美Kenneth H.Rosen 著，袁崇義、屈婉玲、王捍貧、劉田譯，機(jī)械工業(yè)出版社；離散數(shù)學(xué)導(dǎo)引，馬振華，清華大學(xué)出版社，Discrete Mathematical Structures（英文Fourth Edition），B Kolman, Robert C. Busby, Sharon Ross著，高等教育出版社；Discrete Mathematics and Its Applicat

36、ions (英文Fifth Edition), Kenneth H.Rosen著，機(jī)械工業(yè)出版社。14、介紹兩本有代表性的離散數(shù)學(xué)英文參考書籍。答：第一本是高教出版社2001年影印出版的Discrete Mathematical Structures (Fourth Edition) （B Kolman, Robert C. Busby, Sharon Ross著），中文名為離散數(shù)學(xué)結(jié)構(gòu)。這是一本比較經(jīng)典的書，值得一看。內(nèi)容由淺入深，整體思路清晰連貫，英文不是很難，對英文水平要求不高，熟悉了術(shù)語后就很容易看了，但是后面的習(xí)題都不簡單，鼓勵學(xué)生的創(chuàng)造性思維。也是我們以前這門課的教材。其最大的優(yōu)點

37、在于將理論和在計算科學(xué)中的應(yīng)用緊密結(jié)合起來，給出許多偽碼。本書適合于作為計算機(jī)及其相關(guān)專業(yè)離散數(shù)學(xué)課程教材，但更適合做參考書。本書不足之處在于相對于國內(nèi)許多同類教材，大部分內(nèi)容都比較簡單，不夠深入，對立志深造的學(xué)生是能滿足的。該書第一章介紹了關(guān)于離散數(shù)學(xué)的基本知識，包括集合、子集的概念和集合的操作運算，序數(shù)，整數(shù)的劃分，矩陣，數(shù)學(xué)結(jié)構(gòu)（構(gòu)造）等。第二章介紹邏輯及其相關(guān)的內(nèi)容，包括方法證明和數(shù)學(xué)歸納等。第三章介紹數(shù)論的有關(guān)內(nèi)容，包括排列與置換、聯(lián)合、鴿巢原理、事件概率、循環(huán)關(guān)系。第四章通過有向圖來講述關(guān)系的基本類型和基本原理。第五章介紹映射，包括一些典型的映射在計算機(jī)科學(xué)領(lǐng)域中的應(yīng)用。第六章介紹

38、偏序（次序關(guān)系），包括格與布爾代數(shù)。第七章介紹樹，包括有向樹與無向樹及其應(yīng)用。第八章主要講述圖論的知識以及通路問題與穿程問題。第九章介紹了半群與群的基本知識。第十章介紹有限自動機(jī)。最后一章介紹了有關(guān)的二進(jìn)制代碼的知識，包括二進(jìn)制信息的編碼及其錯誤校驗和解碼及其錯誤校驗。第二本是機(jī)械工業(yè)出版社2003年影印出版的Discrete Mathematics and Its Applications (英文Fifth Edition)（Kenneth H.Rosen著），中文名為離散數(shù)學(xué)及其應(yīng)用。這是一本寫得很好的書。它除了具有一般英文教材的特點這外：內(nèi)容由淺入深，思路清晰連貫，英文不難，對英文水平要

39、求不高，大量課后習(xí)題。還有下列特點：1）結(jié)構(gòu)靈活：本教材為靈活使用做了精心設(shè)計，各章對其前面內(nèi)容的依賴降到最??；2）大量實例：書中有700多個實例，用于闡明和應(yīng)用概念、定理；3）廣泛的應(yīng)用：本書涉及的應(yīng)用領(lǐng)域很廣，包括計算機(jī)科學(xué)、數(shù)據(jù)網(wǎng)絡(luò)、心理學(xué)、化學(xué)、 工程、語言學(xué)、生物學(xué)、商業(yè)和互聯(lián)網(wǎng)；4）豐富的歷史資料：本書以腳注的形式給出了60多位數(shù)學(xué)和計算機(jī)科學(xué)家的傳記，并配有照片；5）關(guān)鍵術(shù)語和結(jié)論：每一章后面都列出了本章的關(guān)鍵術(shù)語和結(jié)論；6）復(fù)習(xí)題、補(bǔ)充練習(xí)：每章最后都有一組復(fù)習(xí)題才一組豐富而多樣的補(bǔ)充練習(xí)；7）計算機(jī)課題：每一章后面還有一組計算機(jī)課題，把學(xué)生已經(jīng)學(xué)到的計算和離散數(shù)學(xué)的內(nèi)容結(jié)合在

40、一起。本書以介紹涉及計算機(jī)科學(xué)領(lǐng)域的離散數(shù)學(xué)知識為主，由淺入深地介紹離散數(shù)學(xué)的有關(guān)知識。要學(xué)好離散可以好好看這本書，行文優(yōu)美，通俗易懂，適于自學(xué)，既能學(xué)習(xí)離散數(shù)學(xué)知識，又能應(yīng)用和提高英文能力。該書不足之處是沒有很深入地介紹代數(shù)結(jié)構(gòu)：半群和群方面的知識。 該書內(nèi)容：第一章基礎(chǔ)知識：邏輯，證明方法，集合和函數(shù)；第二章基本知識：算法、整數(shù)數(shù)論和矩陣；第三章數(shù)學(xué)推理，歸納和遞歸；第四章計數(shù)；第五章離散概率論；第六章先進(jìn)的計數(shù)技術(shù)；第七章關(guān)系；第八章圖；第九章樹；第十章布爾代數(shù)；第十一章自動機(jī)理論。15、介紹一個學(xué)習(xí)離散數(shù)學(xué)的網(wǎng)上免費資源。答：這是天津師范大學(xué)計算機(jī)與信息工程學(xué)院副院長16、如何學(xué)習(xí)離散

41、數(shù)學(xué)？答：首先要明確的是，由于離散數(shù)學(xué)是一門數(shù)學(xué)課，且是由幾個數(shù)學(xué)分支綜合在一起的，內(nèi)容繁多，非常抽象，因此即使是數(shù)學(xué)系的學(xué)生學(xué)起來都會倍感困難，對計算科學(xué)專業(yè)的學(xué)生來說就更是如此。大家普遍反映這是大學(xué)四年最難學(xué)的一門課之一。但鑒于離散數(shù)學(xué)在計算科學(xué)中的重要性，這是一門必須牢牢掌握的課程。既然如此，在學(xué)習(xí)離散數(shù)學(xué)時，大家最應(yīng)該牢記的是唐詩“熟讀唐詩三百首，不會做詩也會吟?！睂W(xué)習(xí)過程是一個扎扎實實積累的過程，不能打馬虎眼。離散數(shù)學(xué)是理論性較強(qiáng)的學(xué)科，學(xué)習(xí)離散數(shù)學(xué)的關(guān)鍵是對離散數(shù)學(xué)（集合論、數(shù)理邏輯和圖論）有關(guān)基本概念的準(zhǔn)確掌握，對基本原理及基本運算的運用，并要多做練習(xí)。離散數(shù)學(xué)的特點是：1、知識

42、點集中，概念和定理多：離散數(shù)學(xué)是建立在大量概念之上的邏輯推理學(xué)科，概念的理解是我們學(xué)習(xí)這門學(xué)科的核心。不管哪本離散數(shù)學(xué)教材，都會在每一章節(jié)列出若干定義和定理，接著就是這些定義定理的直接應(yīng)用。掌握、理解和運用這些概念和定理是學(xué)好這門課的關(guān)鍵。要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的則是定理和性質(zhì)。2、方法性強(qiáng)：離散數(shù)學(xué)的特點是抽象思維能力的要求較高。通過對它的學(xué)習(xí)，能大大提高我們本身的邏輯推理能力、抽象思維能力和形式化思維能力，從而今后在學(xué)習(xí)任何一門計算機(jī)科學(xué)的專業(yè)主干課程時，都不會遇上任何思維理解上的困難。離散數(shù)學(xué)的證明題多，不同的題型會需要不同的證明方法（如直接證明法、反證法、歸納法、構(gòu)造

43、性證明法），同一個題也可能有幾種方法。但是離散數(shù)學(xué)證明題的方法性是很強(qiáng)的，如果知道一道題用什么方法講明，則很容易可以證出來，否則就會事倍功半。因此在平時的學(xué)習(xí)中，要勤于思考，對于同一個問題，盡可能多探討幾種證明方法，從而學(xué)會熟練運用這些證明方法。同時要善于總結(jié)，在學(xué)習(xí)離散數(shù)學(xué)的過程，對概念的理解是學(xué)習(xí)的重中之重。一般來說，由于這些概念（定義）非常抽象（學(xué)習(xí)線性代數(shù)時會有這樣的經(jīng)歷），初學(xué)者往往不能在腦海中建立起它們與現(xiàn)實世界中客觀事物的聯(lián)系。這往往是離散數(shù)學(xué)學(xué)習(xí)過程中初學(xué)者要面臨的第一個困難，他們覺得不容易進(jìn)入學(xué)習(xí)的狀態(tài)。因此一開始必須準(zhǔn)確、全面、完整地記住并理解所有的定義和定理。具體做法是在

44、進(jìn)行完一章的學(xué)習(xí)后，用專門的時間對該章包括的定義與定理實施強(qiáng)記。只有這樣才可能本課程的抽象能夠適應(yīng)，并為后續(xù)學(xué)習(xí)打下良好的基礎(chǔ)。學(xué)數(shù)學(xué)就要做數(shù)學(xué)，離散數(shù)學(xué)的學(xué)習(xí)也不例外。學(xué)習(xí)數(shù)學(xué)不僅限于學(xué)習(xí)數(shù)學(xué)知識，更重要的還在于學(xué)習(xí)數(shù)學(xué)思維方法。要做到這一點，學(xué)習(xí)者將要面臨的第二個困難是需要花費大量的時間做課后習(xí)題。但是切記離散數(shù)學(xué)的題目數(shù)量自然是無窮無盡的，但題目的種類卻很有限。尤其是在命題證明的過程中，最重要的是要掌握證明的思路和方法。解離散數(shù)學(xué)的題，方法是非常重要的，如果拿到一道題，立即能夠看出它所屬的類型及關(guān)聯(lián)的知識點，就不難選用正確的方法將其解決，反之則事倍功半。例如在命題邏輯部分，無非是這么幾種

45、題目：將自然語言表述的命題符號化，等價命題的相互轉(zhuǎn)化（包括化為主合取范式與主析取范式），以給出的若干命題為前提進(jìn)行推理和證明。相應(yīng)的對策也馬上就可以提出來。以推理題為例，主要是利用P、T規(guī)則，加上蘊(yùn)涵和等價公式表，由給定的前提出發(fā)進(jìn)行推演，或根據(jù)題目特點采用真值表法、CP規(guī)則和反證法。由此可見，在平常學(xué)習(xí)中，要善于總結(jié)和歸納，仔細(xì)體會題目類型和此類題目的解題套路。如此多作練習(xí)，則即使遇到比較陌生的題也可以較快地領(lǐng)悟其本質(zhì)，從而輕松解出。因此，只要肯下功夫，人人都能有扎實的基礎(chǔ)，擁有足夠的數(shù)學(xué)知識，特別是能大大提高本身的邏輯推理能力、抽象思維能力和形式化思維能力，從而今后在學(xué)習(xí)任何一門計算機(jī)科學(xué)

46、的專業(yè)主干課程時，都不會遇上任何思維理解上的困難。17、離散數(shù)學(xué)的考試題型有哪些？答：考試旨在測試學(xué)生對離散數(shù)學(xué)的基礎(chǔ)知識、基本方法的掌握情況，以及在解決具體問題時使用這些知識的能力。因此離散數(shù)學(xué)的考試題型可分為下列幾種類型：1、基礎(chǔ)題：主要涉及基本概念、基本理論、重要性質(zhì)和結(jié)論、公式及其簡單計算，目的是考查學(xué)生對它們的掌握，以及對它們的簡單運用，如填空題、選擇題、是非判斷題等等。2、定理和性質(zhì)應(yīng)用題：主要考查應(yīng)用概念、性質(zhì)、定理及主要結(jié)論進(jìn)行邏輯推理的能力。這些問題一般只涵蓋一個或二個知識點，如求范式、數(shù)理邏輯的推理題、證明一種關(guān)系是等價關(guān)系、證明一個代數(shù)結(jié)構(gòu)是一個群等等。它是離散數(shù)學(xué)學(xué)習(xí)和

47、考試中學(xué)生們普遍感覺困難的地方，主要體現(xiàn)了離散數(shù)學(xué)方法性強(qiáng)的特點。3、綜合題：就是內(nèi)容涵蓋若干個知識點的問題，它是學(xué)生感覺最困難的地方。解決這些問題往往需要將若干概念、性質(zhì)和定理融會貫通，如下列證明題“設(shè)<S，0，1>是一布爾代數(shù)，則關(guān)系=<a,b> | ab=a是S上的偏序關(guān)系”，它就將代數(shù)結(jié)構(gòu)中的布爾代數(shù)與二元關(guān)系的知識結(jié)合在一起。編寫者編寫試題時，往往把試題難度分為四個等級，即易、較易、較難、難，它們的比例分別為：15%、30%、45%、10%。18、在離散數(shù)學(xué)的證明題中，常用的證明方法是哪些？答：數(shù)學(xué)推理是學(xué)習(xí)數(shù)學(xué)中不可避免的。證明的過程往往表現(xiàn)為一系列的推理，

48、也就是把新的命題（論題）與已確定的有關(guān)命題和概念（論據(jù)）關(guān)聯(lián)起來，通過對它們的重新組織，運用一系列的推理形式而使新命題結(jié)論的真實性得以確立的過程。離散數(shù)學(xué)的證明題是非常之多的，但是題目的種類卻很有限，而且方法性是很強(qiáng)的。如果知道一道題用什么方法講明，則很容易可以證出來，否則就會事倍功半。所以在學(xué)習(xí)過程中，我們不能僅以看懂證明為目的，我們更應(yīng)該了解證明的思路。這樣我們才能在解決新問題時才不至于無法下手。在離散數(shù)學(xué)中證明問題常用的有以下方法： 1）直接證明法：2）反證法3）構(gòu)造法4）數(shù)學(xué)歸納法19、在離散數(shù)學(xué)的證明題中，直接證明法如何使用？答：直接證明法是最常見的一種證明方法，顧名思義是直接證明命

49、題的真實性，即由命題給出的條件，根據(jù)已知的定義、公理、定理，經(jīng)過一系列推理，最后得出結(jié)論。其過程可如下表示： H1H2HnC其中H1是某個已知條件，Hi(2im)或者是某個已知條件，或者是由已知條件和前面的中間結(jié)論按照定理或公理推導(dǎo)出來的中間結(jié)論，C是命題結(jié)論。直接證明法有兩種方式。一種方式是先從命題給出的條件出發(fā)，看看從已知條件按照定理或公理可以推出什么樣的中間結(jié)論，并且判斷這些中間結(jié)論中哪些與最后的結(jié)論有關(guān)，然后繼續(xù)向下推理，直到得出命題的結(jié)論。這種“由因?qū)Ч钡姆椒ㄍǔ７Q為綜合法。另一種方式則是從命題結(jié)論出發(fā)，看看從哪些條件可以按照定理或公理推出這個結(jié)論，并且判斷這些中間條件哪些與命題給

50、出的條件有聯(lián)系，然后繼續(xù)反向推導(dǎo)，直到到達(dá)命題給出的條件。將這個過程逆轉(zhuǎn)，就可得到證明的推理過程。這種“由果索因” 的方法通常稱為分析法。例1、PQ，QR，R，SP=>S問題解析：從已知條件可以看出，由前提（已知條件）QR，R，根據(jù)析取三段論可以得到中間結(jié)論Q；由Q和PQ根據(jù)否定律就可得到中間結(jié)論P；再由P和前提SP 根據(jù)析取三段論得到S，這就是命題結(jié)論。我們用綜合法得到了整個推理過程。證明：(1) R 前提(2) QR 前提(3) Q （1），（2）(4) PQ 前提(5) P （3），（4）(6) SP 前提(7) S （5），（6）例2、A，AB，AC，B(DC) => D問

51、題解析：顯然命題結(jié)論D與前提B(DC)有關(guān)，且是條件式的后件的前件，故如果能有中間結(jié)論B和C，就可依次根據(jù)肯定律和否定律得到D；中間結(jié)論B和C又和前提AB，AC有關(guān)，只要A成立，則根據(jù)肯定律就分別由A，AB和A，AC得出B和C。這樣我們就用分析法建立了整個推理過程。證明：（1） A 前提（2） AB 前提（3） B (1)，(2)（4） AC 前提（5） C (1)，(4)（6） B(DC) 前提（7） DC (3)，(6)（8） D (5)，(7)例3、證明：偶數(shù)階群中階為2 的元素的個數(shù)一定是奇數(shù)。問題解析：這主要是考察學(xué)生對群的元素的階的知識以及元素的階和逆元素的階的關(guān)系。由群的元素的階

52、的有關(guān)知識，任一個群中階為1的就只有單位元一個，階大于2的元素是成雙成對出現(xiàn)的，其余的元素就是階為2 的元素。故階大于2的元素有偶數(shù)個。由于這是一個偶數(shù)階群，而奇數(shù)加上一個偶數(shù)還是奇數(shù)，一個偶數(shù)減去一個奇數(shù)仍是奇數(shù)，故階為2 的元素一定是奇數(shù)。我們用綜合法得出了整個推理過程。證明：設(shè)<G,·>是偶數(shù)階群，則由于群的元素中階為1 的只有一個單位元，階大于2 的元素是偶數(shù)個，剩下的元素中都是階為2 的元素。故偶數(shù)階群中階為2 的元素一定是奇數(shù)個。例4、設(shè)群<G,*>除單位元外每個元素的階均為2，則<G,*>是交換群。問題解析：這主要是考察學(xué)生對交換律的

53、掌握。若<G,>是交換群，則關(guān)于*必須滿足交換律，即對任意a,bG，a*b=b*a，a和b的運算結(jié)果與運算順序無關(guān)。我們知道群的運算和逆元運算滿足這樣的性質(zhì)：(a*b)=b*a，a和b的運算順序有了變化。由已知條件，每個元素和它的逆元是同一的，即對任一aG，a-1=a。因此由(a*b)=b*a就可得a*b=b*a。這樣我們就用分析法得出了整個推理過程。證明：對任一aG，由已知可得a*a=e，即a-1=a。對任意a,bG，因為a*b=(a*b)-1=b-1*a-1=b*a，所以運算*滿足交換律。 從而G,*是交換群。不管是綜合法還是分析法，它們的邏輯依據(jù)是相同的，都是蘊(yùn)涵的傳遞性，只

54、是思考的順序相反。而且對一個問題，并不一定用一種思路就可以完全解決，更多的時候需要將兩種思路綜合在一起使用。例5、一次會議有20人參加，其中每個人都在其中有不下10個朋友。這20人圍成一圓桌入席。有沒有可能使任意相鄰而坐的兩個人都是朋友？為什么？ 問題解析：這主要是考察學(xué)生對判斷一個圖是否是哈密爾頓圖的充分條件的掌握。將每個人看成是頂點，兩個人若是朋友，則對應(yīng)的頂點是鄰接的。則原問題求解就可對這樣得到的無向圖進(jìn)行。原題的結(jié)論就可轉(zhuǎn)化為是否能找出一條哈密爾頓回路了。由已知條件，對應(yīng)的無向圖滿足哈密爾頓圖的某一個充分條件，故該無向圖是一個哈密爾頓圖，而哈密爾頓圖一定存在哈密爾頓回路。這樣我們既用了

55、分析方法又用了綜合方法得出了整個推理過程。證明：可以。將每個人對應(yīng)成相應(yīng)的頂點，若兩人是朋友，則對應(yīng)的兩個頂點間連上一條無向邊，作出一個簡單無向圖。由已知，圖中每個頂點的度數(shù)都大于等于10。即圖中任兩個不相鄰的頂點的度數(shù)大于等于20，即頂點數(shù)。故這個圖是一個哈密爾頓圖，從而存在哈密爾頓回路。任取一條哈密爾頓回路，按回路經(jīng)過的頂點的次序安排對應(yīng)的人的座位，就可滿足要求。20、在離散數(shù)學(xué)的證明題中，反證法如何使用？答：反證法是一種間接證法，也是在離散數(shù)學(xué)的證明中比較常用的方法。它先提出一個與命題結(jié)論相反的假設(shè)，然后從這個假設(shè)出發(fā)，經(jīng)過正確的推理，導(dǎo)致矛盾，否定命題結(jié)論相反的假設(shè)，從而達(dá)到肯定原命題

56、結(jié)論的一種方法。反證法可以分為歸謬反證法(結(jié)論的否定只有一種)與窮舉反證法(結(jié)論的否定不只一種)。用反證法證明一個命題的步驟，大體上分為：(1)反設(shè)；(2)歸謬；(3)結(jié)論。其過程可表示如下：CH1H2HnPP其中H1是某個已知條件，Hi(2im)或者是某個已知條件，或者是由已知條件和前面的中間結(jié)論按照定理或公理推導(dǎo)出來的中間結(jié)論，C是命題結(jié)論的否定。歸謬是反證法的關(guān)鍵，導(dǎo)出矛盾的過程雖然沒有固定的模式，但必須從結(jié)論的否定出發(fā)。反證法的邏輯基礎(chǔ)是形式邏輯的排中律，命題結(jié)論C和它的否定C中一個且只有一個為真，從而如果C為假，那么C必為真。這里的PP是一個永假式，導(dǎo)出的矛盾有如下幾種類型：與已知條

57、件矛盾；與已知的公理、定義、定理、公式矛盾；與結(jié)論的否定矛盾；自相矛盾。例1 、BD，(EF)D，E=>B問題解析：結(jié)論B的否定是B。由前提BD和B，根據(jù)析取三段論可得到D；由前提(EF)D和D根據(jù)否定律可得到(EF)；(EF)等價于EF；由化簡律可得E；這顯然與前提E矛盾。這樣我們就完成了用反證法證明的整個推理過程。證明：(1) B 附加前提(2) BD 前提 (3) D （1），（2）(4) (EF)D 前提(5) (EF) （3），（4）(6) EF （5）(7) E （6）(8) E 前提(9) EE （7），（8）反設(shè)是反證法的基礎(chǔ)。如果結(jié)論中含有：沒有、有、等于或不等于、大(小)于或不大(小)于、都是或不都是、至少有一個或一個也沒有、至少有n個或至多有(n一1)個、唯一或至少有兩個等等這樣的文字，往往就可以對結(jié)論進(jìn)行否定，采用反證法證明。例2、證明在元素不少于兩個的群中不存在零元。問題解析：命題結(jié)論中含有“不存在”，故它的否定是“存在”。命題結(jié)論的反設(shè)是：在元素不少于兩個的群中存在零元。現(xiàn)在要由零