離散數(shù)學(xué)離散第一章VIP

1、廣東工業(yè)大學(xué)計算機學(xué)院1廣東工業(yè)大學(xué)計算機學(xué)院2主要內(nèi)容主要內(nèi)容l 第一章：第一章：命題邏輯基本概念命題邏輯基本概念l 第二章：第二章：命題邏輯等值演算命題邏輯等值演算l 第三章：第三章：命題邏輯推理理論命題邏輯推理理論l 第四章：第四章：一階邏輯基本概念一階邏輯基本概念l 第五章：第五章：一階邏輯等值演算與推理一階邏輯等值演算與推理第一部分第一部分 數(shù)理邏輯數(shù)理邏輯廣東工業(yè)大學(xué)計算機學(xué)院3第一章第一章 命題邏輯的基本概念命題邏輯的基本概念主要內(nèi)容主要內(nèi)容l 1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞命題及其分類命題及其分類聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題l 1.2 命題公式及其賦值命題公式及其賦值廣東

2、工業(yè)大學(xué)計算機學(xué)院4命題與真值命題與真值 命題命題：判斷結(jié)果惟一的陳述句。：判斷結(jié)果惟一的陳述句。 命題的真值命題的真值：判斷的結(jié)果。：判斷的結(jié)果。 真值的取值真值的取值：真與假。：真與假。 真真命題與命題與假假命題：真值為命題：真值為真真( (假假) )的命題的命題注意：注意：1. 1. 感嘆句、祈使句、疑問句都感嘆句、祈使句、疑問句都不是不是命題命題2. 2. 陳述句中的陳述句中的悖論悖論不是命題。不是命題。3. 3. 判斷結(jié)果不惟一確定的不是命題。判斷結(jié)果不惟一確定的不是命題。 1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞廣東工業(yè)大學(xué)計算機學(xué)院5例例1 1 下列句子中那些是命題？下列句子中那些是命題

