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

屈婉玲耿素云張立昂1屈婉玲耿素云張立昂1前言

離散數(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é)工具：微積分.2前言離散數(shù)學(xué)是研

近代數(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é)理論）.3近代數(shù)學(xué)主要以研究連續(xù)數(shù)量關(guān)系及其數(shù)學(xué)結(jié)構(gòu)、數(shù)學(xué)模型，

然而，近半個世紀(jì)以來，計算機的飛速發(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é)模型離散化，從而可由計算機來加以處理.4然而，近半個世紀(jì)以來，計算機的飛速發(fā)展與廣泛應(yīng)用，極大計算機科學(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è)計起了很大作用.

于是，人們開始從新認(rèn)識離散數(shù)量關(guān)系的研究意義，重新重視討論離散數(shù)量關(guān)系的數(shù)學(xué)分枝，并取得新的發(fā)展.5計算機科學(xué)以研究計算領(lǐng)域中的一些普遍規(guī)律為其基本任務(wù)，在

此外，在計算機科學(xué)中普遍采用離散數(shù)學(xué)中的基本概念、基本思想和方法.例如，集合論的概念和方法，抽象代數(shù)的概念和方法等，在計算機科學(xué)的各個領(lǐng)域隨處都能碰到.所有這些都使得離散數(shù)學(xué)在計算機科學(xué)中的地位和作用越來越重要，成了必不可少的工具.因此有人把離散數(shù)學(xué)稱為“計算機數(shù)學(xué)”.6此外，在計算機科學(xué)中普遍采用離散數(shù)學(xué)中的基本概念、基本

離散數(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é)，就像當(dāng)今人們學(xué)習(xí)微積分一樣.7離散數(shù)學(xué)的內(nèi)容涵蓋很廣，到目前為止，它包括的主要內(nèi)容有第一部分

數(shù)理邏輯

第一章命題邏輯的基本概念第二章命題邏輯等值演算第三章命題邏輯的推理理論第四章一階邏輯基本概念第五章一階邏輯等值演算與推理第二部分集合論第六章集合代數(shù)第七章二元關(guān)系第八章函數(shù)第三部分

代數(shù)結(jié)構(gòu)

第九章代數(shù)系統(tǒng)第十章群與環(huán)第十一章格與布爾代數(shù)第四部分

圖論第十四章圖的基本概念第十五章歐拉圖與哈密頓圖第十六章樹

第十七章平面圖第十八章二分圖主要內(nèi)容8第一部分?jǐn)?shù)理邏輯第主要內(nèi)容命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算與推理第一部分?jǐn)?shù)理邏輯9主要內(nèi)容第一部分?jǐn)?shù)理邏輯9數(shù)理邏輯是用數(shù)學(xué)的方法來研究人類推理過程的一門數(shù)學(xué)學(xué)科.

其顯著特征是符號化和形式化，即把邏輯所涉及的“概念、判斷、推理”用符號來表示，用公理體系來刻劃,并基于符號串形式的演算來描述推理過程的一般規(guī)律.又稱符號邏輯、現(xiàn)代邏輯.

10數(shù)理邏輯其顯著特征是符號化和形式化，即把邏輯所涉及的“第一章命題邏輯的基本概念主要內(nèi)容命題與聯(lián)結(jié)詞命題及其分類聯(lián)結(jié)詞與復(fù)合命題命題公式及其賦值11第一章命題邏輯的基本概念主要內(nèi)容11命題與真值命題：判斷結(jié)果唯一的陳述句命題的真值：判斷的結(jié)果真值的取值：真與假真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題陳述句中的悖論，判斷結(jié)果不唯一確定的不是命題

1.1命題與聯(lián)結(jié)詞12命題與真值1.1命題與聯(lián)結(jié)詞12例1

下列句子中那些是命題？(1)是有理數(shù).(2)2+5=7.(3)x+5>3.(4)你去教室嗎？(5)這個蘋果真大呀！(6)請不要講話！(7)2050年元旦下大雪.(8)

我說的這句話假.

假命題命題概念

