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

1、2022-3-20Zhengjin ,CSU1 第二章第二章 集集 合（合（set) 集合的概念在現(xiàn)代數(shù)學(xué)中是一個(gè)非常重要的概念。集合的概念在現(xiàn)代數(shù)學(xué)中是一個(gè)非常重要的概念。本節(jié)主要介紹集合及其表示、集合的運(yùn)算，序偶，本節(jié)主要介紹集合及其表示、集合的運(yùn)算，序偶，集合的笛卡爾乘積。集合的笛卡爾乘積。2022-3-20Zhengjin ,CSU2個(gè)體和集合之間的關(guān)系個(gè)體和集合之間的關(guān)系集合不能精確定義，只能直觀描述：一個(gè)集合就是若干事物的全體一個(gè)集合就是若干事物的全體。組成集合的每個(gè)事物叫做這個(gè)集合的元素。元素。 小寫拉丁字母表示個(gè)體：a、b、c、d 大寫拉丁字母表示集合：A、B、C、D2022-

2、3-20Zhengjin ,CSU3個(gè)體與集合之間的關(guān)系：屬于屬于關(guān)系關(guān)系。 對(duì)于某個(gè)個(gè)體 a 和某個(gè)集合 A 而言，a 只有兩種可能 1）a屬于A，記為 aA，同時(shí)稱 a 是 A 中的元素。 2）a 不屬于 A，記為 aA ，稱 a 不是 A 中的元素。個(gè)體個(gè)體a屬于屬于A或者或者a不屬于不屬于A，二者居其一且只居其一。，二者居其一且只居其一。 2022-3-20Zhengjin ,CSU4集合的集合的表示表示法法 (1)文字表示法文字表示法 用文字表示集合的元素，兩端加上花括號(hào)。 在座的同學(xué) 高等數(shù)學(xué)中的積分公式 (2) 元素列舉法元素列舉法 將集合中的元素逐一列出，兩端加上花括號(hào)。 1，

3、2，3，4，5， 風(fēng)，馬，牛 2，4，6，8，10， 2022-3-20Zhengjin ,CSU5(3)謂詞表示法謂詞表示法 xp(x) p表示x所滿足的性質(zhì)例如： xx2=1=1，-1 yy是開區(qū)間(a，b)上的連續(xù)函數(shù) 2022-3-20Zhengjin ,CSU6（4）歸納定義法）歸納定義法用歸納法定義一個(gè)非空集合A時(shí)，包括以下三步：1)基本項(xiàng)（保證基本項(xiàng)（保證A不空不空) 已知某些元素屬于已知某些元素屬于A2)歸納項(xiàng)（生成規(guī)則）歸納項(xiàng)（生成規(guī)則） 給出一組規(guī)則，從給出一組規(guī)則，從A中的元素出發(fā)，依據(jù)這些規(guī)則所獲得的中的元素出發(fā)，依據(jù)這些規(guī)則所獲得的元素，仍然都是元素，仍然都是A中的元

4、素。（這是構(gòu)造中的元素。（這是構(gòu)造A的關(guān)鍵步驟）的關(guān)鍵步驟）3）極小化極小化（通常省略通常省略） 如果集合如果集合S也滿足（也滿足（1）和（）和（2），且），且S A，則，則S=A。這一。這一點(diǎn)保證集合點(diǎn)保證集合A的唯一性。的唯一性。 2022-3-20Zhengjin ,CSU7例例1 1 如果論域是整數(shù)集如果論域是整數(shù)集I I，那么能被，那么能被3 3整除的正整數(shù)集合整除的正整數(shù)集合S S用歸納法可定義如下：用歸納法可定義如下：（1 1）（基礎(chǔ)）（基礎(chǔ)）3 3 S S，（2 2）（）（歸納）如果歸納）如果x x S S和和y y S S，則，則x+yx+y S S 2022-3-20Zhe

5、ngjin ,CSU8集合的特殊情況集合的特殊情況1 1、不含任何元素的集合稱為空集，記為、不含任何元素的集合稱為空集，記為2 2、含討論問題所需全部元素的集合稱為全集，記為、含討論問題所需全部元素的集合稱為全集，記為 3、 稱含有有限個(gè)元素的集合為稱含有有限個(gè)元素的集合為有限集合有限集合4、 含有無限個(gè)元素的的集合稱為無限集合或無限集含有無限個(gè)元素的的集合稱為無限集合或無限集5、 集合集合A A中元素的個(gè)數(shù)（或基數(shù)或集合的勢(shì)）記為中元素的個(gè)數(shù)（或基數(shù)或集合的勢(shì)）記為: :| |A A| | 提醒提醒:一個(gè)集合也可以是別的集合的元素，如：一個(gè)集合也可以是別的集合的元素，如： a， b， a，b

