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

1、1第一編 集合論第一章 集合21.1 預(yù)備知識（prerequisites）命題邏輯和謂詞邏輯是數(shù)理邏輯中最基本的內(nèi)容。命題邏輯和謂詞邏輯是數(shù)理邏輯中最基本的內(nèi)容。l 十九世紀(jì)中后期，德國數(shù)學(xué)家萊布尼茲、英國數(shù)學(xué)家十九世紀(jì)中后期，德國數(shù)學(xué)家萊布尼茲、英國數(shù)學(xué)家布爾和邏輯學(xué)家懷海特、羅素為數(shù)理邏輯的產(chǎn)生和發(fā)布爾和邏輯學(xué)家懷海特、羅素為數(shù)理邏輯的產(chǎn)生和發(fā)展有突出貢獻(xiàn)。展有突出貢獻(xiàn)。l 從二十世紀(jì)從二十世紀(jì)4040年代起，數(shù)理邏輯成為計算機(jī)科學(xué)的重年代起，數(shù)理邏輯成為計算機(jī)科學(xué)的重要基礎(chǔ)理論之一。如布爾代數(shù)在計算機(jī)硬件設(shè)計中發(fā)要基礎(chǔ)理論之一。如布爾代數(shù)在計算機(jī)硬件設(shè)計中發(fā)揮了重大作用；形式語言的研究

2、為建立計算機(jī)語言提揮了重大作用；形式語言的研究為建立計算機(jī)語言提供了基礎(chǔ)。供了基礎(chǔ)。3命題和命題聯(lián)結(jié)詞命題公式和真值表命題等值式命題推理定律命題邏輯4 命題是客觀上能判明真假的陳述句。當(dāng)命題為真時，稱命題的真值為“真”；否則，說命題的真值為“假”。用T或1表示“真”，用F或0表示“假”。 （ Proposition: a statement that is either true or false,but not both.） 所有這些命題，都應(yīng)具有確定的真值。5判斷下列語句是不是命題:(1) 天氣多好啊!(2) 你去哪里？(3) X3。(4) 別的星球有生物。(5) 我正在說慌。解：(1)(

3、1)是感嘆句；是感嘆句；(2)(2)是疑問句；它們都不是命題。是疑問句；它們都不是命題。 (3) (3) 真假要視的值而定，因此這個語句無確定真假要視的值而定，因此這個語句無確定真值。它不是命題。真值。它不是命題。 (4) (4)的真實性目前還無法判明，但在客觀上，是真的真實性目前還無法判明，但在客觀上，是真是假，二者必居其一。因此它是命題。是假，二者必居其一。因此它是命題。 (5) (5)同樣不能判明真假。如說該命題為真，但原語同樣不能判明真假。如說該命題為真，但原語句卻說句卻說“本命題為假本命題為假”；如果說它為假，卻又肯定了；如果說它為假，卻又肯定了它它( (本命題本命題) )是真的，這

4、樣造成了自相矛盾的結(jié)果！這是真的，這樣造成了自相矛盾的結(jié)果！這是所謂悖論。是所謂悖論。6 無法繼續(xù)分解的簡單陳述句，稱為簡單命題或無法繼續(xù)分解的簡單陳述句，稱為簡單命題或原子命題原子命題。(不包含任何不包含任何“與、或、非與、或、非”等聯(lián)等聯(lián)結(jié)詞的命題結(jié)詞的命題) 由一個或幾個簡單命題通過由一個或幾個簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)詞復(fù)合而成的復(fù)合而成的命題，稱為命題，稱為復(fù)合命題復(fù)合命題。 (1)期中考試，張三沒有考及格期中考試，張三沒有考及格 (2)期中考試，張三和李四都考及格了期中考試，張三和李四都考及格了 (3)期中考試，張三和李四有人考期中考試，張三和李四有人考90分分 (4)如果張三考如果張