真命題不是命題不是命題不是命題不是命題命題，但真值現(xiàn)在不知道不是命題（悖論）13例1下列句子中那些是命題？假命題命題概念真命題不是命題分類：簡單命題（也稱原子命題）與復(fù)合命題簡單命題符號化用小寫英文字母p,q,r,…,pi,qi,ri(i1)表示簡單命題用“1”表示真，用“0”表示假例如，令p：是有理數(shù)，則p的真值為0，q：2+5=7，則q的真值為1

命題分類14命題分類：簡單命題（也稱原子命題）與復(fù)合命題命題分類14否定、合取、析取聯(lián)結(jié)詞定義1.1設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作否定聯(lián)結(jié)詞.規(guī)定p為真當(dāng)且僅當(dāng)p為假.可用下表來規(guī)定否定詞“┐”的意義:

p

┐p011015否定、合取、析取聯(lián)結(jié)詞定義1.1設(shè)p為命題，復(fù)合命題“非定義1.2設(shè)p,q為兩個命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞.規(guī)定p∧q為真當(dāng)且僅當(dāng)p與q同時為真.可用下表來規(guī)定合取詞“∧”的意義：pq

p∧q00110101000116定義1.2設(shè)p,q為兩個命題，復(fù)合命題“p并且q”(或“p定義1.3設(shè)p,q為兩個命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞.規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時為假.可用下表來規(guī)定析取詞“∨”的意義：pq

p∨q00110101011117定義1.3設(shè)p,q為兩個命題，復(fù)合命題“p或q”稱作p與例2

將下列命題符號化.(1)吳穎既用功又聰明.(2)吳穎不僅用功而且聰明.(3)吳穎雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學(xué).合取聯(lián)結(jié)詞的實例18例2將下列命題符號化.合取聯(lián)結(jié)詞的實例18解令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é)詞的實例19解令p:吳穎用功,q:吳穎聰明合取聯(lián)結(jié)詞的實例19例3將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)小元元只能拿一個蘋果或一個梨.(5)王小紅生于1975年或1976年.析取聯(lián)結(jié)詞的實例20例3將下列命題符號化析取聯(lián)結(jié)詞的實例20解(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)為相容或，即當(dāng)p和q均真時，確認(rèn)p∨q為真.在日常生活中，“或”在有的場合下不同于上述意義.析取聯(lián)結(jié)詞的實例21解析取聯(lián)結(jié)詞的實例21例如“人固有一死，或重于泰山，或輕于鴻毛”.其中的“或”是排斥的，即當(dāng)發(fā)現(xiàn)有人的死既重于泰山又輕于鴻毛時，上述論斷被認(rèn)為假.這里的“或”用∨表示不合適.可用下表規(guī)定的新聯(lián)結(jié)詞“排斥或”∨表示之.pq

P

q001101010110∨22例如“人固有一死，或重于泰山，或輕于鴻毛”.其中的“或”是(4)—(5)為排斥或,但是，像上述場合一樣的許多場合下，兩個析取命題事實上不可能同時為真，即上表的末行根本無需定義，這時用∨代替∨就沒有問題，并且能使語句的表示簡化.例如“a>0或a=0或a<0”可表示為“a>0∨a=0∨a<0”，而不必多此一舉地表示為“a>0∨a=0∨a<0”.符號化時(5)可有兩種形式，而(4)則不能23(4)—(5)為排斥或,但是，像上述場合一樣的許多場合下，蘊涵聯(lián)結(jié)詞定義1.4設(shè)p,q為兩個命題，復(fù)合命題“如果p,則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件，q為蘊涵式的后件，稱作蘊涵聯(lián)結(jié)詞.規(guī)定：pq為假當(dāng)且僅當(dāng)p為真q為假.可用下表來規(guī)定該蘊涵詞“→

”的意義：p

q

p

