1、 Peking University1 第一編 集合論 第一章 集合 Peking University2 1.1 預備知識（prerequisites） 命題邏輯和謂詞邏輯是數理邏輯中最基本的內容。命題邏輯和謂詞邏輯是數理邏輯中最基本的內容。 l 十九世紀中后期，德國數學家萊布尼茲、英國數學家十九世紀中后期，德國數學家萊布尼茲、英國數學家 布爾和邏輯學家懷海特、羅素為數理邏輯的產生和發布爾和邏輯學家懷海特、羅素為數理邏輯的產生和發 展有突出貢獻。展有突出貢獻。 l 從二十世紀從二十世紀4040年代起，數理邏輯成為計算機科學的重年代起，數理邏輯成為計算機科學的重 要基礎理論之一。如布爾代數在計

2、算機硬件設計中發要基礎理論之一。如布爾代數在計算機硬件設計中發 揮了重大作用；形式語言的研究為建立計算機語言提揮了重大作用；形式語言的研究為建立計算機語言提 供了基礎。供了基礎。 Peking University3 命題和命題聯結詞 命題公式和真值表 命題等值式 命題推理定律 命題邏輯 Peking University4 命題是客觀上能判明真假的陳述句。當 命題為真時，稱命題的真值為“真”； 否則，說命題的真值為“假”。用T或1 表示“真”，用F或0表示“假”。 （ Proposition: a statement that is either true or false,but not

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

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

5、詞聯結詞復合而成的復合而成的 命題，稱為命題，稱為復合命題復合命題。 (1)期中考試，張三沒有考及格期中考試，張三沒有考及格 (2)期中考試，張三和李四都考及格了期中考試，張三和李四都考及格了 (3)期中考試，張三和李四有人考期中考試，張三和李四有人考90分分 (4)如果張三考如果張三考90分，李四也能考分，李四也能考90分分 (5)張三能考張三能考90分當且僅當李四也考分當且僅當李四也考90分分 Peking University7 否定聯結詞 合取聯結詞 析取聯結詞 蘊涵聯結詞 等價聯結詞 命題聯結詞 Peking University8 定義1 否定聯結詞 設為命題，復合命題非，叫的設為

6、命題，復合命題非，叫的 否定式，記作否定式，記作 。記號。記號 叫叫否定聯結否定聯結 詞詞。 為真當且僅當為假。為真當且僅當為假。 例如，設：今天是星期二。 則：今天不是星期二。 Peking University9 定義2 合取聯結詞 設，表示兩個命題，復合命題設，表示兩個命題，復合命題“且且” 叫命題與的合取，記作叫命題與的合取，記作。記號。記號 叫合取聯結詞。叫合取聯結詞。為真，當且僅當，為真，當且僅當， 同時為真。同時為真。 例如，設: 2是素數。 : 2是偶數。R： 2是奇數。 則：2既是素數又是偶數。(真值為真) R：2既是素數又是奇數。(真值為假) Peking Universi

7、ty10 定義3 析取聯結詞 設，為二命題，復合命題設，為二命題，復合命題“或或”稱稱 作與的析取，記作作與的析取，記作，叫析取叫析取 聯結詞。聯結詞。為真，當且僅當，之為真，當且僅當，之 中至少有一為真。中至少有一為真。 例如，設：2是素數。：2是偶數。 R： 2是奇數。 則：2是素數或2是偶數。(真值為真) R：2是素數或2是奇數。(真值為真) Peking University11 2-30或今天天氣很好。 他今天騎車或走路來上課。 從理科1號樓到圖書館要2分鐘或4分鐘。 Peking University12 注： “或”有兩種標準用法， 張三或李四考了90分（相容“或”） 第一節課上

8、數學或者上英語 Peking University13 定義4 蘊涵聯結詞 設，是二命題，復合命題設，是二命題，復合命題“如，則如，則” 稱為與的稱為與的蘊涵式蘊涵式，記作，記作, 其中其中 叫前件或前題，叫后件或結論。叫前件或前題，叫后件或結論。 為真當且僅當真和假不同時成立為真當且僅當真和假不同時成立。 例如，如果明天天晴就開運動會。 設：明天天晴。:明天開運動會。 則原命題表示為：。 Peking University14 蘊涵式、蘊涵聯結詞 pqp q 001 011 100 111 如果明天下雨，我們就放假 明天不下雨我們不放假 明天不下雨我們放假 明天下雨我們不放假 明天下雨我們放

