離散數(shù)學(xué)1.1-2

1、1離散數(shù)學(xué)離散數(shù)學(xué)張波張波E-mail：手機(jī)：手機(jī)公室：行政樓辦公室：行政樓B2122主要內(nèi)容主要內(nèi)容n數(shù)理邏輯（又稱符號(hào)邏輯）數(shù)理邏輯（又稱符號(hào)邏輯）n集合論集合論n代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)n圖論圖論n組合分析初步組合分析初步n形式語言和自動(dòng)機(jī)初步形式語言和自動(dòng)機(jī)初步3數(shù)理邏輯部分?jǐn)?shù)理邏輯部分n第第1章章 命題邏輯命題邏輯n第第2章章 一階邏輯一階邏輯4第第1章章 命題邏輯命題邏輯 1.1 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞1.2 命題公式及分類命題公式及分類1.3 等值演算等值演算1.4 對(duì)偶與范式對(duì)偶與范式1.5 推理理論推理理論51.1 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化

2、及聯(lián)結(jié)詞 n命題與真值命題與真值n原子命題原子命題n復(fù)合命題復(fù)合命題n命題常項(xiàng)命題常項(xiàng)n命題變項(xiàng)命題變項(xiàng)n聯(lián)結(jié)詞聯(lián)結(jié)詞 6命題與真值命題與真值 命題命題: 判斷結(jié)果惟一的陳述句判斷結(jié)果惟一的陳述句命題的真值命題的真值: 判斷的結(jié)果判斷的結(jié)果真值的取值真值的取值: 真與假真與假真命題真命題: 真值為真的命題真值為真的命題假命題假命題: 真值為假的命題真值為假的命題注意注意: 1.感嘆句、祈使句、疑問句都不是命題；感嘆句、祈使句、疑問句都不是命題； 2.陳述句中的悖論不是命題；陳述句中的悖論不是命題； 3.判斷結(jié)果不惟一確定的不是命題判斷結(jié)果不惟一確定的不是命題7 例例 下列句子中那些是命題？下列

3、句子中那些是命題？ (1) 是無理數(shù)是無理數(shù). (2) 2 + 5 8. (3) x + 5 3. (4) 你今天偷菜了嗎？你今天偷菜了嗎？ (5) 這只兔子跑得真快呀！這只兔子跑得真快呀！ (6) 誠湖內(nèi)不許滑冰！誠湖內(nèi)不許滑冰！ (7) 我正在說謊話我正在說謊話.真命題真命題假命題假命題真值不確定真值不確定疑問句疑問句感嘆句感嘆句祈使句祈使句悖論悖論(3)(7)都不是命題都不是命題28例例 下列句子中那些是命題？下列句子中那些是命題？ (8)明年明年10月月1日是晴天日是晴天. (9) 地球外的星球上也有人地球外的星球上也有人.（10）111100. （8）、（）、（9）的真值雖然現(xiàn)在還不

4、知道，但它）的真值雖然現(xiàn)在還不知道，但它的真值是唯一的，因而是命題。的真值是唯一的，因而是命題。（10）在二進(jìn)制中為真，在十進(jìn)制中為假，需）在二進(jìn)制中為真，在十進(jìn)制中為假，需根據(jù)上下文才能確定其真值，因而不是命題。根據(jù)上下文才能確定其真值，因而不是命題。9命題的分類命題的分類 1. 1.簡(jiǎn)單命題簡(jiǎn)單命題( (原子命題原子命題) ) 簡(jiǎn)單構(gòu)成的命題簡(jiǎn)單構(gòu)成的命題 (不能分解成更簡(jiǎn)單的陳述句不能分解成更簡(jiǎn)單的陳述句) 簡(jiǎn)單命題的真值是確定的，又稱為簡(jiǎn)單命題的真值是確定的，又稱為命題常項(xiàng)命題常項(xiàng)或或命題常元命題常元 2.2.復(fù)合命題復(fù)合命題 由簡(jiǎn)單命題與聯(lián)結(jié)詞按一定規(guī)則復(fù)合而成的命題由簡(jiǎn)單命題與聯(lián)結(jié)

