離散數(shù)學(xué)引論

1、離散數(shù)學(xué)引論離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)基礎(chǔ)理論的核心課程，其內(nèi)容一直隨著計(jì)算機(jī)科學(xué)的發(fā)展而不斷地?cái)U(kuò)充與更新。它所研究的對(duì)象是離散數(shù)據(jù)結(jié)構(gòu)及相互關(guān)系。由于數(shù)字電子計(jì)算機(jī)是一個(gè)離散結(jié)構(gòu)，它只能處理離散的或離散化了的數(shù)量關(guān)系，因此，無(wú)論計(jì)算機(jī)科學(xué)本身，還是與計(jì)算機(jī)科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨著對(duì)離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型、將已用連續(xù)數(shù)量關(guān)系建立起來(lái)的數(shù)學(xué)模型離散化問(wèn)題。在計(jì)算機(jī)科學(xué)中由于普遍采用了離散數(shù)學(xué)中的基本概念、基本思想和方法，從而使得離散數(shù)學(xué)成了不可少的理論工具。 離散數(shù)學(xué)的主要內(nèi)容為：集合論、數(shù)理邏輯、近世代數(shù)、圖論和組合數(shù)學(xué)等。離散數(shù)學(xué)不僅為數(shù)據(jù)結(jié)構(gòu)

2、、操作系統(tǒng)、編譯原理、算法分析、人工智能、形式語(yǔ)言與自動(dòng)機(jī)提供了重要的數(shù)學(xué)理論基礎(chǔ)，而且通過(guò)對(duì)它的學(xué)習(xí)可以使我們熟悉和習(xí)慣抽象的符號(hào)表示和演算形式，培養(yǎng)和訓(xùn)練我們掌握使用數(shù)學(xué)語(yǔ)言或符號(hào)系統(tǒng)處理問(wèn)題的基本方法，提高我們的抽象思維和邏輯推理的能力。參考書(shū)目：離散數(shù)學(xué)，耿素云等著，清華大學(xué)出版社；離散數(shù)學(xué)，陳莉等著，高等教育出版社；離散數(shù)學(xué)，孫吉貴等著，高等教育出版社；離散數(shù)學(xué)及其應(yīng)用，傅彥等著，電子工業(yè)出版社； 第一章 數(shù)理邏輯 數(shù)理邏輯又稱(chēng)符號(hào)邏輯，是邏輯學(xué)的一個(gè)重要分支。邏輯學(xué)是研究人的思維形式的科學(xué)。數(shù)理邏輯是用數(shù)學(xué)方法研究推理、利用符號(hào)體系研究推理過(guò)程中前提和結(jié)論之間的關(guān)系。1.1 命題符

3、號(hào)化及聯(lián)結(jié)詞1.1.1命題命題是一個(gè)非真即假的陳述句。因此不能判斷真假的陳述句、疑問(wèn)句、祈使句和感嘆句都不是命題。（1） 一個(gè)命題的真或假稱(chēng)為命題的真值。真用T或1表示，假用F或0表示；（2）原子命題(簡(jiǎn)單命題)：最簡(jiǎn)單的命題，通常用大寫(xiě)字母p,q,r表示；幾個(gè)簡(jiǎn)單命題用聯(lián)結(jié)詞連接起來(lái)得到的命題叫復(fù)合命題。（3）一個(gè)陳述句有真值與是否知道它的真假是兩回事。例1.1.1判斷下列語(yǔ)句是不是命題？若是，給出命題的真值： (1)2是素?cái)?shù)。 (2)雪是黑色的(3)給我一塊錢(qián)吧！(4)2007年元旦下雨(5)x>y。 數(shù)理邏輯的特點(diǎn)是并不關(guān)心具體某個(gè)命題的真假，而是將邏輯推理變成類(lèi)似數(shù)學(xué)演算的形式化

