屈婉玲離散數(shù)學(xué)第一章

1、12主要內(nèi)容主要內(nèi)容l 命題邏輯基本概念命題邏輯基本概念l 命題邏輯等值演算命題邏輯等值演算l 命題邏輯推理理論命題邏輯推理理論l 一階邏輯基本概念一階邏輯基本概念l 一階邏輯等值演算與推理一階邏輯等值演算與推理第一部分第一部分 數(shù)理邏輯數(shù)理邏輯3第一章第一章 命題邏輯的基本概念命題邏輯的基本概念主要內(nèi)容主要內(nèi)容l 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 命題及其分類命題及其分類 聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題l 命題公式及其賦值命題公式及其賦值4命題與真值命題與真值 命題命題：判斷結(jié)果惟一的陳述句：判斷結(jié)果惟一的陳述句 命題的真值命題的真值：判斷的結(jié)果：判斷的結(jié)果 真值的取值真值的取值：真與假：真與假

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

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

4、設(shè) p為命題，復(fù)合命題為命題，復(fù)合命題“非非p”(或或“p的否定的否定”)稱稱為為p的的否定式否定式，記作，記作 p，符號，符號 稱作稱作否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞. 規(guī)定規(guī)定 p 為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p為假為假. 是有理數(shù)是不對的是有理數(shù)是不對的2p p : : 是有理數(shù)是有理數(shù)2 符號化為符號化為 p p 8例例2 將下列命題符號化將下列命題符號化. (1) 吳穎既用功又聰明吳穎既用功又聰明. (2) 吳穎不僅用功而且聰明吳穎不僅用功而且聰明. (3) 吳穎雖然聰明，但不用功吳穎雖然聰明，但不用功. (4) 張輝與王麗都是三好生張輝與王麗都是三好生. (5) 張輝與張輝與王麗是同學(xué)王麗是同學(xué)

5、.合取聯(lián)結(jié)詞的實例合取聯(lián)結(jié)詞的實例定義定義1.2 設(shè)設(shè)p,q為兩個命題，復(fù)合命題為兩個命題，復(fù)合命題“p并且并且q”(或或“p與與 q”)稱為稱為p與與q的的合取式合取式，記作，記作pq，稱作稱作合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞. 規(guī)定規(guī)定pq為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與q同時為真同時為真.9解解 令令p:吳穎用功吳穎用功, q:吳穎聰明吳穎聰明 (1) p q (2) p q (3) p q (4) 設(shè)設(shè)p:張輝是三好生張輝是三好生, q:王麗是三好生王麗是三好生 p q (5) p:張輝與張輝與王麗是同學(xué)王麗是同學(xué)(1)(3) 說明描述合取式的靈活性與多樣性說明描述合取式的靈活性與多樣性(4)(5)

6、 要求分清要求分清 “與與” 所聯(lián)結(jié)的成分所聯(lián)結(jié)的成分合取聯(lián)結(jié)詞的實例合取聯(lián)結(jié)詞的實例10定義定義1.3 設(shè)設(shè)p, q為兩個命題，復(fù)合命題為兩個命題，復(fù)合命題“p或或q”稱作稱作p與與q的的析取式析取式，記作，記作pq，稱作稱作析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞. 規(guī)定規(guī)定pq為假當(dāng)為假當(dāng)且僅當(dāng)且僅當(dāng)p與與q同時為假同時為假.析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞例例3 將下列命題符號化將下列命題符號化(1) 2 或或 4 是素數(shù)是素數(shù).(2) 2 或或 3 是素數(shù)是素數(shù).(3) 4 或或 6 是素數(shù)是素數(shù).(4) 小元元只能拿一個蘋果或一個梨小元元只能拿一個蘋果或一個梨.(5) 王小紅生于王小紅生于 1975 年或年或 1

