1、1主要內容主要內容l 命題邏輯基本概念命題邏輯基本概念l 命題邏輯等值演算命題邏輯等值演算l 命題邏輯推理理論命題邏輯推理理論l 一階邏輯基本概念一階邏輯基本概念l 一階邏輯等值演算與推理一階邏輯等值演算與推理第一部分第一部分 數理邏輯數理邏輯2第一章第一章 命題邏輯的基本概念命題邏輯的基本概念主要內容主要內容l 命題與聯結詞命題與聯結詞 命題及其分類命題及其分類 聯結詞與復合命題聯結詞與復合命題l 命題公式及其賦值命題公式及其賦值3命題與真值命題與真值 命題：判斷結果惟一的陳述句命題：判斷結果惟一的陳述句 命題的真值：判斷的結果命題的真值：判斷的結果 真值的取值：真與假真值的取值：真與假 真

2、命題與假命題真命題與假命題注意：注意：感嘆句、祈使句、疑問句都不是命題感嘆句、祈使句、疑問句都不是命題陳述句中的悖論，判斷結果不惟一確定的不是命題陳述句中的悖論，判斷結果不惟一確定的不是命題 1.1 命題與聯結詞命題與聯結詞4例例1 1 下列句子中那些是命題？下列句子中那些是命題？ (1) 是有理數是有理數. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室嗎？你去教室嗎？ (5) 這個蘋果真大呀！這個蘋果真大呀！ (6) 請不要講話！請不要講話！ (7) 2050年元旦下大雪年元旦下大雪. 2 假命題假命題命題概念命題概念 真命題真命題不是命題不是命題 不是命題不是命

3、題 不是命題不是命題不是命題不是命題命題，但真值現在不知道命題，但真值現在不知道5命題分類：簡單命題（也稱原子命題）與復合命題命題分類：簡單命題（也稱原子命題）與復合命題簡單命題符號化簡單命題符號化l 用小寫英文字母用小寫英文字母 p, q, r, , pi, qi, ri (i 1)表示簡單命題表示簡單命題l 用用“1”表示真，用表示真，用“0”表示假表示假 例如，令例如，令 p： 是有理數，則是有理數，則 p 的真值為的真值為0， q：2 + 5 = 7，則，則 q 的真值為的真值為1 2命題分類命題分類6否定、合取、析取聯結詞否定、合取、析取聯結詞定義定義1.3 設設p, q為兩個命題，

4、復合命題為兩個命題，復合命題“p或或q”稱作稱作p與與q的的析取式析取式，記作，記作pq，稱作稱作析取聯結詞析取聯結詞. 規定規定pq為假當為假當且僅當且僅當p與與q同時為假同時為假.定義定義1.1 設設 p為命題，復合命題為命題，復合命題“非非p”(或或“p的否定的否定”)稱稱為為p的的否定式否定式，記作，記作 p，符號，符號 稱作稱作否定聯結詞否定聯結詞. 規定規定 p 為真當且僅當為真當且僅當p為假為假.定義定義1.2 設設p,q為兩個命題，復合命題為兩個命題，復合命題“p并且并且q”(或或“p與與 q”)稱為稱為p與與q的的合取式合取式，記作，記作pq，稱作稱作合取聯結詞合取聯結詞.

5、規定規定pq為真當且僅當為真當且僅當p與與q同時為真同時為真.7例例2 將下列命題符號化將下列命題符號化. (1) 吳穎既用功又聰明吳穎既用功又聰明. (2) 吳穎不僅用功而且聰明吳穎不僅用功而且聰明. (3) 吳穎雖然聰明，但不用功吳穎雖然聰明，但不用功. (4) 張輝與王麗都是三好生張輝與王麗都是三好生. (5) 張輝與張輝與王麗是同學王麗是同學.合取聯結詞的實例合取聯結詞的實例8解解 令令p:吳穎用功吳穎用功, q:吳穎聰明吳穎聰明 (1) p q (2) p q (3) p q (4) 設設p:張輝是三好生張輝是三好生, q:王麗是三好生王麗是三好生 p q (5) p:張輝與張輝與王