3、？ (1) 是有理數(shù)是有理數(shù). (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室嗎？你去教室嗎？ (5) 這個蘋果真大呀！這個蘋果真大呀！ (6) 請不要講話！請不要講話！ (7) 2034年中國勇奪世界杯年中國勇奪世界杯. (8) 我正在說假話我正在說假話.2 假命題假命題命題概念命題概念 真命題真命題不是命題。真值無法確定不是命題。真值無法確定 不是命題不是命題 。疑問句。疑問句不是命題。感嘆句不是命題。感嘆句不是命題。祈使句不是命題。祈使句命題，但真值現(xiàn)在不知道命題，但真值現(xiàn)在不知道不是命題。不是命題。悖論：悖論：由真能推出假，又由假能推出真，從由真能推出假，又由

4、假能推出真，從而既不能為真，又不能為假的陳述句而既不能為真，又不能為假的陳述句廣東工業(yè)大學(xué)計算機學(xué)院6l 命題分類：簡單命題（也稱原子命題）與復(fù)合命題命題分類：簡單命題（也稱原子命題）與復(fù)合命題簡單命題符號化（本書定義）：簡單命題符號化（本書定義）：l 1. 用用小寫英文字母小寫英文字母 p, q, r, , pi, qi, ri (I 1)表示簡單命表示簡單命題題l 2. 用用“1”表示真，用表示真，用“0”表示假表示假 例如：例如：令令 p： 是有理數(shù)，則是有理數(shù)，則 p 的真值為的真值為0， q：2 + 5 = 7，則，則 q 的真值為的真值為1 2命題分類命題分類廣東工業(yè)大學(xué)計算機學(xué)院

5、71. 否定、合取、析取聯(lián)結(jié)詞否定、合取、析取聯(lián)結(jié)詞定義定義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同時為假同時為假.定義定義1.1 設(shè)設(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為假為假.定義定義1.2 設(shè)設(shè)p,q為兩個命題，復(fù)合命題為兩個命題，復(fù)合命題“p并且并且q”(

6、或或“p與與 q”)稱為稱為p與與q的的合取式合取式，記作，記作pq，稱作稱作合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞. 規(guī)定：規(guī)定： pq為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與q同時為真同時為真.廣東工業(yè)大學(xué)計算機學(xué)院8例例2 將下列命題符號化將下列命題符號化. (1) 吳穎既用功又聰明吳穎既用功又聰明. (2) 吳穎不僅用功而且聰明吳穎不僅用功而且聰明. (3) 吳穎雖然聰明，但不用功吳穎雖然聰明，但不用功. (4) 張輝與王麗都是三好生張輝與王麗都是三好生. (5) 張輝與張輝與王麗是同學(xué)王麗是同學(xué).合取聯(lián)結(jié)詞的實例合取聯(lián)結(jié)詞的實例 (1) p q解解 令令p:吳穎用功吳穎用功, q:吳穎聰明吳穎聰明 (2) p

7、q (3) p q設(shè)設(shè)p:張輝是三好生張輝是三好生, q:王麗是三好生王麗是三好生(4) p q(5) p: 張輝與張輝與王麗是同學(xué)王麗是同學(xué)(1)(3) 說明描述合取式的靈活性與多樣性說明描述合取式的靈活性與多樣性(4)(5) 要求分清要求分清 “與與” 所聯(lián)結(jié)的成分所聯(lián)結(jié)的成分廣東工業(yè)大學(xué)計算機學(xué)院9例例3 將下列命題符號化將下列命題符號化(1) 2 或或 4 是素數(shù)是素數(shù).(2) 2 或或 3 是素數(shù)是素數(shù).(3) 4 或或 6 是素數(shù)是素數(shù).(4) 小元只能拿一個蘋果或一個梨小元只能拿一個蘋果或一個梨.(5) 王小紅生于王小紅生于 1975 年或年或 1976 年年.析取聯(lián)結(jié)詞的實例析

8、取聯(lián)結(jié)詞的實例解：解：(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相容或相容或排斥或排斥或廣東工業(yè)大學(xué)計算機學(xué)院10定義定義1.4 設(shè)設(shè)p, q為兩個命題，復(fù)合命題為兩個命題，復(fù)合命題“如果如果p

9、, 則則q”稱作稱作p與與q的的蘊涵式蘊涵式，記作，記作pq，并稱，并稱p是蘊涵式的是蘊涵式的前件前件，q為蘊涵式的為蘊涵式的后后件件，稱作稱作蘊涵聯(lián)結(jié)詞蘊涵聯(lián)結(jié)詞. 規(guī)定：規(guī)定：pq為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng)p為真為真q為假為假.2. 蘊涵聯(lián)結(jié)詞蘊涵聯(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 或或 除非除非q，否則非，否則非p， (3) 當(dāng)當(dāng) p 為假時，為假時，pq恒為真，稱為恒為真

10、，稱為空證明空證明 (4) 常出現(xiàn)的錯誤：不分常出現(xiàn)的錯誤：不分充分與必要條件充分與必要條件廣東工業(yè)大學(xué)計算機學(xué)院11例例4 設(shè)設(shè) p：天冷，：天冷，q：小王穿羽絨服，將下列命題符號化：小王穿羽絨服，將下列命題符號化(1) 只要天冷，小王就穿羽絨服只要天冷，小王就穿羽絨服.(2) 因為天冷，所以小王穿羽絨服因為天冷，所以小王穿羽絨服.(3) 若小王不穿羽絨服，則天不冷若小王不穿羽絨服，則天不冷.(4) 只有天冷，小王才穿羽絨服只有天冷，小王才穿羽絨服.(5) 除非天冷，小王才穿羽絨服除非天冷，小王才穿羽絨服.(6) 除非小王穿羽絨服，否則天不冷除非小王穿羽絨服，否則天不冷.(7) 如果天不冷，

11、則小王不穿羽絨服如果天不冷，則小王不穿羽絨服.(8) 小王穿羽絨服僅當(dāng)天冷的時候小王穿羽絨服僅當(dāng)天冷的時候.(9) 只要小王穿羽絨服，天就冷只要小王穿羽絨服，天就冷.蘊涵聯(lián)結(jié)詞的實例蘊涵聯(lián)結(jié)詞的實例pq注意：注意： pq 與與 qp 等值（真值表相同）等值（真值表相同）pqpqqpqppqqpqpqp廣東工業(yè)大學(xué)計算機學(xué)院12定義定義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 的邏

12、輯關(guān)系：的邏輯關(guān)系：p與與q互為充分必要條件互為充分必要條件3. 等價聯(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ù). 10010廣東工業(yè)大學(xué)計算機學(xué)院13l 本小節(jié)中本小節(jié)中p, q, r, 均表示命題均表示命題.l

13、 聯(lián)結(jié)詞集為聯(lián)結(jié)詞集為 , , , , 。運算順序：。運算順序： , , , , , 同級按先出現(xiàn)者先運算同級按先出現(xiàn)者先運算.l p, p q, p q, p q, p q為基本復(fù)合命題為基本復(fù)合命題. 其中要特其中要特別注意理解別注意理解pq的涵義的涵義. 反復(fù)使用反復(fù)使用 , , , , 中的聯(lián)中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題結(jié)詞組成更為復(fù)雜的復(fù)合命題. 其定義見其定義見P7.例：例：設(shè)設(shè) p: 是無理數(shù)，是無理數(shù)，q: 3是奇數(shù)，是奇數(shù)， r: 蘋果是方的，蘋果是方的， s: 太陽繞地球轉(zhuǎn)太陽繞地球轉(zhuǎn) 則復(fù)合命題則復(fù)合命題 (pq) (rs) p) 是？是？. 2小結(jié)小結(jié)假命題假命題廣

14、東工業(yè)大學(xué)計算機學(xué)院141.2 命題公式及其賦值命題公式及其賦值1. 1. 命題變項與合式公式命題變項與合式公式l 命題變項命題變項l 合式公式合式公式l 合式公式的層次合式公式的層次2. 2. 公式的賦值公式的賦值l 公式賦值公式賦值l 公式類型公式類型l 真值表真值表廣東工業(yè)大學(xué)計算機學(xué)院15命題變項與合式公式命題變項與合式公式 命題常項（命題常元）：命題常項（命題常元）：即簡單命題，其真值是確定的。即簡單命題，其真值是確定的。 命題變項（命題變元）：命題變項（命題變元）：可取值為可取值為1（真）或者（真）或者0（假）的變元（假）的變元 常項與變項均用常項與變項均用 p, q, r, ,

15、pi, qi, ri, , 等表示等表示. l 定義定義1.6 合式公式合式公式（簡稱公式）的遞歸定義（簡稱公式）的遞歸定義(P8)： (1) 單個命題變項和命題常項是合式公式單個命題變項和命題常項是合式公式, 稱作稱作原子命題公式原子命題公式 (2) 若若A是合式公式，則是合式公式，則 ( A)也是也是合式公式合式公式 (3) 若若A, B是合式公式，則是合式公式，則(A B), (A B), (AB), (AB)也是也是合合式公式式公式 (4) 只有有限次地應(yīng)用只有有限次地應(yīng)用(1) (3)形成的符號串才是形成的符號串才是合式公式合式公式廣東工業(yè)大學(xué)計算機學(xué)院16命題變項與合式公式的補充說

16、明命題變項與合式公式的補充說明定義定義1.6 合式公式合式公式幾點補充說明：幾點補充說明：1. 定義使用了定義使用了遞歸方式遞歸方式，這種方式類似于漢諾塔問題的描述，這種方式類似于漢諾塔問題的描述，是一種常見的定義方式是一種常見的定義方式2. 定義中使用定義中使用A、B等符號表示任意的合式公式，稱作等符號表示任意的合式公式，稱作元語言符元語言符號號。 p, p q, p q, p q,等稱作等稱作對象語言符號對象語言符號。對象語言對象語言是指是指用來描述研究對象的語言。用來描述研究對象的語言。 元語言元語言和和對象語言對象語言的關(guān)系：的關(guān)系：元語言元語言用于描述用于描述對象語言對象語言。3.

17、( A)、(A B)等公式單獨出現(xiàn)時，外層括號可省去。等公式單獨出現(xiàn)時，外層括號可省去。廣東工業(yè)大學(xué)計算機學(xué)院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(i, j)； (c) A=B C, 其中其中 B,C 的層次及的層次及 n 同同(b)； (d) A=BC, 其

18、中其中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層公式層公式.廣東工業(yè)大學(xué)計算機學(xué)院18定義定義1.8 設(shè)設(shè)p1, p2, , pn是出現(xiàn)在公式是出現(xiàn)在公式A中的全部命題變項中的全部命題變項, 給給p1, p2, , pn各指定一個真值各指定一個真值, 稱為對稱為對A的一個的一個賦

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

20、(pq)r：成真賦值：成真賦值：000, 010, 101, 110成假賦值：成假賦值：001, 011, 100, 111廣東工業(yè)大學(xué)計算機學(xué)院19定義定義1.9 將命題公式將命題公式A在所有賦值下取值的情況列成表在所有賦值下取值的情況列成表, 稱作稱作A的的真值表真值表.構(gòu)造真值表的步驟構(gòu)造真值表的步驟:(1) 找出公式中所含的全部命題變項找出公式中所含的全部命題變項p1, p2, , pn(若無下角標(biāo)若無下角標(biāo) 則按字母順序排列則按字母順序排列), 列出列出2n個全部賦值個全部賦值, 從從000開始開始, 按按 二進(jìn)制加法二進(jìn)制加法, 每次加每次加1, 直至直至111為止為止. (2)

21、按從低到高的順序?qū)懗龉降母鱾€層次按從低到高的順序?qū)懗龉降母鱾€層次.(3) 對每個賦值依次計算各層次的真值對每個賦值依次計算各層次的真值, 直到最后計算出公式直到最后計算出公式 的真值為止的真值為止.真值表真值表廣東工業(yè)大學(xué)計算機學(xué)院20例例6. 寫出下列公式的真值表寫出下列公式的真值表, 并求它們的成真賦值和成假賦值并求它們的成真賦值和成假賦值: (1) (p q) r真值表舉例真值表舉例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 成真賦值成真賦值成假賦值成假賦值

