1、1.離散數(shù)學(xué)，離散數(shù)學(xué)，2。前言：離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)與技術(shù)的核心課程，也是整個(gè)計(jì)算機(jī)學(xué)科的專(zhuān)業(yè)基礎(chǔ)課。離散數(shù)學(xué)旨在研究離散量的結(jié)構(gòu)及其相互關(guān)系，其研究對(duì)象一般是有限或可數(shù)元素，因此它充分描述了計(jì)算機(jī)科學(xué)的離散性特征。離散數(shù)學(xué)是隨著計(jì)算機(jī)科學(xué)的發(fā)展而逐漸建立起來(lái)的。它形成于20世紀(jì)70年代初，是一門(mén)新的工具學(xué)科。3、離散數(shù)學(xué)課程，計(jì)算機(jī)科學(xué)的核心課程，信息專(zhuān)業(yè)的必修課，以及其他專(zhuān)業(yè)的重要選修課；4、后續(xù)課程，數(shù)據(jù)結(jié)構(gòu)編譯理論，系統(tǒng)結(jié)構(gòu)，人工智能數(shù)據(jù)庫(kù)原理；5、離散數(shù)學(xué)的發(fā)展。在18世紀(jì)之前，數(shù)學(xué)基本上是一門(mén)研究離散物體的數(shù)量和空間關(guān)系的科學(xué)。此后，由于天文學(xué)和物理學(xué)的

2、發(fā)展，如行星軌道和牛頓力學(xué)三定律，連續(xù)數(shù)學(xué)(以微積分、數(shù)學(xué)物理方程、實(shí)變函數(shù)和復(fù)變函數(shù)為代表)的發(fā)展得到了極大的促進(jìn)。對(duì)離散物體的研究處于停滯狀態(tài)。20世紀(jì)30年代，圖靈提出了計(jì)算機(jī)圖靈機(jī)的理論模型。這種模型比計(jì)算機(jī)的實(shí)際制造早了十多年，真正計(jì)算機(jī)的計(jì)算能力與圖靈機(jī)基本相同。由于計(jì)算機(jī)中機(jī)器的字長(zhǎng)總是有限的，它代表離散的數(shù)字或其他離散的對(duì)象，所以隨著計(jì)算機(jī)科學(xué)技術(shù)的飛速發(fā)展，離散數(shù)學(xué)變得重要起來(lái)。離散數(shù)學(xué)的發(fā)展(續(xù))，7。算術(shù)思維：許多問(wèn)題可以通過(guò)構(gòu)造一個(gè)可以用程序?qū)崿F(xiàn)的算法來(lái)解決。它的三個(gè)步驟是：構(gòu)造(選擇合適的離散模型和操作步驟)、驗(yàn)證(算法的正確性)和評(píng)估(時(shí)間和空間的復(fù)雜性)。應(yīng)用和建

3、模：離散數(shù)學(xué)可以用于任何可能的研究領(lǐng)域。計(jì)算科學(xué)、化學(xué)、植物學(xué)、動(dòng)物學(xué)、語(yǔ)言學(xué)、地理學(xué)、經(jīng)濟(jì)學(xué)等。和構(gòu)建離散模型都是解決問(wèn)題的非常有用的方法。離散數(shù)學(xué)的發(fā)展(續(xù))，8。計(jì)算機(jī)求解的基本模式是：實(shí)際問(wèn)題、數(shù)學(xué)建模、算法設(shè)計(jì)、編程、離散數(shù)學(xué)的實(shí)現(xiàn)，為數(shù)學(xué)建模奠定知識(shí)基礎(chǔ)，為算法設(shè)計(jì)提供具體指導(dǎo)。告訴你各種模式的基本特征和它們之間的關(guān)系，以及選擇它們的策略；告訴你哪些問(wèn)題是可以解決的，哪些問(wèn)題目前在圖靈機(jī)模型上沒(méi)有(最佳)解決，哪些問(wèn)題可以得到近似/更好的解決方案。簡(jiǎn)而言之，離散數(shù)學(xué)的功能是培養(yǎng)使用離散結(jié)構(gòu)作為抽象模型、構(gòu)造算法和解決問(wèn)題的能力。9，教學(xué)內(nèi)容，集合論，數(shù)理邏輯，圖論，代數(shù)結(jié)構(gòu)，10，

4、教材和教學(xué)參考書(shū)，教材：耿素云，曲萬(wàn)玲，離散數(shù)學(xué)(修訂版)，高等教育出版社，2004年。教學(xué)參考書(shū)：左曉玲，李，離散數(shù)學(xué)，上?？茖W(xué)技術(shù)文獻(xiàn)出版社概念(正確)必須掌握大量離散數(shù)學(xué)中的概念判斷(準(zhǔn)確)，根據(jù)概念判斷和推理事物的屬性(可靠)，并根據(jù)多重判斷推出新的判斷。12.就本課程的特征定義定理的例子做更多的練習(xí)，完成作業(yè)時(shí)思路清晰，說(shuō)話清晰，書(shū)寫(xiě)工整，學(xué)習(xí)離散數(shù)學(xué)的要領(lǐng)。13.考試方法，平均分40，期末考試60，14，孟志剛郵件地址：tel 336015874982948web 3360，15，數(shù)理邏輯，第1章，命題邏輯的基本概念，第2章，命題邏輯的等價(jià)演算，第3章，命題邏輯的推理理論，16，數(shù)