6、 a，b， ，a，b 2022-3-20Zhengjin ,CSU9集合與集合之間的關(guān)系集合與集合之間的關(guān)系 設(shè)A，B是兩個(gè)集合 1）若對(duì)于A中的每個(gè)元素x，都有x屬于B， 則稱A包含在B中，記為:A B。同時(shí)稱A是B的子集。 2）若A中的每個(gè)元素都屬于B，且B中的每個(gè)元素都屬于A，則稱A等于B，記為A=B。 (A=B A=B 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A A B B 且且 B B A A） 3)3)集合的包含關(guān)系具有傳遞性集合的包含關(guān)系具有傳遞性: :即即 若A B且B C，則A C2022-3-20Zhengjin ,CSU10子集的兩種特殊情況（平凡子集）：子集的兩種特殊情況（平凡子集）： 1）空

7、集是任一集合的子集。）空集是任一集合的子集。 2）任何集合都是它自己的子集。）任何集合都是它自己的子集。2022-3-20Zhengjin ,CSU11例例1：確定下列各命題的真假：確定下列各命題的真假：( (a) a) (b) (b) (c) ( (d) d) (e) a(e) a，b b aa，b b，c c，aa，b b，cc(f) a(f) a，b b aa，b b，c c，aa，b b，cc(g) a(g) a，b b aa，b b，c c，aa，bb(h) a(h) a，bb a a，b b，c c，aa，bb例例2 2 求出下列集合的全部子集：（a) ， (b)(b) aa，bb

8、，aa，a a，bb，bb，a a，bb2022-3-20Zhengjin ,CSU12集合上的運(yùn)算集合上的運(yùn)算定義定義2 設(shè)A，B是兩個(gè)集合 1）AB = xxAxB ，稱AB為A與B的交集，稱為集合交運(yùn)算。 2）AB = xxAxB ，稱AB為A與B的并集，稱為集合并運(yùn)算。 3) AB= xxA x B ， 稱AB為A與B的差集例例 1 設(shè) A=1，2，3，4，5，B=2，5，7，則 A B=1，2，3，4，5，7 A B=2，5 AB=1，3，42022-3-20Zhengjin ,CSU13 定理定理1 設(shè)U是全集，A，B，C是U的三個(gè)子集 1）AA=A， AA=A 2）AU=A， A

9、U=U 3）A = ， A =A 4）AB= BA， AB= BA 5）(AB) C = A (BC)， (AB) C = A (BC) 6）A(B C) = (AB) (AC) A(B C) = (AB) (AC) 2022-3-20Zhengjin ,CSU14定理定理2 設(shè)A，B，C為三個(gè)集合，則 1）A AB， AB A； 2）若 A C 且 B C，則 AB C； 3）若 C A 且 C B，則 C AB 。 4) A-B A 5) A- =A 6) A(B-C)= (AB)-( AC) ；定理定理3 設(shè)A，B為兩個(gè)集合，則下面三式等價(jià)。 1）A B 2）AB = B 3) AB=A

10、 圖形表示：2022-3-20Zhengjin ,CSU15 集合上的補(bǔ)運(yùn)算集合上的補(bǔ)運(yùn)算(一元運(yùn)算）一元運(yùn)算） 設(shè)U是全 集，A是U的子集。 A= x x U x A =U-A稱A 是A關(guān)于U的補(bǔ)集，稱 為補(bǔ)運(yùn)算。例例2 設(shè)U=a，b，c，d，e， A=c，d，則 A=o 定理定理4 設(shè)U是全 集，A，B是U的子集。則 1 ( A)=A； 2）若A B，則 B A； 3）若A = B，則 A= B ； 4） U= ， =U。 5) A A =U， A A = 2022-3-20Zhengjin ,CSU16定理定理5 設(shè)A，B為兩個(gè)集合，則 1） ( AB) = A B 2） ( AB) =

11、 A B 2022-3-20Zhengjin ,CSU17集合的環(huán)和（對(duì)稱差）運(yùn)算集合的環(huán)和（對(duì)稱差）運(yùn)算定義：定義： 設(shè)A，B是兩個(gè)集合， AB = (A-B) (B-A) = x(xAxB) (xBxA) 稱 AB 為A和B的環(huán)和，稱 為集合環(huán)和運(yùn)算。由環(huán)和運(yùn)算和并、差運(yùn)算的定義知 A B=(AB)(A B)例例：設(shè)A=a，b，c，d，e，B=a，b，c，f，g，則 2022-3-20Zhengjin ,CSU18 冪冪 集集定義：設(shè)定義：設(shè)A是集合，是集合，A的所有子集組成的集合稱為的所有子集組成的集合稱為A的冪集，的冪集，記為記為 ：2A或或p(A)。 2A = x x A 例例1：如