9、假 Peking University15 定義5 等價聯結詞 設設,為二命題，復合命題為二命題，復合命題“當當 且僅當且僅當”稱為與的稱為與的等價式等價式，記，記 作作。叫叫等價等價聯結詞，也記聯結詞，也記 作作iff。為真當且僅當為真當且僅當,真真 值相同值相同。 例如，2+24當且僅當雪是白的。 設： 2+24 。：雪是白的。 則原命題表示為：。 Peking University16 命題一般用大寫英文字母表示。表示命題的符號叫命題一般用大寫英文字母表示。表示命題的符號叫命命 題標識符題標識符。 例如，用表示“雪是黑的”，記作“：雪是黑 的”。 如果一個命題標識符表示某個確定的命題，則

10、稱為如果一個命題標識符表示某個確定的命題，則稱為命命 題常量題常量。特別地，真命題。特別地，真命題( (用用T T表示表示) )和假命題和假命題( (用用F F表示表示) ) 是命題常量。是命題常量。 如果一個命題標識符表示不確定的命題，則稱為如果一個命題標識符表示不確定的命題，則稱為命題命題 變元變元。 命題常量和命題變元 命題變元不是命題命題變元不是命題。在命題演算中，對命題變元指定相應。在命題演算中，對命題變元指定相應 的真值的真值( (真或假真或假) )，稱為對命題變元的，稱為對命題變元的真值指派真值指派。 集合集合 T,FT,F 是是命題變元的值域命題變元的值域。 Peking Un

11、iversity17 (negation)： p， p為真當且僅當p為假 (conjunction):p q， p q為真當且僅當p,q同時為真 (disjunction):p q， p q為假當且僅當p,q同時為假 (implication):pq，pq為假當且僅當p為真而q為假 (biconditional):pq，pq 否定式 合 為真當且 取式 析取式 蘊涵式 等僅當p與q價式的真值相同 相應的真值表相應的真值表 Peking University18 命題公式 設P和Q是任意兩個命題，則下列命題都是復合命題 ,()(),()P PQ PQRQ PQP 設P和Q是命題變元命題變元，則上

12、述公式均稱作命題公式命題公式。P和Q 稱作命題公式的分量。 Peking University19 命題公式 (1)單個命題變元（或常元）是命題公式； (2)若A是命題公式，則(A)是命題公式； (3)若A,B是命題公式，則（AB），（AB）, (AB), (A B)也是命題公式； (4)只有有限次應用(1)-(3)形成的符號串才是命 題公式。 注意： 命題公式是沒有真假值的，僅當在一個公式中命 題變元用確定的命題代入時，才得到一個值。 Peking University20 真值表(truth table) 定義設為一命題公式，P1, P2，, Pn為出 現在中的所有命題變元，簡記為（P1,

13、 P2，, Pn）。給命題變元P1, P2，, Pn指定 一組真值，稱為對的一個指派或一個賦值。 含有個命題變元的命題公式（P1, P2，, Pn）共有n個指派。將命題公式（P1, P2，, Pn）在所有指派之下取值的情況列成 表，叫的真值表。 Peking University21 真值表 命題形式A在其所有可能的賦值下取得的值 列成的表； n元真值函數 F: 0, 1n 0，1 (n1)。 Peking University22 聯結詞的真值表 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

14、 Peking University23 A的一個賦值賦值: n個命題變元 成真賦值成真賦值 成假賦值成假賦值 重言式重言式（永真式（永真式tautology） P P = 1 矛盾式矛盾式（永假式（永假式contradiction） P P = 0 可滿足式可滿足式 Peking University24 公式分類 重言式 矛盾式 可滿足式 重言式 Peking University25 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 賦值 可滿足式 矛盾式 重言式 (永假式) (永真式) Peking University2

15、6 等值式（等價公式） 給定兩個命題公式（給定兩個命題公式（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 構造命題公式構造命題公式 （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 對于、的任一