4、了的過(guò)程，它關(guān)心的是命題之間的關(guān)聯(lián)性。因此需要進(jìn)行命題符號(hào)化：原子(簡(jiǎn)單)命題就是簡(jiǎn)單陳述句，用大寫(xiě)字母(或帶下標(biāo))表示；命題常元：T(1)或F(0)，或者表示一個(gè)確定的命題；命題變?cè)阂訲(1)或F(0)為值的變?cè)恢概?解釋)：用一個(gè)具體命題代替一個(gè)命題變?cè)?。而不是?jiǎn)單命題的復(fù)合命題需要使用稱(chēng)為命題聯(lián)結(jié)詞的運(yùn)算符來(lái)進(jìn)行符號(hào)化。命題聯(lián)結(jié)詞的作用是為了將原子命題組合成復(fù)合命題。常用的有五種：(1) 否定聯(lián)結(jié)詞P(否定式)：非P： 不，非，沒(méi)有 規(guī)定P是T當(dāng)且僅當(dāng)P是F。（2） 合取聯(lián)結(jié)詞 PQ(合取式) ：P 并且Q，P合取Q ： 并且，且，既又，不僅而且規(guī)定PQ是T當(dāng)且僅當(dāng)P和Q都是T。（3

5、） 析取聯(lián)結(jié)詞 PQ(析取式)：P或者Q，P析取Q： 或，或者說(shuō)，不是就是，要么要么 規(guī)定PQ是T當(dāng)且僅當(dāng)P，Q中至少一個(gè)是T(或者PQ是F當(dāng)且僅當(dāng)P，Q都是F)。（4） 蘊(yùn)含聯(lián)結(jié)詞 PQ(條件式、命題)：如果P則Q P稱(chēng)為條件式的前件(前提)，Q稱(chēng)為條件式的后件(結(jié)論)：如果(若)就(則)，只要就，若才能規(guī)定PQ是F當(dāng)且僅當(dāng)P是T，Q是F。（5） 等價(jià)(雙條件)聯(lián)結(jié)詞PQ (雙條件式、命題) ：P當(dāng)且僅當(dāng)Q規(guī)定PQ是T當(dāng)且僅當(dāng)P，Q或者都是T，或者都是F。 命題符號(hào)化的目的在于用五個(gè)聯(lián)結(jié)詞將日常語(yǔ)言中的命題轉(zhuǎn)化為數(shù)理邏輯中的形式命題，其關(guān)鍵在于使用適當(dāng)?shù)穆?lián)結(jié)詞。對(duì)自然語(yǔ)言中語(yǔ)句之間的邏輯關(guān)系

6、以及命題聯(lián)結(jié)詞的含義要有正確的理解：（1） 確定語(yǔ)句是否是一個(gè)命題；（2） 找出句中連詞，用適當(dāng)?shù)拿}聯(lián)結(jié)詞表示。例1.1.2試將下列命題符號(hào)化：（1） 若你不看電影，則我也不看電影。（2） 小王一邊吃飯，一邊看書(shū)。1.2 命題公式及分類(lèi)1.2.1命題公式 一個(gè)命題越復(fù)雜，符號(hào)化該命題所需的命題變?cè)吐?lián)結(jié)詞就越來(lái)越多。如何安排這么多的東西使之有意義呢？定義1.2.1 一個(gè)(合式)公式是由下列方式遞歸定義的：（1） 命題常元或命題變?cè)且粋€(gè)公式；（2） 若A是一個(gè)公式，則(A)也是一個(gè)公式；（3） 若A、B是公式，則(AB)、(AB)、(AB)和(AB)均為公式；（4） 只有經(jīng)過(guò)有限次地應(yīng)用(1

7、)、(2)、(3)所得的結(jié)果才是公式。 注：1、公式一般無(wú)真值，只有對(duì)其所有的變?cè)M(jìn)行解釋后，它才有真值； 2、公式無(wú)限多； 3、在一個(gè)復(fù)雜的公式中，常常有許多括號(hào)，為了簡(jiǎn)便起見(jiàn)，規(guī)定下列運(yùn)算順序：，。從而外層括號(hào)可以省略；在不會(huì)引起混淆的情形中，可以省略公式中的一些括號(hào)。定義1.2.1 命題常項(xiàng)或命題變項(xiàng)稱(chēng)為0層公式；A是n+1層公式如果：（1）A=B, B是n層公式;(2)A=CB (或CB、CB、CB),n為C,B的層數(shù)的最大者； 指出下列公式的層(PQR)(PR)，PR，(PR)，(PQR)(PR)。1.2.2 命題公式的解釋對(duì)于一個(gè)命題公式，數(shù)理邏輯的目的在于利用這些形式化的表達(dá)式來(lái)

