離散數(shù)學(xué)課件1

1、1,第一編 集合論,第一章 集合,2,1.1 預(yù)備知識(shí)（prerequisites）,命題邏輯和謂詞邏輯是數(shù)理邏輯中最基本的內(nèi)容。 十九世紀(jì)中后期，德國數(shù)學(xué)家萊布尼茲、英國數(shù)學(xué)家布爾和邏輯學(xué)家懷海特、羅素為數(shù)理邏輯的產(chǎn)生和發(fā)展有突出貢獻(xiàn)。 從二十世紀(jì)40年代起，數(shù)理邏輯成為計(jì)算機(jī)科學(xué)的重要基礎(chǔ)理論之一。如布爾代數(shù)在計(jì)算機(jī)硬件設(shè)計(jì)中發(fā)揮了重大作用；形式語言的研究為建立計(jì)算機(jī)語言提供了基礎(chǔ)。,3,命題和命題聯(lián)結(jié)詞 命題公式和真值表 命題等值式 命題推理定律,命題邏輯,4,命題是客觀上能判明真假的陳述句。當(dāng)命題為真時(shí)，稱命題的真值為“真”；否則，說命題的真值為“假”。用T或1表示“真”，用F或0表示

2、“假”。 （ Proposition: a statement that is either true or false,but not both.） 所有這些命題，都應(yīng)具有確定的真值。,5,判斷下列語句是不是命題:,(1) 天氣多好啊! (2) 你去哪里？ (3) X3。 (4) 別的星球有生物。 (5) 我正在說慌。,解：(1)是感嘆句；(2)是疑問句；它們都不是命題。 (3) 真假要視的值而定，因此這個(gè)語句無確定真值。它不是命題。 (4)的真實(shí)性目前還無法判明，但在客觀上，是真是假，二者必居其一。因此它是命題。 (5)同樣不能判明真假。如說該命題為真，但原語句卻說“本命題為假”；如果說它

3、為假，卻又肯定了它(本命題)是真的，這樣造成了自相矛盾的結(jié)果！這是所謂悖論。,6,無法繼續(xù)分解的簡單陳述句，稱為簡單命題或原子命題。(不包含任何“與、或、非”等聯(lián)結(jié)詞的命題) 由一個(gè)或幾個(gè)簡單命題通過聯(lián)結(jié)詞復(fù)合而成的命題，稱為復(fù)合命題。 (1)期中考試，張三沒有考及格 (2)期中考試，張三和李四都考及格了 (3)期中考試，張三和李四有人考90分 (4)如果張三考90分，李四也能考90分 (5)張三能考90分當(dāng)且僅當(dāng)李四也考90分,7,否定聯(lián)結(jié)詞 合取聯(lián)結(jié)詞 析取聯(lián)結(jié)詞 蘊(yùn)涵聯(lián)結(jié)詞 等價(jià)聯(lián)結(jié)詞,命題聯(lián)結(jié)詞,8,定義1 否定聯(lián)結(jié)詞,設(shè)為命題，復(fù)合命題非，叫的否定式，記作。記號(hào)叫否定聯(lián)結(jié)詞。為真當(dāng)且

4、僅當(dāng)為假。 例如，設(shè)：今天是星期二。 則：今天不是星期二。,9,定義2 合取聯(lián)結(jié)詞,設(shè)，表示兩個(gè)命題，復(fù)合命題“且”叫命題與的合取，記作。記號(hào)叫合取聯(lián)結(jié)詞。為真，當(dāng)且僅當(dāng)，同時(shí)為真。 例如，設(shè): 2是素?cái)?shù)。 : 2是偶數(shù)。R： 2是奇數(shù)。 則：2既是素?cái)?shù)又是偶數(shù)。(真值為真) R：2既是素?cái)?shù)又是奇數(shù)。(真值為假),10,定義3 析取聯(lián)結(jié)詞,設(shè)，為二命題，復(fù)合命題“或”稱作與的析取，記作，叫析取聯(lián)結(jié)詞。為真，當(dāng)且僅當(dāng)，之中至少有一為真。 例如，設(shè)：2是素?cái)?shù)。：2是偶數(shù)。 R： 2是奇數(shù)。 則：2是素?cái)?shù)或2是偶數(shù)。(真值為真) R：2是素?cái)?shù)或2是奇數(shù)。(真值為真),11,2-30或今天天氣很好。,

