第一編 集合論

1、 Peking University1第一編 集合論第一章 集合 Peking University21.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ì)算機(jī)科學(xué)的重年代起，數(shù)理邏輯成為計(jì)算機(jī)科學(xué)的重要基礎(chǔ)理論之一。如布爾代數(shù)在計(jì)算機(jī)硬件設(shè)計(jì)中發(fā)要

2、基礎(chǔ)理論之一。如布爾代數(shù)在計(jì)算機(jī)硬件設(shè)計(jì)中發(fā)揮了重大作用；形式語言的研究為建立計(jì)算機(jī)語言提揮了重大作用；形式語言的研究為建立計(jì)算機(jī)語言提供了基礎(chǔ)。供了基礎(chǔ)。 Peking University3命題和命題聯(lián)結(jié)詞命題公式和真值表命題等值式命題推理定律命題邏輯 Peking University4 命題是客觀上能判明真假的陳述句。當(dāng)命題為真時，稱命題的真值為“真”；否則，說命題的真值為“假”。用T或1表示“真”，用F或0表示“假”。 （ Proposition: a statement that is either true or false,but not both.） 所有這些命題，都應(yīng)具有確

3、定的真值。 Peking University5判斷下列語句是不是命題:(1) 天氣多好啊!(2) 你去哪里？(3) X3。(4) 別的星球有生物。(5) 我正在說慌。解：(1)(1)是感嘆句；是感嘆句；(2)(2)是疑問句；它們都不是命題。是疑問句；它們都不是命題。 (3) (3) 真假要視的值而定，因此這個語句無確定真假要視的值而定，因此這個語句無確定真值。它不是命題。真值。它不是命題。 (4) (4)的真實(shí)性目前還無法判明，但在客觀上，是真的真實(shí)性目前還無法判明，但在客觀上，是真是假，二者必居其一。因此它是命題。是假，二者必居其一。因此它是命題。 (5) (5)同樣不能判明真假。如說該命

4、題為真，但原語同樣不能判明真假。如說該命題為真，但原語句卻說句卻說“本命題為假本命題為假”；如果說它為假，卻又肯定了；如果說它為假，卻又肯定了它它( (本命題本命題) )是真的，這樣造成了自相矛盾的結(jié)果！這是真的，這樣造成了自相矛盾的結(jié)果！這是所謂悖論。是所謂悖論。 Peking University6 無法繼續(xù)分解的簡單陳述句，稱為簡單命題或無法繼續(xù)分解的簡單陳述句，稱為簡單命題或原子命題原子命題。(不包含任何不包含任何“與、或、非與、或、非”等聯(lián)等聯(lián)結(jié)詞的命題結(jié)詞的命題) 由一個或幾個簡單命題通過由一個或幾個簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)詞復(fù)合而成的復(fù)合而成的命題，稱為命題，稱為復(fù)合命題復(fù)合命題。

5、 (1)期中考試，張三沒有考及格期中考試，張三沒有考及格 (2)期中考試，張三和李四都考及格了期中考試，張三和李四都考及格了 (3)期中考試，張三和李四有人考期中考試，張三和李四有人考90分分 (4)如果張三考如果張三考90分，李四也能考分，李四也能考90分分 (5)張三能考張三能考90分當(dāng)且僅當(dāng)李四也考分當(dāng)且僅當(dāng)李四也考90分分 Peking University7 否定聯(lián)結(jié)詞 合取聯(lián)結(jié)詞 析取聯(lián)結(jié)詞 蘊(yùn)涵聯(lián)結(jié)詞 等價聯(lián)結(jié)詞 命題聯(lián)結(jié)詞 Peking University8定義1 否定聯(lián)結(jié)詞 設(shè)為命題，復(fù)合命題非，叫的設(shè)為命題，復(fù)合命題非，叫的否定式，記作否定式，記作 。記號。記號 叫叫否定