12、果A=a，b，則2A=，a，b，a，b 例例2：設(shè)：設(shè)A=，則2A=， ， ， ， 定理定理1 設(shè)集合A是有限集合， A = n，則 2A = 2 A 定理定理2 設(shè)A，B是兩個(gè)集合。那么， A=B當(dāng)且僅當(dāng) 2A = 2B。2022-3-20Zhengjin ,CSU19有限集的計(jì)數(shù)原理有限集的計(jì)數(shù)原理設(shè)A和B都是有限集合，則以下公式成立:| AB |= | A |+ |B |- | A B | A B |= | A |- | B | A1A2 A3 |= | A 1|+ | A2 |+ | A3 |- | A1 A2 |- | A2 A3 |- | A1 A3 |+ | A1 A2 A3 |

13、2022-3-20Zhengjin ,CSU20有限集計(jì)數(shù)原理o P682022-3-20Zhengjin ,CSU21集合的廣義并和廣義交集合的廣義并和廣義交 定義定義6 6：如果集合：如果集合C C中的成員本身又都是集合，則集合中的成員本身又都是集合，則集合C C稱稱為為集類集類( (或稱為搜集或稱為搜集) )。 設(shè)設(shè)C=A1C=A1，A2A2，A3A3，AnAn (1) C (1) C的成員的并，記為：的成員的并，記為：C C，稱為，稱為C C的廣義并的廣義并 C=A1A2 C=A1A2AnAn（2 2）C C的成員的交，記為：的成員的交，記為：C C，稱為，稱為C C的廣義交的廣義交

14、C=A1A2 C=A1A2An An 例：設(shè)例：設(shè)A=1A=1，2 2，44，33，4 4，55，44，66則則A A廣義交：廣義交：A=1A=1，2 2，4343，4 4，5454，6=6=A A的廣義并：的廣義并：A=1A=1，2 2，4343，4 4，5454，66 =1 =1，2 2，3 3，4 4，5 5，662022-3-20Zhengjin ,CSU22數(shù)學(xué)歸納法數(shù)學(xué)歸納法對(duì)于以自然數(shù)為論域的對(duì)于以自然數(shù)為論域的 x P(x)形式的歸納證明過程形式的歸納證明過程如下如下: 第一數(shù)學(xué)歸納法第一數(shù)學(xué)歸納法(1)（基礎(chǔ)）先證明P(0)是真。(2)（歸納) 再證明 n( P(n) P(n

15、+1)是真即先假設(shè)“P(n) 對(duì)任意取定的自然數(shù)n是真，再由此推出P(n+1)也真，一旦證明了P(n) P(n+1)對(duì)任意n是真，則用全稱推廣規(guī)則得 n( P(n) P(n+1) 再根據(jù)數(shù)學(xué)歸納法第一原理得出 x P(x)。2022-3-20Zhengjin ,CSU23第二數(shù)學(xué)歸納法原理第二數(shù)學(xué)歸納法原理 n kk0，如果P(k)對(duì)一切kn 成立，那么P(n)成立。數(shù)學(xué)歸納法數(shù)學(xué)歸納法2022-3-20Zhengjin ,CSU24集合的笛卡爾乘積集合的笛卡爾乘積 由任意兩個(gè)元素由任意兩個(gè)元素x x和和y y組成的集合組成的集合 x x，yy為偶集。因?yàn)闉榕技?。因?yàn)?x x，y=yy=y，x

16、x，所以這種偶集只能叫無序偶集，所以這種偶集只能叫無序偶集， 簡稱簡稱無序偶無序偶。 有序偶有序偶: :它不僅與含有的元素它不僅與含有的元素x x，y y有關(guān)，還與有關(guān)，還與x x，y y出現(xiàn)的次序有關(guān)。出現(xiàn)的次序有關(guān)。這樣的偶集稱為這樣的偶集稱為有序偶有序偶，并記為，并記為： 例如，用例如，用 y表示平面直角坐標(biāo)系下的橫坐標(biāo)為表示平面直角坐標(biāo)系下的橫坐標(biāo)為x x且縱且縱坐標(biāo)為坐標(biāo)為y y的點(diǎn)時(shí)，則的點(diǎn)時(shí)，則 y和和 x在在x x y y時(shí)就代表不時(shí)就代表不同的點(diǎn)，因而就不相同。同的點(diǎn)，因而就不相同。 2022-3-20Zhengjin ,CSU25定義定義1 有序偶的集合定義：若有序偶的集合