6、麗是同學王麗是同學(1)(3) 說明描述合取式的靈活性與多樣性說明描述合取式的靈活性與多樣性(4)(5) 要求分清要求分清 “與與” 所聯結的成分所聯結的成分合取聯結詞的實例合取聯結詞的實例9例例3 將下列命題符號化將下列命題符號化(1) 2 或或 4 是素數是素數.(2) 2 或或 3 是素數是素數.(3) 4 或或 6 是素數是素數.(4) 小元元只能拿一個蘋果或一個梨小元元只能拿一個蘋果或一個梨.(5) 王小紅生于王小紅生于 1975 年或年或 1976 年年.析取聯結詞的實例析取聯結詞的實例10解解 (1) 令令p:2是素數是素數, q:4是素數是素數, p q(2) 令令p:2是素數

7、是素數, q:3是素數是素數, p q(3) 令令p:4是素數是素數, q:6是素數是素數, p q(4) 令令p:小元元拿一個蘋果小元元拿一個蘋果, q:小元元拿一個梨小元元拿一個梨 (pq) ( p q)(5) p:王小紅生于王小紅生于 1975 年年, q:王小紅生于王小紅生于1976 年年, (pq) ( p q) 或或 p q(1)(3) 為相容或為相容或(4)(5) 為排斥或為排斥或, 符號化時符號化時(5)可有兩種形式，而可有兩種形式，而(4)則不能則不能析取聯結詞的實例析取聯結詞的實例11定義定義1.4 設設p, q為兩個命題，復合命題為兩個命題，復合命題“如果如果p, 則則q

8、”稱作稱作p與與q的的蘊涵式蘊涵式，記作，記作pq，并稱，并稱p是蘊涵式的是蘊涵式的前件前件，q為蘊涵式的為蘊涵式的后后件件，稱作稱作蘊涵聯結詞蘊涵聯結詞. 規定：規定：pq為假當且僅當為假當且僅當p為真為真q為假為假.蘊涵聯結詞蘊涵聯結詞(1) pq 的邏輯關系：的邏輯關系：q為為 p 的必要條件的必要條件(2) “如果如果 p, 則則 q” 有很多不同的表述方法：有很多不同的表述方法： 若若p，就，就q 只要只要p，就，就q p僅當僅當q 只有只有q 才才p 除非除非q, 才才p 或或 除非除非q，否則非，否則非p， (3) 當當 p 為假時，為假時，pq恒為真，稱為空證明恒為真，稱為空證

9、明 (4) 常出現的錯誤：不分充分與必要條件常出現的錯誤：不分充分與必要條件12例例4 設設 p：天冷，：天冷，q：小王穿羽絨服，將下列命題符號化：小王穿羽絨服，將下列命題符號化(1) 只要天冷，小王就穿羽絨服只要天冷，小王就穿羽絨服.(2) 因為天冷，所以小王穿羽絨服因為天冷，所以小王穿羽絨服.(3) 若小王不穿羽絨服，則天不冷若小王不穿羽絨服，則天不冷.(4) 只有天冷，小王才穿羽絨服只有天冷，小王才穿羽絨服.(5) 除非天冷，小王才穿羽絨服除非天冷，小王才穿羽絨服.(6) 除非小王穿羽絨服，否則天不冷除非小王穿羽絨服，否則天不冷.(7) 如果天不冷，則小王不穿羽絨服如果天不冷，則小王不穿

10、羽絨服.(8) 小王穿羽絨服僅當天冷的時候小王穿羽絨服僅當天冷的時候.蘊涵聯結詞的實例蘊涵聯結詞的實例pq注意：注意： pq 與與 qp 等值（真值相同）等值（真值相同）pqpqqpqppqqpqp13定義定義1.5 設設 p, q為兩個命題，復合命題為兩個命題，復合命題“p當且僅當當且僅當q”稱作稱作p與與q的的等價式等價式，記作，記作pq，稱作稱作等價聯結詞等價聯結詞. 規定規定pq為真為真當且僅當當且僅當p與與q同時為真或同時為假同時為真或同時為假.pq 的邏輯關系：的邏輯關系：p與與q互為充分必要條件互為充分必要條件等價聯結詞等價聯結詞例例5 5 求下列復合命題的真值求下列復合命題的真

11、值(1) 2 + 2 4 當且僅當當且僅當 3 + 3 6. (2) 2 + 2 4 當且僅當當且僅當 3 是偶數是偶數.(3) 2 + 2 4 當且僅當當且僅當 太陽從東方升起太陽從東方升起.(4) 2 + 2 4 當且僅當當且僅當 美國位于非洲美國位于非洲.(5) 函數函數 f (x) 在在 x0 可導的充要條件是可導的充要條件是 它在它在 x0 連續連續. 1001014l 本小節中本小節中p, q, r, 均表示命題均表示命題.l 聯結詞集為聯結詞集為 , , , , ， p, p q, p q, pq, pq為為基本復合命題基本復合命題. 其中要特別注意理解其中要特別注意理解pq的涵