5、他今天騎車或走路來上課。,從理科1號(hào)樓到圖書館要2分鐘或4分鐘。,相容或?,意思： 大約2分鐘到4分鐘,一個(gè)人不可能同時(shí)騎車又走路,12,注：,“或”有兩種標(biāo)準(zhǔn)用法， 張三或李四考了90分（相容“或”） 第一節(jié)課上數(shù)學(xué)或者上英語,13,定義4 蘊(yùn)涵聯(lián)結(jié)詞,設(shè)，是二命題，復(fù)合命題“如，則”稱為與的蘊(yùn)涵式，記作, 其中叫前件或前題，叫后件或結(jié)論。為真當(dāng)且僅當(dāng)真和假不同時(shí)成立。 例如，如果明天天晴就開運(yùn)動(dòng)會(huì)。 設(shè)：明天天晴。:明天開運(yùn)動(dòng)會(huì)。 則原命題表示為：。,14, 蘊(yùn)涵式、蘊(yùn)涵聯(lián)結(jié)詞,p,q,就,則,只要,僅當(dāng),才,只有,p,q,蘊(yùn)涵符號(hào),如果,如果明天下雨，我們就放假,明天不下雨,我們不放假,

6、明天不下雨,我們放假,明天下雨,我們不放假,明天下雨,我們放假,15,定義5 等價(jià)聯(lián)結(jié)詞,設(shè),為二命題，復(fù)合命題“當(dāng)且僅當(dāng)”稱為與的等價(jià)式，記作。叫等價(jià)聯(lián)結(jié)詞，也記作iff。為真當(dāng)且僅當(dāng),真值相同。 例如，2+24當(dāng)且僅當(dāng)雪是白的。 設(shè)： 2+24 。：雪是白的。 則原命題表示為：。,16,命題一般用大寫英文字母表示。表示命題的符號(hào)叫命題標(biāo)識(shí)符。 例如，用表示“雪是黑的”，記作“：雪是黑的”。 如果一個(gè)命題標(biāo)識(shí)符表示某個(gè)確定的命題，則稱為命題常量。特別地，真命題(用T表示)和假命題(用F表示)是命題常量。 如果一個(gè)命題標(biāo)識(shí)符表示不確定的命題，則稱為命題變?cè)?命題常量和命題變?cè)?命題變?cè)皇敲?/p>

7、題。在命題演算中，對(duì)命題變?cè)付ㄏ鄳?yīng)的真值(真或假)，稱為對(duì)命題變?cè)恼嬷抵概伞?集合T,F是命題變?cè)闹涤颉?17,相應(yīng)的真值表,18,命題公式,設(shè)P和Q是任意兩個(gè)命題，則下列命題都是復(fù)合命題,設(shè)P和Q是命題變?cè)瑒t上述公式均稱作命題公式。P和Q稱作命題公式的分量。,19,命題公式,(1)單個(gè)命題變?cè)ɑ虺Ｔ┦敲}公式； (2)若A是命題公式，則(A)是命題公式； (3)若A,B是命題公式，則（AB），（AB）, (AB), (A B)也是命題公式； (4)只有有限次應(yīng)用(1)-(3)形成的符號(hào)串才是命題公式。,注意： 命題公式是沒有真假值的，僅當(dāng)在一個(gè)公式中命題變?cè)么_定的命題代入時(shí)，才

8、得到一個(gè)值。,20,真值表(truth table),定義設(shè)為一命題公式，P1, P2，, Pn為出現(xiàn)在中的所有命題變?cè)営洖椋≒1, P2，, Pn）。給命題變?cè)狿1, P2，, Pn指定一組真值，稱為對(duì)的一個(gè)指派或一個(gè)賦值。含有個(gè)命題變?cè)拿}公式（P1, P2，, Pn）共有n個(gè)指派。將命題公式（P1, P2，, Pn）在所有指派之下取值的情況列成表，叫的真值表。,21,真值表 命題形式A在其所有可能的賦值下取得的值列成的表； n元真值函數(shù) F: 0, 1n 0，1 (n1)。,22,聯(lián)結(jié)詞的真值表,23,A的一個(gè)賦值: n個(gè)命題變?cè)?成真賦值 成假賦值 重言式（永真式tautolog

