離散數(shù)學第1章課件-高等教育出版社-屈婉玲-耿素云-張立昂主編

1、1,2,主要內容命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算與推理,第一部分 數(shù)理邏輯,3,第一章 命題邏輯的基本概念,主要內容命題與聯(lián)結詞 命題及其分類 聯(lián)結詞與復合命題命題公式及其賦值,4,命題與真值 命題：判斷結果惟一的陳述句 命題的真值：判斷的結果 真值的取值：真與假 真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題陳述句中的悖論，判斷結

2、果不惟一確定的不是命題,1.1 命題與聯(lián)結詞,5,例1 下列句子中那些是命題？ (1) 是有理數(shù). (2) 2 + 5 = 7. (3) x + 5 > 3. (4) 你去教室嗎？ (5) 這個蘋果真大呀！ (6) 請不要講話！ (7) 2050年元旦下大雪.,假命題,命題概念,真命題,不是命題,不是命題,不是命題,不是命題,命題，但真值現(xiàn)在不知道,6,,命題分類：簡單命題（也稱原子命題）與復合命題

3、簡單命題符號化用小寫英文字母 p, q, r, …, pi, qi, ri (i?1)表示簡單命題用“1”表示真，用“0”表示假 例如，令 p： √2 是有理數(shù)，則 p 的真值為0， q：2 + 5 = 7，則 q 的真值為1,命題分類,7,否定、合取、析取聯(lián)結詞,定義1.3 設p, q為兩個命題，復合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結詞. 規(guī)定p∨q為假當且僅當p與q同