→q00110101110124蘊涵聯(lián)結(jié)詞定義1.4設(shè)p,q為兩個命題，復(fù)合命題“如果p(1)pq的邏輯關(guān)系：q為p的必要條件(2)“如果p,則q”有很多不同的表述方法：若p，就q只要p，就qp僅當(dāng)q只有q才p除非q,才p或除非q，否則非p，…．(3)當(dāng)p為假時，pq恒為真，稱為空證明(4)常出現(xiàn)的錯誤：不分充分與必要條件25(1)pq的邏輯關(guān)系：q為p的必要條件25例4設(shè)p：天冷，q：小王穿羽絨服，將下列命題符號化(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時候.蘊涵聯(lián)結(jié)詞的實例pq注意：pq與qp等值（真值相同）pqpqqpqppqqpqp26例4設(shè)p：天冷，q：小王穿羽絨服，將下列命題符號化蘊涵注意:上述規(guī)定的蘊涵詞稱為實質(zhì)蘊涵，因為它不要求p→q中的p，q有什么關(guān)系，只要p，q為命題，p→q就有意義.例如“如果2+2=5，那么雪是黑的”，就是一個有意義的命題，且據(jù)定義其真值為“真”.27注意:上述規(guī)定的蘊涵詞稱為實質(zhì)蘊涵，因為它不要求p→q中的定義1.5設(shè)p,q為兩個命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價式，記作pq，稱作等價聯(lián)結(jié)詞.規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時為真或同時為假.pq的邏輯關(guān)系：p與q互為充分必要條件等價聯(lián)結(jié)詞可用下表來規(guī)定該雙向蘊涵詞“”的意義：pqp

q00110101100128定義1.5設(shè)p,q為兩個命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”例5求下列復(fù)合命題的真值(1)2+2＝4當(dāng)且僅當(dāng)3+3＝6.(2)2+2＝4當(dāng)且僅當(dāng)3是偶數(shù).(3)2+2＝4當(dāng)且僅當(dāng)太陽從東方升起.(4)2+2＝4當(dāng)且僅當(dāng)美國位于非洲.(5)函數(shù)f(x)在x0可導(dǎo)的充要條件是它在x0連續(xù).1010029例5求下列復(fù)合命題的真值1010029本小節(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)者先運算.30本小節(jié)中p,q,r,…均表示命題.聯(lián)結(jié)詞集為{,1.2命題公式及其賦值命題變項與合式公式命題變項合式公式合式公式的層次公式的賦值公式賦值真值表311.2命題公式及其賦值命題變項與合式公式31命題變項與合式公式

命題常項：表示具體命題及表示常命題的統(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)形成的符號串才是合式公式約定公式最外層和不影響運算次序的括號可省去.32命題變項與合式公式命題常項：表示具體命題及表示常命題的統(tǒng)稱合式公式的層次定義1.7(1)若公式A是單個命題變項，則稱A為0層公式.(2)稱A是n+1(n≥0)層公式是指下面情況之一：(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層公式.33合式公式的層次定義1.733定義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賦值=12…n是指p1=1,p2=2,…,pn=n,i=0或1,i之間不加標(biāo)點符號

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是成假賦值.公式賦值34定義1.8設(shè)p1,p2,…,pn是出現(xiàn)在公式A中定義1.9

將命題公式A在所有賦值下取值的情況列成表,稱作A的真值表.構(gòu)造真值表的步驟:(1)找出公式中所含的全部命題變項p1,p2,…,pn(若無下角標(biāo)則按字母順序排列),列出2n個全部賦值,從000開始,按二進制加法,每次加1,直至111為止.

(2)按從低到高的順序?qū)懗龉降母鱾€層次.(3)對每個賦值依次計算各層次的真值,直到最后計算出公式的真值為止.真值表35定義1.9將命題公式A在所有賦值下取值的情況列成表,稱例6

寫出下列公式的真值表,并求它們的成真賦值和成假賦值:(1)(pq)r(2)(qp)qp(3)(pq)q真值表36例6寫出下列公式的真值表,并求它們的成真賦值和成假真值表(1)A=(pq)r成真賦值:000,001,010,100,110;成假賦值:011,101,111

pqrpq

r

(pq)r000001010011100101110111001111111010101011101010真值表137(1)A=(pq)r成真賦值:000,001(2)B＝(qp)qp成真賦值:00,01,10,11;無成假賦值p

q

qp(qp)q(qp)qp00011011101100011111真值表238(2)B＝(qp)qp成真賦值:00,01,10,(3)C＝(pq)q的真值表成假賦值:00,01,10,11;無成真賦值p

q

ppq(pq)(pq)q000110111100110100100000真值表339(3)C＝(pq)q的真值表成假賦值:00,0語句形式化要注意以下幾個方面：

①

要準(zhǔn)確確定原子命題，并將其形式化.

②

要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識別自然語言中的聯(lián)結(jié)詞（有時它們被省略），否定詞的位置要放準(zhǔn)確.

③

必要時可以進行改述，即改變原來的敘述方式，但要保證表達意思一致.④

需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦可不省略.⑤要注意語句的形式化未必是唯一的.

用我們已有的符號語言，可以將許多自然語言語句形式化，下面我們用一些例子來說明，語句形式化須注意的地方，以及如何理解形式化了的語句.40語句形式化要注意以下幾個方面：①要準(zhǔn)確確定原子命題，（1）我和他既是兄弟又是同學(xué).令p：我和他是兄弟，q：我和他是同學(xué).（3）狗急跳墻.令p：狗急了，q：狗跳墻.（2）我和他之間至少有一個要去邊疆.令p：我去邊疆，q：他去邊疆.例將下列語句形式化，并表示為命題公式：表示為p∧q表示為p∨q表示為p→q41（1）我和他既是兄弟又是同學(xué).（3）狗急跳墻.（2）我和他之（4）風(fēng)雨無阻，我去上學(xué).令p：天刮風(fēng)，q：天下雨，r：我去上學(xué).（5）△ABC與△A′B′C′

全等的充要條件是

△ABC與△A′B′C′的三邊對應(yīng)相等.令p：△ABC與△A′B′C′

全等，

q：△ABC與△A′B′C′的三邊對應(yīng)相等.還可表示為(p∧q∧r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r).表示為(p∧q→r)∧(p∧┐q→r)∧(┐p∧q→r)∧(┐p∧┐q→r),表示為pq42（4）風(fēng)雨無阻，我去上學(xué).（5）△ABC與△A′B′C′全（1）p∨q（是偶數(shù)或是奇數(shù)）（3）r∧┐s→q（若是不等于2的質(zhì)數(shù)，則為奇數(shù)）（2）p∧r→s（若是偶質(zhì)數(shù)，則=2）（5）rq∨s（是質(zhì)數(shù)當(dāng)且僅當(dāng)是奇數(shù)或=2）（4）┐(q∨s)→┐r（若“是奇數(shù)與=2之一真”不能成立，則非質(zhì)數(shù)）例：設(shè)p表示“是偶數(shù)”，q表示“是奇數(shù)”，r表示“是質(zhì)數(shù)”，s表示“=2”，那么，可如下理解各命題公式：43（1）p∨q（3）r∧┐s→q（2）p∧r→s（5）rq∨第一章習(xí)題課主要內(nèi)容命題、真值、簡單命題與復(fù)合命題、命題符號化聯(lián)結(jié)詞,,,,及復(fù)合命題符號化命題公式及層次真值表及應(yīng)用基本要求深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系,熟練地將命題符號化會求復(fù)合命題的真值深刻理解合式公式的概念熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值44第一章習(xí)題課主要內(nèi)容44作業(yè)習(xí)題一：1，2，4，8，9，10.45作業(yè)451.將下列命題符號化(1)豆沙包是由面粉和紅小豆做成的.(2)蘋果樹和梨樹都是落葉喬木.(3)王小紅或李大明是物理組成員.(4)王小紅或李大明中的一人是物理組成員.(5)由于交通阻塞，他遲到了.(6)如果交通不阻塞，他就不會遲到.(7)他沒遲到，所以交通沒阻塞.(8)除非交通阻塞，否則他不會遲到.(9)他遲到當(dāng)且僅當(dāng)交通阻塞.練習(xí)1461.將下列命題符號化練習(xí)146提示：分清復(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解答47提示：練習(xí)1解答472.設(shè)p:2是素數(shù)q:北京比天津人口多r:美國的首都是舊金山求下面命題的真值

(1)(pq)r(2)(qr)(pr)(3)(qr)(pr)(4)(qp)((pr)(rq))0練習(xí)2100482.設(shè)p:2是素數(shù)0練習(xí)2100483.用真值表判斷下面公式的類型

(1)pr(qp)(2)((pq)(qp))r(3)(pq)(pr)練習(xí)3493.用真值表判斷下面公式的類型練習(xí)349練習(xí)3解答(1)pr(qp)

矛盾式pqrqp

(qp)

pr(qp)00000101001110010111011111001111001100000000000050練習(xí)3解答(1)pr(qp)矛盾式pq練習(xí)3解答(2)((pq)(qp))r

永真式111111111111001111110011000001010011100101110111((pq)(qp))rqp

pq

pqr51練習(xí)3解答(2)((pq)(qp))r永練習(xí)3解答(3)(pq)(pr)非永真式的可滿足式pqrpq

pr

(pq)(pr)00000101001110010111011111110011111101011111100152練習(xí)3解答(3)(pq)(pr)非永真式的可滿足式習(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é)53習(xí)題一解答1.是命題的為：（1）（2）（3）（6）（7）（1(10)P:（13）P：2025年元旦下雪.3.（1）（2）54(10)P:55555656屈婉玲耿素云張立昂57屈婉玲耿素云張立昂1前言

離散數(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é)工具：微積分.58前言離散數(shù)學(xué)是研

近代數(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é)理論）.59近代數(shù)學(xué)主要以研究連續(xù)數(shù)量關(guān)系及其數(shù)學(xué)結(jié)構(gòu)、數(shù)學(xué)模型，

然而，近半個世紀(jì)以來，計算機的飛速發(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é)模型離散化，從而可由計算機來加以處理.60然而，近半個世紀(jì)以來，計算機的飛速發(fā)展與廣泛應(yīng)用，極大計算機科學(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è)計起了很大作用.

于是，人們開始從新認(rèn)識離散數(shù)量關(guān)系的研究意義，重新重視討論離散數(shù)量關(guān)系的數(shù)學(xué)分枝，并取得新的發(fā)展.61計算機科學(xué)以研究計算領(lǐng)域中的一些普遍規(guī)律為其基本任務(wù)，在

此外，在計算機科學(xué)中普遍采用離散數(shù)學(xué)中的基本概念、基本思想和方法.例如，集合論的概念和方法，抽象代數(shù)的概念和方法等，在計算機科學(xué)的各個領(lǐng)域隨處都能碰到.所有這些都使得離散數(shù)學(xué)在計算機科學(xué)中的地位和作用越來越重要，成了必不可少的工具.因此有人把離散數(shù)學(xué)稱為“計算機數(shù)學(xué)”.62此外，在計算機科學(xué)中普遍采用離散數(shù)學(xué)中的基本概念、基本

離散數(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é)，就像當(dāng)今人們學(xué)習(xí)微積分一樣.63離散數(shù)學(xué)的內(nèi)容涵蓋很廣，到目前為止，它包括的主要內(nèi)容有第一部分

數(shù)理邏輯

第一章命題邏輯的基本概念第二章命題邏輯等值演算第三章命題邏輯的推理理論第四章一階邏輯基本概念第五章一階邏輯等值演算與推理第二部分集合論第六章集合代數(shù)第七章二元關(guān)系第八章函數(shù)第三部分

代數(shù)結(jié)構(gòu)

第九章代數(shù)系統(tǒng)第十章群與環(huán)第十一章格與布爾代數(shù)第四部分

圖論第十四章圖的基本概念第十五章歐拉圖與哈密頓圖第十六章樹

第十七章平面圖第十八章二分圖主要內(nèi)容64第一部分?jǐn)?shù)理邏輯第主要內(nèi)容命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算與推理第一部分?jǐn)?shù)理邏輯65主要內(nèi)容第一部分?jǐn)?shù)理邏輯9數(shù)理邏輯是用數(shù)學(xué)的方法來研究人類推理過程的一門數(shù)學(xué)學(xué)科.