12、義的涵義. 反復使用反復使用 , , , , 中的聯結詞組成更為復雜的復合命題中的聯結詞組成更為復雜的復合命題.設設 p: 是無理數，是無理數，q: 3是奇數，是奇數， r: 蘋果是方的，蘋果是方的， s: 太陽繞地球轉太陽繞地球轉 則復合命題則復合命題 (pq) (rs) p) 是假命題是假命題. 2小結小結l 聯結詞的運算順序：聯結詞的運算順序： , , , , , 同級按先出現者先運算同級按先出現者先運算.151.2 命題公式及其賦值命題公式及其賦值命題變項與合式公式命題變項與合式公式l 命題變項命題變項l 合式公式合式公式l 合式公式的層次合式公式的層次公式的賦值公式的賦值l 公式賦值

13、公式賦值l 公式類型公式類型l 真值表真值表16命題變項與合式公式命題變項與合式公式 命題常項命題常項 命題變項（命題變元）命題變項（命題變元） 常項與變項均用常項與變項均用 p, q, r, , pi, qi, ri, , 等表示等表示. 定義定義1.6 合式公式合式公式（簡稱公式）的遞歸定義：（簡稱公式）的遞歸定義： (1) 單個命題變項和命題常項是合式公式單個命題變項和命題常項是合式公式, 稱作稱作原子命題公式原子命題公式 (2) 若若A是合式公式，則是合式公式，則 ( A)也是也是 (3) 若若A, B是合式公式，則是合式公式，則(A B), (A B), (AB), (AB)也是也是

14、 (4) 只有有限次地應用只有有限次地應用(1)(3) 形成的符號串才是合式公式形成的符號串才是合式公式幾點說明：幾點說明：歸納或遞歸定義歸納或遞歸定義, 元語言與對象語言元語言與對象語言, 外層括號可以省去外層括號可以省去17合式公式的層次合式公式的層次定義定義1.7(1) 若公式若公式A是單個命題變項，則稱是單個命題變項，則稱A為為0層公式層公式.(2) 稱稱 A 是是 n+1(n0) 層公式是指下面情況之一：層公式是指下面情況之一： (a) A= B, B 是是 n 層公式；層公式； (b) A=B C, 其中其中B,C 分別為分別為 i 層和層和 j 層公式，層公式， 且且 n=max

15、(i,j)； (c) A=B C, 其中其中 B,C 的層次及的層次及 n 同同(b)； (d) A=BC, 其中其中B,C 的層次及的層次及 n 同同(b)； (e) A=BC, 其中其中B,C 的層次及的層次及 n 同同(b). (3) 若公式若公式A的層次為的層次為k, 則稱則稱A為為k層公式層公式.例如例如 公式公式 A=p, B= p, C= pq, D= (pq)r, E=( p q) r) ( r s) 分別為分別為0層，層，1層，層，2層，層，3層，層，4層公式層公式.18定義定義1.8 設設p1, p2, , pn是出現在公式是出現在公式A中的全部命題變項中的全部命題變項,

16、給給p1, p2, , pn各指定一個真值各指定一個真值, 稱為對稱為對A的一個的一個賦值賦值或或解釋解釋. 若使若使A為為1, 則稱這組值為則稱這組值為A的的成真賦值成真賦值; 若使若使A為為0, 則稱這組則稱這組值為值為A的的成假賦值成假賦值.幾點說明：幾點說明：l A中僅出現中僅出現 p1, p2, , pn，給，給A賦值賦值 = 1 2 n是指是指 p1= 1, p2= 2, , pn= n, i=0或或1, i之間不加標點符號之間不加標點符號l A中僅出現中僅出現 p, q, r, , 給給A賦值賦值 1 2 3是指是指 p= 1, q= 2 , r= 3 l 含含n個命題變項的公式

17、有個命題變項的公式有2n個賦值個賦值. 如如 000, 010, 101, 110是是 (pq)r的成真賦值的成真賦值 001, 011, 100, 111是成假賦值是成假賦值.公式賦值公式賦值19定義定義1.9 將命題公式將命題公式A在所有賦值下取值的情況列成表在所有賦值下取值的情況列成表, 稱作稱作A的的真值表真值表.構造真值表的步驟構造真值表的步驟:(1) 找出公式中所含的全部命題變項找出公式中所含的全部命題變項p1, p2, , pn(若無下角標若無下角標 則按字母順序排列則按字母順序排列), 列出列出2n個全部賦值個全部賦值, 從從000開始開始, 按按 二進制加法二進制加法, 每次