9、y） P P = 1 矛盾式（永假式contradiction） P P = 0 可滿足式,24, 公式分類, 重言式, 矛盾式, 可滿足式,真！,假！,真真假假,重言式,等值演算,邏輯推理,25,p q pq pp p(pq)p 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0 1 賦值 可滿足式 矛盾式 重言式 (永假式) (永真式),26,等值式（等價(jià)公式）,給定兩個(gè)命題公式（P1, P2，, Pn）和（P1, P2，, Pn），若對(duì)P1, P2，, Pn的任一組真值指派，與的真值都相同，則稱與等價(jià)或邏輯相等。記作。,例4 構(gòu)造命題公式（PQ）和PQ的真值表。,

10、對(duì)于、的任一種真值指派，（PQ）與PQ都有相同的真值，所以這兩個(gè)命題公式是等價(jià)的。,27, 為書寫方便而省略括號(hào), 公式最外層的括號(hào)可以省略, 聯(lián)結(jié)詞運(yùn)算優(yōu)先級(jí)別, 同一個(gè)聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無括號(hào)，則從左到右運(yùn)算,省略括號(hào)不改變公式復(fù)雜性,、,28,例題：層次法構(gòu)造真值表,(p (pq) (pq),(p (pq) (pq),(p (pq) (pq),(p (pq) (pq),p q,pq,pq,p(pq),(pq),公式,0,真值表和真值函數(shù),29,等值式(logical equivalences),30,AAA, AAA A(BC) (AB)(AC) A(BC) (AB)(AC),冪等律,

11、交換律,結(jié)合律,分配律,ABBA, ABBA,(AB)C A(BC) (AB)C A(BC),31,德摩根律,(AB) A B (AB) A B,吸收律,A (AB) A A (AB) A,32,A1 1, A0 0 A0 A, A1 A AA 1 AA 0,零律,同一律,排中律,矛盾律,(對(duì)偶原理: -互換, 0-1互換),33,A A AB AB AB (AB)(BA),雙重否定律,蘊(yùn)涵等值式,等價(jià)等值式,34,AB AB AB BA (AB)(AB) A,等價(jià)否定等值式,假言易位,歸謬論,牢固記住并能熟練運(yùn)用， 是學(xué)好離散數(shù)學(xué)的關(guān)鍵之一,35,設(shè)是合式公式中的一個(gè)部分，且也是一個(gè)合式公式

12、，則稱是的子公式。 例如，設(shè)： (PQ)（Q(RS)），則PQ、 RS、 S、 Q(RS)都是的子公式。,置換規(guī)則,定理（置換規(guī)則）： 設(shè)X是合式公式中的子公式，若是一個(gè)合式公式，且 ，用置換中的，得到新的合式公式，則。 證明：與除替換部分外均相同，又由于替換部分，即是說對(duì)任一指派，與真值相同，那么與對(duì)任一真值指派也應(yīng)有相同的真值。故。,36,等值演算： 由已知的等值式，應(yīng)用置換規(guī)則推演出新的等值式的過程。,等值演算,P (Q R) P ( Q R) P ( Q R) ( P Q) R ( P Q) R ( P Q) R,37,給定命題公式(P1, P2，, Pn)，如果用某個(gè)命題公式Bi取代

13、中的某個(gè)變?cè)狿i，并且用Bi取代中出現(xiàn)的所有Pi，這樣得到的命題公式稱為命題公式的代入實(shí)例。 例如，設(shè)：P(QP)，用(RS)取代中的命題變?cè)茫?RS)(Q(RS)，是的代入實(shí)例。,代入規(guī)則,定理（代入規(guī)則）： 一個(gè)重言式的代入實(shí)例仍然是一個(gè)重言式。 證明： 由于重言式的真值與真值指派無關(guān)，故對(duì)同一命題變?cè)加媚硞€(gè)命題公式代替，該重言式的真值仍為。,例 證明(PS)R)(PS)R)為重言式 證：因P P T，根據(jù)代入規(guī)則 (PS)R)(PS)R)T,38,在太平洋中有AB兩個(gè)相鄰的小島。A島居民都是誠實(shí)的人，B島的居民都是騙子。當(dāng)你問一個(gè)問題時(shí)，A島的居民會(huì)告訴你正確的答案，而B島的居民給你