8、研究命題之間的邏輯關(guān)系。這種邏輯關(guān)系是用真假來(lái)表示的；而命題公式一般而言只是一個(gè)符號(hào)串，不表示具體的命題，無(wú)確定真值，只有對(duì)其所有的變?cè)概梢源_定的真值后，它才有真值。定義1.2.4 設(shè)公式A(P1, P2, , Pn)含有n個(gè)命題變?cè)狿1, P2, , Pn，對(duì)P1, P2, , Pn進(jìn)行賦值，即讓每一個(gè)Pi(i=1,2,n)分別取T(1)或F(0)，這稱(chēng)為對(duì)A的一個(gè)解釋或指派I。一般地，含n個(gè)命題變?cè)墓焦灿?n種不同的解釋。在公式A(P1, P2, , Pn)的任一個(gè)解釋I下，每個(gè)命題變?cè)写_定的真值，從而公式A(P1, P2, , Pn)有確定的真值。一個(gè)公式在其所有可能的解釋下所取

9、的真值，可列出一個(gè)真值表。定義1.2.5設(shè)A 是一個(gè)公式，則A的真值表由兩部分組成：左邊部分是A的所有命題變?cè)约八械慕忉專(zhuān)挥疫叢糠质茿及A相應(yīng)于對(duì)應(yīng)解釋的真值。例1.2.4 構(gòu)造五個(gè)常用命題聯(lián)結(jié)詞的真值表。例1.2.5 構(gòu)造下列公式的真值表：(1) (PQ)(PQ)；(2) PP ； (3) PQ。1.2.3公式分類(lèi)與永真式定義1.2.6設(shè)A 是一個(gè)公式，(1)若A在任何解釋下都為T(mén)，則稱(chēng)為永真式(重言式)；(2)若A在任何解釋下都為F，則稱(chēng)A為永假式(矛盾式)；(3)若至少存在一個(gè)解釋使A為T(mén)，則稱(chēng)A為可滿足式。注: 1、永真式必為可滿足式，反之則不然；永真式的否定是永假式，反之亦然；2

10、、決定一個(gè)公式是否是一個(gè)永真式、永假式或可滿足式有兩種方法：真值表法(適用于變?cè)俣?jiǎn)單的公式)和等值演算法等；3、永真式的合取、析取、蘊(yùn)含和等值式都是永真式。例1.2.6判斷下列幾個(gè)公式的類(lèi)型： PP，PP，PQ。例1.2.7用真值表決定公式(PQ)P的類(lèi)型。1.3 等值演算1.3.1 等值演算 設(shè)A，B是兩個(gè)公式，若AB是永真式，即在所有的解釋下A和B的真值對(duì)應(yīng)相同，則稱(chēng)A與B 是等值的，記作AB，并稱(chēng)AB為邏輯恒等式。注1、可用真值表法證明兩個(gè)公式是否等價(jià)；例1.3.1證明 ()()。2、等值公式不必含有同樣多變?cè)?、等值關(guān)系是等價(jià)關(guān)系：自反性(AA)，對(duì)稱(chēng)性(若AB，則BA)和傳遞性