4、時為假.,定義1.1 設 p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式，記作?p，符號?稱作否定聯(lián)結詞. 規(guī)定?p 為真當且僅當p為假.,定義1.2 設p,q為兩個命題，復合命題“p并且q”(或“p與 q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結詞. 規(guī)定p∧q為真當且僅當p與q同時為真.,8,例2 將下列命題符號化. (1) 吳穎既用功又聰明. (2) 吳穎不僅用功而且聰明. (3) 吳穎雖然聰明

5、，但不用功. (4) 張輝與王麗都是三好生. (5) 張輝與王麗是同學.,合取聯(lián)結詞的實例,9,解 令p:吳穎用功, q:吳穎聰明 (1) p?q (2) p?q (3) ?p?q (4) 設p:張輝是三好生, q:王麗是三好生 p?q (5) p:張輝與王麗是同學(1)—(3) 說明描述合取式的靈活性與多樣性(4)—(5) 要求分清 “與” 所聯(lián)結的成分,合取聯(lián)結詞的實例,10,例3 將下列命

6、題符號化(1) 2 或 4 是素數(shù).(2) 2 或 3 是素數(shù).(3) 4 或 6 是素數(shù).(4) 小元元只能拿一個蘋果或一個梨.(5) 王小紅生于 1975 年或 1976 年.,析取聯(lián)結詞的實例,11,解 (1) 令p:2是素數(shù), q:4是素數(shù), p?q(2) 令p:2是素數(shù), q:3是素數(shù), p?q(3) 令p:4是素數(shù), q:6是素數(shù), p?q(4) 令p:小元元拿一個蘋果, q:小元元拿一

7、個梨 (p??q)?(?p?q)(5) p:王小紅生于 1975 年, q:王小紅生于1976 年, (p??q)?(?p?q) 或 p?q(1)—(3) 為相容或(4)—(5) 為排斥或, 符號化時(5)可有兩種形式，而(4)則不能,析取聯(lián)結詞的實例,12,必要條件： 滿足B，必然可以滿足A，或者說不滿足A，必然可以推出不滿足B， 則A是B的必要條件。 例如：只有努力才能成功

8、。??如果不能努力就不會成功。 努力是成功的必要條件。充分條件： 由A可以推出B，但是則A是B的充分條件。,13,定義1.4 設p, q為兩個命題，復合命題“如果p, 則q”稱作p與q的蘊涵式，記作p?q，并稱p是蘊涵式的前件，q為蘊涵式的后件，?稱作蘊涵聯(lián)結詞. 規(guī)定：p?q為假當且僅當p為真q為假.,蘊涵聯(lián)結詞,(1) p?q 的邏輯關系：q為 p 的必要條件(2) “如果 p, 則 q” 有很多不同的表述

9、方法： 若p，就q 只要p，就q p僅當q 只有q 才p 除非q, 才p 或 除非q，否則非p，…． (3) 當 p 為假時，p?q恒為真，稱為空證明 (4) 常出現(xiàn)的錯誤：不分充分與必要條件,蘊涵聯(lián)結詞的實例,例1.5 （5）只要a能被4整除，則a一定能被 2整除。 （6）a能被4整除，僅當a能被2整除。 （7）除非a能被2整除，a才能被4

10、整除。,14,15,例4 設 p：天冷，q：小王穿羽絨服，將下列命題符號化(1) 只要天冷，小王就穿羽絨服.(2) 因為天冷，所以小王穿羽絨服.(3) 若小王不穿羽絨服，則天不冷.(4) 只有天冷，小王才穿羽絨服.(5) 除非天冷，小王才穿羽絨服.(6) 除非小王穿羽絨服，否則天不冷.(7) 如果天不冷，則小王不穿羽絨服.(8) 小王穿羽絨服僅當天冷的時候.,蘊涵聯(lián)結詞的實例,p?q,注意： p?q 與 ?q??p 等

11、值（真值相同）,p?q,p?q,q?p,q?p,p?q,q?p,q?p,16,定義1.5 設 p, q為兩個命題，復合命題“p當且僅當q”稱作p與q的等價式，記作p?q，?稱作等價聯(lián)結詞. 規(guī)定p?q為真當且僅當p與q同時為真或同時為假.p?q 的邏輯關系：p與q互為充分必要條件,等價聯(lián)結詞,,17,,18,練習 求下列復合命題的真值(1) 2 + 2 ＝ 4 當且僅當 3 + 3 ＝ 6. (2) 2 + 2 ＝ 4 當且

12、僅當 3 是偶數(shù).(3) 2 + 2 ＝ 4 當且僅當 太陽從東方升起.(4) 2 + 2 ＝ 4 當且僅當 美國位于非洲.(5) 函數(shù) f (x) 在 x0 可導的充要條件是 它在 x0 連續(xù).,1,0,0,1,0,19,本小節(jié)中p, q, r, … 均表示命題.,在聯(lián)結詞集 {?, ?, ?, ?, ?}中，?是一元聯(lián)結詞，其他聯(lián)結詞是二元聯(lián)結詞。反復使用{?, ?, ?, ?, ?}中的聯(lián)結詞組成更為復雜的復合命題.,優(yōu)先級

13、和結合性,聯(lián)結詞的優(yōu)先順序為：?, ?, ?, ?, ?, 有括號的先算括號。同級按自左到右的順序運算.,p→q ∧ ¬ r → p ∧ ¬ q → r,p?q ? ?q ? ?p ? r,,20,,21,,22,練習 求式子的真值。,,p:0 q:0 r:0p:1 q:0 r:1p:0 q:1 r:0,23,1.2 命題公式及其賦值,命題變項與合式

14、公式命題變項合式公式合式公式的層次公式的賦值公式賦值公式類型真值表,24,命題變項與合式公式,25,命題變項與合式公式,定義1.6 合式公式（簡稱公式）的遞歸定義： (1) 單個命題變項和命題常項是合式公式, 稱作原子命題公式 (2) 若A是合式公式，則 (?A)也是 (3) 若A, B是合式公式，則(A?B), (A?B), (A?B), (A?B)也是 (4) 只有有限次地應用(1)—(3) 形成的符號

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

16、 (c) A=B?C, 其中 B,C 的層次及 n 同(b)； (d) A=B?C, 其中B,C 的層次及 n 同(b)； (e) A=B?C, 其中B,C 的層次及 n 同(b). (3) 若公式A的層次為k, 則稱A為k層公式.,,27,28,定義1.8 設p1, p2, … , pn是出現(xiàn)在公式A中的全部命題變項, 給p1, p2, … , pn各指定一個真值, 稱為對A的一個賦值或解釋

17、. 若使A為1, 則稱這組值為A的成真賦值; 若使A為0, 則稱這組值為A的成假賦值.幾點說明：A中僅出現(xiàn) p1, p2, … , pn，給A賦值?=?1?2…?n是指 p1=?1, p2=?2, …, pn=?n, ?i=0或1, ?i之間不加標點符號 如：在公式（ p1 ∧ p3 ）? p2中，給公式賦值 011后 ， 各命題變項的值為：,公式賦值,,29,A中僅出現(xiàn) p, q, r, …, 給

18、A賦值?1?2?3…是指 p=?1, q=?2 , r=?3 …如：在公式（ p∧ r ）? q中，給公式賦值 011后 ， 各命題變項的值為： 含n個命題變項的公式有2n個賦值. 如 000, 010, 101, 110是?(p?q)?r的成真賦值 001, 011, 100, 111是成假賦值.,30,定義1.9 將命題公式A在所有賦值下取值的情況列成表, 稱

19、作A的真值表.構造真值表的步驟:(1) 找出公式中所含的全部命題變項p1, p2, … , pn(若無下角標 則按字母順序排列), 列出2n個全部賦值, 從00?0開始, 按 二進制加法, 每次加1, 直至11?1為止. (2) 按從低到高的順序寫出公式的各個層次.(3) 對每個賦值依次計算各層次的真值, 直到最后計算出公式 的真值為止.,真值表,31,例6 寫出下列公式的真值表, 并求它

20、們的成真賦值和成假 賦值: (1) (p?q) ??r (2) (q?p) ?q?p (3) ? (?p?q) ?q,真值表,32,(1) A = (p?q) ??r,成真賦值:000,001,010,100,110; 成假賦值:011,101,111,真值表1,33,(2) B＝(q?p)?q?p,成真賦值:00,01,10,11; 無成假賦值,真值表2,34,(3) C＝? (?p?q)?q的真

21、值表,成假賦值:00,01,10,11; 無成真賦值,真值表3,35,公式的類型,定義1.10 (1) 若A在它的任何賦值下均為真, 則稱A為重言式或永真式;(2) 若A在它的任何賦值下均為假, 則稱A為矛盾式或永假式;(3) 若A不是矛盾式, 則稱A是可滿足式.由例1可知, (p?q) ??r, (q?p) ?q?p, ? (?p?q) ?q 分別為非重言式的可滿足式, 重言式, 矛盾式.注意：重言式

22、是可滿足式，但反之不真.真值表的用途: 求出公式的全部成真賦值與成假賦值, 判斷公式的類型,36,37,第一章 習題課,主要內容命題、真值、簡單命題與復合命題、命題符號化聯(lián)結詞?, ?, ?, ?, ?及復合命題符號化命題公式及層次公式的類型真值表及應用基本要求深刻理解各聯(lián)結詞的邏輯關系, 熟練地將命題符號化會求復合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等概念熟練地求公式的真值表，并用它求

23、公式的成真賦值與成假賦值及判斷公式類型,38,1. 將下列命題符號化 (1) 豆沙包是由面粉和紅小豆做成的. (2) 蘋果樹和梨樹都是落葉喬木. (3) 王小紅或李大明是物理組成員. (4) 王小紅或李大明中的一人是物理組成員. (5) 由于交通阻塞，他遲到了. (6) 如果交通不阻塞，他就不會遲到. (7) 他沒遲到，所以交通沒阻塞. (8) 除非交通阻塞，否則他不會遲到. (9) 他遲到當且僅當交

24、通阻塞.,練習1,39,提示：分清復合命題與簡單命題分清相容或與排斥或分清必要與充分條件及充分必要條件答案: (1) 是簡單命題 (2) 是合取式 (3) 是析取式（相容或）(4) 是析取式（排斥或）設 p: 交通阻塞，q: 他遲到 (5) p?q, (6) ?p??q或q?p

25、 (7) ?q??p 或p?q, (8) q?p或?p??q (9) p?q 或?p??q可見(5)與(7)，(6)與(8) 相同（等值）,練習1解答,40,2. 設 p : 2是素數(shù) q : 北京比天津人口多 r : 美國的首都是舊金山 求下面命題的真值 (1) (p?q)?r (2) (q?r)?(

26、p??r) (3) (q?r)?(p??r) (4) (q?p)?((p??r)?(?r??q)),0,練習2,1,0,0,41,3. 用真值表判斷下面公式的類型 (1) p?r??(q?p) (2) ((p?q) ?(?q??p)) ?r (3) (p?q) ?(p?r),練習3,42,練習3解答,(1) p?r??(q?p),矛盾式,43,練習3解答,(2) ((p?q) ?(?q??p))