離散數(shù)學(xué) 集合初步

1、第1章 數(shù)學(xué)語言與證明方法1第1章 數(shù)學(xué)語言與證明方法1.1 邏輯符號(hào)邏輯符號(hào)1.2 集合及其運(yùn)算集合及其運(yùn)算1.3 證明方法概述證明方法概述21.1 邏輯符號(hào)3命題與真值命題與真值聯(lián)結(jié)詞聯(lián)結(jié)詞(, , , ,)命題公式命題公式(重言式重言式,矛盾式矛盾式,可滿足式可滿足式)重要等值式重要等值式重要推理規(guī)則重要推理規(guī)則個(gè)體個(gè)體,個(gè)體域與謂詞個(gè)體域與謂詞全稱量詞與存在量詞全稱量詞與存在量詞聯(lián)結(jié)詞真值真值:真真, 假假 或或 1, 0命題命題:具有確定真值的陳述句具有確定真值的陳述句, 通常用通常用p,q,r等表示等表示真命題真命題:真值為真的命題真值為真的命題假命題假命題:真值為假的命題真值為假

2、的命題例如例如, p:2+2=4, q:3是偶數(shù)是偶數(shù)它們都是命題它們都是命題, p是真命題是真命題, q是假命題是假命題.否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞 否定式否定式 p: 非非p (p的否定的否定) ) p 為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p為假為假4聯(lián)結(jié)詞(續(xù))5合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞 合取式合取式p q: :p并且并且q ( (p與與q) p q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與q同時(shí)為真同時(shí)為真析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞 析取式析取式p q: p或或q p q為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng)p與與q同時(shí)為假同時(shí)為假排斥或聯(lián)結(jié)詞排斥或聯(lián)結(jié)詞排斥或排斥或p q: p并且非并且非q, 或者或者q并且非并且非p p q為真當(dāng)且僅

3、當(dāng)為真當(dāng)且僅當(dāng)p與與q中一個(gè)為真中一個(gè)為真,另一個(gè)為假另一個(gè)為假聯(lián)結(jié)詞(續(xù))蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵式蘊(yùn)涵式pq:如果如果p,則則q pq為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng) p 為真為真 q 為假為假等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞等價(jià)式等價(jià)式pq:p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q pq為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與q同時(shí)為真或同時(shí)為假同時(shí)為真或同時(shí)為假6實(shí)例 設(shè)設(shè)p:2是偶數(shù)是偶數(shù), q:1+1=3, 則則7p的真值為的真值為 1q的真值為的真值為p的真值為的真值為q的真值為的真值為p q的真值為的真值為p q的真值為的真值為p q的真值為的真值為 p q的真值為的真值為p q的真值為的真值為p q的真值為的真值為p q的真

4、值為的真值為p q的真值為的真值為p q的真值為的真值為p q的真值為的真值為0010110111001 p q的真值為的真值為 p q的真值為的真值為00實(shí)例(續(xù)) pq的真值為的真值為8pq的真值為的真值為pq的真值為的真值為pq的真值為的真值為0111又設(shè)又設(shè) r:今天是星期一今天是星期一, s:明天是星期二明天是星期二, t:明天是星期三明天是星期三rs的真值為的真值為rt的真值為的真值為1不定不定命題公式命題變項(xiàng)命題變項(xiàng):取值為取值為0或或1的變?cè)淖冊(cè)? 也用也用p,q,r等表示等表示.命題公式命題公式:用聯(lián)結(jié)詞和圓括號(hào)把命題和命題變項(xiàng)按照一定用聯(lián)結(jié)詞和圓括號(hào)把命題和命題變項(xiàng)按照一