5、詞按一定規(guī)則復(fù)合而成的命題 3.3.命題變項(xiàng)（命題變?cè)┟}變項(xiàng)（命題變?cè)?真值不確定的陳述句，如真值不確定的陳述句，如:x+35:x+35 注意：命題變?cè)⒁猓好}變?cè)皇遣皇敲}！命題！10簡(jiǎn)單命題符號(hào)化簡(jiǎn)單命題符號(hào)化 2用小寫英文字母用小寫英文字母 p, q, r, , ,pi, ,qi, ,ri (i1）表示）表示簡(jiǎn)單命題簡(jiǎn)單命題用用“1”表示真，用表示真，用“0”表示假表示假例如，令例如，令 p： 是有理數(shù)，則是有理數(shù)，則 p 的真值為的真值為 0 q：2 + 5 = 7，則，則 q 的真值為的真值為 1命題變項(xiàng)：命題變項(xiàng)：也用小寫英文字母也用小寫英文字母 p, q, r, , ,

6、pi, ,qi, ,ri (i1）表示）表示11聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題 1.否定式與否定聯(lián)結(jié)詞否定式與否定聯(lián)結(jié)詞“ ” 定義定義 設(shè)設(shè)p為命題，復(fù)合命題為命題，復(fù)合命題 “ “非非p”（或（或 “ “p的否定的否定”）稱稱 為為p的的否定式否定式，記作，記作 p，符號(hào)，符號(hào) 稱作稱作否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞 p 為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p為假為假2.合取式與合取聯(lián)結(jié)詞合取式與合取聯(lián)結(jié)詞“” 定義定義 設(shè)設(shè)p, ,q為二命題為二命題, ,復(fù)合命題復(fù)合命題“p并且并且q”(”(或或“p與與q”)”)稱稱 為為p與與q的的合取式合取式，記作，記作pq，稱作稱作合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞，并規(guī)，并規(guī)

7、定定 pq為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與q同時(shí)為真同時(shí)為真注意：描述合取式的靈活性與多樣性注意：描述合取式的靈活性與多樣性 分清簡(jiǎn)單命題與復(fù)合命題分清簡(jiǎn)單命題與復(fù)合命題 12 例例 將下列命題符號(hào)化將下列命題符號(hào)化. (1) 王曉既用功又聰明王曉既用功又聰明. (2) 王曉不僅聰明，而且用功王曉不僅聰明，而且用功. (3) 王曉雖然聰明，但不用功王曉雖然聰明，但不用功. (4) 張輝與王麗都是三好生張輝與王麗都是三好生. (5) 張輝與王麗是同學(xué)張輝與王麗是同學(xué).解解 令令 p：王曉用功，：王曉用功，q：王曉聰明，則：王曉聰明，則 (1) pq (2) pq (3) q p.13 例例 令令

8、r : 張輝是三好學(xué)生，張輝是三好學(xué)生，s :王麗是三好學(xué)生王麗是三好學(xué)生 (4) rs. (5) 令令 t : 張輝與王麗是同學(xué)，張輝與王麗是同學(xué)，t 是簡(jiǎn)單命題是簡(jiǎn)單命題 .說明說明: (1)(4)說明描述合取式的靈活性與多樣性說明描述合取式的靈活性與多樣性. (5) 中中“與與”不是聯(lián)結(jié)詞的含義，因而不是聯(lián)結(jié)詞的含義，因而(5)中句子中句子是是 簡(jiǎn)單命題簡(jiǎn)單命題.又如：李文與李武是兄弟。又如：李文與李武是兄弟。14聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題 定義定義 設(shè)設(shè) p,q為二命題，復(fù)合命題為二命題，復(fù)合命題“p或或q”稱作稱作p與與q 的的析取式析取式，記作，記作pq，稱作稱作析取聯(lián)結(jié)詞析

9、取聯(lián)結(jié)詞，并規(guī)，并規(guī) 定定pq為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng)p與與q同時(shí)為假同時(shí)為假.例例 將下列命題符號(hào)化將下列命題符號(hào)化 (1) 2或或4是素?cái)?shù)是素?cái)?shù). (2) 2或或3是素?cái)?shù)是素?cái)?shù). (3) 4或或6是素?cái)?shù)是素?cái)?shù). (4) 小元元只能拿一個(gè)蘋果或一個(gè)梨小元元只能拿一個(gè)蘋果或一個(gè)梨. (5) 王曉紅生于王曉紅生于1989年或年或1990年年. 3.析取式與析取聯(lián)結(jié)詞析取式與析取聯(lián)結(jié)詞“”15解解 令令 p:2是素?cái)?shù)是素?cái)?shù), q:3是素?cái)?shù)是素?cái)?shù), r:4是素?cái)?shù)是素?cái)?shù), s:6是素?cái)?shù)是素?cái)?shù), , 則則 (1), (2), (3) 均為均為相容或相容或（允許（允許同時(shí)為真同時(shí)為真）. . 分別符號(hào)化為

