離散數學課程名稱離散數學

DiscreteMathematics

課程簡介離散數學，是現代數學的一個重要分支，計算機科學與技術一級學科的核心課程，是整個計算機學科的專業基礎課。離散數學是以研究離散量的結構和相互間的關系為主要目標，其研究對象一般地是有限個或可數個元素，因此它充分描述了計算機科學離散性的特點。離散數學是隨著計算機科學的發展而逐步建立的，它形成于七十年代初期，是一門新興的工具性學科。后續課程數據結構 操作系統編譯理論 算法分析系統結構 容錯判斷機器定理證明 數據庫原理人工智能 …………離散數學的發展18世紀以前,數學基本上是研究離散對象的數量和空間關系的科學。之后,因天文學,物理學的發展,如行星軌道,牛頓三大力學定律等研究,極大地推動了連續數學(以微積分,數學物理方程,實、復變函數論為代表)的發展。離散對象的研究則處于停滯狀態。20世紀30年代,圖靈提出計算機的理論模型——圖靈機。這種模型早于實際制造計算機十多年,現實的計算機的計算能力,本質上和圖靈機的計算能力一樣。由于在計算機內,機器字長總是有限的,它代表離散的數或其它離散對象，因此隨著計算機科學和技術的迅猛發展,離散數學就顯得重要。離散數學的內容數理邏輯：“證明”在計算科學的某些領域至關重要，構造一個證明和寫一個程序的思維過程在本質上是一樣的。組合分析：解決問題的一個重要方面就是計數或枚舉對象。離散結構：用來表示離散對象以及它們之間關系的抽象數學結構，包括：集合、排列、關系、樹、圖。算法化思維：許多問題都可以通過構造一個可以被程序實現的算法來解決。它的三個步驟是：構造（選擇合適的離散模型和操作步驟）、驗證（算法的正確性）、評估（時間和空間的復雜性）。應用和建模：在可以想到的任何研究領域都有離散數學的應用。計算科學、化學、植物學、動物學、語言學、地理、經濟學等，構造離散模型都是極其有用的解決問題的方法。為什么要學離散數學

計算機求解的基本模式是：

實際問題

數學建模

算法設計

編程實現

離散數學為數學建模打下知識基礎、為算法設計提供具體指導。離散數學結構實際上就是通用的抽象的模式的集合。告訴你各種模式的本質特征和它們之間的關系，以及選用它們的策略；告訴你哪些問題是可解的，哪些是當前在圖靈機模型上無（最優）解的，哪些是可以得到近似/較優解的。簡而言之，離散數學的作用就在于訓練運用離散結構作為問題的抽象模型、構造算法、解決問題的能力。離散數學的應用舉例關系型數據庫的設計（關系代數）表達式解析（樹）優化編譯器的構造（閉包）編譯技術、程序設計語言（代數結構）Lisp和Prolog、人工智能、自動推理、機器證明（數理邏輯）網絡路由算法（圖論）游戲中的人工智能算法（圖論、樹、博弈論）專家系統（集合論、數理邏輯—知識和推理規則的計算機表達）軟件工程—團隊開發—時間和分工的優化（圖論—網絡、劃分）(各種)算法的構造、正確性的證明和效率的評估（離散數學的各分支）由于離散數學的重要地位，因此通過本課程的教學，使計算機及應用專業的學生能夠掌握數理邏輯、集合論、近世代數與圖論的基本概念、基本定理、基本方法，并且培養學生具有一定的抽象思維能力和邏輯推理能力。同時為計算機及應用專業的其它重要后續課程（如數據結構、操作系統、編譯原理等課程）奠定比較堅實的基礎。

目的和任務學習要求本課程特點

定義+定理+例題學習要領

概念（正確）：必須掌握好離散數學中大量的概念判斷（準確）：根據概念對事物的屬性進行判斷推理（可靠）：根據多個判斷推出一個新的判斷

多做習題，完成作業

想的清楚，說的明白，寫的工整教材

左孝凌，李為鑒，劉永才編著．《離散數學》．上海：上海科學技術文獻出版社,1982參考教材耿素云，屈婉玲編著．離散數學(修訂版)．北京：高等教育出版社,2004耿素云，屈婉玲編著．離散數學學習指導與習題解析．北京：高等教育出版社,2005輔助教材

左孝凌，李為鑒，劉永才編著．《離散數學：理論·分析·題解》

．上海：上海科學技術文獻出版社,1982第一章

命題邏輯第二章

謂詞邏輯第四章函數第六章格和布爾代數第七章

圖論第五章

代數結構第一篇數理邏輯第二篇集合論

第三章集合與關系第四篇圖論第三篇代數系統教學內容第五篇應用第八章形式語言與自動機第九章糾錯碼初步教學內容集合論數理邏輯圖論代數結構數理邏輯簡介邏輯學是一門研究思維形式及思維規律的科學，也就是研究推理過程的規律的科學。邏輯規律就是客觀事物在人的主觀意識中的反映。邏輯學分為辯證邏輯與形式邏輯兩種，辯證邏輯是以辯證法認識論的世界觀為基礎的邏輯學，形式邏輯主要是對思維的形式結構和規律進行研究的類似于語法的一門工具性學科。思維的形式結構包括了概念、判斷和推理之間的結構和聯系，其中概念是思維的基本單位，通過概念對事物是否具有某種屬性進行肯定或否定的回答，這就是判斷；由一個或幾個判斷推出另一判斷的思維形式，就是推理。用數學方法來研究推理的規律稱為數理邏輯。這里所指的數學方法，就是引進一套符號體系的方法，在其中表達和研究推理的規律。