22、廣東工業(yè)大學(xué)計算機學(xué)院21(2) B (qp) qp成真賦成真賦值值:00, 01, 10, 11; 無成假賦值無成假賦值p q qp(qp) q(qp) qp0 00 11 01 1101100011111真值表舉例真值表舉例(續(xù)續(xù)1)廣東工業(yè)大學(xué)計算機學(xué)院22(3) C ( p q) q的真值表的真值表成假賦值成假賦值:00, 01, 10, 11; 無成真賦值無成真賦值p q p p q ( p q) ( p q) q0 00 11 01 11100110100100000真值表舉例真值表舉例(續(xù)續(xù)2)廣東工業(yè)大學(xué)計算機學(xué)院23啞元啞元啞元：啞元：設(shè)公式設(shè)公式A，B中含有命題變項中含有命

23、題變項p1, p2, , pn。A或者或者B不不全含全含這些命題變項，比如這些命題變項，比如A中不含中不含pi, 則稱這些命題變項為則稱這些命題變項為A的啞元。的啞元。特點：特點：A的取值與啞元無關(guān)。的取值與啞元無關(guān)。例：例：存在下列公式：存在下列公式： (1) p q (2) q r (3) ( p q) (q r) p則在這些公式中：則在這些公式中：對于公式對于公式(1)，r是啞元。是啞元。對于公式對于公式(2)，p是啞元。是啞元。對于公式對于公式(3)沒有啞元。沒有啞元。廣東工業(yè)大學(xué)計算機學(xué)院24公式的類型公式的類型定義定義1.10 設(shè)設(shè)A為任一命題公式為任一命題公式.(1) 若若A在它

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