6、聯(lián)結(jié)否定聯(lián)結(jié)詞詞。 為真當(dāng)且僅當(dāng)為假。為真當(dāng)且僅當(dāng)為假。 例如，設(shè)：今天是星期二。 則：今天不是星期二。 Peking University9定義2 合取聯(lián)結(jié)詞 設(shè)，表示兩個命題，復(fù)合命題設(shè)，表示兩個命題，復(fù)合命題“且且”叫命題與的合取，記作叫命題與的合取，記作。記號。記號叫合取聯(lián)結(jié)詞。叫合取聯(lián)結(jié)詞。為真，當(dāng)且僅當(dāng)，為真，當(dāng)且僅當(dāng)，同時為真。同時為真。 例如，設(shè): 2是素?cái)?shù)。 : 2是偶數(shù)。R： 2是奇數(shù)。 則：2既是素?cái)?shù)又是偶數(shù)。(真值為真) R：2既是素?cái)?shù)又是奇數(shù)。(真值為假) Peking University10定義3 析取聯(lián)結(jié)詞 設(shè)，為二命題，復(fù)合命題設(shè)，為二命題，復(fù)合命題“或或”稱

7、稱作與的析取，記作作與的析取，記作，叫析取叫析取聯(lián)結(jié)詞。聯(lián)結(jié)詞。為真，當(dāng)且僅當(dāng)，之為真，當(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ù)。(真值為真) Peking University112-30或今天天氣很好。他今天騎車或走路來上課。 從理科1號樓到圖書館要2分鐘或4分鐘。 Peking University12注： “或”有兩種標(biāo)準(zhǔn)用法， 張三或李四考了90分（相容“或”） 第一節(jié)課上數(shù)學(xué)或者上英語 Peking University13定義4 蘊(yùn)涵聯(lián)結(jié)詞 設(shè)，是二命題，復(fù)合命題

8、設(shè)，是二命題，復(fù)合命題“如，則如，則”稱為與的稱為與的蘊(yùn)涵式蘊(yùn)涵式，記作，記作, 其中其中叫前件或前題，叫后件或結(jié)論。叫前件或前題，叫后件或結(jié)論。為真當(dāng)且僅當(dāng)真和假不同時成立為真當(dāng)且僅當(dāng)真和假不同時成立。 例如，如果明天天晴就開運(yùn)動會。 設(shè)：明天天晴。:明天開運(yùn)動會。 則原命題表示為：。 Peking University14 蘊(yùn)涵式、蘊(yùn)涵聯(lián)結(jié)詞pqp q001011100111如果明天下雨，我們就放假明天不下雨我們不放假明天不下雨我們放假明天下雨我們不放假明天下雨我們放假 Peking University15定義5 等價聯(lián)結(jié)詞 設(shè)設(shè),為二命題，復(fù)合命題為二命題，復(fù)合命題“當(dāng)當(dāng)且僅當(dāng)且僅當(dāng)”

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

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

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

12、題公式； (3)若A,B是命題公式，則（AB），（AB）, (AB), (A B)也是命題公式； (4)只有有限次應(yīng)用(1)-(3)形成的符號串才是命題公式。注意： 命題公式是沒有真假值的，僅當(dāng)在一個公式中命題變元用確定的命題代入時，才得到一個值。 Peking University20真值表(truth table)定義設(shè)為一命題公式，P1, P2，, Pn為出現(xiàn)在中的所有命題變元，簡記為（P1, P2，, Pn）。給命題變元P1, P2，, Pn指定一組真值，稱為對的一個指派或一個賦值。含有個命題變元的命題公式（P1, P2，, Pn）共有n個指派。將命題公式（P1, P2，, Pn）在所