10、分別符號(hào)化為: : pr , pq, rs, 它們的真值分別為它們的真值分別為 1, 1, 0. 而而 (4), (5) 為為排斥或排斥或（不相容或）（不相容或）. 令令 t :小元元拿一個(gè)蘋果，小元元拿一個(gè)蘋果，u:小元元拿一個(gè)梨，小元元拿一個(gè)梨， 則則 (4) 符號(hào)化為符號(hào)化為 (t u) ( tu). 令令v :王曉紅生于王曉紅生于1975年年, ,w: :王曉紅生于王曉紅生于1976年年, ,則則 (5) 既可符號(hào)化為既可符號(hào)化為 (v w)( vw), 又可又可符號(hào)化為符號(hào)化為 vw , 為什么為什么? 16例例 （7）小王現(xiàn)在在宿舍或圖書館里）小王現(xiàn)在在宿舍或圖書館里. 令令v :

11、小王在宿舍小王在宿舍, ,w: :小王在圖書館小王在圖書館 則則 (7) 符號(hào)化為符號(hào)化為 vw例例 （6 6）選小王或小李中的一人當(dāng)班長）選小王或小李中的一人當(dāng)班長. . 解解 令令 t :小王當(dāng)班長，小王當(dāng)班長，u:小李當(dāng)班長小李當(dāng)班長 則則 (6) 符號(hào)化為符號(hào)化為 (t u) ( tu).17 定義定義 設(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 為真為

12、真 q 為假為假. 注意：注意：1. p與與q不一定有內(nèi)在聯(lián)系不一定有內(nèi)在聯(lián)系 2. 前件前件p為假時(shí)，為假時(shí)， pq為真為真4.蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞“”18pq 的邏輯關(guān)系：的邏輯關(guān)系： p為為 q 的充分條件，的充分條件，q 為為 p 的必要條件的必要條件“如果如果 p，則，則 q ” 的不同表述法很多：的不同表述法很多： 若若 p，就，就 q 只要只要 p，就，就 q p 僅當(dāng)僅當(dāng) q 只有只有 q 才才 p 除非除非 q, 才才 p 或或 除非除非 q, 否則非否則非 p，常出現(xiàn)的錯(cuò)誤：不分充分與必要條件常出現(xiàn)的錯(cuò)誤：不分充分與必要條件19 例例 設(shè)設(shè) p p: :天冷

13、，天冷，q q: :小王穿羽絨服，小王穿羽絨服， 將下列命題符號(hào)化將下列命題符號(hào)化 (1) 只要天冷，小王就穿羽絨服只要天冷，小王就穿羽絨服. (2) 因?yàn)樘炖?，所以小王穿羽絨服因?yàn)樘炖?，所以小王穿羽絨服. (3) 若小王不穿羽絨服，則天不冷若小王不穿羽絨服，則天不冷. (4) 只有天冷，小王才穿羽絨服只有天冷，小王才穿羽絨服. (5) 除非天冷，小王才穿羽絨服除非天冷，小王才穿羽絨服. (6) 除非小王穿羽絨服，否則天不冷除非小王穿羽絨服，否則天不冷. (7) 如果天不冷，則小王不穿羽絨服如果天不冷，則小王不穿羽絨服. (8) 小王穿羽絨服僅當(dāng)天冷的時(shí)候小王穿羽絨服僅當(dāng)天冷的時(shí)候.注意：注意