16、種真值指派，對于、的任一種真值指派， （PQ）與與 P Q 都有相同的真值，都有相同的真值，所以這所以這兩個命題公式是等價的兩個命題公式是等價的。 Peking University27 為書寫方便而省略括號 公式最外層的括號可以省略 聯結詞運算優先級別 同一個聯結詞連續多次出現且 無括號，則從左到右運算 Peking University28 例題：層次法構造真值表 (p (pq) (pq)(p (pq) (pq)(p (pq) (pq)(p (pq) (pq) p q pq pq p(pq) (pq)公式公式 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 1 1

17、1 0 0 0 1 1 0 0 Peking University29 等值式等值式(logical equivalences) , ()(),()() ()()(),()()() , (),() 11,00 0,1 1 ABBA ABBA ABCABCABCABC ABCABACABCABAC ABABABAB AABA AABA AA AA AA AA 冪等律AAA, AAA 交換律 結合律 分配律 的摩根律()() 吸收律 零律 同一律 排中律 矛盾律0 ()() ()() AA AA ABAB ABABBA ABAB ABBA ABABA 雙重否定律 蘊涵等值式 等價等值式 等價否定等

18、值式 假言易位 歸繆論 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 University32 A1 1, A0 0 A0 A, A1 A AA 1 AA 0 (對偶原理: -互換, 0-1互換) Peking University33 A A AB AB AB (AB)(BA) Peking University34 AB AB AB BA (AB)(AB) A Peking University3

19、5 設是合式公式中的一個部分，且也是一個合設是合式公式中的一個部分，且也是一個合 式公式，則稱是的式公式，則稱是的子公式子公式。 例例如，設：如，設： ( (PQ)PQ)（Q(RQ(R S)S)），），則則PQPQ、 RR S S、 S S、 Q(R Q(R S)S)都是的子公式。都是的子公式。 置換規則 定理（置換規則）： 設X是合式公式中的子公式，若是一個合式公式， 且 ，用置換中的，得到新的合式公式，則 。 證明：證明：與除替換部分外均相同，又由于替換部分與除替換部分外均相同，又由于替換部分 ，即是說對任一指派，與真值相同，那么與對，即是說對任一指派，與真值相同，那么與對 任一真值指派也

20、應有相同的真值。故任一真值指派也應有相同的真值。故。 Peking University36 等值演算： 由已知的等值式，應用置換規則推演出新的等值式的 過程。 等值演算 P (Q R) P ( Q R) P ( Q R) ( P Q) R ( P Q) R ( P Q) R Peking University37 給定命題公式(P1, P2，, Pn)，如果用某個命題公 式Bi取代中的某個變元Pi，并且用Bi取代中出現的所有 Pi，這樣得到的命題公式稱為命題公式的代入實例。 例例如，設：如，設：P(QP)，用用(RS)取代中的命題取代中的命題 變元得：變元得：(RS)(Q(RS)，是的代入實

21、例。是的代入實例。 代入代入規則規則 定理（代入規則）： 一個重言式的代入實例仍然是一個重言式。 證明證明： 由于重言式的真值與真值指派無關，故對同一命題由于重言式的真值與真值指派無關，故對同一命題 變元變元都用某個都用某個命題公式命題公式代替代替，該重言式的真值仍為。，該重言式的真值仍為。 例例 證明證明(PS)R) (PS)R)為重言式為重言式 證：證：因因P P T，根據根據代入規則代入規則 (PS)R) (PS)R)T Peking University38 命題邏輯推理 “”“”ABAB 若推理的形式結構為重言式，則稱推理正確。 用表示是重言式 1. 推理的形式結構 前提: A1,

22、A2, , Ak 結論: B 推理的形式結構: (A1A2Ak)B Peking University39 ( () () () B CC CC CDBD 附加律AAB 化簡律AB)A, AB) 假言推理定律 (AB) AB 拒取式推理定律 (AB)BA 析取三段論推理定律 (AB)BA;(AB)AB 假言三段論推理定律 (AB)B)A 等價三段論推理定律 (AB)B)A 構造性二難推理定律 (AB) (AC) 推理定律推理定律 Peking University40 (1) 附加律 A(AB) 前提: A 結論: AB A(AB)是永真式 Peking University41 (2) 化簡