13、有指派之下取值的情況列成表，叫的真值表。 Peking University21 真值表 命題形式A在其所有可能的賦值下取得的值列成的表； n元真值函數(shù) F: 0, 1n 0，1 (n1)。 Peking University22聯(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 Peking University23 A的一個賦值賦值: n個命題變元 成真賦值成真賦值 成假賦值成假賦值 重言式重言式（永真式（永真式tautology）P P = 1 矛盾式矛盾式（永假式（永假式con

14、tradiction）P P = 0 可滿足式可滿足式 Peking University24 公式分類 重言式 矛盾式 可滿足式重言式 Peking University25p 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 賦值 可滿足式 矛盾式 重言式 (永假式) (永真式) Peking University26等值式（等價公式） 給定兩個命題公式（給定兩個命題公式（P P1 1, P, P2 2，, P, Pn n）和和（P P1 1, P, P2 2，, P, Pn n），），若對若對P P1 1, P, P2 2，,

15、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 1 1 1 0 0 0 0 對于、的任一種真值指派，對于、的任一種真值指派， （PQ）與與 P Q都有相同的真值，都有相同的真值，所以這所以這兩個命題公式是等價的。兩個命題公式是等價的。 Peking University27 為書寫方便而省略括號 公式最外層的括號可以省

16、略 聯(lián)結(jié)詞運(yùn)算優(yōu)先級別 同一個聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無括號，則從左到右運(yùn)算 Peking University28例題：層次法構(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 0 Peking University29等值式等值式(logical equivalences),()(),()()()()(),()()(),(),()11,000,11ABBA ABBAABCABCABCABCABC

17、ABACABCABACABABABABAABA AABAAAAA AAAA 冪等律AAA, AAA交換律結(jié)合律分配律的摩根律()()吸收律零律同一律排中律矛盾律0()()()()AAAAABABABABBAABABABBAABABA 雙重否定律蘊(yùn)涵等值式等價等值式等價否定等值式假言易位歸繆論 Peking University30 AAA, AAA A(BC) (AB)(AC) A(BC) (AB)(AC) ABBA, ABBA(AB)C A(BC) (AB)C A(BC) Peking University31 Peking University32A1 1, A0 0 A0 A, A1 A

18、 AA 1 AA 0 (對偶原理: -互換, 0-1互換) Peking University33A A AB AB AB (AB)(BA) Peking University34AB AB AB BA (AB)(AB) A Peking University35 設(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是合式公式中

19、的子公式，若是一個合式公式，且 ，用置換中的，得到新的合式公式，則。證明：證明：與除替換部分外均相同，又由于替換部分與除替換部分外均相同，又由于替換部分，即是說對任一指派，與真值相同，那么與對，即是說對任一指派，與真值相同，那么與對任一真值指派也應(yīng)有相同的真值。故任一真值指派也應(yīng)有相同的真值。故。 Peking University36等值演算： 由已知的等值式，應(yīng)用置換規(guī)則推演出新的等值式的過程。等值演算 P (Q R) P ( Q R) P ( Q R) ( P Q) R ( P Q) R ( P Q) R Peking University37 給定命題公式(P1, P2，, Pn)，如

20、果用某個命題公式Bi取代中的某個變元Pi，并且用Bi取代中出現(xiàn)的所有Pi，這樣得到的命題公式稱為命題公式的代入實(shí)例。 例例如，設(shè)：如，設(shè)：P(QP)，用用(RS)取代中的命題取代中的命題變元得：變元得：(RS)(Q(RS)，是的代入實(shí)例。是的代入實(shí)例。代入代入規(guī)則規(guī)則定理（代入規(guī)則）： 一個重言式的代入實(shí)例仍然是一個重言式。證明：證明： 由于重言式的真值與真值指派無關(guān)，故對同一命題由于重言式的真值與真值指派無關(guān)，故對同一命題變元變元都用某個都用某個命題公式命題公式代替代替，該重言式的真值仍為。，該重言式的真值仍為。例例 證明證明(PS)R) (PS)R)為重言式為重言式證：證：因因P P T，

21、根據(jù)根據(jù)代入規(guī)則代入規(guī)則 (PS)R) (PS)R)T Peking University38命題邏輯推理“”“”ABAB若推理的形式結(jié)構(gòu)為重言式，則稱推理正確。用表示是重言式1. 推理的形式結(jié)構(gòu) 前提: A1, A2, , Ak結(jié)論: B 推理的形式結(jié)構(gòu): (A1A2Ak)B Peking University39()()()BCCCCCDBD 附加律AAB化簡律AB)A, AB)假言推理定律 (AB) AB拒取式推理定律 (AB)BA析取三段論推理定律 (AB)BA;(AB)AB假言三段論推理定律 (AB)B)A等價三段論推理定律 (AB)B)A構(gòu)造性二難推理定律 (AB) (AC)推理定

