離散數(shù)學(xué)概述

離散數(shù)學(xué)課程名稱離散數(shù)學(xué)

DiscreteMathematics

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

計(jì)算機(jī)求解的基本模式是：

實(shí)際問題

數(shù)學(xué)建模

算法設(shè)計(jì)

編程實(shí)現(xiàn)

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

目的和任務(wù)學(xué)習(xí)要求本課程特點(diǎn)

定義+定理+例題學(xué)習(xí)要領(lǐng)

概念（正確）：必須掌握好離散數(shù)學(xué)中大量的概念判斷（準(zhǔn)確）：根據(jù)概念對(duì)事物的屬性進(jìn)行判斷推理（可靠）：根據(jù)多個(gè)判斷推出一個(gè)新的判斷

多做習(xí)題，完成作業(yè)

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

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

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

．上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版社,1982第一章

命題邏輯第二章

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

圖論第五章

代數(shù)結(jié)構(gòu)第一篇數(shù)理邏輯第二篇集合論

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

數(shù)理邏輯簡(jiǎn)介通常認(rèn)為數(shù)理邏輯是由萊布尼茲(Leibniz)創(chuàng)立的。數(shù)理邏輯的內(nèi)容包括：

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

請(qǐng)問這個(gè)人說得對(duì)嗎？他是怎么推導(dǎo)出來的呢？

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

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

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

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

第