7、976 年年.11解解 (1) 令令p:2是素數(shù)是素數(shù), q:4是素數(shù)是素數(shù), p q(2) 令令p:2是素數(shù)是素數(shù), q:3是素數(shù)是素數(shù), p q(3) 令令p:4是素數(shù)是素數(shù), q:6是素數(shù)是素數(shù), p q(4) 令令p:小元元拿一個蘋果小元元拿一個蘋果, q:小元元拿一個梨小元元拿一個梨 (pq) ( p q)(5) p:王小紅生于王小紅生于 1975 年年, q:王小紅生于王小紅生于1976 年年, (pq) ( p q) 或或 p q(1)(3) 為為相容或相容或(4)(5) 為為排斥或排斥或, 符號化時符號化時(5)可有兩種形式，而可有兩種形式，而(4)則不能則不能析取聯(lián)結(jié)詞的實例

8、析取聯(lián)結(jié)詞的實例12定義定義1.4 設(shè)設(shè)p, q為兩個命題，復(fù)合命題為兩個命題，復(fù)合命題“如果如果p, 則則q”稱作稱作p與與q的的蘊(yùn)涵式蘊(yùn)涵式，記作，記作pq，并稱，并稱p是蘊(yùn)涵式的是蘊(yùn)涵式的前件前件，q為蘊(yùn)涵式的為蘊(yùn)涵式的后后件件，稱作稱作蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞. 規(guī)定：規(guī)定：pq為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng)p為真為真q為假為假.蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞(1) pq 的邏輯關(guān)系：的邏輯關(guān)系：q為為 p 的必要條件的必要條件(2) “如果如果 p, 則則 q” 有很多不同的表述方法：有很多不同的表述方法： 若若p，就，就q 只要只要p，就，就q p僅當(dāng)僅當(dāng)q 只有只有q 才才p 除非除非q, 才才p

9、或或 除非除非q，否則非，否則非p， (3) 當(dāng)當(dāng) p 為假時，為假時，pq恒為真，稱為空證明恒為真，稱為空證明 (4) 常出現(xiàn)的錯誤：不分充分與必要條件常出現(xiàn)的錯誤：不分充分與必要條件13例例4 設(shè)設(shè) p：天冷，：天冷，q：小王穿羽絨服：小王穿羽絨服，將下列命題符號化，將下列命題符號化(1) 只要天冷，小王就穿羽絨服只要天冷，小王就穿羽絨服.(2) 因為天冷，所以小王穿羽絨服因為天冷，所以小王穿羽絨服.(3) 若小王不穿羽絨服，則天不冷若小王不穿羽絨服，則天不冷.(4) 只有天冷，小王才穿羽絨服只有天冷，小王才穿羽絨服.(5) 除非天冷，小王才穿羽絨服除非天冷，小王才穿羽絨服.(6) 除非小

10、王穿羽絨服，否則天不冷除非小王穿羽絨服，否則天不冷.(7) 如果天不冷，則小王不穿羽絨服如果天不冷，則小王不穿羽絨服.(8) 小王穿羽絨服僅當(dāng)天冷的時候小王穿羽絨服僅當(dāng)天冷的時候.蘊(yùn)涵聯(lián)結(jié)詞的實例蘊(yùn)涵聯(lián)結(jié)詞的實例pq注意：注意： pq 與與 qp 等值（真值相同）等值（真值相同）pqpqqpqppqqpqp14定義定義1.5 設(shè)設(shè) p, q為兩個命題，復(fù)合命題為兩個命題，復(fù)合命題“p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q”稱作稱作p與與q的的等價式等價式，記作，記作pq，稱作稱作等價聯(lián)結(jié)詞等價聯(lián)結(jié)詞. 規(guī)定規(guī)定pq為真為真當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)p與與q同時為真或同時為假同時為真或同時為假.pq 的邏輯關(guān)系：的邏輯關(guān)系：

11、p與與q互為充分必要條件互為充分必要條件等價聯(lián)結(jié)詞等價聯(lián)結(jié)詞例例5 5 求下列復(fù)合命題的真值求下列復(fù)合命題的真值(1) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 3 + 3 6. (2) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 3 是偶數(shù)是偶數(shù).(3) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 太陽從東方升起太陽從東方升起.(4) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 美國位于非洲美國位于非洲.(5) 函數(shù)函數(shù) f (x) 在在 x0 可導(dǎo)的充要條件是可導(dǎo)的充要條件是 它在它在 x0 連續(xù)連續(xù). 1001115l 本小節(jié)中本小節(jié)中p, q, r, 均表示命題均表示命題.l 聯(lián)結(jié)詞集為聯(lián)結(jié)詞集為 , , , , ， p,