18、加每次加1, 直至直至111為止為止. (2) 按從低到高的順序寫出公式的各個層次按從低到高的順序寫出公式的各個層次.(3) 對每個賦值依次計算各層次的真值對每個賦值依次計算各層次的真值, 直到最后計算出公式直到最后計算出公式 的真值為止的真值為止.真值表真值表20例例6 寫出下列公式的真值表寫出下列公式的真值表, 并求它們的成真賦值和成假并求它們的成真賦值和成假 賦值賦值: (1) (p q) r (2) (qp) qp (3) ( p q) q真值表真值表21(1) A = (p q) r成真賦值成真賦值:000,001,010,100,110; 成假賦值成假賦值:011,101,111

19、p q rp q r (p q)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 真值表真值表122(2) B(qp) qp成真賦成真賦值值:00,01,10,11; 無成假賦值無成假賦值p q qp(qp) q(qp) qp0 00 11 01 1101100011111真值表真值表223(3) C ( p q) q的真值表的真值表成假賦值成假賦值:00,01,10,11; 無成真賦值無成真賦值p q p p q ( p q) ( p q) q0 00 11 01 11100110100100000真值表

20、真值表324公式的類型公式的類型定義定義1.10 (1) 若若A在它的任何賦值下均為真在它的任何賦值下均為真, 則稱則稱A為為重言式重言式或或永真式永真式;(2) 若若A在它的任何賦值下均為假在它的任何賦值下均為假, 則稱則稱A為為矛盾式矛盾式或或永假式永假式;(3) 若若A不是矛盾式不是矛盾式, 則稱則稱A是是可滿足式可滿足式.由例由例1可知可知, (p q) r, (qp) qp, ( p q) q 分別為非重言式的可滿足式分別為非重言式的可滿足式, 重言式重言式, 矛盾式矛盾式.注意：重言式是可滿足式，但反之不真注意：重言式是可滿足式，但反之不真.真值表的用途真值表的用途: 求出公式的全

21、部成真賦值與成假賦值求出公式的全部成真賦值與成假賦值, 判斷公式的類型判斷公式的類型25第一章第一章 習題課習題課主要內容主要內容l 命題、真值、簡單命題與復合命題、命題符號化命題、真值、簡單命題與復合命題、命題符號化l 聯結詞聯結詞 , , , , 及復合命題符號化及復合命題符號化l 命題公式及層次命題公式及層次l 公式的類型公式的類型l 真值表及應用真值表及應用基本要求基本要求l 深刻理解各聯結詞的邏輯關系深刻理解各聯結詞的邏輯關系, 熟練地將命題符號化熟練地將命題符號化l 會求復合命題的真值會求復合命題的真值l 深刻理解合式公式及重言式、矛盾式、可滿足式等概念深刻理解合式公式及重言式、矛

22、盾式、可滿足式等概念l 熟練地求公式的真值表，并用它求公式的成真賦值與成假熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型賦值及判斷公式類型261. 將下列命題符號化將下列命題符號化 (1) 豆沙包是由面粉和紅小豆做成的豆沙包是由面粉和紅小豆做成的. (2) 蘋果樹和梨樹都是落葉喬木蘋果樹和梨樹都是落葉喬木. (3) 王小紅或李大明是物理組成員王小紅或李大明是物理組成員. (4) 王小紅或李大明中的一人是物理組成員王小紅或李大明中的一人是物理組成員. (5) 由于交通阻塞，他遲到了由于交通阻塞，他遲到了. (6) 如果交通不阻塞，他就不會遲到如果交通不阻塞，他就不會遲到. (7) 他沒遲到，所以交通沒阻塞他沒遲到，所以交通沒阻塞. (8) 除非交通阻塞，否則他不會遲到除非交通阻塞，否則他不會遲到. (9) 他遲到當且僅當交通阻塞他遲到當且僅當交通阻塞.練習練習127提示：提示：分清復合命題與簡單命題分清復合命題與簡單命題分清相容或與排斥或分清相容或與排斥或分清必要與充分條件及充分必要條件分清必要與充分條件及充分必要條件答案答案: (1) 是簡單命題是簡單命題 (2) 是合取式是合取式 (3) 是析取式（