其顯著特征是符號化和形式化，即把邏輯所涉及的“概念、判斷、推理”用符號來表示，用公理體系來刻劃,并基于符號串形式的演算來描述推理過程的一般規(guī)律.又稱符號邏輯、現(xiàn)代邏輯.

66數(shù)理邏輯其顯著特征是符號化和形式化，即把邏輯所涉及的“第一章命題邏輯的基本概念主要內(nèi)容命題與聯(lián)結(jié)詞命題及其分類聯(lián)結(jié)詞與復(fù)合命題命題公式及其賦值67第一章命題邏輯的基本概念主要內(nèi)容11命題與真值命題：判斷結(jié)果唯一的陳述句命題的真值：判斷的結(jié)果真值的取值：真與假真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題陳述句中的悖論，判斷結(jié)果不唯一確定的不是命題

1.1命題與聯(lián)結(jié)詞68命題與真值1.1命題與聯(lián)結(jié)詞12例1

下列句子中那些是命題？(1)是有理數(shù).(2)2+5=7.(3)x+5>3.(4)你去教室嗎？(5)這個蘋果真大呀！(6)請不要講話！(7)2050年元旦下大雪.(8)

我說的這句話假.

假命題命題概念

真命題不是命題不是命題不是命題不是命題命題，但真值現(xiàn)在不知道不是命題（悖論）69例1下列句子中那些是命題？假命題命題概念真命題不是命題分類：簡單命題（也稱原子命題）與復(fù)合命題簡單命題符號化用小寫英文字母p,q,r,…,pi,qi,ri(i1)表示簡單命題用“1”表示真，用“0”表示假例如，令p：是有理數(shù)，則p的真值為0，q：2+5=7，則q的真值為1