14、的答案都是錯(cuò)誤的。一天，一個(gè)旅游者獨(dú)自登上了兩島中的某個(gè)島。他分辨不清這個(gè)島是A島還是B島，只知道這個(gè)島上的人既有本島的居民又有另一島的來客。他想問島上的人“這是A島還是B島？”卻又無法判斷被問者的答案是否正確。旅游者動(dòng)腦筋想了會(huì)一兒，終于想出一個(gè)辦法，他只需要問他所遇到的任意一人一句話，就能從對(duì)方的回答中準(zhǔn)確無誤地?cái)喽ㄟ@里是哪個(gè)島。你能猜出旅游者所問的問題嗎？,例:,命題邏輯應(yīng)用,39,命題邏輯推理,1. 推理的形式結(jié)構(gòu) 前提: A1, A2, , Ak 結(jié)論: B 推理的形式結(jié)構(gòu): (A1A2Ak)B,40,推理定律,41,(1) 附加律 A(AB) 前提: A 結(jié)論: AB A(AB)是

15、永真式,42,(2) 化簡律 (AB)A, (AB)B 前提: AB 結(jié)論: A (AB)A是永真式,43,(3) 假言推理 (AB)AB 前提: AB A 結(jié)論: B (AB)A)B是永真式,44,(4) 拒取式 (AB)B A 前提: AB B 結(jié)論: A (AB) B)( A)是永真式,45,(5) 析取三段論 (AB)AB (AB)BA 前提: AB A 結(jié)論: B (AB)A)B是永真式,46,(6) 假言三段論 (AB)(BC)(AC) 前提: AB BC 結(jié)論: AC (AB)(BC)(AC)是永真式,47,(7) 等價(jià)三段論 (AB)(BC)(AC) 前提: AB BC 結(jié)論:

16、 AC (AB)(BC)(AC)是永真式,48,(8) 構(gòu)造性兩難 (AB)(CD)(AC)(BD) 前提: AB CD AC 結(jié)論: BD,49,判斷推理正確的方法 例 前提: p(qr), p, q 結(jié)論: r 方法一: 推理的形式結(jié)構(gòu) 方法二: 從前提推演結(jié)論,50,方法一(形式結(jié)構(gòu)是永真式) (p(qr)pqr (p(qr)pqr （蘊(yùn)涵等值式） (pp)(qr)p)qr （分配律） (qr)q)pr （零律，同一律，交換律） (qq)(rq)pr （分配律） (rqp)r (rqp)r （蘊(yùn)涵等值式） rqpr (rr)qp 1,51,方法二(從前提推演結(jié)論) (p(qr)pq (p

17、(qr)p)q (qr)q （假言推理） r,52,命題邏輯 命題和命題聯(lián)結(jié)詞 命題公式和真值表 命題等值式 命題推理定律,53,數(shù)學(xué)量,運(yùn)算方式,數(shù)學(xué)表達(dá)式,命題,邏輯聯(lián)結(jié)詞,命題公式,計(jì)算表達(dá)式的值,真值表法,54,謂詞邏輯,在命題邏輯中，研究命題和命題的演算。命題演算的基本單位是原子命題。在命題演算中，原子命題不再分解。命題邏輯在推證中有很大的局限性，有些簡單的論斷也不能用命題邏輯進(jìn)行推證。 例如，對(duì)著名的“蘇格拉底三段論”就無法判斷其正確性：“所有的人都是要死的。蘇格拉底是人，所以蘇格拉底是要死的?！?為了克服命題邏輯的局限性，就需要深入分析命題的內(nèi)部的邏輯結(jié)構(gòu)。為此，必須對(duì)原子命題作

18、進(jìn)一步的分解，引入謂詞邏輯的概念。,55,謂詞的概念與量詞 謂詞公式與翻譯 等價(jià)式、蘊(yùn)含式 前束范式,謂詞邏輯,56,謂詞的概念,命題是反映判斷的句子。反映判斷的句子由主語和謂語兩部分組成。主語一般是客體；用以刻劃客體性質(zhì)或關(guān)系的部分即是謂語。在命題中作為主語的客體稱為個(gè)體。而用以描述個(gè)體性質(zhì)或幾個(gè)個(gè)體間關(guān)系的部分稱為謂詞。 例如對(duì)“張三是大學(xué)生”和“李四是大學(xué)生” 這兩個(gè)命題，個(gè)體分別是“張三”和“李四”，謂詞都是“是大學(xué)生”。在作符號(hào)化處理時(shí)，用表示“是大學(xué)生”，用表示“張三”，用表示“李四”。上述兩個(gè)命題可分別表示為()和() ，從而把命題中的主語和謂語分離開來。,57,謂詞的概念(續(xù))

19、,用謂詞表達(dá)命題，必須包括個(gè)體和謂詞兩部分。一般地說，“是”類型的命題可用()表達(dá)。而表示兩個(gè)或兩個(gè)以上客體之間關(guān)系的命題，如“大于”，“在和之中”，可表示成(，)，(，)。這里表示“.大于.”，表示“在和之中”。 表示一個(gè)個(gè)體的性質(zhì)的謂詞稱為一元謂詞，如（e）。而表述個(gè)個(gè)體相互關(guān)系的謂詞稱為元謂詞，可表示為(e1，e2， ， en)。,58,個(gè)體域,對(duì)命題函數(shù)而言，客體變?cè)恼撌龇秶袀€(gè)體域，將所有個(gè)體域的集合(即宇宙間的一切事物)稱為全總個(gè)體域。 客體變?cè)≈档姆秶鷮?duì)命題函數(shù)是否構(gòu)成命題及命題的真值密切相關(guān)。,例如, 用（）表示“是大學(xué)生”，如果的取值范圍是某大學(xué)某班中的全體學(xué)生，則（）是