17、定義：若x，y為任意兩個(gè)元素，為任意兩個(gè)元素，令令 =x，x，y稱稱為由為由x，y組成的二元序偶，簡稱有序偶或序偶。組成的二元序偶，簡稱有序偶或序偶。 提醒提醒：此種定義顯然體現(xiàn)了二元元素的有序性。但有序：此種定義顯然體現(xiàn)了二元元素的有序性。但有序偶的定義不只一種，還有別的定義方法，只要能體現(xiàn)偶的定義不只一種，還有別的定義方法，只要能體現(xiàn)有序性就可以了有序性就可以了用集合定義有序偶用集合定義有序偶2022-3-20Zhengjin ,CSU26定理定理1 1 = = v當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) x=ux=u且且y=vy=v （根據(jù)序偶的定義即可得出。）根據(jù)序偶的定義即可得出。）定義定義2 2 設(shè)設(shè)n

18、n是正整數(shù)，是正整數(shù)，x1x1，x2x2，xnxn是任意的元素。是任意的元素。 若若n=1n=1，則令，則令 =x1x1=x1 若若n=2n=2，則令，則令 =x=x1 1,x,x1 1，x x2 2 若若n2n2，則令，則令 =,x xn n 我們稱我們稱 為由為由x x1 1，x x2 2，x xn n 組成組成的的n n元序偶，并稱每個(gè)元序偶，并稱每個(gè)x xi i為它的第為它的第i i個(gè)分量。個(gè)分量。 （這樣就定義了（這樣就定義了n n元序偶）元序偶） 2022-3-20Zhengjin ,CSU27定義定義3 3 設(shè)設(shè)n n是正整數(shù)，是正整數(shù)，A A1 1，A A2 2，A An n為

19、為n n個(gè)任意集合。個(gè)任意集合。 A A1 1A A2 2A An n=x= 若若11inin，則，則x xi iAAi i 稱稱A A1 1A A2 2A An n為為A A1 1，A A2 2，A An n的的n n維維笛卡爾笛卡爾乘積。乘積。 定義定義4 4 設(shè)設(shè)A A，B B是兩個(gè)非空集合是兩個(gè)非空集合 A AB=aB=ba a A bA b B B ( (即所有第一元素在即所有第一元素在A A中，第二元素在中，第二元素在B B中的序偶的集合中的序偶的集合) ) 稱稱A AB B是是A A與與B B的叉積（笛卡兒積）集合。的叉積（笛卡兒積）集合。 記記: :A AA=AA=A2 2 2

20、022-3-20Zhengjin ,CSU28n （1 1）在）在A AB B中，中，A A稱為前集，稱為前集，B B稱為后集。前集與后稱為后集。前集與后集可以相同，也可以不同。若前集與后集相同，則記集可以相同，也可以不同。若前集與后集相同，則記為為A AA=AA=A2 2 。n （2 2）規(guī)定規(guī)定A A=B B。若偶對(duì)的第一分量或第若偶對(duì)的第一分量或第二分量不存在就沒有偶對(duì)存在，故規(guī)定它們的叉積集二分量不存在就沒有偶對(duì)存在，故規(guī)定它們的叉積集合為空集。合為空集。n （3 3）由于偶對(duì)中的元素是有序的，因此一般地說）由于偶對(duì)中的元素是有序的，因此一般地說A ABBBBA A。( (除非除非A=

21、BA=B，或者，或者A A、B B中至少有一個(gè)為空中至少有一個(gè)為空集集) ) 2022-3-20Zhengjin ,CSU29例例1 1 A=aA=a，b b，cc， B=0B=0，11 A AB=aB=0，a1，b0，b1，c0，c 1 B BA=0A=a，0b，0c，1a，1b，1 c A A2 2=a=a，ab，ac，ba，bb，bc，ca，cb，cc2022-3-20Zhengjin ,CSU30定理定理2 2：設(shè)：設(shè)A A，B B是兩集合，則是兩集合，則 A A B B= =A A* *B B ( (即即A A B B中元素的個(gè)數(shù)等于中元素的個(gè)數(shù)等于A A中元素個(gè)數(shù)乘以中元素個(gè)數(shù)乘以

22、B B中元素個(gè)中元素個(gè)數(shù)數(shù)) )。定理定理3 3 設(shè)設(shè)A A，B B，C C，D D是四個(gè)非空集合，那么是四個(gè)非空集合，那么A AB=CB=CD D當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A=CA=C且且B=D B=D 。2022-3-20Zhengjin ,CSU31定理定理4 4 設(shè)設(shè)A A，B B，C C是三個(gè)集合，則是三個(gè)集合，則 1 1）A A(BC)=(A(BC)=(AB)(AB)(AC)C) 2 2）A A(BC)=(A(BC)=(AB)(AB)(AC)C) 3 3）(AB)(AB)C=(AC=(AC)(BC)(BC)C) 4 4）(AB)(AB)C=(AC=(AC)(BC)(BC)C) 5 5 ） ( A B )( A B )