5、理邏輯，一門(mén)用數(shù)學(xué)方法研究推理和證明的學(xué)科。這里所指的數(shù)學(xué)方法是引入一套符號(hào)系統(tǒng)的方法。數(shù)理邏輯，也稱(chēng)為符號(hào)邏輯，從量的角度研究思維規(guī)律。數(shù)字電子計(jì)算機(jī)是數(shù)理邏輯和電子學(xué)結(jié)合的產(chǎn)物。，17，第1章命題邏輯的基本概念，1.1命題和連通性1.2命題公式及其賦值練習(xí)1，18，1.1命題和連通性，命題和真值原子命題復(fù)合命題常數(shù)命題變量連通性，19，命題和真值，命題：判斷結(jié)果唯一陳述句命題的真值：判斷結(jié)果的真值：真假命題3360真值為真的命題3360真值為假的命題注：(1)它是一個(gè)無(wú)理數(shù)。(2) 2 5 8。(3) x 5 3。你有鉛筆嗎？這只兔子跑得真快！請(qǐng)不要說(shuō)話！(7)這個(gè)命題是假的，真命題，假命

6、題，不確定真值，疑問(wèn)句，感嘆句，祈使句，悖論，(3)(7)它不是命題，21，命題的分類(lèi)，簡(jiǎn)單命題(原子命題):由簡(jiǎn)單陳述句組成的命題復(fù)合命題：由簡(jiǎn)單命題和連詞按一定規(guī)則組成的命題，22日(i1)表示簡(jiǎn)單命題為真，為“1”，為假，為“0”。例如，如果P:是一個(gè)有理數(shù)，那么P的真值是0，Q: 25=7，那么Q的真值是1，23，共軛和復(fù)合命題。1.否定和否定共軛“把P定義為命題，復(fù)合命題為“非P”。符號(hào)被稱(chēng)為否定連詞，并規(guī)定P為真的條件是P為假。根據(jù)定義，P的邏輯關(guān)系不是真的，所以當(dāng)P為真時(shí)，P為假，否則，P為真，24，真值表，25，2。合取公式和合取連詞“”將P、Q定義為兩個(gè)命題，復(fù)合命題“P和Q

7、”(or)規(guī)定當(dāng)且僅當(dāng)P和Q同時(shí)為真時(shí)，pq為真。從定義上看，pq的邏輯關(guān)系是P和Q同時(shí)成立，所以pq只有在pq同時(shí)成立時(shí)才成立。在其他情況下，pq是假的。注：描述連詞的靈活性和多樣性，以區(qū)分簡(jiǎn)單命題和復(fù)合命題，連詞和復(fù)合命題(續(xù))，26，真值表，27，下列命題被符號(hào)化。王曉既勤奮又聰明。(2)王曉不僅聰明，而且勤奮。(3)王曉聰明但不勤奮。張輝和王麗都是好學(xué)生。張輝和王莉是同班同學(xué)。解釋是：P:學(xué)習(xí)努力，Q:聰明，那么(1) PQ使r :張輝成為三好學(xué)生，s :王成為三好學(xué)生。(4) rs。(5)讓張輝和王麗同學(xué)做t :而t是一個(gè)簡(jiǎn)單的命題。它表明： (1)(4)顯示了描述連詞的靈活性和多樣

8、性。連接詞和復(fù)合命題(續(xù))，將P和Q定義為兩個(gè)命題，復(fù)合命題“P或Q”被稱(chēng)為P和Q的析取表達(dá)式，它們被稱(chēng)為析取連接詞，并規(guī)定當(dāng)且僅當(dāng)P和Q都為假時(shí)pq為假。根據(jù)定義，如果pq為真，則至少有一個(gè)為真，所以pq只有在P和Q同時(shí)為假時(shí)才為假，在其他情況下pq為真。注：兼容或和異或，見(jiàn)例3。析取和析取連詞，30，真值表，31。例子象征下列命題：(1) 2或4是素?cái)?shù)。(2) 2或3是素?cái)?shù)。(3) 4或6是素?cái)?shù)。小源只能帶一個(gè)蘋(píng)果或一個(gè)梨。(5)如果q:3是質(zhì)數(shù)，r:4是質(zhì)數(shù)，s:6是質(zhì)數(shù)，那么(1)、(2)和(3)都是相容的或。它們被符號(hào)化為：pr、pq和RS，它們的真值分別為1、1和0，而(4)和(5

9、)是異或，然后(4)被符號(hào)化為(tu) (tu)。如果v :王小紅生于1975年，w:王小紅生于1976年，則(5)可以符號(hào)化為(大眾)(大眾)和大眾。為什么？33，連詞和復(fù)合命題(續(xù))，將P和Q定義為兩個(gè)命題，復(fù)合命題“如果P，那么Q”稱(chēng)為P和Q的蘊(yùn)涵，稱(chēng)為pq，P是蘊(yùn)涵的先行詞，Q是蘊(yùn)涵的后半部分。它被稱(chēng)為蘊(yùn)涵連詞，并規(guī)定當(dāng)且僅當(dāng)P為真，Q為假時(shí)pq為假。4.蘊(yùn)涵和蘊(yùn)涵連詞之間的邏輯關(guān)系“”，34，真值表，35，pq:Q是P的必要條件“如果P，那么Q”可以用許多不同的方式表達(dá)：如果P，那么Q只需要P，那么q p只有當(dāng)Q只有Q，那么P不是P除非Q，否則它不是P，當(dāng)P是假的，Pq是一個(gè)常見(jiàn)的錯(cuò)