20、永真式；如果的取值范圍是某中學(xué)某班中的全體學(xué)生，則（）是永假式；如果的取值范圍是某劇場中的觀眾，則（）的真值可真可假，因?yàn)橛^眾中可能有大學(xué)生，也可能有非大學(xué)生,59,量詞,考慮命題“所有的人都是要死的”和“有些人能活百歲以上”的符號(hào)化問題，除個(gè)體變?cè)椭^詞之外，還有對(duì)個(gè)體在數(shù)量上的量化和約束，如“所有的”和“有些”，稱這種表示數(shù)量的詞為量詞。,用符號(hào)表達(dá)“對(duì)所有的”，“對(duì)任一個(gè)”，“對(duì)每一個(gè)”等詞，叫做全稱量詞。,例如， “所有的人都是要死的” 。設(shè)M(x) : x是人。D(x) : x是要死的。則命題可符號(hào)化為：(x)(M(x)D(x)。,用符號(hào)表達(dá)“至少有一個(gè)”，“存在一個(gè)”，“對(duì)某些”等

21、詞，叫做存在量詞。,例如， “有些人能活百歲以上” 。設(shè)M(x):x是人。L(x): x能活百歲以上。則命題可符號(hào)化為：(x)(M(x)L(x)。,60,(1) 個(gè)體域中所有有性質(zhì)F的個(gè)體都有性質(zhì)G，應(yīng)符號(hào)化為 (2) 個(gè)體域中存在有性質(zhì)F同時(shí)有性質(zhì)G的個(gè)體，應(yīng)符號(hào)化為,61,一階謂詞基本概念,個(gè)體（詞） 個(gè)體域 全總個(gè)體域 謂詞(Predicate) 量詞(quantifiers) 全稱量詞(universal quantifier) 存在量詞(existential quantifier),62,謂詞公式定義為 （1）n元謂詞是一個(gè)謂詞公式； （2）若A是謂詞公式，則（A）也是謂詞公式；

22、（3）若A，B是謂詞公式，則（AB）、（AB）、（AB）、（AB）也是謂詞公式； （4）若A是謂詞公式且含有未被量化的個(gè)體變量x，則 xA(x)，XA(x)也是謂詞公式。 （5）有限次地使用（1）（4）所得到的也是謂詞公式。,63,指導(dǎo)變?cè)?xA(x)，xA(x)中的x 相應(yīng)量詞的轄域： xA(x)，xA(x)中的A 約束出現(xiàn)： x，x的轄域中，x的所有出現(xiàn) 自由出現(xiàn)：A中不是約束出現(xiàn)的變?cè)?例： (x)(P(x)Q(x，y),謂詞公式中的基本概念,64,謂詞公式的解釋,謂詞公式中含有個(gè)體變?cè)椭^詞變?cè)?。給定個(gè)體域，將謂詞公式中個(gè)體變?cè)纱_定的個(gè)體來取代，謂詞變?cè)商囟ǖ闹^詞來取代，稱為對(duì)謂

