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

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

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

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)結(jié)詞,定義1.3 設(shè)p, q為兩個命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞. 規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同

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

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

6、題符號化(1) 2 或 4 是素數(shù).(2) 2 或 3 是素數(shù).(3) 4 或 6 是素數(shù).(4) 小元元只能拿一個蘋果或一個梨.(5) 王小紅生于 1975 年或 1976 年.,析取聯(lián)結(jié)詞的實例,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)結(jié)詞的實例,12,必要條件： 滿足B，必然可以滿足A，或者說不滿足A，必然可以推出不滿足B， 則A是B的必要條件。 例如：只有努力才能成功

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

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

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

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

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

13、和結(jié)合性,聯(lián)結(jié)詞的優(yōu)先順序為：?, ?, ?, ?, ?, 有括號的先算括號。同級按自左到右的順序運(yùn)算.,p→q ∧ ¬ r → p ∧ ¬ q → r,p?q ? ?q ? ?p ? r,,20,,21,,22,練習(xí) 求式子的真值。,,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) 只有有限次地應(yīng)用(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 設(shè)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之間不加標(biāo)點符號 如：在公式（ 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的真值表.構(gòu)造真值表的步驟:(1) 找出公式中所含的全部命題變項p1, p2, … , pn(若無下角標(biāo) 則按字母順序排列), 列出2n個全部賦值, 從00?0開始, 按 二進(jìn)制加法, 每次加1, 直至11?1為止. (2) 按從低到高的順序?qū)懗龉降母鱾€層次.(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,第一章 習(xí)題課,主要內(nèi)容命題、真值、簡單命題與復(fù)合命題、命題符號化聯(lián)結(jié)詞?, ?, ?, ?, ?及復(fù)合命題符號化命題公式及層次公式的類型真值表及應(yīng)用基本要求深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系, 熟練地將命題符號化會求復(fù)合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等概念熟練地求公式的真值表，并用它求

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

24、通阻塞.,練習(xí)1,39,提示：分清復(fù)合命題與簡單命題分清相容或與排斥或分清必要與充分條件及充分必要條件答案: (1) 是簡單命題 (2) 是合取式 (3) 是析取式（相容或）(4) 是析取式（排斥或）設(shè) 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) 相同（等值）,練習(xí)1解答,40,2. 設(shè) 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,練習(xí)2,1,0,0,41,3. 用真值表判斷下面公式的類型 (1) p?r??(q?p) (2) ((p?q) ?(?q??p)) ?r (3) (p?q) ?(p?r),練習(xí)3,42,練習(xí)3解答,(1) p?r??(q?p),矛盾式,43,練習(xí)3解答,(2) ((p?q) ?(?q??p))