10、誤：不管充分和必要條件，連詞和復(fù)合命題(續(xù))，36， 例如，p:是冷的，而q:小王穿羽絨服，象征著以下命題：(1)小王只要冷就穿羽絨服。 小王穿羽絨服是因?yàn)樘鞖饫洹?3)如果小王不穿羽絨服，小王只穿羽絨服。除非天氣冷，小王都穿羽絨服。(6)除非天氣冷，否則不冷。如果天氣不冷，小王就不穿羽絨服。小王只在那天冷的時(shí)候穿羽絨服。注意：pq等于pq(真值相同)，PQ，PQ，PQ，PQ，PQ，Q:小王穿羽絨服，象征著以下命題：(1)小王只要冷就穿羽絨服。因?yàn)樘鞖饫?，小王穿著羽絨服。(3)如果小王不穿羽絨服，就不冷。只有當(dāng)天氣冷的時(shí)候，小王才穿羽絨服。(5)只有在冷的時(shí)候。(6)那么小王不穿羽絨服。小王只

11、在那天冷的時(shí)候穿羽絨服。pq，pq，q p，q p，QP，QP，PQ，38，真值表。注：PQ等于QP(真值相同)，PQ等于QP。，39，連詞和復(fù)合命題(續(xù))，把P和Q定義為兩個(gè)命題，而復(fù)合命題“P當(dāng)且僅當(dāng)Q”被稱(chēng)為P和Q的等價(jià)公式，這被稱(chēng)為pq和等價(jià)連詞。當(dāng)且僅當(dāng)P和Q同時(shí)為真或假時(shí)，pq才被規(guī)定為真。證明了： P(1)PQ 3360 P和Q的邏輯關(guān)系是彼此的一個(gè)充要條件。5.等價(jià)公式和等價(jià)連接詞“”，40，真值表，41，找出下列復(fù)合命題的真值：(1) 2 2 4當(dāng)且僅當(dāng)3 3 6。(2) 2 2 4當(dāng)且僅當(dāng)3是偶數(shù)。如果且僅當(dāng)太陽(yáng)從東方升起。(4) 2 2 4如果且僅當(dāng)美國(guó)位于非洲。(5)函

12、數(shù)f (x)當(dāng)且僅當(dāng)它在x0處可導(dǎo)時(shí)，它在x0處是連續(xù)的。它們的真實(shí)值是1，0，1，0，0。42，連詞和復(fù)合命題(續(xù))。上面給出了五個(gè)連詞：組成一個(gè)連詞集、連詞的優(yōu)先順序是：如果連詞出現(xiàn)在同一個(gè)級(jí)別，并且沒(méi)有括號(hào)，它們將從左到右操作；如果有支架，應(yīng)先進(jìn)行支架操作。請(qǐng)注意，33，360本書(shū)中使用的括號(hào)都是括號(hào)。43，1.2命題公式及其賦值，命題變量和復(fù)合公式的賦值，真值表，范疇重言式，矛盾可滿足性，44，命題變量和復(fù)合公式，命題常量：簡(jiǎn)單命題變量：真值不確定的陳述句定義公式(命題公式，公式)遞歸定義如下：(1)單個(gè)命題常量或變量p，q，r，pi，qi，ri，0，1是復(fù)合公式(2)如果a是復(fù)合公式

13、，那么(a)也是只有在有限時(shí)間內(nèi)應(yīng)用(1)和(3)形成的符號(hào)串才是復(fù)合公式的元語(yǔ)言和目標(biāo)語(yǔ)言?？梢允÷酝庵Ъ?。45、復(fù)合配方的水平。定義(1)如果公式甲是一個(gè)單一的命題變量，那么甲被稱(chēng)為0層公式。(2)稱(chēng)之為A. (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)相同，46，以及式(續(xù))的水平，例如式p 0、p 1、pq 2、(pq)r 3、(pq)r(RS)4、47。公式的賦值被定義為命題變量P1，在公式A中。由pn賦值的一組真值被稱(chēng)為對(duì)A的賦值或被解釋為真賦值。使公式真假賦值。使公式賦值錯(cuò)誤。描述：賦值=12n之間沒(méi)有標(biāo)點(diǎn)符號(hào)，只有p1，p2，pn出現(xiàn)在i=0或1中。A .將12n賦給A意味著只有P出現(xiàn)在P1=1，P2=2，PN=N A中。給出值123意味著一