23、詞公式的賦值或解釋。 對(duì)謂詞公式作了這樣的賦值之后，謂詞公式成為命題。,例 求(x)（P(x)Q(x)）的真值，其中(x)：x等于1；(x)：x等于2；且個(gè)體域1,2。 解：(x)(P(x)Q(x) (P(1)Q(1)(P(2)Q(2) ()() ,65,分類：,66,等價(jià)式和蘊(yùn)含式,定義 給定個(gè)體域E上的兩個(gè)謂詞公式和，若對(duì)和中的變項(xiàng)作同樣的賦值，所得命題的真值都相同，則稱謂詞公式和在上是等價(jià)的，記作：。,67,謂詞演算中的等價(jià)式和蘊(yùn)含式的來源可分為如下幾類：,1命題公式的推廣 2. 在有限個(gè)體域中消去量詞 3. 量詞與聯(lián)結(jié)詞之間的關(guān)系 量詞轄域的擴(kuò)張與收縮 量詞分配的等值式 量詞分配的蘊(yùn)含

24、式,68,1命題公式的推廣 用原子謂詞公式取代命題演算等價(jià)公式中的各命題變?cè)?，命題演算的等價(jià)式就轉(zhuǎn)化為謂詞演算的等價(jià)式。例如： A(x) A(x) (x)A(x)(x)B(x) (x)A(x)(x)B(x),69,2在有限個(gè)體域中消去量詞 xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an),70,3量詞與聯(lián)結(jié)詞之間的關(guān)系,(x)A(x) (x)A(x)。 (x)A(x) (x)A(x)。 ,例如，設(shè)A(x)表示“x今天來校上課”，則A(x)表示“x今天沒來校上課”。那麼， 對(duì)(1),“不是所有的人今天都來上課(x)A(x) ”與“有(存在)一些人今天

25、沒來上課(x)A(x)”在意義上是相同的。 對(duì)(2),“今天沒有(不存在)來上課的人(x)A(x) ”與“所有的人今天都沒來上課(x)A(x)”在意義上是相同的。,和式稱為量詞轉(zhuǎn)換律。這里約定，出現(xiàn)在量詞之前的否定不是否定該量詞，而是否定被量化了的整個(gè)命題。例如，(x)A(x) (x)A(x)。,71,等價(jià)式和蘊(yùn)含式(續(xù)),4量詞轄域的擴(kuò)張與收縮,(x)A(x)B(x)（A(x)B） (x)A(x)B(x)（A(x)B） (x)A(x)B(x)（A(x)B） (x)A(x)B(x)（A(x)B） ,當(dāng)個(gè)體域?yàn)橛邢藜痑1, a2,., an時(shí)，我們可以驗(yàn)證式： (x)A(x)B(A(a1)A(a2).A(an)B (A(a1)B)(A(a2)B).(A(an)B) (x)(A(x)B)。,例:證明 (x)(A(x)B) (x)A(x)B 證：(x)(A(x)B) (x)(A(x)B) (x)A(x)B (x)A(x)B(x)A(x)B),72,等價(jià)式和蘊(yùn)含式(續(xù)),5量詞分配的等值式,(x)(A(x)B(x) (x)A(x)(x)B(x) (x)(A(x)B(x) (x)A(x)(x)B(x) ,式的左邊表示“對(duì)于所有的，A(x)和B(x)都是真的”；右邊表示“對(duì)于所有