25、, 判斷公判斷公式的類型式的類型廣東工業(yè)大學(xué)計算機學(xué)院25第一章第一章 小結(jié)小結(jié)主要內(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 熟練地求公

26、式的真值表，并用它求公式的成真賦值與成假熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型賦值及判斷公式類型廣東工業(yè)大學(xué)計算機學(xué)院261. 將下列命題符號化將下列命題符號化 (1) 豆沙包是由面粉和紅小豆做成的豆沙包是由面粉和紅小豆做成的. (2) 蘋果樹和梨樹都是落葉喬木蘋果樹和梨樹都是落葉喬木. (3) 王小紅或李大明是物理組成員王小紅或李大明是物理組成員. (4) 王小紅或李大明中的一人是物理組成員王小紅或李大明中的一人是物理組成員.提示：提示：分清復(fù)合命題與簡單命題分清復(fù)合命題與簡單命題分清相容或與排斥或分清相容或與排斥或 解：解： (1) 是簡單命題是簡單命題 (2) 是合取式是合取式 (3) 是析取式（相容或）是析取式（相容或）(4) 是析取式（排斥或）是析取式（排斥或）練習(xí)練習(xí)1pp qp q(pq) ( p q)廣東工業(yè)大學(xué)計算機學(xué)院271. 將下列命題符號化將下列命題符號化 (5) 由于交通阻塞，他遲到了由于交通阻塞，他遲到了. (6) 如果交通不阻塞，他就不會遲到如果交通不阻塞，他就不會遲到. (7) 他沒遲到，所以交通沒阻塞他沒遲到，所以交通沒阻塞. (8) 除非交通阻塞，否則他不會遲到除非交通阻塞，否則他不會遲到. (9) 他遲