離散數(shù)學(xué)是研究離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)模型的數(shù)學(xué).ppt

1,屈婉玲耿素云張立昂,2,前言,離散數(shù)學(xué)是研究離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)模型的數(shù)學(xué)分支的統(tǒng)稱.是計算機科學(xué)與技術(shù)專業(yè)的核心基礎(chǔ)課程.,“離散”和“連續(xù)”之間的對立與統(tǒng)一是數(shù)學(xué)發(fā)展的重要動力之一.古代數(shù)學(xué)主要討論整數(shù)等離散與離散化了的數(shù)量關(guān)系，因而，那時數(shù)學(xué)被看成是研究上述數(shù)量關(guān)系的科學(xué).但隨著數(shù)學(xué)理論的發(fā)展，處理離散數(shù)量關(guān)系的數(shù)學(xué)工具在刻畫和處理某類事務(wù)方面顯得無能為力，因此出現(xiàn)了處理連續(xù)數(shù)量關(guān)系的數(shù)學(xué)工具：微積分.,3,近代數(shù)學(xué)主要以研究連續(xù)數(shù)量關(guān)系及其數(shù)學(xué)結(jié)構(gòu)、數(shù)學(xué)模型，并取得了極其輝煌的成果，這一特征一直延續(xù)至今，仍在現(xiàn)代數(shù)學(xué)中占據(jù)支配地位（人們現(xiàn)在仍在學(xué)習(xí)微積分等經(jīng)典數(shù)學(xué)理論）.,4,然而，近半個世紀以來，計算機的飛速發(fā)展與廣泛應(yīng)用，極大地沖擊了現(xiàn)代數(shù)學(xué).由于計算機是一個離散結(jié)構(gòu)，它只能處理離散或離散化了的數(shù)量關(guān)系，因此，無論是計算機科學(xué)本身，還是與計算機科學(xué)極其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)領(lǐng)域，都面臨如何更有效地處理離散的對象和離散的數(shù)量關(guān)系，如何對離散結(jié)構(gòu)建立數(shù)學(xué)模型以及如何將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化，從而可由計算機來加以處理.,5,計算機科學(xué)以研究計算領(lǐng)域中的一些普遍規(guī)律為其基本任務(wù)，在此過程中，涉及和應(yīng)用了很多現(xiàn)代數(shù)學(xué)，所以需要以近代數(shù)學(xué)作為工具.離散數(shù)學(xué)的內(nèi)容一直隨著計算機科學(xué)的發(fā)展而不斷得到擴充與更新.同時，離散數(shù)學(xué)也促進了計算機技術(shù)和計算機科學(xué)的發(fā)展.在計算機發(fā)展初期，人們利用布爾代數(shù)理論研究開關(guān)電路，建立了一套完整的數(shù)理邏輯理論，對計算機邏輯設(shè)計起了很大作用.,于是，人們開始從新認識離散數(shù)量關(guān)系的研究意義，重新重視討論離散數(shù)量關(guān)系的數(shù)學(xué)分枝，并取得新的發(fā)展.,6,此外，在計算機科學(xué)中普遍采用離散數(shù)學(xué)中的基本概念、基本思想和方法.例如，集合論的概念和方法，抽象代數(shù)的概念和方法等，在計算機科學(xué)的各個領(lǐng)域隨處都能碰到.所有這些都使得離散數(shù)學(xué)在計算機科學(xué)中的地位和作用越來越重要，成了必不可少的工具.因此有人把離散數(shù)學(xué)稱為“計算機數(shù)學(xué)”.,7,離散數(shù)學(xué)的內(nèi)容涵蓋很廣，到目前為止，它包括的主要內(nèi)容有：集合論、數(shù)理邏輯、抽象代數(shù)、圖論、自動機理論等.它們廣泛應(yīng)用于計算機科學(xué)的研究中，也大量應(yīng)用于數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫理論等后續(xù)課程中.在物理、化學(xué)、生物等自然科學(xué)以及經(jīng)濟、教育等社會科學(xué)中，也正在獲得廣泛應(yīng)用，有人預(yù)計，未來社會將有越來越多的人學(xué)習(xí)離散數(shù)學(xué)，就像當今人們學(xué)習(xí)微積分一樣.,8,第一部分數(shù)理邏輯第一章命題邏輯的基本概念第二章命題邏輯等值演算第三章命題邏輯的推理理論第四章一階邏輯基本概念第五章一階邏輯等值演算與推理,第二部分集合論第六章集合代數(shù)第七章二元關(guān)系第八章函數(shù),第三部分代數(shù)結(jié)構(gòu)第九章代數(shù)系統(tǒng)第十章群與環(huán)第十一章格與布爾代數(shù),第四部分圖論第十四章圖的基本概念第十五章歐拉圖與哈密頓圖第十六章樹第十七章平面圖第十八章二分圖,主要內(nèi)容,9,主要內(nèi)容命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算與推理,第一部分數(shù)理邏輯,10,數(shù)理邏輯是用數(shù)學(xué)的方法來研究人類推理過程的一門數(shù)學(xué)學(xué)科.,其顯著特征是符號化和形式化，即把邏輯所涉及的“概念、判斷、推理”用符號來表示，用公理體系來刻劃,并基于符號串形式的演算來描述推理過程的一般規(guī)律.,又稱符號邏輯、現(xiàn)代邏輯.,11,第一章命題邏輯的基本概念,主要內(nèi)容命題與聯(lián)結(jié)詞命題及其分類聯(lián)結(jié)詞與復(fù)合命題命題公式及其賦值,12,命題與真值命題：判斷結(jié)果唯一的陳述句命題的真值：判斷的結(jié)果真值的取值：真與假真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題陳述句中的悖論，判斷結(jié)果不唯一確定的不是命題,1.1命題與聯(lián)結(jié)詞,13,例1下列句子中那些是命題？(1)是有理數(shù).(2)2+5=7.(3)x+5>3.(4)你去教室嗎？(5)這個蘋果真大呀！(6)請不要講話！(7)2050年元旦下大雪.(8)我說的這句話假.,假命題,命題概念,真命題,不是命題,不是命題,不是命題,不是命題,命題，但真值現(xiàn)在不知道,不是命題（悖論）,14,命題分類：簡單命題（也稱原子命題）與復(fù)合命題簡單命題符號化用小寫英文字母p,q,r,pi,qi,ri(i1)表示簡單命題用“1”表示真，用“0”表示假例如，令p：是有理數(shù)，則p的真值為0，q：2+5=7，則q的真值為1,命題分類,15,否定、合取、析取聯(lián)結(jié)詞,定義1.1設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作否定聯(lián)結(jié)詞.規(guī)定p為真當且僅當p為假.,可用下表來規(guī)定否定詞“”的意義:,16,定義1.2設(shè)p,q為兩個命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作pq，稱作合取聯(lián)結(jié)詞.規(guī)定pq為真當且僅當p與q同時為真.,可用下表來規(guī)定合取詞“”的意義：,17,定義1.3設(shè)p,q為兩個命題，復(fù)合命題“p或q”稱作p與q的析取式，記作pq，稱作析取聯(lián)結(jié)詞.規(guī)定pq為假當且僅當p與q同時為假.,可用下表來規(guī)定析取詞“”的意義：,18,例2將下列命題符號化.(1)吳穎既用功又聰明.(2)吳穎不僅用功而且聰明.(3)吳穎雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學(xué).,合取聯(lián)結(jié)詞的實例,19,解令p:吳穎用功,q:吳穎聰明(1)pq(2)pq(3)pq(4)設(shè)p:張輝是三好生,q:王麗是三好生pq(5)p:張輝與王麗是同學(xué)(1)(3)說明描述合取式的靈活性與多樣性(4)(5)要求分清“與”所聯(lián)結(jié)的成分,合取聯(lián)結(jié)詞的實例,20,例3將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)小元元只能拿一個蘋果或一個梨.(5)王小紅生于1975年或1976年.,析取聯(lián)結(jié)詞的實例,21,解(1)令p:2是素數(shù),q:4是素數(shù),pq(2)令p:2是素數(shù),q:3是素數(shù),pq(3)令p:4是素數(shù),q:6是素數(shù),pq(4)令p:小元元拿一個蘋果,q:小元元拿一個梨(pq)(pq)(5)p:王小紅生于1975年,q:王小紅生于1976年,(pq)(pq)或pq(1)(3)為相容或，即當p和q均真時，確認pq為真.在日常生活中，“或”在有的場合下不同于上述意義.,析取聯(lián)結(jié)詞的實例,22,例如“人固有一死，或重于泰山，或輕于鴻毛”.其中的“或”是排斥的，即當發(fā)現(xiàn)有人的死既重于泰山又輕于鴻毛時，上述論斷被認為假.這里的“或”用表示不合適.可用下表規(guī)定的新聯(lián)結(jié)詞“排斥或”表示之.,23,(4)(5)為排斥或,但是，像上述場合一樣的許多場合下，兩個析取命題事實上不可能同時為真，即上表的末行根本無需定義，這時用代替就沒有問題，并且能使語句的表示簡化.例如“a>0或a=0或a0a=0a0a=0a<0”.符號化時(5)可有兩種形式，而(4)則不能,24,蘊涵聯(lián)結(jié)詞,定義1.4設(shè)p,q為兩個命題，復(fù)合命題“如果p,則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件，q為蘊涵式的后件，稱作蘊涵聯(lián)結(jié)詞.規(guī)定：pq為假當且僅當p為真q為假.,可用下表來規(guī)定該蘊涵詞“”的意義：,25,(1)pq的邏輯關(guān)系：q為p的必要條件(2)“如果p,則q”有很多不同的表述方法：若p，就q只要p，就qp僅當q只有q才p除非q,才p或除非q，否則非p，(3)當p為假時，pq恒為真，稱為空證明(4)常出現(xiàn)的錯誤：不分充分與必要條件,26,例4設(shè)p：天冷，q：小王穿羽絨服，將下列命題符號化(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當天冷的時候.,蘊涵聯(lián)結(jié)詞的實例,pq,注意：pq與qp等值（真值相同）,pq,pq,qp,qp,pq,qp,qp,27,注意:上述規(guī)定的蘊涵詞稱為實質(zhì)蘊涵，因為它不要求pq中的p，q有什么關(guān)系，只要p，q為命題，pq就有意義.例如“如果2+2=5，那么雪是黑的”，就是一個有意義的命題，且據(jù)定義其真值為“真”.,28,定義1.5設(shè)p,q為兩個命題，復(fù)合命題“p當且僅當q”稱作p與q的等價式，記作pq，稱作等價聯(lián)結(jié)詞.規(guī)定pq為真當且僅當p與q同時為真或同時為假.pq的邏輯關(guān)系：p與q互為充分必要條件,等價聯(lián)結(jié)詞,可用下表來規(guī)定該雙向蘊涵詞“”的意義：,29,例5求下列復(fù)合命題的真值(1)2+24當且僅當3+36.(2)2+24當且僅當3是偶數(shù).(3)2+24當且僅當太陽從東方升起.(4)2+24當且僅當美國位于非洲.(5)函數(shù)f(x)在x0可導(dǎo)的充要條件是它在x0連續(xù).,1,0,1,0,0,30,本小節(jié)中p,q,r,均表示命題.,聯(lián)結(jié)詞集為,，p,pq,pq,pq,pq為基本復(fù)合命題.其中要特別注意理解pq的涵義.反復(fù)使用,中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題.設(shè)p:是無理數(shù)，q:3是奇數(shù)，r:蘋果是方的，s:太陽繞地球轉(zhuǎn)則復(fù)合命題(pq)(rs)p)是假命題.,小結(jié),聯(lián)結(jié)詞的運算順序：,同級按先出現(xiàn)者先運算.,31,1.2命題公式及其賦值,命題變項與合式公式命題變項合式公式合式公式的層次公式的賦值公式賦值真值表,32,命題變項與合式公式,命題常項：表示具體命題及表示常命題的統(tǒng)稱命題常項命題變項（命題變元）：以“真、假”或“1，0”為取值范圍的變元，它未指出符號所表示的具體命題.常項與變項均用p,q,r,pi,qi,ri,等表示.,定義1.6合式公式（簡稱公式）的遞歸定義：(1)單個命題變項和命題常項是合式公式,稱作原子命題公式(2)若A是合式公式，則(A)也是(3)若A,B是合式公式，則(AB),(AB),(AB),(AB)也是(4)只有有限次地應(yīng)用(1)(3)形成的符號串才是合式公式,約定公式最外層和不影響運算次序的括號可省去.,33,合式公式的層次,定義1.7(1)若公式A是單個命題變項，則稱A為0層公式.(2)稱A是n+1(n0)層公式是指下面情況之一：(a)A=B,B是n層公式；(b)A=BC,其中B,C分別為i層和j層公式，且n=max(i,j)；(c)A=BC,其中B,C的層次及n同(b)；(d)A=BC,其中B,C的層次及n同(b)；(e)A=BC,其中B,C的層次及n同(b).(3)若公式A的層次為k,則稱A為k層公式.例如公式A=p,B=p,C=pq,D=(pq)r,E=(pq)r)(rs)分別為0層，1層，2層，3層，4層公式.,34,定義1.8設(shè)p1,p2,pn是出現(xiàn)在公式A中的全部命題變項,給p1,p2,pn各指定一個真值,稱為對A的一個賦值或解釋.若使A為1,則稱這組值為A的成真賦值;若使A為0,則稱這組值為A的成假賦值.幾點說明：A中僅出現(xiàn)p1,p2,pn，給A賦值=12n是指p1=1,p2=2,pn=n,i=0或1,i之間不加標點符號A中僅出現(xiàn)p,q,r,給A賦值123是指p=1,q=2,r=3含n個命題變項的公式有2n個賦值.如000,010,101,110是(pq)r的成真賦值001,011,100,111是成假賦值.,公式賦值,35,定義1.9將命題公式A在所有賦值下取值的情況列成表,稱作A的真值表.構(gòu)造真值表的步驟:(1)找出公式中所含的全部命題變項p1,p2,pn(若無下角標則按字母順序排列),列出2n個全部賦值,從000開始,按二進制加法,每次加1,直至111為止.(2)按從低到高的順序?qū)懗龉降母鱾€層次.(3)對每個賦值依次計算各層次的真值,直到最后計算出公式的真值為止.,真值表,36,例6寫出下列公式的真值表,并求它們的成真賦值和成假賦值:(1)(pq)r(2)(qp)qp(3)(pq)q,真值表,37,(1)A=(pq)r,成真賦值:000,001,010,100,110;成假賦值:011,101,111,真值表1,38,(2)B(qp)qp,成真賦值:00,01,10,11;無成假賦值,真值表2,39,(3)C(pq)q的真值表,成假賦值:00,01,10,11;無成真賦值,真值表3,40,語句形式化要注意以下幾個方面：,要準確確定原子命題，并將其形式化.,要選用恰當?shù)穆?lián)結(jié)詞，尤其要善于識別自然語言中的聯(lián)結(jié)詞（有時它們被省略），否定詞的位置要放準確.,必要時可以進行改述，即改變原來的敘述方式，但要保證表達意思一致.,需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦可不省略.,要注意語句的形式化未必是唯一的.,用我們已有的符號語言，可以將許多自然語言語句形式化，下面我們用一些例子來說明，語句形式化須注意的地方，以及如何理解形式化了的語句.,41,（1）我和他既是兄弟又是同學(xué).令p：我和他是兄弟，q：我和他是同學(xué).,（3）狗急跳墻.令p：狗急了，q：狗跳墻.,（2）我和他之間至少有一個要去邊疆.令p：我去邊疆，q：他去邊疆.,例將下列語句形式化，并表示為命題公式：,表示為pq,表示為pq,表示為pq,42,（4）風(fēng)雨無阻，我去上學(xué).令p：天刮風(fēng)，q：天下雨，r：我去上學(xué).,（5）ABC與ABC全等的充要條件是ABC與ABC的三邊對應(yīng)相等.令p：ABC與ABC全等，q：ABC與ABC的三邊對應(yīng)相等.,還可表示為(pqr)(pqr)(pqr)(pqr).,表示為(pqr)(pqr)(pqr)(pqr),表示為pq,43,（1）pq（是偶數(shù)或是奇數(shù)）,（3）rsq（若是不等于2的質(zhì)數(shù)，則為奇數(shù)）,（2）prs（若是偶質(zhì)數(shù)，則=2）,（5）rqs（是質(zhì)數(shù)當且僅當是奇數(shù)或=2）,（4）(qs)r（若“是奇數(shù)與=2之一真”不能成立，則非質(zhì)數(shù)）,例：設(shè)p表示“是偶數(shù)”，q表示“是奇數(shù)”，r表示“是質(zhì)數(shù)”，s表示“=2”，那么，可如下理解各命題公式：,44,第一章習(xí)題課,主要內(nèi)容命題、真值、簡單命題與復(fù)合命題、命題符號化聯(lián)結(jié)詞,及復(fù)合命題符號化命題公式及層次真值表及應(yīng)用基本要求深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系,熟練地將命題符號化會求復(fù)合命題的真值深刻理解合式公式的概念熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值,45,作業(yè)習(xí)題一：1，2，4，8，9，10.,46,1.將下列命題符號化(1)豆沙包是由面粉和紅小豆做成的.(2)蘋果樹和梨樹都是落葉喬木.(3)王小紅或李大明是物理組成員.(4)王小紅或李大明中的一人是物理組成員.(5)由于交通阻塞，他遲到了.(6)如果交通不阻塞，他就不會遲到.(7)他沒遲到，所以交通沒阻塞.(8)除非交通阻塞，否則他不會遲到.(9)他遲到當且僅當交通阻塞.,練習(xí)1,47,提示：分清復(fù)合命題與簡單命題分清相容或與排斥或分清必要與充分條件及充分必要條件答案:(1)是簡單命題(2)是合取式(3)是析取式（相容或）(4)是析取式（排斥或）設(shè)p:交通阻塞，q:他遲到(5)pq,(6)pq或qp(7)qp或pq,(8)qp或pq(9)pq或pq可見(5)與(7)，(6)與(8)相同（等值）,練習(xí)1解答,48,2.設(shè)p:2是素數(shù)q:北京比天津人口多r:美國的首都是舊金山求下面命題的真值(1)(pq)r(2)(qr)(pr)(3)(qr)(pr)(4)(qp)(pr)(rq),0,練習(xí)2,1,0,0,49,3.用真值表判斷下面公式的類型(1)pr(qp)(2)(pq)(qp)r(3)(pq)(pr),練習(xí)3,50,練習(xí)3解答,(1)pr(qp),矛盾式,51,練習(xí)3解答,(2)(pq)(qp)r,永真式,52,練習(xí)3解答,(3)(pq)(pr),非永真式的可滿足式,53,習(xí)題一解答,1.是命題的為：（1）（2）（3）（6）（7）（10）（11）（12）（13）是簡單命題的為：（1）（2）（7）（10）（13）是真命題的為：（1）（2）（3）（10）（11）真值現(xiàn)在還不知道的為：（13），到2025年元旦該命題的真值就可判定，（7）的真值要視實際情況而定，如果劉紅與魏新確實是同學(xué)，則（7）為真命題，否則為假命題.2.（1）p:中國有四大發(fā)明（2）p:(7)P:劉紅與魏新是同學(xué),54,(10)P:（13）P：2025年元旦下雪.3.（1）（2）,55,56,