12、 p q, p q, pq, pq為為基本復(fù)合命題基本復(fù)合命題. 其中要特別注意理解其中要特別注意理解pq的涵義的涵義. 反復(fù)使用反復(fù)使用 , , , , 中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題.設(shè)設(shè) p: 是無理數(shù)，是無理數(shù)，q: 3是奇數(shù)，是奇數(shù)， r: 蘋果是方的，蘋果是方的， s: 太陽繞地球轉(zhuǎn)太陽繞地球轉(zhuǎn) 則復(fù)合命題則復(fù)合命題 (pq) (rs) p) 是真是假？是真是假？2小結(jié)小結(jié)l 聯(lián)結(jié)詞的優(yōu)先順序：聯(lián)結(jié)詞的優(yōu)先順序： , , , , , 同級按先出現(xiàn)者先運(yùn)算同級按先出現(xiàn)者先運(yùn)算.假命題假命題 161.2 命題公式及其賦值命題公式及其賦值命題變項與合式公

13、式命題變項與合式公式l 命題變項命題變項l 合式公式合式公式l 合式公式的層次合式公式的層次公式的賦值公式的賦值l 公式賦值公式賦值l 公式類型公式類型l 真值表真值表17命題變項與合式公式命題變項與合式公式 命題常項：命題常項：真值確定的簡單命題真值確定的簡單命題 命題變項（命題變元）：命題變項（命題變元）：取值取值1或或0的變元，表示真值可以變化的變元，表示真值可以變化的陳述句的陳述句 常項與變項均用常項與變項均用 p, q, r, , pi, qi, ri, , 等表示等表示. 定義定義1.6 合式公式合式公式（簡稱公式）的遞歸定義：（簡稱公式）的遞歸定義： (1) 單個命題變項和命題常

14、項是合式公式單個命題變項和命題常項是合式公式, 稱作稱作原子命題公式原子命題公式 (2) 若若A是合式公式，則是合式公式，則 ( A)也是也是 (3) 若若A, B是合式公式，則是合式公式，則(A B), (A B), (AB), (AB)也是也是 (4) 只有有限次地應(yīng)用只有有限次地應(yīng)用(1)(3) 形成的符號串才是合式公式形成的符號串才是合式公式幾點(diǎn)說明：幾點(diǎn)說明：歸納或遞歸定義歸納或遞歸定義, 元語言與對象語言元語言與對象語言, 外層括號可以省去外層括號可以省去18合式公式的層次合式公式的層次定義定義1.7(1) 若公式若公式A是單個命題變項，則稱是單個命題變項，則稱A為為0層公式層公式

15、.(2) 稱稱 A 是是 n+1(n0) 層公式是指下面情況之一：層公式是指下面情況之一： (a) A= B, B 是是 n 層公式；層公式； (b) A=B C, 其中其中B,C 分別為分別為 i 層和層和 j 層公式，層公式， 且且 n=max(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

16、= pq, D= (pq)r, E=( p q) r) ( r s) 分別為分別為0層，層，1層，層，2層，層，3層，層，4層公式層公式.19定義定義1.8 設(shè)設(shè)p1, p2, , pn是出現(xiàn)在公式是出現(xiàn)在公式A中的全部命題變項中的全部命題變項, 給給p1, p2, , pn各指定一個真值各指定一個真值, 稱為對稱為對A的一個的一個賦值賦值或或解釋解釋. 若使若使A為為1, 則稱這組值為則稱這組值為A的的成真賦值成真賦值; 若使若使A為為0, 則稱這組則稱這組值為值為A的的成假賦值成假賦值.幾點(diǎn)說明：幾點(diǎn)說明：l A中僅出現(xiàn)中僅出現(xiàn) p1, p2, , pn，給，給A賦值賦值 = 1 2 n是