命題分類70命題分類：簡單命題（也稱原子命題）與復(fù)合命題命題分類14否定、合取、析取聯(lián)結(jié)詞定義1.1設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作否定聯(lián)結(jié)詞.規(guī)定p為真當(dāng)且僅當(dāng)p為假.可用下表來規(guī)定否定詞“┐”的意義:

p

┐p011071否定、合取、析取聯(lián)結(jié)詞定義1.1設(shè)p為命題，復(fù)合命題“非定義1.2設(shè)p,q為兩個命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞.規(guī)定p∧q為真當(dāng)且僅當(dāng)p與q同時為真.可用下表來規(guī)定合取詞“∧”的意義：pq

p∧q00110101000172定義1.2設(shè)p,q為兩個命題，復(fù)合命題“p并且q”(或“p定義1.3設(shè)p,q為兩個命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞.規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時為假.可用下表來規(guī)定析取詞“∨”的意義：pq

p∨q00110101011173定義1.3設(shè)p,q為兩個命題，復(fù)合命題“p或q”稱作p與例2

將下列命題符號化.(1)吳穎既用功又聰明.(2)吳穎不僅用功而且聰明.(3)吳穎雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學(xué).合取聯(lián)結(jié)詞的實例74例2將下列命題符號化.合取聯(lián)結(jié)詞的實例18解令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é)詞的實例75解令p:吳穎用功,q:吳穎聰明合取聯(lián)結(jié)詞的實例19例3將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)小元元只能拿一個蘋果或一個梨.(5)王小紅生于1975年或1976年.析取聯(lián)結(jié)詞的實例76例3將下列命題符號化析取聯(lián)結(jié)詞的實例20解(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)為相容或，即當(dāng)p和q均真時，確認(rèn)p∨q為真.在日常生活中，“或”在有的場合下不同于上述意義.析取聯(lián)結(jié)詞的實例77解析取聯(lián)結(jié)詞的實例21例如“人固有一死，或重于泰山，或輕于鴻毛”.其中的“或”是排斥的，即當(dāng)發(fā)現(xiàn)有人的死既重于泰山又輕于鴻毛時，上述論斷被認(rèn)為假.這里的“或”用∨表示不合適.可用下表規(guī)定的新聯(lián)結(jié)詞“排斥或”∨表示之.pq