5、三考90分，李四也能考分，李四也能考90分分 (5)張三能考張三能考90分當(dāng)且僅當(dāng)李四也考分當(dāng)且僅當(dāng)李四也考90分分7 否定聯(lián)結(jié)詞 合取聯(lián)結(jié)詞 析取聯(lián)結(jié)詞 蘊涵聯(lián)結(jié)詞 等價聯(lián)結(jié)詞 命題聯(lián)結(jié)詞8定義1 否定聯(lián)結(jié)詞 設(shè)為命題，復(fù)合命題非，叫的設(shè)為命題，復(fù)合命題非，叫的否定式，記作否定式，記作 。記號。記號 叫叫否定聯(lián)結(jié)否定聯(lián)結(jié)詞詞。 為真當(dāng)且僅當(dāng)為假。為真當(dāng)且僅當(dāng)為假。 例如，設(shè)：今天是星期二。 則：今天不是星期二。9定義2 合取聯(lián)結(jié)詞 設(shè)，表示兩個命題，復(fù)合命題設(shè)，表示兩個命題，復(fù)合命題“且且”叫命題與的合取，記作叫命題與的合取，記作。記號。記號叫合取聯(lián)結(jié)詞。叫合取聯(lián)結(jié)詞。為真，當(dāng)且僅當(dāng)，為真，

6、當(dāng)且僅當(dāng)，同時為真。同時為真。 例如，設(shè): 2是素數(shù)。 : 2是偶數(shù)。R： 2是奇數(shù)。 則：2既是素數(shù)又是偶數(shù)。(真值為真) R：2既是素數(shù)又是奇數(shù)。(真值為假)10定義3 析取聯(lián)結(jié)詞 設(shè)，為二命題，復(fù)合命題設(shè)，為二命題，復(fù)合命題“或或”稱稱作與的析取，記作作與的析取，記作，叫析取叫析取聯(lián)結(jié)詞。聯(lián)結(jié)詞。為真，當(dāng)且僅當(dāng)，之為真，當(dāng)且僅當(dāng)，之中至少有一為真。中至少有一為真。 例如，設(shè)：2是素數(shù)。：2是偶數(shù)。 R： 2是奇數(shù)。 則：2是素數(shù)或2是偶數(shù)。(真值為真) R：2是素數(shù)或2是奇數(shù)。(真值為真)112-30或今天天氣很好。他今天騎車或走路來上課。 從理科1號樓到圖書館要2分鐘或4分鐘。 12注

7、： “或”有兩種標(biāo)準(zhǔn)用法， 張三或李四考了90分（相容“或”） 第一節(jié)課上數(shù)學(xué)或者上英語13定義4 蘊涵聯(lián)結(jié)詞 設(shè)，是二命題，復(fù)合命題設(shè)，是二命題，復(fù)合命題“如，則如，則”稱為與的稱為與的蘊涵式蘊涵式，記作，記作, 其中其中叫前件或前題，叫后件或結(jié)論。叫前件或前題，叫后件或結(jié)論。為真當(dāng)且僅當(dāng)真和假不同時成立為真當(dāng)且僅當(dāng)真和假不同時成立。 例如，如果明天天晴就開運動會。 設(shè)：明天天晴。:明天開運動會。 則原命題表示為：。 14 蘊涵式、蘊涵聯(lián)結(jié)詞pqp q001011100111如果明天下雨，我們就放假明天不下雨我們不放假明天不下雨我們放假明天下雨我們不放假明天下雨我們放假15定義5 等價聯(lián)結(jié)詞