22、律推理定律 Peking University40(1) 附加律 A(AB) 前提: A 結(jié)論: AB A(AB)是永真式 Peking University41(2) 化簡律 (AB)A, (AB)B前提: AB 結(jié)論: A (AB)A是永真式 Peking University42(3) 假言推理 (AB)AB 前提: AB A 結(jié)論: B (AB)A)B是永真式 Peking University43(4) 拒取式 (AB) B A 前提: AB B 結(jié)論: A (AB) B)( A)是永真式 Peking University44(5) 析取三段論 (AB)AB (AB)BA 前提:

23、AB A 結(jié)論: B (AB)A)B是永真式 Peking University45(6) 假言三段論 (AB)(BC)(AC) 前提: AB BC 結(jié)論: AC (AB)(BC)(AC)是永真式 Peking University46(7) 等價三段論 (AB)(BC)(AC) 前提: AB BC 結(jié)論: AC (AB)(BC)(AC)是永真式 Peking University47(8) 構(gòu)造性兩難 (AB)(CD)(AC)(BD) 前提: AB CD AC 結(jié)論: BD Peking University48判斷推理正確的方法判斷推理正確的方法 例前提: p(qr), p, q 結(jié)論:

24、r 方法一方法一: 推理的形式結(jié)構(gòu) 方法二方法二: 從前提推演結(jié)論 Peking University49方法一方法一(形式結(jié)構(gòu)是永真式) (p(qr)pqr (p(qr)pqr （蘊(yùn)涵等值式）蘊(yùn)涵等值式） (pp)(qr)p)qr （分配律）分配律） (qr)q)pr （零律，同一律，交換律）零律，同一律，交換律） (qq)(rq)pr （分配律）分配律） (rqp)r (rqp)r （蘊(yùn)涵等值式）蘊(yùn)涵等值式） rqpr (rr)qp 1 Peking University50方法二方法二(從前提從前提推演推演結(jié)論結(jié)論) (p(qr)pq (p(qr)p)q (qr)q （假言推理）假言推理

25、） r Peking University51 命題邏輯命題和命題聯(lián)結(jié)詞命題公式和真值表命題等值式命題推理定律 Peking University52 Peking University53謂詞邏輯 在命題邏輯中，研究命題和命題的演算。命題演算在命題邏輯中，研究命題和命題的演算。命題演算的基本單位是原子命題。在命題演算中，原子命題不的基本單位是原子命題。在命題演算中，原子命題不再分解。命題邏輯在推證中有很大的局限性，有些簡再分解。命題邏輯在推證中有很大的局限性，有些簡單的論斷也不能用命題邏輯進(jìn)行推證。單的論斷也不能用命題邏輯進(jìn)行推證。 例如，對著名的例如，對著名的“蘇格拉底三段論蘇格拉底三段論

26、”就無法判斷其就無法判斷其正確性：正確性：“所有的人都是要死的。蘇格拉底是人，所所有的人都是要死的。蘇格拉底是人，所以蘇格拉底是要死的。以蘇格拉底是要死的?！?為了克服命題邏輯的局限性，就需要深入分析命為了克服命題邏輯的局限性，就需要深入分析命題的內(nèi)部的邏輯結(jié)構(gòu)。為此，必須對原子命題作進(jìn)一題的內(nèi)部的邏輯結(jié)構(gòu)。為此，必須對原子命題作進(jìn)一步的分解，引入謂詞邏輯的概念。步的分解，引入謂詞邏輯的概念。 Peking University54謂詞邏輯 在命題邏輯中，研究命題和命題的演算。命題演算在命題邏輯中，研究命題和命題的演算。命題演算的基本單位是原子命題。在命題演算中，原子命題不的基本單位是原子命題

27、。在命題演算中，原子命題不再分解。命題邏輯在推證中有很大的局限性，有些簡再分解。命題邏輯在推證中有很大的局限性，有些簡單的論斷也不能用命題邏輯進(jìn)行推證。單的論斷也不能用命題邏輯進(jìn)行推證。 例如，對著名的例如，對著名的“蘇格拉底三段論蘇格拉底三段論”就無法判斷其就無法判斷其正確性：正確性：“所有的人都是要死的。蘇格拉底是人，所所有的人都是要死的。蘇格拉底是人，所以蘇格拉底是要死的。以蘇格拉底是要死的?！?為了克服命題邏輯的局限性，就需要深入分析命為了克服命題邏輯的局限性，就需要深入分析命題的內(nèi)部的邏輯結(jié)構(gòu)。為此，必須對原子命題作進(jìn)一題的內(nèi)部的邏輯結(jié)構(gòu)。為此，必須對原子命題作進(jìn)一步的分解，引入謂詞

28、邏輯的概念。步的分解，引入謂詞邏輯的概念。 Peking University55謂詞的概念與量詞謂詞公式與翻譯等價式、蘊(yùn)含式前束范式謂詞邏輯 Peking University56謂詞的概念 命題是反映判斷的句子。反映判斷的句子由主語和命題是反映判斷的句子。反映判斷的句子由主語和謂語兩部分組成。主語一般是客體；用以刻劃客體性質(zhì)謂語兩部分組成。主語一般是客體；用以刻劃客體性質(zhì)或關(guān)系的部分即是謂語。或關(guān)系的部分即是謂語。在命題中作為主語的客體稱為個體。而。而用以描述個體性質(zhì)或幾個個體間關(guān)系的部分稱為謂詞。 例如對例如對“張三是大學(xué)生張三是大學(xué)生”和和“李四是大學(xué)生李四是大學(xué)生” ” 這兩這兩個命

29、題，個體分別是個命題，個體分別是“張三張三”和和“李四李四”，謂詞謂詞都是都是“是大學(xué)生是大學(xué)生”。在作符號化處理時，用表示。在作符號化處理時，用表示“是大學(xué)是大學(xué)生生”，用表示，用表示“張三張三”，用表示，用表示“李四李四”。上述兩。上述兩個命題可分別表示為個命題可分別表示為()和和() ，從而把命題中的，從而把命題中的主語和謂語分離開來。主語和謂語分離開來。 Peking University57謂詞的概念(續(xù)) 用謂詞表達(dá)命題，必須包括用謂詞表達(dá)命題，必須包括個體和謂詞個體和謂詞兩部分。一般地說，兩部分。一般地說，“是是”類型的命題可用類型的命題可用( () )表達(dá)。而表示兩個或兩表達(dá)。

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

31、示“是大學(xué)生是大學(xué)生”，如果的取值范圍，如果的取值范圍是某大學(xué)某班中的全體學(xué)生，則（）是永真式；如果的是某大學(xué)某班中的全體學(xué)生，則（）是永真式；如果的取值范圍是某中學(xué)某班中的全體學(xué)生，則（）是永假式；取值范圍是某中學(xué)某班中的全體學(xué)生，則（）是永假式；如果的取值范圍是某劇場中的觀眾，則（）的真值可真如果的取值范圍是某劇場中的觀眾，則（）的真值可真可假，因?yàn)橛^眾中可能有大學(xué)生，也可能有非大學(xué)生可假，因?yàn)橛^眾中可能有大學(xué)生，也可能有非大學(xué)生 Peking University59量詞 考慮命題考慮命題“所有的所有的人都是要死的人都是要死的”和和“有些有些人能活百歲以上人能活百歲以上”的符號化問題，的

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

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