P

q001101010110∨78例如“人固有一死，或重于泰山，或輕于鴻毛”.其中的“或”是(4)—(5)為排斥或,但是，像上述場合一樣的許多場合下，兩個析取命題事實上不可能同時為真，即上表的末行根本無需定義，這時用∨代替∨就沒有問題，并且能使語句的表示簡化.例如“a>0或a=0或a<0”可表示為“a>0∨a=0∨a<0”，而不必多此一舉地表示為“a>0∨a=0∨a<0”.符號化時(5)可有兩種形式，而(4)則不能79(4)—(5)為排斥或,但是，像上述場合一樣的許多場合下，蘊涵聯(lián)結(jié)詞定義1.4設(shè)p,q為兩個命題，復(fù)合命題“如果p,則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件，q為蘊涵式的后件，稱作蘊涵聯(lián)結(jié)詞.規(guī)定：pq為假當(dāng)且僅當(dāng)p為真q為假.可用下表來規(guī)定該蘊涵詞“→

”的意義：p

q

p

→q00110101110180蘊涵聯(lián)結(jié)詞定義1.4設(shè)p,q為兩個命題，復(fù)合命題“如果p(1)pq的邏輯關(guān)系：q為p的必要條件(2)“如果p,則q”有很多不同的表述方法：若p，就q只要p，就qp僅當(dāng)q只有q才p除非q,才p或除非q，否則非p，…．(3)當(dāng)p為假時，pq恒為真，稱為空證明(4)常出現(xiàn)的錯誤：不分充分與必要條件81(1)pq的邏輯關(guān)系：q為p的必要條件25例4設(shè)p：天冷，q：小王穿羽絨服，將下列命題符號化(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時候.蘊涵聯(lián)結(jié)詞的實例pq注意：pq與qp等值（真值相同）pqpqqpqppqqpqp82例4設(shè)p：天冷，q：小王穿羽絨服，將下列命題符號化蘊涵注意:上述規(guī)定的蘊涵詞稱為實質(zhì)蘊涵，因為它不要求p→q中的p，q有什么關(guān)系，只要p，q為命題，p→q就有意義.例如“如果2+2=5，那么雪是黑的”，就是一個有意義的命題，且據(jù)定義其真值為“真”.83注意:上述規(guī)定的蘊涵詞稱為實質(zhì)蘊涵，因為它不要求p→q中的定義1.5設(shè)p,q為兩個命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價式，記作pq，稱作等價聯(lián)結(jié)詞.規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時為真或同時為假.pq的邏輯關(guān)系：p與q互為充分必要條件等價聯(lián)結(jié)詞可用下表來規(guī)定該雙向蘊涵詞“”的意義：pqp

q00110101100184定義1.5設(shè)p,q為兩個命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”例5求下列復(fù)合命題的真值(1)2+2＝4當(dāng)且僅當(dāng)3+3＝6.(2)2+2＝4當(dāng)且僅當(dāng)3是偶數(shù).(3)2+2＝4當(dāng)且僅當(dāng)太陽從東方升起.(4)2+2＝4當(dāng)且僅當(dāng)美國位于非洲.(5)函數(shù)f(x)在x0可導(dǎo)的充要條件是它在x0連續(xù).1010085例5求下列復(fù)合命題的真值1010029本小節(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)者先運算.86本小節(jié)中p,q,r,…均表示命題.聯(lián)結(jié)詞集為{,1.2命題公式及其賦值命題變項與合式公式命題變項合式公式合式公式的層次公式的賦值公式賦值真值表871.2命題公式及其賦值命題變項與合式公式31命題變項與合式公式

命題常項：表示具體命題及表示常命題的統(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)形成的符號串才是合式公式約定公式最外層和不影響運算次序的括號可省去.88命題變項與合式公式命題常項：表示具體命題及表示常命題的統(tǒng)稱合式公式的層次定義1.7(1)若公式A是單個命題變項，則稱A為0層公式.(2)稱A是n+1(n≥0)層公式是指下面情況之一：(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層公式.89合式公式的層次定義1.733定義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賦值=12…n是指p1=1,p2=2,…,pn=n,i=0或1,i之間不加標(biāo)點符號

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是成假賦值.公式賦值90定義1.8設(shè)p1,p2,…,pn是出現(xiàn)在公式A中定義1.9

將命題公式A在所有賦值下取值的情況列成表,稱作A的真值表.構(gòu)造真值表的步驟:(1)找出公式中所含的全部命題變項p1,p2,…,pn(若無下角標(biāo)則按字母順序排列),列出2n個全部賦值,從000開始,按二進制加法,每次加1,直至111為止.

(2)按從低到高的順序?qū)懗龉降母鱾€層次.(3)對每個賦值依次計算各層次的真值,直到最后計算出公式的真值為止.真值表91定義1.9將命題公式A在所有賦值下取值的情況列成表,稱例6

寫出下列公式的真值表,并求它們的成真賦值和成假賦值:(1)(pq)r(2)(qp)qp(3)(pq)q真值表92例6寫出下列公式的真值表,并求它們的成真賦值和成假真值表(1)A=(pq)r成真賦值:000,001,010,100,110;成假賦值:011,101,111

pqrpq

r

(pq)r000001010011100101110111001111111010101011101010真值表193(1)A=(pq)r成真賦值:000,001(2)B＝(qp)qp成真賦值:00,01,10,11;無成假賦值p

q

qp(qp)q(qp)qp00011011101100011111真值表294(2)B＝(qp)qp成真賦值:00,01,10,(3)C＝(pq)q的真值表成假賦值:00,01,10,11;無成真賦值p

q

ppq(pq)(pq)q000110111100110100100000真值表395(3)C＝(pq)q的真值表成假賦值:00,0語句形式化要注意以下幾個方面：

①

要準(zhǔn)確確定原子命題，并將其形式化.

②

要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識別自然語言中的聯(lián)結(jié)詞（有時它們被省略），否定詞的位置要放準(zhǔn)確.

③

必要時可以進行改述，即改變原來的敘述方式，但要保證表達意思一致.④

需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦可不省略.⑤要注意語句的形式化未必是唯一的.

用我們已有的符號語言，可以將許多自然語言語句形式化，下面我們用一些例子來說明，語句形式化須注意的地方，以及如何理解形式化了的語句.96語句形式化要注意以下幾個方面：①要準(zhǔn)確確定原子命題，（1）我和他既是兄弟又是同學(xué).令p：我和他是兄弟，q：我和他是同學(xué).（3）狗急跳墻.令p：狗急了，q：狗跳墻.（2）我和他之間至少有一個要去邊疆.令p：我去邊疆，q：他去邊疆.例將下列語句形式化，并表示為命題公式：表示為p∧q表示為p∨q表示為p→q97（1）我和他既是兄弟又是同學(xué).（3）狗急跳墻.（2）我和他之（4）風(fēng)雨無阻，我去上學(xué).令p：天刮風(fēng)，q：天下雨，r：我去上學(xué).（5）△ABC與△A′B′C′

全等的充要條件是

△ABC與△A′B′C′的三邊對應(yīng)相等.令p：△ABC與△A′B′C′

全等，

q：△ABC與△A′B′C′的三邊對應(yīng)相等.還可表示為(p∧q∧r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r).表示為(p∧q→r)∧(p∧┐q→r)∧(┐p∧q→r)∧(┐p∧┐q→r),表示為pq98（4）風(fēng)雨無阻，我去上學(xué).（5）△ABC與△A′B′C′全（1）p∨q（是偶數(shù)或是奇數(shù)）（3）r∧┐s→q（若是不等于2的質(zhì)數(shù)，則為奇數(shù)）（2）p∧r→s（若是偶質(zhì)數(shù)，則