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

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

2、及聯(lián)結(jié)詞 n命題與真值命題與真值n原子命題原子命題n復(fù)合命題復(fù)合命題n命題常項命題常項n命題變項命題變項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ù)上下文才能確定其真值，因而不是命題。根據(jù)上下文才能確定其真值，因而不是命題。9命題的分類命題的分類 1. 1.簡單命題簡單命題( (原子命題原子命題) ) 簡單構(gòu)成的命題簡單構(gòu)成的命題 (不能分解成更簡單的陳述句不能分解成更簡單的陳述句) 簡單命題的真值是確定的，又稱為簡單命題的真值是確定的，又稱為命題常項命題常項或或命題常元命題常元 2.2.復(fù)合命題復(fù)合命題 由簡單命題與聯(lián)結(jié)詞按一定規(guī)則復(fù)合而成的命題由簡單命題與聯(lián)結(jié)

5、詞按一定規(guī)則復(fù)合而成的命題 3.3.命題變項（命題變元）命題變項（命題變元） 真值不確定的陳述句，如真值不確定的陳述句，如:x+35:x+35 注意：命題變元注意：命題變元不是不是命題！命題！10簡單命題符號化簡單命題符號化 2用小寫英文字母用小寫英文字母 p, q, r, , ,pi, ,qi, ,ri (i1）表示）表示簡單命題簡單命題用用“1”表示真，用表示真，用“0”表示假表示假例如，令例如，令 p： 是有理數(shù)，則是有理數(shù)，則 p 的真值為的真值為 0 q：2 + 5 = 7，則，則 q 的真值為的真值為 1命題變項：命題變項：也用小寫英文字母也用小寫英文字母 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，符號，符號 稱作稱作否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞 p 為真當且僅當為真當且僅當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為真當且僅當為真當且僅當p與與q同時為真同時為真注意：描述合取式的靈活性與多樣性注意：描述合取式的靈活性與多樣性 分清簡單命題與復(fù)合命題分清簡單命題與復(fù)合命題 12 例例 將下列命題符號化將下列命題符號化. (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 是簡單命題是簡單命題 .說明說明: (1)(4)說明描述合取式的靈活性與多樣性說明描述合取式的靈活性與多樣性. (5) 中中“與與”不是聯(lián)結(jié)詞的含義，因而不是聯(lián)結(jié)詞的含義，因而(5)中句子中句子是是 簡單命題簡單命題.又如：李文與李武是兄弟。又如：李文與李武是兄弟。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為假當且僅當為假當且僅當p與與q同時為假同時為假.例例 將下列命題符號化將下列命題符號化 (1) 2或或4是素數(shù)是素數(shù). (2) 2或或3是素數(shù)是素數(shù). (3) 4或或6是素數(shù)是素數(shù). (4) 小元元只能拿一個蘋果或一個梨小元元只能拿一個蘋果或一個梨. (5) 王曉紅生于王曉紅生于1989年或年或1990年年. 3.析取式與析取聯(lián)結(jié)詞析取式與析取聯(lián)結(jié)詞“”15解解 令令 p:2是素數(shù)是素數(shù), q:3是素數(shù)是素數(shù), r:4是素數(shù)是素數(shù), s:6是素數(shù)是素數(shù), , 則則 (1), (2), (3) 均為均為相容或相容或（允許（允許同時為真同時為真）. . 分別符號化為

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

11、小王在宿舍小王在宿舍, ,w: :小王在圖書館小王在圖書館 則則 (7) 符號化為符號化為 vw例例 （6 6）選小王或小李中的一人當班長）選小王或小李中的一人當班長. . 解解 令令 t :小王當班長，小王當班長，u:小李當班長小李當班長 則則 (6) 符號化為符號化為 (t u) ( tu).17 定義定義 設(shè)設(shè) p,q為二命題，復(fù)合命題為二命題，復(fù)合命題 “如果如果p,則則q” 稱作稱作p與與q的的蘊涵式蘊涵式，記作，記作pq，并稱，并稱p是蘊涵式的是蘊涵式的前件前件，q為蘊涵式的為蘊涵式的后件后件. 稱稱作作蘊涵聯(lián)結(jié)詞蘊涵聯(lián)結(jié)詞，并規(guī)定，并規(guī)定，pq為假當且僅為假當且僅當當 p 為真為

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

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

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

15、下列復(fù)合命題的真值求下列復(fù)合命題的真值 (1) 2 + 2 4 當且僅當當且僅當 3 + 3 6. (2) 2 + 2 4 當且僅當當且僅當 3 是偶數(shù)是偶數(shù). (3) 2 + 2 4 當且僅當當且僅當 太陽從東方升起太陽從東方升起. (4) 2 + 2 4 當且僅當當且僅當 美國位于非洲美國位于非洲. (5) 2 + 2 4 當且僅當當且僅當3不是奇數(shù)不是奇數(shù). （6）兩圓面積相等當且僅當它們的半徑）兩圓面積相等當且僅當它們的半徑相等相等. 它們的真值分別為它們的真值分別為 1，0，1，0，1, 122復(fù)合命題符號化：復(fù)合命題符號化：第一步：分析出各簡單命題，并將它們符號化第一步：分析出各簡

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

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

18、言式重言式 矛盾式矛盾式 可滿足式可滿足式25命題變項與合式公式命題變項與合式公式 命題常項命題常項：簡單命題：簡單命題, ,真值確定的陳述句真值確定的陳述句命題變項命題變項：真值不確定的陳述句：真值不確定的陳述句定義定義 合式公式合式公式 (命題公式命題公式, 公式公式) 遞歸定義如下：遞歸定義如下：(1) 單個命題常項或變項單個命題常項或變項 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)形成的符號串才是形成的符號串才是合式公式合式公式26合式公式的層次合式公式的層次 定義定義 (1) 若公式若公式A是單個的命題變項或命題常項（包括是單個的命題變項或命題常項（包括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中的命題變項中的命題變項 p1, p2, , pn，給給p1, p2, , pn各指定一個真值（各指定一個真值（0或或1），稱為對），稱為對A的一個的一個賦值賦值或或解釋解釋成真賦值成真賦值: 使公式為真的賦值使公式為真的賦值成假賦值成假賦值: 使公式為假的賦值使公式為假的賦值說明說明： 賦值賦值 = 1 2 n之間不加標點符號，之間不加標點符號， 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個變項的公式有個變項的公式有2n個賦值個賦值.29真值表真值表 真值表真值表: 公式公式A在所有賦值下的取值情況列成的表在所有賦值下的取值情況列成的表 （1）列出所有命題變項，列出所有可能賦值）列出所有命題變項，列出所