5、定規(guī)則連接起來的符號(hào)串規(guī)則連接起來的符號(hào)串, 常用常用A,B,C等表示等表示.例如例如, A=( p q)(r p)公式的賦值公式的賦值:對(duì)公式中每一個(gè)命題變項(xiàng)給定一個(gè)值對(duì)公式中每一個(gè)命題變項(xiàng)給定一個(gè)值(0或或1).公式的公式的成真賦值成真賦值:使公式為真的賦值使公式為真的賦值.公式的公式的成假賦值成假賦值:使公式為假的賦值使公式為假的賦值.例如例如, p=1,q=1,r=1是是A的成真賦值的成真賦值, p=0,q=1,r=0是是A的成假賦值的成假賦值.9重言式,矛盾式與可滿足式重言式重言式( (永真式永真式) ): :無成假賦值的命題公式無成假賦值的命題公式矛盾式矛盾式( (永假式永假式)

6、): :無成真賦值的命題公式無成真賦值的命題公式可滿足式可滿足式: :不是矛盾式的命題公式不是矛盾式的命題公式例如例如, , A= ( p q)(r p)是可滿足式是可滿足式, 但不是重言式但不是重言式, B= (p q) ( p q) (p q) ( p q)是重言式是重言式, C= p (p q) (p q)是矛盾式是矛盾式. .AB: :蘊(yùn)涵式蘊(yùn)涵式AB B是重言式的簡(jiǎn)記是重言式的簡(jiǎn)記. .AB:等價(jià)式等價(jià)式AB是重言式的簡(jiǎn)記，是重言式的簡(jiǎn)記， 稱稱A與與B等值等值，AB是是等值式等值式. . 10基本等值式雙重否定律雙重否定律 AA冪等律冪等律 A AA, A AA交換律交換律 A B

7、B A, A BB A結(jié)合律結(jié)合律 (A B) CA (B C) (A B) CA (B C)分配律分配律 A (B C)(A B) (A C) A (B C) (A B) (A C)德德摩根律摩根律 (A B)AB (A B)AB11基本等值式(續(xù))吸收律吸收律 A (A B)A, A (A B)A零律零律 A 11, A 00 同一律同一律 A 0A, A 1A排中律排中律 AA1矛盾律矛盾律 AA0蘊(yùn)涵等值式蘊(yùn)涵等值式 AB A B等價(jià)等值式等價(jià)等值式 AB(AB) (BA)假言易位等值式假言易位等值式 AB B A等價(jià)否定等值式等價(jià)否定等值式 AB A B歸謬論歸謬論 (AB) (AB

8、) A12重要推理規(guī)則(推理定律)附加律附加律 A (A B) 化簡(jiǎn)律化簡(jiǎn)律 (A B) A假言推理假言推理 (AB) A B拒取式拒取式 (AB)B A析取三段論析取三段論 (A B)B A假言三段論假言三段論 (AB) (BC) (AC)等價(jià)三段論等價(jià)三段論 (AB) (BC) (AC)構(gòu)造性二難構(gòu)造性二難 (AB) (CD) (A C) (B D) 破壞性二難破壞性二難 (AB) (CD) ( BD) ( AC) 13謂詞與量詞個(gè)體域個(gè)體域:被研究對(duì)象的全體被研究對(duì)象的全體, 如自然數(shù)集如自然數(shù)集, 人類等人類等.個(gè)體詞個(gè)體詞:個(gè)體域中的一個(gè)元素個(gè)體域中的一個(gè)元素.全稱量詞全稱量詞 :

9、表示任意的表示任意的, 所有的所有的, 一切的等一切的等.存在量詞存在量詞 : 表示存在表示存在, 有的有的, 至少有一個(gè)等至少有一個(gè)等.謂詞謂詞: 表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞例如例如, 謂詞謂詞P(x)表示表示x具有性質(zhì)具有性質(zhì)P x P(x) 表示個(gè)體域中所有的表示個(gè)體域中所有的x具有性質(zhì)具有性質(zhì)P x P(x) 表示個(gè)體域中存在表示個(gè)體域中存在x具有性質(zhì)具有性質(zhì)P141.2 集合及其運(yùn)算集合及其表示法集合及其表示法包含包含(子集子集)與相等與相等空集與全集空集與全集集合運(yùn)算集合運(yùn)算( , , - , , )基本集合恒等式基本集合恒等式包含與相等的證明

10、方法包含與相等的證明方法15集合的概念樸素集合論樸素集合論(康托康托, G.Cantor), 羅素羅素(Russell)悖論悖論集合集合是數(shù)學(xué)中最基本的概念是數(shù)學(xué)中最基本的概念,沒有嚴(yán)格的定義沒有嚴(yán)格的定義 理解成理解成某些個(gè)體組成的整體某些個(gè)體組成的整體, 常用常用A,B,C等表示等表示元素元素:集合中的個(gè)體集合中的個(gè)體無窮集無窮集:元素個(gè)數(shù)無限的集合元素個(gè)數(shù)無限的集合有窮集有窮集(有限集有限集):元素個(gè)數(shù)有限的集合元素個(gè)數(shù)有限的集合. |A|:A中元素個(gè)數(shù)中元素個(gè)數(shù)k元集元集:k個(gè)元素的集合個(gè)元素的集合, k 016集合的表示法列舉法列舉法 如如 A= a, b, c, d , N=0,1