數理邏輯簡介通常認為數理邏輯是由萊布尼茲(Leibniz)創立的。數理邏輯的內容包括：

證明論、模型論、遞歸論、公理化集合論。數理邏輯的應用在形式語義學、程序設計方法學和軟件工程領域。在邏輯程序設計方面。在數據庫理論方面。在程序自動生成、自動轉換等的理論和技術研究中。在形式語言理論、自動機理論、可計算理論、計算復雜性理論等方面。在人工智能方面。數理邏輯簡介一個土耳其商人想找一個十分聰明的助手協助他經商，有兩人前來應聘，這個商人為了試試哪個更聰明些，就把兩個人帶進一間漆黑的屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現在，我把燈關掉，而且把帽子擺的位置弄亂，然后我們三個人每人摸一頂帽子戴在自己頭上，在我開燈后，請你們盡快說出自己頭上戴的帽子是什么顏色的。”說完后，商人將電燈關掉，然后三人都摸了一頂帽子戴在頭上，同時商人將余下的兩頂帽子藏了起來，接著把燈打開。這時，那兩個應試者看到商人頭上戴的是一頂紅帽子，過了一會兒，其中一個人便喊道：“我戴的是黑帽子”。

請問這個人說得對嗎？他是怎么推導出來的呢？

《土耳其商人和帽子》答案：首先5頂帽子去掉兩頂，并且剩下的已知有一頂是紅色（商人戴），那么這兩個人中必有一人戴黑帽子。

情況1：被應聘人如果看到另外的人戴紅帽子，則第一時間可斷定自己是黑帽子。

情況2：被應聘人如果看到另外的人戴黑帽子，則無法立刻判斷自己戴的是黑是紅，但對方也沒有馬上回答，很明顯是2人都戴黑帽子。由于被應聘者比另一個聰明，所以先想到了。數理邏輯簡介前提結論推理（規則）集合論(settheroy)概述20世紀數學中最為深刻的活動，是關于數學基礎的探討。這不僅涉及到數學的本性，也涉及到演繹數學的正確性。數學中若干悖論的發現，引發了數學史上的第三次危機，這種悖論在集合論中尤為突出。集合論最初是一門研究數學基礎的學科，它從一個比“數”更簡單的概念----集合出發，定義數及其運算，進而發展到整個數學領域，在這方面它取得了極大的成功。集合論的起源可以追溯到19世紀末期。1874年，29歲的德國數學家康托爾(GeorgCantor)在“數學雜志”發表了關于無窮集合論的第一篇革命性文章，從1874年至1884年間，Cantor的系列有關集合的文章，奠定了集合論的基礎。集合論概述康托爾開創的集合論被稱為樸素集合論，因為他沒有對集合論作完整的形式的刻畫，從而導致了理論的不一致(產生了悖論)。在集合論的若干悖論中，最通俗易懂的是Russell(羅素)的理發師悖論：一個鄉村理發師，自夸本村無人可與相比，宣稱他當然不給自己刮臉的人刮臉，但卻給本村所有自己不刮臉的人刮臉。一天他發生了疑問，他是否應當給自己刮臉。

集合論概述集合不僅可以用來表示數及其運算，更可以用于非數值信息的表示和處理，如數據的增加、刪除、修改、排序，以及數據間關系的描述，有些很難用傳統的數值計算來處理，但可以用集合運算來處理。因此，集合論在程序語言、數據結構、編譯原理、數據庫與知識庫、形式語言和人工智能等領域中都得到了廣泛的應用，并且還得到了發展，如Zadeh(扎德)的模糊集理論和Pawlak的粗糙集理論。代數系統近世代數，……，是關于運算的學說，是關于運算規則的學說，但它不把自己局限在研究數的運算性質上，而是企圖研究一般性元素的運算性質。 ——Ｍ.Klein數學之所以重要，其中心原因在于它所提供的數學系統的豐富多彩；此外的原因是，數學給出了一個系統，以便于使用這些模型對物理現實和技術領域提出問題，回答問題，并且也就探索了模型的行為。 ——R.C.Buck&E.F.Buck代數系統--具有運算的集合--是抽象代數研究的主要對象。圖論圖論是離散數學的重要組成部分，是近代應用數學的重要分支。1736年是圖論歷史元年，因為在這一年瑞士數學家歐拉(Euler)發表了圖論的首篇論文——《哥尼斯堡七橋問題無解》，所以人們普遍認為歐拉是圖論的創始人。1936年，匈牙利數學家寇尼格（Konig）出版了圖論的第一部專著《有限圖與無限圖理論》，這是圖論發展史上的重要的里程碑，它標志著圖論將進入突飛猛進發展的新階段。計算機科學的發展為圖論的發展提供了計算工具。現代科學技術的發展需要借助圖論來描述和解決各類課題中的各種關系，從而推動科學技術不斷地攀登新的高峰。作為描述事務之間關系的手段或稱工具，圖論在許多領域，諸如，計算機科學、物理學、化學、運籌學、信息論、控制論、網絡通訊、社會科學以及經濟管理、軍事、國防、工農業生產等方面都得到廣泛的應用，也正是因為在眾多方面的應用中，圖論自身才得到了非常迅速的發展。離散數學與計算機的關系

第