11、(若AB，BC，則AC)；4、若AB，則AB。1.3.2 基本等值式下面是常用的基本邏輯等值式，是公式推理法的基礎(chǔ)。（） 雙否律：；（） 交換律：，；（） 結(jié)合律：()()，()()；（） 分配律：() ()()，() ()()；（） De Morgan律：(AB)AB，(AB)AB；（） 等冪律:AAA，AAA；（） 同一律:A0A，A1A；（） 零一律:A00，A11；（） 吸收律:A(AB)A，A(AB)A；(10)矛盾律與排中律: AA1，AA0；(11)蘊(yùn)含等值式:ABAB， ABBA；(12)等價(jià)等值式:AB( AB)(BA)(AB)(BA)(AB)(AB)；(置換原理)設(shè)是含命題

12、公式A的公式 是用公式B代替中的A之后所得到的公式，若AB，則。例如： 所以例1.3.2證明：P(qr) (pq)r。例1.3.3證明：P(pq) (Pq) 1.4對(duì)偶與范式1.4.1 對(duì)偶式 設(shè)A是僅含，和這三種命題聯(lián)結(jié)詞的公式，在A中將和互換、1和0(若有的話)所得到的公式稱(chēng)為A的對(duì)偶式，記為A。例1.4.1求(PQ)R的對(duì)偶式。(PQ)R的對(duì)偶式是 設(shè)A(P1, P2, , Pn)是僅含，和這三種命題聯(lián)結(jié)詞的公式，則A(P1, P2, , Pn) A(P1, P2, , Pn)。(對(duì)偶原理)設(shè)A和B都是僅含，和這三種命題聯(lián)結(jié)詞的公式，若A B，則AB。1.4.2 范式 1.4.2.1 范

13、式范式使千變?nèi)f化的公式有了一個(gè)統(tǒng)一的表示方式，從而為實(shí)現(xiàn)公式的機(jī)器判斷提供了基礎(chǔ)。范式也在電子線路技術(shù)、自動(dòng)機(jī)理論和人工智能方面有重要的應(yīng)用。（1）簡(jiǎn)單析（合）取式 有限個(gè)命題變項(xiàng)或者其否定構(gòu)成的析取式叫簡(jiǎn)單析取式：有限個(gè)命題變項(xiàng)或者其否定構(gòu)成的合取式叫簡(jiǎn)單合取式。 P， P，PP，PQR是簡(jiǎn)單析取式。P， P，PP，PQR是簡(jiǎn)單合取式。顯然：一個(gè)簡(jiǎn)單析取式是永真式它同時(shí)含有某命題變?cè)c它的否定。 一個(gè)簡(jiǎn)單合取式是矛盾式它同時(shí)含有某命題變?cè)c它的否定。（2）析（合）范式 有限個(gè)簡(jiǎn)單合取式的析取式叫析取范式；有限個(gè)簡(jiǎn)單析取式的合取式叫和取范式。 注（1）若B是合取范式，A是合式公式。若AB，則稱(chēng)

14、B是A的合取范式。（2）若B是析取范式，A是合式公式。若AB，則稱(chēng)B是A的析取范式。結(jié)論：任意一個(gè)命題公式總存在于志等值得合取范式和析取范式。下面是求一個(gè)公式范式的方法：（1）首先將公式中的蘊(yùn)涵式和等價(jià)式轉(zhuǎn)化為只含，；（2）利用De Morgan 律和雙否律將括號(hào)外的轉(zhuǎn)化到括號(hào)內(nèi)；（3）利用交換、分配以及結(jié)合律按相應(yīng)范式的要求安排，。 求 (P(QR)(PQ)的合取范式。1.4.2.2主范式從例1.4.2中可以看出，一個(gè)公式的合取范式或析取范式是不唯一的，這就給用形式化的方法(特別是用計(jì)算機(jī)作為工具)來(lái)判斷兩公式是否等價(jià)帶來(lái)了困難。為此我們?cè)谙旅嬉胫骱先》妒脚c主合取范式。l 極小項(xiàng)與極大項(xiàng)