11、,2,描述法描述法 x | P(x) 如如N= x | x是自然數(shù)是自然數(shù) 說明說明: (1) 集合中的元素各不相同集合中的元素各不相同. 如如, 1,2,3=1,1,2,3(2) 集合中的元素沒有次序集合中的元素沒有次序. 如如, 1,2,3=3,1,2=1,3,1,2,2(3) 有時(shí)兩種方法都適用有時(shí)兩種方法都適用, 可根據(jù)需要選用可根據(jù)需要選用.常用集合常用集合 自然數(shù)集自然數(shù)集N, 整數(shù)集整數(shù)集Z, 正整數(shù)集正整數(shù)集Z+, 有理數(shù)集有理數(shù)集Q, 非零有理數(shù)集非零有理數(shù)集Q*, 實(shí)數(shù)集實(shí)數(shù)集R, 非零實(shí)數(shù)集非零實(shí)數(shù)集R*, 復(fù)數(shù)集復(fù)數(shù)集C, 區(qū)間區(qū)間a,b,(a,b)等等17包含與相等包

12、含包含(子集子集) A B x (x A x B)不包含不包含 A B x (x A x B) 相等相等 A = B A B B A不相等不相等 A B A B B A真包含真包含(真子集真子集) A B A B A B 例如例如, A=1,2,3, B= x | x R |x| 1 , C= x | x R x2=1 , D=-1,1, C B, C B, C A, A B, B A, C = D性質(zhì)性質(zhì) (1) A A (2) A B B C A C18空集與全集空集空集: 不含任何元素的集合不含任何元素的集合例如例如, x | x20 x R=定理定理1.1 空集是任何集合的子集空集是任

13、何集合的子集證證 用歸謬法用歸謬法. 假設(shè)不然假設(shè)不然, 則存在集合則存在集合A, 使得使得 A, 即存在即存在x, x 且且x A, 矛盾矛盾. 推論推論 空集是惟一的空集是惟一的.證證 假設(shè)存在假設(shè)存在1和和2，則，則12 且且12，因此，因此1=2全集全集E:限定所討論的集合都是限定所討論的集合都是E的子集的子集. 相對(duì)性相對(duì)性 19冪集冪集冪集P(A):A的所有子集組成的集合的所有子集組成的集合, 即即 P(A) = x | x A 例如例如, 設(shè)設(shè)A=a,b,c A的的0元子集元子集: A的的1元子集元子集: a, b, c A的的2元子集元子集:a,b,a,c,b,c A的的3元子

14、集元子集: a,b,c P(A) =, a, b, c, a,b. a,c, b,c, a,b,c20nnnnnnCCCAP2)11(| )(|10定理定理1.2 如果如果 |A| = n，則則 |P(A)| = 2n 證證集合運(yùn)算并并 A B = x | x A x B 交交 A B = x | x A x B 相對(duì)補(bǔ)相對(duì)補(bǔ) A B = x | x A x B 對(duì)稱差對(duì)稱差 A B = (A B) (B A) = (A B) (A B) 絕對(duì)補(bǔ)絕對(duì)補(bǔ) A = E A= x | x A 例如例如 設(shè)設(shè)E=0,1, ,9, A=0,1,2,3, B=1,3,5,7,9, 則則 A B =0,1,

15、2,3,5,7,9, A B =1,3, A B =0,2, A B =0,2,5,7,9, A =4,5,6,7,8,9, B =0,2,4,6,821實(shí)例例例1 設(shè)設(shè)E= x | x是北京某大學(xué)學(xué)生是北京某大學(xué)學(xué)生, A,B,C,D是是E的子集的子集,A= x | x是北京人是北京人, B= x | x是走讀生是走讀生,C= x | x是數(shù)學(xué)系學(xué)生是數(shù)學(xué)系學(xué)生, D= x | x是喜歡聽音樂的學(xué)生是喜歡聽音樂的學(xué)生.試描述下列各集合中學(xué)生的特征試描述下列各集合中學(xué)生的特征:22(A D) C= A B=(A-B) D= D B= x | x是北京人或喜歡聽音樂是北京人或喜歡聽音樂, 但不是

16、數(shù)學(xué)系學(xué)生但不是數(shù)學(xué)系學(xué)生 x | x是外地走讀生是外地走讀生 x | x是北京住校生是北京住校生, 并且喜歡聽音樂并且喜歡聽音樂 x | x是不喜歡聽音樂的住校生是不喜歡聽音樂的住校生文氏圖表示23集合運(yùn)算(續(xù))24并和交運(yùn)算可以推廣到有窮個(gè)集合上并和交運(yùn)算可以推廣到有窮個(gè)集合上 A1 A2 An= x | x A1 x A2 x An A1 A2 An= x | x A1 x A2 x An并和交運(yùn)算還可以推廣到可數(shù)無窮個(gè)集合上并和交運(yùn)算還可以推廣到可數(shù)無窮個(gè)集合上 A1 A2 = x | i (i=1,2,) x Ai A1 A2 = x | i (i=1,2,) x Ai niiA1n

17、iiA11iiA1iiA實(shí)例例例2 設(shè)設(shè)Ai=0, 1/i ), Bi=(0, i ), i=1,2, , 則則25niiA11iiAniiA11iiAniiB11iiBnii1B1iiB0, 1)0, 1)0, 1/n ) 0 (0, n)(0, +)(0, 1)(0, 1)基本集合恒等式1. 冪等律冪等律A A=A, A A=A2. 交換律交換律A B=B A, A B=B A3. 結(jié)合律結(jié)合律(A B) C=A (B C) (A B) C=A (B C)4. 分配律分配律A (B C)=(A B) (A C) A (B C)=(A B) (A C)5. 德摩根律德摩根律 絕對(duì)形式絕對(duì)形式