14、： pq 與與 q p 等值（真值相同）等值（真值相同） pqpqpqpqqp qpqpqp20定義定義 設(shè)設(shè)p，q為二命題，復(fù)合命題為二命題，復(fù)合命題 “p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q”稱稱作作p與與q的的等價(jià)式等價(jià)式，記作，記作pq，稱作稱作等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞.并并pq規(guī)為真當(dāng)且僅當(dāng)規(guī)為真當(dāng)且僅當(dāng)p與與q同時(shí)為真或同時(shí)為假同時(shí)為真或同時(shí)為假.說明說明: (1) pq 的邏輯關(guān)系的邏輯關(guān)系:p與與q互為充分必要條件互為充分必要條件 (2) pq為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與q同真或同假同真或同假 (3) p q與與(p q) (q p)等值等值5.等價(jià)式與等價(jià)聯(lián)結(jié)詞等價(jià)式與等價(jià)聯(lián)結(jié)詞“”21例例 求

15、下列復(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) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)3不是奇數(shù)不是奇數(shù). （6）兩圓面積相等當(dāng)且僅當(dāng)它們的半徑）兩圓面積相等當(dāng)且僅當(dāng)它們的半徑相等相等. 它們的真值分別為它們的真值分別為 1，0，1，0，1, 122復(fù)合命題符號(hào)化：復(fù)合命題符號(hào)化：第一步：分析出各簡(jiǎn)單命題，并將它們符號(hào)化第一步：分析出各簡(jiǎn)

16、單命題，并將它們符號(hào)化第二步：使用合適的連接詞，把簡(jiǎn)單命題逐個(gè)聯(lián)結(jié)起來第二步：使用合適的連接詞，把簡(jiǎn)單命題逐個(gè)聯(lián)結(jié)起來例例 1. 小王是小王是500米速滑冠軍或米速滑冠軍或1000米速滑冠軍米速滑冠軍 2. 小王現(xiàn)在在宿舍或在圖書館里小王現(xiàn)在在宿舍或在圖書館里 3. 選小王或小李中的一人當(dāng)班長選小王或小李中的一人當(dāng)班長 4. 如果我上街，我就去書店看看，除非我很累如果我上街，我就去書店看看，除非我很累 r （pq ） 或或 （ r p)p) q 5. 小王是計(jì)算機(jī)系學(xué)生，他生于小王是計(jì)算機(jī)系學(xué)生，他生于1990年或年或1991 年，他是三好學(xué)生年，他是三好學(xué)生23聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命