8、 設(shè)設(shè),為二命題，復(fù)合命題為二命題，復(fù)合命題“當(dāng)當(dāng)且僅當(dāng)且僅當(dāng)”稱為與的稱為與的等價式等價式，記，記作作。叫叫等價等價聯(lián)結(jié)詞，也記聯(lián)結(jié)詞，也記作作iff。為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng),真真值相同。值相同。 例如，2+24當(dāng)且僅當(dāng)雪是白的。 設(shè)： 2+24 。：雪是白的。 則原命題表示為：。16 命題一般用大寫英文字母表示。表示命題的符號叫命題一般用大寫英文字母表示。表示命題的符號叫命命題標(biāo)識符題標(biāo)識符。 例如，用表示“雪是黑的”，記作“：雪是黑的”。 如果一個命題標(biāo)識符表示某個確定的命題，則稱為如果一個命題標(biāo)識符表示某個確定的命題，則稱為命命題常量題常量。特別地，真命題。特別地，真命題( (用用T

9、 T表示表示) )和假命題和假命題( (用用F F表示表示) )是命題常量。是命題常量。 如果一個命題標(biāo)識符表示不確定的命題，則稱為如果一個命題標(biāo)識符表示不確定的命題，則稱為命題命題變元變元。命題常量和命題變元命題變元不是命題命題變元不是命題。在命題演算中，對命題變元指定相應(yīng)。在命題演算中，對命題變元指定相應(yīng)的真值的真值( (真或假真或假) )，稱為對命題變元的，稱為對命題變元的真值指派真值指派。 集合集合 T,FT,F是是命題變元的值域命題變元的值域。17(negation)： p， p為真當(dāng)且僅當(dāng)p為假(conjunction):p q， p q為真當(dāng)且僅當(dāng)p,q同時為真(disjunct

10、ion):p q， p q為假當(dāng)且僅當(dāng)p,q同時為假(implication):pq，pq為假當(dāng)且僅當(dāng)p為真而q為假 (biconditional):pq，pq否定式合為真當(dāng)且取式析取式蘊涵式等僅當(dāng)p與q價式的真值相同相應(yīng)的真值表相應(yīng)的真值表18命題公式設(shè)P和Q是任意兩個命題，則下列命題都是復(fù)合命題,()(),()P PQ PQRQ PQP設(shè)P和Q是命題變元命題變元，則上述公式均稱作命題公式命題公式。P和Q稱作命題公式的分量。19命題公式 (1)單個命題變元（或常元）是命題公式； (2)若A是命題公式，則(A)是命題公式； (3)若A,B是命題公式，則（AB），（AB）, (AB), (A B

11、)也是命題公式； (4)只有有限次應(yīng)用(1)-(3)形成的符號串才是命題公式。注意： 命題公式是沒有真假值的，僅當(dāng)在一個公式中命題變元用確定的命題代入時，才得到一個值。20真值表(truth table)定義設(shè)為一命題公式，P1, P2，, Pn為出現(xiàn)在中的所有命題變元，簡記為（P1, P2，, Pn）。給命題變元P1, P2，, Pn指定一組真值，稱為對的一個指派或一個賦值。含有個命題變元的命題公式（P1, P2，, Pn）共有n個指派。將命題公式（P1, P2，, Pn）在所有指派之下取值的情況列成表，叫的真值表。21 真值表 命題形式A在其所有可能的賦值下取得的值列成的表； n元真值函數(shù)

12、 F: 0, 1n 0，1 (n1)。22聯(lián)結(jié)詞的真值表P Q P PQ PQ PQ PQ 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 23 A的一個賦值賦值: n個命題變元 成真賦值成真賦值 成假賦值成假賦值 重言式重言式（永真式（永真式tautology）P P = 1 矛盾式矛盾式（永假式（永假式contradiction）P P = 0 可滿足式可滿足式24 公式分類 重言式 矛盾式 可滿足式重言式25p 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 賦值

13、 可滿足式 矛盾式 重言式 (永假式) (永真式) 26等值式（等價公式） 給定兩個命題公式（給定兩個命題公式（P P1 1, P, P2 2，, P, Pn n）和和（P P1 1, P, P2 2，, P, Pn n），），若對若對P P1 1, P, P2 2，, P, Pn n的任的任一組真值指派，與的真值都相同，則稱一組真值指派，與的真值都相同，則稱與等價或邏輯相等。記作與等價或邏輯相等。記作。例4 構(gòu)造命題公式構(gòu)造命題公式 （PQ）和和 P Q的真值表的真值表。P Q PQ （PQ） P Q PQ 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0