15、設(shè)公式A是關(guān)于的簡(jiǎn)單合取式,如果(1) 每個(gè)變?cè)c其否定不同時(shí)出現(xiàn)，但二者之一必須恰好出現(xiàn)一次,(2) 出現(xiàn)在第i個(gè)位置上 ,則稱(chēng)A未極小項(xiàng),用m表示.注(1) 共有2n個(gè)不同的n元極小項(xiàng)； (2) 極小項(xiàng)的下標(biāo)編號(hào)有唯一的真賦值；(3)極小項(xiàng)的下標(biāo)編號(hào)方法：給出成真賦值,把成真賦值視為二進(jìn)制數(shù),把二進(jìn)制數(shù)化為十進(jìn)制數(shù)即得 注：相應(yīng)地定義極大項(xiàng)，極大項(xiàng)編號(hào)方法類(lèi)似于極小項(xiàng),只需把“成真”改成“成假”l 主范式 如果析取范式中的每個(gè)簡(jiǎn)單合取式都是極小項(xiàng)，則稱(chēng)它為主析取范式；如果合取范式中的每個(gè)簡(jiǎn)單析取式都是極大項(xiàng)，則稱(chēng)它為主和取范式。任意命題公式都存在與其等值的主析（合）取范式；且在不計(jì)極大項(xiàng)出

16、現(xiàn)的順序情形下是唯一的。l 求主析（合）取范式的方法: （1）先將公式化為析取范式;（）對(duì)每一個(gè)簡(jiǎn)單析取式若其中既有某個(gè)變?cè)钟兴姆穸?，則去掉該它，若某個(gè)變?cè)?或其否定)在式中同時(shí)出現(xiàn)二次或二次以上，則用等冪律化簡(jiǎn);若其中既無(wú)某個(gè)變?cè)譄o(wú)它的否定，則用同一律、排中律和矛盾律使變?cè)蛩姆穸ǔ霈F(xiàn)在該和中(擴(kuò)充)。例1.4. (PQ) (PR)和(PQ)R的主析取范式及主合取范式。1.4.主范式的應(yīng)用：(1)主范式與真值表相互確定 主析取范式成真賦值真值表成假賦值主合取范式極小項(xiàng)成真賦值 極大項(xiàng)成假賦值例1.4. 用真值表法求 (PQ)(PR)的主析取范式。(2)主析取范式與主合取范式相互確定可

17、以利用主析取范式求主合取范式或反之：(1)兩個(gè)主范式中,極小項(xiàng)與極大項(xiàng)共有2n項(xiàng);(2) 兩個(gè)主范式中的下標(biāo)集互為補(bǔ)集. 例1.4. 求 (PQ)(PR)(3)公式的分類(lèi)：若n元公式A的主析取范式含2n個(gè)極小項(xiàng)，則A為永真式 ;若n元公式A的主合取范式含2n個(gè)極大項(xiàng)，則A為矛盾式;若n元公式A的主合取范式所含極大項(xiàng)不到2n個(gè)，則A為可滿足式;規(guī)定: 永真式的主合取范式為1, 矛盾式的主析取范式為0例1.4. 判斷下列公式是何種公式: (PQ)Q。(4)判斷公式等值若兩個(gè)公式有相同的主范式，則這兩個(gè)公式等價(jià)。例1.4. 求證 (PQ)(PR) (P（QR）)； 1.5 命題邏輯的推理理論1.5.1推理的基本概念和推理形式推理就是從一組已知的命題出發(fā)，按照一組推理規(guī)則推出新的命題的過(guò)程。已知命題稱(chēng)為推理的前提，推出的命題稱(chēng)為推理的結(jié)論。 推理的格式 設(shè)和是公式，若，是永真式，則稱(chēng)是前提的有效結(jié)論。記位推理形式是一個(gè)有限公式序列，它的最后一個(gè)是結(jié)論，其余的公式或者是一個(gè)給定的前提，或者是由若干個(gè)在它前面出現(xiàn)的公式的有效結(jié)論。判斷有效結(jié)論的常用方法：真值表法,等值演算法,主范式法等 求證1.5.推理規(guī)則P規(guī)則(前提引入): 在推導(dǎo)過(guò)程中，前提可視需要引入使用。T規(guī)則(結(jié)論引入): 在推導(dǎo)過(guò)程中，利用推