17、題以上給出了以上給出了5個(gè)聯(lián)結(jié)詞：個(gè)聯(lián)結(jié)詞： , , , , ，組成，組成一個(gè)聯(lián)結(jié)詞集合一個(gè)聯(lián)結(jié)詞集合 , , , , ， 聯(lián)結(jié)詞的優(yōu)先順序?yàn)椋郝?lián)結(jié)詞的優(yōu)先順序?yàn)椋?, , , , ; 如果出如果出現(xiàn)的聯(lián)結(jié)詞同級(jí)，又無括號(hào)時(shí)，則按從左到右現(xiàn)的聯(lián)結(jié)詞同級(jí)，又無括號(hào)時(shí)，則按從左到右的字典順序運(yùn)算的字典順序運(yùn)算; 若遇有括號(hào)時(shí)，應(yīng)該先進(jìn)行括若遇有括號(hào)時(shí)，應(yīng)該先進(jìn)行括號(hào)中的運(yùn)算號(hào)中的運(yùn)算. 注意注意: : 本書中使用的本書中使用的 括號(hào)全為圓括號(hào)括號(hào)全為圓括號(hào). 241.2 命題公式及分類命題公式及分類命題變項(xiàng)與合式公式命題變項(xiàng)與合式公式公式的賦值公式的賦值真值表真值表命題公式的分類命題公式的分類 重

18、言式重言式 矛盾式矛盾式 可滿足式可滿足式25命題變項(xiàng)與合式公式命題變項(xiàng)與合式公式 命題常項(xiàng)命題常項(xiàng)：簡(jiǎn)單命題：簡(jiǎn)單命題, ,真值確定的陳述句真值確定的陳述句命題變項(xiàng)命題變項(xiàng)：真值不確定的陳述句：真值不確定的陳述句定義定義 合式公式合式公式 (命題公式命題公式, 公式公式) 遞歸定義如下：遞歸定義如下：(1) 單個(gè)命題常項(xiàng)或變項(xiàng)單個(gè)命題常項(xiàng)或變項(xiàng) p,q,r,pi ,qi ,ri ,0,1 是是合式公式合式公式(2) 若若A是合式公式，則是合式公式，則 ( A)也是合式公式也是合式公式(3) 若若A, B是合式公式，則是合式公式，則(A B), (A B), (AB), (AB)也是合式公式也

19、是合式公式(4) 只有有限次地應(yīng)用只有有限次地應(yīng)用(1)(3)形成的符號(hào)串才是形成的符號(hào)串才是合式公式合式公式26合式公式的層次合式公式的層次 定義定義 (1) 若公式若公式A是單個(gè)的命題變項(xiàng)或命題常項(xiàng)（包括是單個(gè)的命題變項(xiàng)或命題常項(xiàng)（包括0，1）, 則稱則稱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=B

20、C, 其中其中B,C的層次及的層次及n同同(b)； (e) A=BC, 其中其中B,C的層次及的層次及n同同(b). 27合式公式的層次合式公式的層次 例如例如 公式公式 p 0層層 p 1層層 pq 2層層 (pq)r 3層層 ( p q) r)( r s) 4層層28公式的賦值公式的賦值 定義定義 給公式給公式A中的命題變項(xiàng)中的命題變項(xiàng) p1, p2, , pn，給給p1, p2, , pn各指定一個(gè)真值（各指定一個(gè)真值（0或或1），稱為對(duì)），稱為對(duì)A的一個(gè)的一個(gè)賦值賦值或或解釋解釋成真賦值成真賦值: 使公式為真的賦值使公式為真的賦值成假賦值成假賦值: 使公式為假的賦值使公式為假的賦值說明說明： 賦值賦值 = 1 2 n之間不加標(biāo)點(diǎn)符號(hào)，之間不加標(biāo)點(diǎn)符號(hào)， i=0或或1. A中僅出現(xiàn)中僅出現(xiàn) p1, p2, , pn，給，給A賦值賦值 1 2 n是是指指 p1= 1, p2= 2, , pn= n A中僅出現(xiàn)中僅出現(xiàn) p, q, r, , 給給A賦值賦值 1 2 3是指是指p= 1,q= 2 , r= 3 含含n個(gè)變項(xiàng)的公式有個(gè)變項(xiàng)的公式有2n個(gè)賦值個(gè)賦值.29真值表真值表 真值表真值表: 公式公式A在所有賦值下的取值情況列成的表在所有賦值下的取值情況列成的表 （1）列出所有命題變項(xiàng)，列出所有可能賦值）列出所有命題變項(xiàng)，列出所