18、 (B C)= BC, (B C)= BC 相對(duì)形式相對(duì)形式 A (B C)=(A B) (A C) A (B C)=(A B) (A C)26基本集合恒等式(續(xù))6. 吸收律吸收律 A (A B)=A, A (A B)=A7. 零律零律 A E=E, A=8. 同一律同一律 A=A,A E=A9. 排中律排中律 AA=E10. 矛盾律矛盾律 AA=11. 余補(bǔ)律余補(bǔ)律 =E, E=12. 雙重否定律雙重否定律 A=A13. 補(bǔ)交轉(zhuǎn)換律補(bǔ)交轉(zhuǎn)換律 A-B= AB27基本集合恒等式(續(xù))14. 關(guān)于對(duì)稱差的恒等式關(guān)于對(duì)稱差的恒等式 (1) 交換律交換律 A B=B A (2) 結(jié)合律結(jié)合律 (A

19、 B) C=A (B C) (3) 對(duì)對(duì) 的分配律的分配律 A (B C)=(A B) (A C) (4) A=A, A E= A (5) A A=, A A= E28注意注意: 對(duì)對(duì) 沒有分配律沒有分配律, 反例如下反例如下 A=a,b,c, B=b,c,d, C=c,d,e A (B C)= a,b,c b,e= a,b,c,e (A B) (A C)= a,b,c,d a,b,c,d,e= e, 兩者不等兩者不等證明集合包含或相等方法一方法一. 根據(jù)定義根據(jù)定義, 通過邏輯等值演算證明通過邏輯等值演算證明方法二方法二. 利用已知集合等式或包含式利用已知集合等式或包含式, 通過集合演算證明

20、通過集合演算證明例例3 證明證明:(1) A B=B A (交換交換律律)證證 x x A B x A x B (并的定義并的定義) x B x A (邏輯演算的交換律邏輯演算的交換律) x B A (并的定義并的定義)29例3(續(xù))(2) A (B C)=(A B) (A C) (分配律分配律)證證 x x A (B C) x A (x B x C) (并并,交的定義交的定義) (x A x B) (x A x C) (邏輯演算的分配律邏輯演算的分配律) x (A B) (A C) (并并,交的定義交的定義)(3) A E=E (零律零律)證證 x x A E x A x E (并的定義并的

21、定義) x A 1 (全集全集E的定義的定義) 1 (邏輯演算的零律邏輯演算的零律) x E (全集全集E的定義的定義)30例3(續(xù))(4) A E=A (同一同一律律)證證 x x A E x A x E (交的定義交的定義) x A 1 (全集全集E的定義的定義) x A (邏輯演算的同一律邏輯演算的同一律)31實(shí)例例例4 證明證明 A (A B)=A （吸收律）吸收律）證證 利用例利用例3證明的證明的4條等式證明條等式證明 A (A B) = (A E) (A B) (同一律同一律) = A (E B) (分配律分配律) = A (B E) (交換律交換律) = A E (零律零律) = A (同一律同一律)對(duì)其余的基本集合恒等式不再一一證明對(duì)其余的基本集合恒等式不再一一證明,今后把它們作為已知的集合等式使用今后把它們作為已知的集合等式使用.32實(shí)例例例5 證明證明 (A-B)-