14、1 1 1 0 0 0 0 對于、的任一種真值指派，對于、的任一種真值指派， （PQ）與與 P Q都有相同的真值，都有相同的真值，所以這所以這兩個命題公式是等價的。兩個命題公式是等價的。27 為書寫方便而省略括號 公式最外層的括號可以省略 聯(lián)結(jié)詞運算優(yōu)先級別 同一個聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無括號，則從左到右運算28例題：層次法構(gòu)造真值表(p (pq) (pq)(p (pq) (pq)(p (pq) (pq)(p (pq) (pq)p qpq pq p(pq) (pq)公式公式0 00 11 01 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 029等值式等值式(l

15、ogical equivalences),()(),()()()()(),()()(),(),()11,000,11ABBA ABBAABCABCABCABCABCABACABCABACABABABABAABA AABAAAAA AAAA 冪等律AAA, AAA交換律結(jié)合律分配律的摩根律()()吸收律零律同一律排中律矛盾律0()()()()AAAAABABABABBAABABABBAABABA 雙重否定律蘊涵等值式等價等值式等價否定等值式假言易位歸繆論30 AAA, AAA A(BC) (AB)(AC) A(BC) (AB)(AC) ABBA, ABBA(AB)C A(BC) (AB)C A(

16、BC)3132A1 1, A0 0 A0 A, A1 A AA 1 AA 0 (對偶原理: -互換, 0-1互換)33A A AB AB AB (AB)(BA) 34AB AB AB BA (AB)(AB) A35 設(shè)是合式公式中的一個部分，且也是一個合設(shè)是合式公式中的一個部分，且也是一個合式公式，則稱是的式公式，則稱是的子公式子公式。 例例如，設(shè)：如，設(shè)： ( (PQ)PQ)（Q(RQ(R S)S)），），則則PQPQ、 RR S S、 S S、 Q(R Q(R S)S)都是的子公式。都是的子公式。置換規(guī)則定理（置換規(guī)則）： 設(shè)X是合式公式中的子公式，若是一個合式公式，且 ，用置換中的，得到

17、新的合式公式，則。證明：證明：與除替換部分外均相同，又由于替換部分與除替換部分外均相同，又由于替換部分，即是說對任一指派，與真值相同，那么與對，即是說對任一指派，與真值相同，那么與對任一真值指派也應(yīng)有相同的真值。故任一真值指派也應(yīng)有相同的真值。故。36等值演算： 由已知的等值式，應(yīng)用置換規(guī)則推演出新的等值式的過程。等值演算 P (Q R) P ( Q R) P ( Q R) ( P Q) R ( P Q) R ( P Q) R37 給定命題公式(P1, P2，, Pn)，如果用某個命題公式Bi取代中的某個變元Pi，并且用Bi取代中出現(xiàn)的所有Pi，這樣得到的命題公式稱為命題公式的代入實例。 例例

18、如，設(shè)：如，設(shè)：P(QP)，用用(RS)取代中的命題取代中的命題變元得：變元得：(RS)(Q(RS)，是的代入實例。是的代入實例。代入代入規(guī)則規(guī)則定理（代入規(guī)則）： 一個重言式的代入實例仍然是一個重言式。證明：證明： 由于重言式的真值與真值指派無關(guān)，故對同一命題由于重言式的真值與真值指派無關(guān)，故對同一命題變元變元都用某個都用某個命題公式命題公式代替代替，該重言式的真值仍為。，該重言式的真值仍為。例例 證明證明(PS)R) (PS)R)為重言式為重言式證：證：因因P P T，根據(jù)根據(jù)代入規(guī)則代入規(guī)則 (PS)R) (PS)R)T38在太平洋中有AB兩個相鄰的小島。A島居民都是誠實的人，B島的居民

19、都是騙子。當(dāng)你問一個問題時，A島的居民會告訴你正確的答案，而B島的居民給你的答案都是錯誤的。一天，一個旅游者獨自登上了兩島中的某個島。他分辨不清這個島是A島還是B島，只知道這個島上的人既有本島的居民又有另一島的來客。他想問島上的人“這是A島還是B島？”卻又無法判斷被問者的答案是否正確。旅游者動腦筋想了會一兒，終于想出一個辦法，他只需要問他所遇到的任意一人一句話，就能從對方的回答中準(zhǔn)確無誤地斷定這里是哪個島。你能猜出旅游者所問的問題嗎？例:命題邏輯應(yīng)用39命題邏輯推理“”“”ABAB若推理的形式結(jié)構(gòu)為重言式，則稱推理正確。用表示是重言式1. 推理的形式結(jié)構(gòu) 前提: A1, A2, , Ak結(jié)論:

20、 B 推理的形式結(jié)構(gòu): (A1A2Ak)B 40()()()BCCCCCDBD 附加律AAB化簡律AB)A, AB)假言推理定律 (AB) AB拒取式推理定律 (AB)BA析取三段論推理定律 (AB)BA;(AB)AB假言三段論推理定律 (AB)B)A等價三段論推理定律 (AB)B)A構(gòu)造性二難推理定律 (AB) (AC)推理定律推理定律41(1) 附加律 A(AB) 前提: A 結(jié)論: AB A(AB)是永真式 42(2) 化簡律 (AB)A, (AB)B前提: AB 結(jié)論: A (AB)A是永真式43(3) 假言推理 (AB)AB 前提: AB A 結(jié)論: B (AB)A)B是永真式 44

21、(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) 等價三段論 (AB)(BC)(AC) 前提: AB BC 結(jié)論: AC (AB)(BC)(AC)是永真式 48(8) 構(gòu)造性兩難 (AB)(CD)(AC)(BD) 前提: AB CD AC 結(jié)論: BD 49判斷推理正確的方法判斷推理正確的方法 例前提: p(qr),

