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

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

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

4、僅當為假。 例如，設：今天是星期二。 則：今天不是星期二。,9,定義2 合取聯結詞,設，表示兩個命題，復合命題“且”叫命題與的合取，記作。記號叫合取聯結詞。為真，當且僅當，同時為真。 例如，設: 2是素數。 : 2是偶數。R： 2是奇數。 則：2既是素數又是偶數。(真值為真) R：2既是素數又是奇數。(真值為假),10,定義3 析取聯結詞,設，為二命題，復合命題“或”稱作與的析取，記作，叫析取聯結詞。為真，當且僅當，之中至少有一為真。 例如，設：2是素數。：2是偶數。 R： 2是奇數。 則：2是素數或2是偶數。(真值為真) R：2是素數或2是奇數。(真值為真),11,2-30或今天天氣很好。,

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

6、明天不下雨,我們放假,明天下雨,我們不放假,明天下雨,我們放假,15,定義5 等價聯結詞,設,為二命題，復合命題“當且僅當”稱為與的等價式，記作。叫等價聯結詞，也記作iff。為真當且僅當,真值相同。 例如，2+24當且僅當雪是白的。 設： 2+24 。：雪是白的。 則原命題表示為：。,16,命題一般用大寫英文字母表示。表示命題的符號叫命題標識符。 例如，用表示“雪是黑的”，記作“：雪是黑的”。 如果一個命題標識符表示某個確定的命題，則稱為命題常量。特別地，真命題(用T表示)和假命題(用F表示)是命題常量。 如果一個命題標識符表示不確定的命題，則稱為命題變元。,命題常量和命題變元,命題變元不是命

7、題。在命題演算中，對命題變元指定相應的真值(真或假)，稱為對命題變元的真值指派。 集合T,F是命題變元的值域。,17,相應的真值表,18,命題公式,設P和Q是任意兩個命題，則下列命題都是復合命題,設P和Q是命題變元，則上述公式均稱作命題公式。P和Q稱作命題公式的分量。,19,命題公式,(1)單個命題變元（或常元）是命題公式； (2)若A是命題公式，則(A)是命題公式； (3)若A,B是命題公式，則（AB），（AB）, (AB), (A B)也是命題公式； (4)只有有限次應用(1)-(3)形成的符號串才是命題公式。,注意： 命題公式是沒有真假值的，僅當在一個公式中命題變元用確定的命題代入時，才

8、得到一個值。,20,真值表(truth table),定義設為一命題公式，P1, P2，, Pn為出現在中的所有命題變元，簡記為（P1, P2，, Pn）。給命題變元P1, P2，, Pn指定一組真值，稱為對的一個指派或一個賦值。含有個命題變元的命題公式（P1, P2，, Pn）共有n個指派。將命題公式（P1, P2，, Pn）在所有指派之下取值的情況列成表，叫的真值表。,21,真值表 命題形式A在其所有可能的賦值下取得的值列成的表； n元真值函數 F: 0, 1n 0，1 (n1)。,22,聯結詞的真值表,23,A的一個賦值: n個命題變元 成真賦值 成假賦值 重言式（永真式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,等值式（等價公式）,給定兩個命題公式（P1, P2，, Pn）和（P1, P2，, Pn），若對P1, P2，, Pn的任一組真值指派，與的真值都相同，則稱與等價或邏輯相等。記作。,例4 構造命題公式（PQ）和PQ的真值表。,

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

11、交換律,結合律,分配律,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,零律,同一律,排中律,矛盾律,(對偶原理: -互換, 0-1互換),33,A A AB AB AB (AB)(BA),雙重否定律,蘊涵等值式,等價等值式,34,AB AB AB BA (AB)(AB) A,等價否定等值式,假言易位,歸謬論,牢固記住并能熟練運用， 是學好離散數學的關鍵之一,35,設是合式公式中的一個部分，且也是一個合式公式

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

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

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

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

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

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

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

19、,用謂詞表達命題，必須包括個體和謂詞兩部分。一般地說，“是”類型的命題可用()表達。而表示兩個或兩個以上客體之間關系的命題，如“大于”，“在和之中”，可表示成(，)，(，)。這里表示“.大于.”，表示“在和之中”。 表示一個個體的性質的謂詞稱為一元謂詞，如（e）。而表述個個體相互關系的謂詞稱為元謂詞，可表示為(e1，e2， ， en)。,58,個體域,對命題函數而言，客體變元的論述范圍叫個體域，將所有個體域的集合(即宇宙間的一切事物)稱為全總個體域。 客體變元取值的范圍對命題函數是否構成命題及命題的真值密切相關。,例如, 用（）表示“是大學生”，如果的取值范圍是某大學某班中的全體學生，則（）是

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

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

22、（3）若A，B是謂詞公式，則（AB）、（AB）、（AB）、（AB）也是謂詞公式； （4）若A是謂詞公式且含有未被量化的個體變量x，則 xA(x)，XA(x)也是謂詞公式。 （5）有限次地使用（1）（4）所得到的也是謂詞公式。,63,指導變元： xA(x)，xA(x)中的x 相應量詞的轄域： xA(x)，xA(x)中的A 約束出現： x，x的轄域中，x的所有出現 自由出現：A中不是約束出現的變元 例： (x)(P(x)Q(x，y),謂詞公式中的基本概念,64,謂詞公式的解釋,謂詞公式中含有個體變元和謂詞變元。給定個體域，將謂詞公式中個體變元由確定的個體來取代，謂詞變元由特定的謂詞來取代，稱為對謂

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

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

25、沒來上課(x)A(x)”在意義上是相同的。 對(2),“今天沒有(不存在)來上課的人(x)A(x) ”與“所有的人今天都沒來上課(x)A(x)”在意義上是相同的。,和式稱為量詞轉換律。這里約定，出現在量詞之前的否定不是否定該量詞，而是否定被量化了的整個命題。例如，(x)A(x) (x)A(x)。,71,等價式和蘊含式(續(xù)),4量詞轄域的擴張與收縮,(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） ,當個體域為有限集a1, a2,., an時，我們可以驗證式： (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,等價式和蘊含式(續(xù)),5量詞分配的等值式,(x)(A(x)B(x) (x)A(x)(x)B(x) (x)(A(x)B(x) (x)A(x)(x)B(x) ,式的左邊表示“對于所有的，A(x)和B(x)都是真的”；右邊表示“對于所有