34、tial quantifier) Peking University62謂詞公式謂詞公式定義為定義為（1）n元謂詞是一個謂詞公式；元謂詞是一個謂詞公式；（2）若）若A是謂詞公式，則（是謂詞公式，則（A）也是謂詞公式；也是謂詞公式；（3）若）若A，B是謂詞公式，則（是謂詞公式，則（AB）、（）、（AB）、）、（AB）、（）、（AB）也是謂詞公式；也是謂詞公式；（4）若）若A是謂詞公式且含有未被量化的個體變量是謂詞公式且含有未被量化的個體變量x，則則 xA(x)， XA(x)也是謂詞公式。也是謂詞公式。（5）有限次地使用（）有限次地使用（1）（4）所得到的也是謂詞公式。）所得到的也是謂詞公式。 P

35、eking University63 指導(dǎo)變元： xA(x)， xA(x)中的中的x 相應(yīng)量詞的轄域： xA(x)， xA(x)中的中的A 約束出現(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)謂詞公式中的基本概念 Peking University64謂詞公式的解釋謂詞公式的解釋 謂詞公式中含有個體變元和謂詞變元。給定個體域，謂詞公式中含有個體變元和謂詞變元。給定個體域，將謂詞公式中個體變元由確定的個體來取代，謂詞變元由特定的謂詞來取代，稱為對謂詞公式的賦值或解釋。對