22、 p, q 結(jié)論: r 方法一方法一: 推理的形式結(jié)構(gòu) 方法二方法二: 從前提推演結(jié)論 50方法一方法一(形式結(jié)構(gòu)是永真式) (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方法二方法二(從前提從前提推演推演結(jié)論結(jié)論) (p(qr)pq (p(qr)p)q (qr)q （假言推理）假言推理） r 52 命題邏輯命題和命題聯(lián)結(jié)詞命題公式和

23、真值表命題等值式命題推理定律5354謂詞邏輯 在命題邏輯中，研究命題和命題的演算。命題演算在命題邏輯中，研究命題和命題的演算。命題演算的基本單位是原子命題。在命題演算中，原子命題不的基本單位是原子命題。在命題演算中，原子命題不再分解。命題邏輯在推證中有很大的局限性，有些簡再分解。命題邏輯在推證中有很大的局限性，有些簡單的論斷也不能用命題邏輯進(jìn)行推證。單的論斷也不能用命題邏輯進(jìn)行推證。 例如，對著名的例如，對著名的“蘇格拉底三段論蘇格拉底三段論”就無法判斷其就無法判斷其正確性：正確性：“所有的人都是要死的。蘇格拉底是人，所所有的人都是要死的。蘇格拉底是人，所以蘇格拉底是要死的。以蘇格拉底是要死的

24、?！?為了克服命題邏輯的局限性，就需要深入分析命為了克服命題邏輯的局限性，就需要深入分析命題的內(nèi)部的邏輯結(jié)構(gòu)。為此，必須對原子命題作進(jìn)一題的內(nèi)部的邏輯結(jié)構(gòu)。為此，必須對原子命題作進(jìn)一步的分解，引入謂詞邏輯的概念。步的分解，引入謂詞邏輯的概念。55謂詞的概念與量詞謂詞公式與翻譯等價式、蘊含式前束范式謂詞邏輯56謂詞的概念 命題是反映判斷的句子。反映判斷的句子由主語和命題是反映判斷的句子。反映判斷的句子由主語和謂語兩部分組成。主語一般是客體；用以刻劃客體性質(zhì)謂語兩部分組成。主語一般是客體；用以刻劃客體性質(zhì)或關(guān)系的部分即是謂語。或關(guān)系的部分即是謂語。在命題中作為主語的客體稱為個體。而。而用以描述個體

25、性質(zhì)或幾個個體間關(guān)系的部分稱為謂詞。 例如對例如對“張三是大學(xué)生張三是大學(xué)生”和和“李四是大學(xué)生李四是大學(xué)生” 這兩這兩個命題，個體分別是個命題，個體分別是“張三張三”和和“李四李四”，謂詞謂詞都是都是“是大學(xué)生是大學(xué)生”。在作符號化處理時，用表示。在作符號化處理時，用表示“是大學(xué)是大學(xué)生生”，用表示，用表示“張三張三”，用表示，用表示“李四李四”。上述兩。上述兩個命題可分別表示為個命題可分別表示為()和和() ，從而把命題中的，從而把命題中的主語和謂語分離開來。主語和謂語分離開來。57謂詞的概念(續(xù)) 用謂詞表達(dá)命題，必須包括用謂詞表達(dá)命題，必須包括個體和謂詞個體和謂詞兩部分。一般地說，兩部

26、分。一般地說，“是是”類型的命題可用類型的命題可用( () )表達(dá)。而表示兩個或兩表達(dá)。而表示兩個或兩個以上客體之間關(guān)系的命題，如個以上客體之間關(guān)系的命題，如“大于大于”，“在在和之中和之中”，可表示成，可表示成( (，) )，( (，) )。這。這里表示里表示“.大于大于.”，表示，表示“在在和和之中之中”。 表示一個個體的性質(zhì)的謂詞稱為一元謂詞，如（e）。而表述個個體相互關(guān)系的謂詞稱為元謂詞，可表示為(e1，e2， ， en)。 58個體域 對命題函數(shù)而言，客體變元的論述范圍叫個體域，將所有個體域的集合(即宇宙間的一切事物)稱為全總個體域。 客體變元取值的范圍對命題函數(shù)是否構(gòu)成命題及命題的

27、真值密切相關(guān)。 例如例如, 用（）表示用（）表示“是大學(xué)生是大學(xué)生”，如果的取值范圍，如果的取值范圍是某大學(xué)某班中的全體學(xué)生，則（）是永真式；如果的是某大學(xué)某班中的全體學(xué)生，則（）是永真式；如果的取值范圍是某中學(xué)某班中的全體學(xué)生，則（）是永假式；取值范圍是某中學(xué)某班中的全體學(xué)生，則（）是永假式；如果的取值范圍是某劇場中的觀眾，則（）的真值可真如果的取值范圍是某劇場中的觀眾，則（）的真值可真可假，因為觀眾中可能有大學(xué)生，也可能有非大學(xué)生可假，因為觀眾中可能有大學(xué)生，也可能有非大學(xué)生59量詞 考慮命題考慮命題“所有的所有的人都是要死的人都是要死的”和和“有些有些人能活百歲以上人能活百歲以上”的符號

28、化問題，的符號化問題，除個體變元和謂詞之外，還有除個體變元和謂詞之外，還有對個體在數(shù)量上的對個體在數(shù)量上的量化和約束量化和約束，如，如“所有的所有的”和和“有些有些”，稱這種表示數(shù)量的詞為，稱這種表示數(shù)量的詞為量詞量詞。 用符號 表達(dá)“對所有的”，“對任一個”，“對每一個”等詞，叫做全稱量詞。 例如，例如， “所有的人都是要死的所有的人都是要死的” 。設(shè)。設(shè)M(x) : x是人。是人。D(x) : x是要死的是要死的。則命題可符號化為：。則命題可符號化為：( x)(M(x)D(x)。 用符號 表達(dá)“至少有一個”，“存在一個”，“對某些”等詞，叫做存在量詞。 例如，例如， “有些人能活百歲以上有

29、些人能活百歲以上” 。設(shè)。設(shè)M(x):x是人。是人。L(x): x能活百歲以上能活百歲以上。則命題可符號化為：。則命題可符號化為：( x)(M(x) L(x)。60 (1) 個體域中所有有性質(zhì)F的個體都有性質(zhì)G，應(yīng)符號化為 (2) 個體域中存在有性質(zhì)F同時有性質(zhì)G的個體，應(yīng)符號化為( ( )( )x F xG x( ( )( )x F xG x61一階謂詞基本概念 個體（詞） 個體域 全總個體域 謂詞(Predicate) 量詞(quantifiers)全稱量詞(universal quantifier)存在量詞(existential quantifier)62謂詞公式謂詞公式定義為定義為（

30、1）n元謂詞是一個謂詞公式；元謂詞是一個謂詞公式；（2）若）若A是謂詞公式，則（是謂詞公式，則（A）也是謂詞公式；也是謂詞公式；（3）若）若A，B是謂詞公式，則（是謂詞公式，則（AB）、（）、（AB）、）、（AB）、（）、（AB）也是謂詞公式；也是謂詞公式；（4）若）若A是謂詞公式且含有未被量化的個體變量是謂詞公式且含有未被量化的個體變量x，則則 xA(x)， XA(x)也是謂詞公式。也是謂詞公式。（5）有限次地使用（）有限次地使用（1）（4）所得到的也是謂詞公式。）所得到的也是謂詞公式。63 指導(dǎo)變元： xA(x)， xA(x)中的中的x 相應(yīng)量詞的轄域： xA(x)， xA(x)中的中的A

31、 約束出現(xiàn)： x， x的轄域中，的轄域中，x的所有出現(xiàn)的所有出現(xiàn) 自由出現(xiàn)：A中不是約束出現(xiàn)的變元中不是約束出現(xiàn)的變元 例：( ( x)(P(x)Q(xx)(P(x)Q(x，y)y)謂詞公式中的基本概念64謂詞公式的解釋謂詞公式的解釋 謂詞公式中含有個體變元和謂詞變元。給定個體域，謂詞公式中含有個體變元和謂詞變元。給定個體域，將謂詞公式中個體變元由確定的個體來取代，謂詞變元由特定的謂詞來取代，稱為對謂詞公式的賦值或解釋。對謂詞公式作了這樣的賦值之后，謂詞公式成為命題。對謂詞公式作了這樣的賦值之后，謂詞公式成為命題。例例 求求( ( x)x)（P(x)Q(x)P(x)Q(x)）的真值，其中的真值

32、，其中( (x)x)：x x等等于于1 1；( (x)x)：x x等于等于2 2；且個體域；且個體域1,21,2。解解：( ( x)(P(x)Q(x)x)(P(x)Q(x) (P(1)Q(1)(P(2)Q(2)(P(1)Q(1)(P(2)Q(2) ( ()()() ) 65可滿足公式不可滿足公式（永假式）永真式可真可假式（不確定式）謂詞公式分類：66等價式和蘊含式定義 給定個體域E上的兩個謂詞公式和，若對和中的變項作同樣的賦值，所得命題的真值都相同，則稱謂詞公式和在上是等價的，記作：。67謂詞演算中的等價式和蘊含式的來源可分為如下幾類：謂詞演算中的等價式和蘊含式的來源可分為如下幾類：1命題公式

33、的推廣2. 在有限個體域中消去量詞3. 量詞與聯(lián)結(jié)詞 之間的關(guān)系 4. 量詞轄域的擴(kuò)張與收縮5. 量詞分配的等值式6. 量詞分配的蘊含式681命題公式的推廣 用原子謂詞公式取代命題演算等價公式中的各命題變用原子謂詞公式取代命題演算等價公式中的各命題變元，命題演算的等價式就轉(zhuǎn)化為謂詞演算的等價式。例元，命題演算的等價式就轉(zhuǎn)化為謂詞演算的等價式。例如：如： A(x) A(x) ( x)A(x)( x)B(x) ( x)A(x)( x)B(x)692在有限個體域中有限個體域中消去量詞 xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an)703量詞與聯(lián)結(jié)詞 之

34、間的關(guān)系 ( x)A(x) ( x) A(x)。 ( x)A(x) ( x) A(x)。 例如，設(shè)例如，設(shè)A(x)表示表示“x今天來校上課今天來校上課”，則，則 A(x)表示表示“x今天沒來今天沒來校上課校上課”。那麼，。那麼， 對對(1),“不是所有的人今天都來上課不是所有的人今天都來上課 ( x)A(x) ”與與“有有(存在存在)一些一些人今天沒來上課人今天沒來上課( x) A(x)”在意義上是相同的。在意義上是相同的。 對對(2),“今天沒有今天沒有(不存在不存在)來上課的人來上課的人 ( x)A(x) ”與與“所有的人今所有的人今天都沒來上課天都沒來上課( x) A(x)”在意義上是相

35、同的。在意義上是相同的。 和式稱為和式稱為量詞轉(zhuǎn)換律。這里這里約定，出現(xiàn)在量詞之前的否定不是否定該量詞，而是否定被量化了的整個命題。例如， ( x)A(x) ( x)A(x)。71等價式和蘊含式(續(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)個體域為有限集當(dāng)個體域為有限集a1, a2,., an時，我們可以驗證式：時，我們可以驗證式： ( x)A(x)B(A(a1)A(a2).A(an)B (A(a1)B)(A(a2)B).(A(an)B) (

36、 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)都是真的都是真的”；右邊表示；右邊表示“對于所有的，對于所有的，A(x)是真的；同時對于所有的，是真的；同時對于所有的，B(x)也是真的也是真的”。顯然，這兩個命

37、題是等價的。例如，顯然，這兩個命題是等價的。例如，“聯(lián)歡會上所有的人既唱歌又跳舞聯(lián)歡會上所有的人既唱歌又跳舞”和和“聯(lián)歡會上所有的人唱歌且所有的人跳舞聯(lián)歡會上所有的人唱歌且所有的人跳舞”的意義相同。的意義相同。 式左邊的命題可表述成式左邊的命題可表述成“存在一個，能使存在一個，能使()為真或者能使為真或者能使()為真為真”；右邊的命題可表述成；右邊的命題可表述成“存在使存在使()為真，或者存在使為真，或者存在使()為真為真”。顯然，這兩個命題也是等價的。例如，。顯然，這兩個命題也是等價的。例如，“聯(lián)歡會上有人聯(lián)歡會上有人唱歌或跳舞唱歌或跳舞”和和“聯(lián)歡會上有人唱歌，或有人跳舞聯(lián)歡會上有人唱歌，或有人跳舞”的意義相同。的意義相同。73等價式和蘊含式(續(xù))6 6量詞分配的蘊含式 ( x)A(x)( x)B(x) ( x)(A(x)B(x) ( x)(A(x)B(x) ( x)A(x)( x)B(x) 例