23、律 (AB)A, (AB)B 前提: AB 結論: A (AB)A是永真式 Peking University42 (3) 假言推理 (AB)AB 前提: AB A 結論: B (AB)A)B是永真式 Peking University43 (4) 拒取式 (AB) B A 前提: AB B 結論: A (AB) B)( A)是永真式 Peking University44 (5) 析取三段論 (AB)AB (AB)BA 前提: AB A 結論: B (AB)A)B是永真式 Peking University45 (6) 假言三段論 (AB)(BC)(AC) 前提: AB BC 結論: AC

24、(AB)(BC)(AC)是永真式 Peking University46 (7) 等價三段論 (AB)(BC)(AC) 前提: AB BC 結論: AC (AB)(BC)(AC)是永真式 Peking University47 (8) 構造性兩難 (AB)(CD)(AC)(BD) 前提: AB CD AC 結論: BD Peking University48 判斷推理正確的方法判斷推理正確的方法 例 前提: p(qr), p, q 結論: r 方法一方法一: 推理的形式結構 方法二方法二: 從前提推演結論 Peking University49 方法一方法一(形式結構是永真式) (p(qr)p

25、qr (p(qr)pqr （蘊涵等值式）蘊涵等值式） (pp)(qr)p)qr （分配律）分配律） (qr)q)pr （零律，同一律，交換律）零律，同一律，交換律） (qq)(rq)pr （分配律）分配律） (rqp)r (rqp)r （蘊涵等值式）蘊涵等值式） rqpr (rr)qp 1 Peking University50 方法二方法二(從前提從前提推演推演結論結論) (p(qr)pq (p(qr)p)q (qr)q （假言推理）假言推理） r Peking University51 命題邏輯 命題和命題聯結詞 命題公式和真值表 命題等值式 命題推理定律 Peking Universit

26、y52 Peking University53 謂詞邏輯 在命題邏輯中，研究命題和命題的演算。命題演算在命題邏輯中，研究命題和命題的演算。命題演算 的基本單位是原子命題。在命題演算中，原子命題不的基本單位是原子命題。在命題演算中，原子命題不 再分解。命題邏輯在推證中有很大的局限性，有些簡再分解。命題邏輯在推證中有很大的局限性，有些簡 單的論斷也不能用命題邏輯進行推證。單的論斷也不能用命題邏輯進行推證。 例如，對著名的例如，對著名的“蘇格拉底三段論蘇格拉底三段論”就無法判斷其就無法判斷其 正確性：正確性：“所有的人都是要死的。蘇格拉底是人，所所有的人都是要死的。蘇格拉底是人，所 以蘇格拉底是要死

27、的。以蘇格拉底是要死的。” 為了克服命題邏輯的局限性，就需要深入分析命為了克服命題邏輯的局限性，就需要深入分析命 題的內部的邏輯結構。為此，必須對原子命題作進一題的內部的邏輯結構。為此，必須對原子命題作進一 步的分解，引入謂詞邏輯的概念。步的分解，引入謂詞邏輯的概念。 Peking University54 謂詞邏輯 在命題邏輯中，研究命題和命題的演算。命題演算在命題邏輯中，研究命題和命題的演算。命題演算 的基本單位是原子命題。在命題演算中，原子命題不的基本單位是原子命題。在命題演算中，原子命題不 再分解。命題邏輯在推證中有很大的局限性，有些簡再分解。命題邏輯在推證中有很大的局限性，有些簡 單

28、的論斷也不能用命題邏輯進行推證。單的論斷也不能用命題邏輯進行推證。 例如，對著名的例如，對著名的“蘇格拉底三段論蘇格拉底三段論”就無法判斷其就無法判斷其 正確性：正確性：“所有的人都是要死的。蘇格拉底是人，所所有的人都是要死的。蘇格拉底是人，所 以蘇格拉底是要死的。以蘇格拉底是要死的。” 為了克服命題邏輯的局限性，就需要深入分析命為了克服命題邏輯的局限性，就需要深入分析命 題的內部的邏輯結構。為此，必須對原子命題作進一題的內部的邏輯結構。為此，必須對原子命題作進一 步的分解，引入謂詞邏輯的概念。步的分解，引入謂詞邏輯的概念。 Peking University55 謂詞的概念與量詞 謂詞公式與

29、翻譯 等價式、蘊含式 前束范式 謂詞邏輯 Peking University56 謂詞的概念 命題是反映判斷的句子。反映判斷的句子由主語和命題是反映判斷的句子。反映判斷的句子由主語和 謂語兩部分組成。主語一般是客體；用以刻劃客體性質謂語兩部分組成。主語一般是客體；用以刻劃客體性質 或關系的部分即是謂語。或關系的部分即是謂語。在命題中作為主語的客體稱為 個體。而。而用以描述個體性質或幾個個體間關系的部分稱 為謂詞。 例如對例如對“張三是大學生張三是大學生”和和“李四是大學生李四是大學生” ” 這兩這兩 個命題，個體分別是個命題，個體分別是“張三張三”和和“李四李四”，謂詞謂詞都是都是 “是大學生

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

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

32、大學某班中的全體學生，則（）是永真式；如果的是某大學某班中的全體學生，則（）是永真式；如果的 取值范圍是某中學某班中的全體學生，則（）是永假式；取值范圍是某中學某班中的全體學生，則（）是永假式； 如果的取值范圍是某劇場中的觀眾，則（）的真值可真如果的取值范圍是某劇場中的觀眾，則（）的真值可真 可假，因為觀眾中可能有大學生，也可能有非大學生可假，因為觀眾中可能有大學生，也可能有非大學生 Peking University59 量詞 考慮命題考慮命題“所有的所有的人都是要死的人都是要死的”和和“有些有些人能活百歲以上人能活百歲以上” 的符號化問題，的符號化問題，除個體變元和謂詞之外，還有除個體變元

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

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

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

36、niversity63 指導變元： xA(x)， xA(x)中的中的x 相應量詞的轄域： xA(x)， xA(x)中的中的A 約束出現： x， x的轄域中，的轄域中，x的所有出現的所有出現 自由出現：A中不是約束出現的變元中不是約束出現的變元 例： ( ( x)(P(x)Q(xx)(P(x)Q(x，y)y) 謂詞公式中的基本概念 Peking University64 謂詞公式的解釋謂詞公式的解釋 謂詞公式中含有個體變元和謂詞變元。給定個體域，謂詞公式中含有個體變元和謂詞變元。給定個體域，將 謂詞公式中個體變元由確定的個體來取代，謂詞變元由 特定的謂詞來取代，稱為對謂詞公式的賦值或解釋。 對謂

37、詞公式作了這樣的賦值之后，謂詞公式成為命題。對謂詞公式作了這樣的賦值之后，謂詞公式成為命題。 例例 求求( ( 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 Univer

38、sity66 等價式和蘊含式 定義 給定個體域E上的兩個謂詞公式和，若對和 中的變項作同樣的賦值，所得命題的真值都相同，則 稱謂詞公式和在上是等價的，記作：。 Peking University67 謂詞演算中的等價式和蘊含式的來源可分為如下幾類：謂詞演算中的等價式和蘊含式的來源可分為如下幾類： 1命題公式的推廣 2. 在有限個體域中消去量詞 3. 量詞與聯結詞 之間的關系 4. 量詞轄域的擴張與收縮 5. 量詞分配的等值式 6. 量詞分配的蘊含式 Peking University68 1命題公式的推廣 用原子謂詞公式取代命題演算等價公式中的各命題變用原子謂詞公式取代命題演算等價公式中的各命

39、題變 元，命題演算的等價式就轉化為謂詞演算的等價式。例元，命題演算的等價式就轉化為謂詞演算的等價式。例 如：如： A(x) A(x) ( x)A(x)( x)B(x) ( x)A(x)( x)B(x) Peking University69 2在有限個體域中有限個體域中消去量詞 xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an) Peking University70 3量詞與聯結詞 之間的關系 ( x)A(x) ( x) A(x)。 ( x)A(x) ( x) A(x)。 例如，設例如，設A(x)表示表示“x今天來校上課今天來校上課”，則，則 A(

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

41、 ( x)A(x)。 Peking University71 等價式和蘊含式(續) 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)

42、 ( x)( A(x)B) ( x) A(x)B ( x)A(x)B( x)A(x)B) Peking University72 等價式和蘊含式(續) 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)也是真的也是真的”。 顯然，這兩個命題是等價的。例如，顯然，這兩個命題是等價的。例如，“聯歡會上所有的人

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