17、指是指 p1= 1, p2= 2, , pn= n, i=0或或1, i之間不加標(biāo)點(diǎn)符號之間不加標(biāo)點(diǎn)符號l A中僅出現(xiàn)中僅出現(xiàn) p, q, r, , 給給A賦值賦值 1 2 3是指是指 p= 1, q= 2 , r= 3 l 含含n個命題變項的公式有個命題變項的公式有2n個賦值個賦值. 如如 000, 010, 101, 110是是 (pq)r的成真賦值的成真賦值 001, 011, 100, 111是成假賦值是成假賦值.公式賦值公式賦值20定義定義1.9 將命題公式將命題公式A在所有賦值下取值的情況列成表在所有賦值下取值的情況列成表, 稱作稱作A的的真值表真值表.構(gòu)造真值表的步驟構(gòu)造真值表的

18、步驟:(1) 找出公式中所含的全部命題變項找出公式中所含的全部命題變項p1, p2, , pn(若無下角標(biāo)若無下角標(biāo) 則按字母順序排列則按字母順序排列), 列出列出2n個全部賦值個全部賦值, 從從000開始開始, 按按 二進(jìn)制加法二進(jìn)制加法, 每次加每次加1, 直至直至111為止為止. (2) 按從低到高的順序?qū)懗龉降母鱾€層次按從低到高的順序?qū)懗龉降母鱾€層次.(3) 對每個賦值依次計算各層次的真值對每個賦值依次計算各層次的真值, 直到最后計算出公式直到最后計算出公式 的真值為止的真值為止.真值表真值表21例例6 寫出下列公式的真值表寫出下列公式的真值表, 并求它們的成真賦值和成假并求它們的

19、成真賦值和成假 賦值賦值: (1) (p q) r (2) (qp) qp (3) ( p q) q真值表真值表22(1) A = (p q) r成真賦值成真賦值:000,001,010,100,110; 成假賦值成假賦值:011,101,111 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 真值表真值表123(2) B(qp) qp成真賦成真賦值值:00,01,10,11; 無成假賦值無成假賦值p q qp(qp) q(qp) qp0 00 11 01 11011000

20、11111真值表真值表224(3) C ( p q) q的真值表的真值表成假賦值成假賦值:00,01,10,11; 無成真賦值無成真賦值p q p p q ( p q) ( p q) q0 00 11 01 11100110100100000真值表真值表325公式的類型公式的類型定義定義1.10 (1) 若若A在它的任何賦值下均為真在它的任何賦值下均為真, 則稱則稱A為為重言式重言式或或永真式永真式;(2) 若若A在它的任何賦值下均為假在它的任何賦值下均為假, 則稱則稱A為為矛盾式矛盾式或或永假式永假式;(3) 若若A不是矛盾式不是矛盾式, 則稱則稱A是是可滿足式可滿足式.由例由例1可知可知,

21、 (p q) r, (qp) qp, ( p q) q 分別為非重言式的可滿足式分別為非重言式的可滿足式, 重言式重言式, 矛盾式矛盾式.注意：重言式是可滿足式，但反之不真注意：重言式是可滿足式，但反之不真.真值表的用途真值表的用途: 求出公式的全部成真賦值與成假賦值求出公式的全部成真賦值與成假賦值, 判斷公式的類型判斷公式的類型26公式的類型公式的類型含含n個命題變項的公式有無窮多，問這些公式的真值表是否個命題變項的公式有無窮多，問這些公式的真值表是否也有無窮多？也有無窮多？含含n個命題變項的公式的真值表只有個命題變項的公式的真值表只有 種不同情況種不同情況注意：啞元的定義注意：啞元的定義2

22、7第一章第一章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 命題、真值、簡單命題與復(fù)合命題、命題符號化命題、真值、簡單命題與復(fù)合命題、命題符號化l 聯(lián)結(jié)詞聯(lián)結(jié)詞 , , , , 及復(fù)合命題符號化及復(fù)合命題符號化l 命題公式及層次命題公式及層次l 公式的類型公式的類型l 真值表及應(yīng)用真值表及應(yīng)用基本要求基本要求l 深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系, 熟練地將命題符號化熟練地將命題符號化l 會求復(fù)合命題的真值會求復(fù)合命題的真值l 深刻理解合式公式及重言式、矛盾式、可滿足式等概念深刻理解合式公式及重言式、矛盾式、可滿足式等概念l 熟練地求公式的真值表，并用它求公式的成真賦值與成假熟練地求公式

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