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

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

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

3、當為真當且僅當p與與q中一個為真中一個為真,另一個為假另一個為假聯(lián)結詞(續(xù))蘊涵聯(lián)結詞蘊涵聯(lián)結詞蘊涵式蘊涵式pq:如果如果p,則則q pq為假當且僅當為假當且僅當 p 為真為真 q 為假為假等價聯(lián)結詞等價聯(lián)結詞等價式等價式pq:p當且僅當當且僅當q pq為真當且僅當為真當且僅當p與與q同時為真或同時為假同時為真或同時為假6實例 設設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實例(續(xù)) pq的真值為的真值為8pq的真值為的真值為pq的真值為的真值為pq的真值為的真值為0111又設又設 r:今天是星期一今天是星期一, s:明天是星期二明天是星期二, t:明天是星期三明天是星期三rs的真值為的真值為rt的真值為的真值為1不定不定命題公式命題變項命題變項:取值為取值為0或或1的變元的變元, 也用也用p,q,r等表示等表示.命題公式命題公式:用聯(lián)結詞和圓括號把命題和命題變項按照一定用聯(lián)結詞和圓括號把命題和命題變項按照一

5、定規(guī)則連接起來的符號串規(guī)則連接起來的符號串, 常用常用A,B,C等表示等表示.例如例如, A=( p q)(r p)公式的賦值公式的賦值:對公式中每一個命題變項給定一個值對公式中每一個命題變項給定一個值(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: :蘊涵式蘊涵式AB B是重言式的簡記是重言式的簡記. .AB:等價式等價式AB是重言式的簡記，是重言式的簡記， 稱稱A與與B等值等值，AB是是等值式等值式. . 10基本等值式雙重否定律雙重否定律 AA冪等律冪等律 A AA, A AA交換律交換律 A B

7、B A, A BB A結合律結合律 (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蘊涵等值式蘊涵等值式 AB A B等價等值式等價等值式 AB(AB) (BA)假言易位等值式假言易位等值式 AB B A等價否定等值式等價否定等值式 AB A B歸謬論歸謬論 (AB) (AB

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

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

10、方法包含與相等的證明方法15集合的概念樸素集合論樸素集合論(康托康托, G.Cantor), 羅素羅素(Russell)悖論悖論集合集合是數(shù)學中最基本的概念是數(shù)學中最基本的概念,沒有嚴格的定義沒有嚴格的定義 理解成理解成某些個體組成的整體某些個體組成的整體, 常用常用A,B,C等表示等表示元素元素:集合中的個體集合中的個體無窮集無窮集:元素個數(shù)無限的集合元素個數(shù)無限的集合有窮集有窮集(有限集有限集):元素個數(shù)有限的集合元素個數(shù)有限的集合. |A|:A中元素個數(shù)中元素個數(shù)k元集元集:k個元素的集合個元素的集合, 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) 有時兩種方法都適用有時兩種方法都適用, 可根據(jù)需要選用可根據(jù)需要選用.常用集合常用集合 自然數(shù)集自然數(shù)集N, 整數(shù)集整數(shù)集Z, 正整數(shù)集正整數(shù)集Z+, 有理數(shù)集有理數(shù)集Q, 非零有理數(shù)集非零有理數(shù)集Q*, 實數(shù)集實數(shù)集R, 非零實數(shù)集非零實數(shù)集R*, 復數(shù)集復數(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性質性質 (1) A A (2) A B B C A C18空集與全集空集空集: 不含任何元素的集合不含任何元素的集合例如例如, x | x20 x R=定理定理1.1 空集是任何集合的子集空集是任

13、何集合的子集證證 用歸謬法用歸謬法. 假設不然假設不然, 則存在集合則存在集合A, 使得使得 A, 即存在即存在x, x 且且x A, 矛盾矛盾. 推論推論 空集是惟一的空集是惟一的.證證 假設存在假設存在1和和2，則，則12 且且12，因此，因此1=2全集全集E:限定所討論的集合都是限定所討論的集合都是E的子集的子集. 相對性相對性 19冪集冪集冪集P(A):A的所有子集組成的集合的所有子集組成的集合, 即即 P(A) = x | x A 例如例如, 設設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 證證集合運算并并 A B = x | x A x B 交交 A B = x | x A x B 相對補相對補 A B = x | x A x B 對稱差對稱差 A B = (A B) (B A) = (A B) (A B) 絕對補絕對補 A = E A= x | x A 例如例如 設設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實例例例1 設設E= x | x是北京某大學學生是北京某大學學生, A,B,C,D是是E的子集的子集,A= x | x是北京人是北京人, B= x | x是走讀生是走讀生,C= x | x是數(shù)學系學生是數(shù)學系學生, D= x | x是喜歡聽音樂的學生是喜歡聽音樂的學生.試描述下列各集合中學生的特征試描述下列各集合中學生的特征:22(A D) C= A B=(A-B) D= D B= x | x是北京人或喜歡聽音樂是北京人或喜歡聽音樂, 但不是

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

17、iiA11iiA1iiA實例例例2 設設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. 結合律結合律(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. 德摩根律德摩根律 絕對形式絕對形式

18、 (B C)= BC, (B C)= BC 相對形式相對形式 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. 余補律余補律 =E, E=12. 雙重否定律雙重否定律 A=A13. 補交轉換律補交轉換律 A-B= AB27基本集合恒等式(續(xù))14. 關于對稱差的恒等式關于對稱差的恒等式 (1) 交換律交換律 A B=B A (2) 結合律結合律 (A

19、 B) C=A (B C) (3) 對對 的分配律的分配律 A (B C)=(A B) (A C) (4) A=A, A E= A (5) A A=, A A= E28注意注意: 對對 沒有分配律沒有分配律, 反例如下反例如下 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實例例例4 證明證明 A (A B)=A （吸收律）吸收律）證證 利用例利用例3證明的證明的4條等式證明條等式證明 A (A B) = (A E) (A B) (同一律同一律) = A (E B) (分配律分配律) = A (B E) (交換律交換律) = A E (零律零律) = A (同一律同一律)對其余的基本集合恒等式不再一一證明對其余的基本集合恒等式不再一一證明,今后把它們作為已知的集合等式使用今后把它們作為已知的集合等式使用.32實例例例5 證明證明 (A-B)-