36、謂詞公式作了這樣的賦值之后，謂詞公式成為命題。對謂詞公式作了這樣的賦值之后，謂詞公式成為命題。例例 求求( ( x)x)（P(x)Q(x)P(x)Q(x)）的真值，其中的真值，其中( (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) ( ()()() ) Peking University65可滿足公式不可滿足公式（永假式）永真式可真可假式（不確定式）謂詞公式分類： Peking University66等價

37、式和蘊(yùn)含式定義 給定個體域E上的兩個謂詞公式和，若對和中的變項(xiàng)作同樣的賦值，所得命題的真值都相同，則稱謂詞公式和在上是等價的，記作：。 Peking University67謂詞演算中的等價式和蘊(yùn)含式的來源可分為如下幾類：謂詞演算中的等價式和蘊(yùn)含式的來源可分為如下幾類：1命題公式的推廣2. 在有限個體域中消去量詞3. 量詞與聯(lián)結(jié)詞 之間的關(guān)系 量詞轄域的擴(kuò)張與收縮量詞分配的等值式4. 量詞分配的蘊(yùn)含式 Peking University681命題公式的推廣 用原子謂詞公式取代命題演算等價公式中的各命題變用原子謂詞公式取代命題演算等價公式中的各命題變元，命題演算的等價式就轉(zhuǎn)化為謂詞演算的等價式。

38、例元，命題演算的等價式就轉(zhuǎn)化為謂詞演算的等價式。例如：如： A(x) A(x) ( x)A(x)( x)B(x) ( x)A(x)( x)B(x) Peking University692在有限個體域中有限個體域中消去量詞 xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an) Peking University703量詞與聯(lián)結(jié)詞 之間的關(guān)系 ( x)A(x) ( x) A(x)。 ( x)A(x) ( x) A(x)。 例如，設(shè)例如，設(shè)A(x)表示表示“x今天來校上課今天來校上課”，則，則 A(x)表示表示“x今天沒來今天沒來校上課校上課”。那麼，。那

39、麼， 對對(1),“不是所有的人今天都來上課不是所有的人今天都來上課 ( x)A(x) ”與與“有有(存在存在)一些一些人今天沒來上課人今天沒來上課( x) A(x)”在意義上是相同的。在意義上是相同的。 對對(2),“今天沒有今天沒有(不存在不存在)來上課的人來上課的人 ( x)A(x) ”與與“所有的人今所有的人今天都沒來上課天都沒來上課( x) A(x)”在意義上是相同的。在意義上是相同的。 和式稱為和式稱為量詞轉(zhuǎn)換律。這里這里約定，出現(xiàn)在量詞之前的否定不是否定該量詞，而是否定被量化了的整個命題。例如， ( x)A(x) ( x)A(x)。 Peking University71等價式和

40、蘊(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)個體域?yàn)橛邢藜?dāng)個體域?yàn)橛邢藜痑1, a2,., an時，我們可以驗(yàn)證式：時，我們可以驗(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)

41、A(x)B) Peking University72等價式和蘊(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) 式的左邊表示式的左邊表示“對于所有的，對于所有的，A(x)和和B(x)都是真的都是真的”；右邊表示；右邊表示“對于所有的，對于所有的，A(x)是真的；同時對于所有的，是真的；同時對于所有的，B(x)也是真的也是真的”。顯然，這兩個命題是等價的。例如，顯然，這兩個命題是等價的。例如，“聯(lián)歡會上所有的人既唱歌又跳舞聯(lián)歡會上所有的人既唱歌又跳舞”和和“聯(lián)歡會上所有的人唱歌且所有的人跳舞聯(lián)

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