離散數(shù)學(xué)集合與關(guān)系集合

離散數(shù)學(xué)集合與關(guān)系集合第一頁，共四十八頁，2022年，8月28日第三章集合與關(guān)系—集合這里采用樸素集合論的方法，介紹有關(guān)集合的一些基本知識，內(nèi)容顯得較為直觀，學(xué)起來易于接受。但集合及其相關(guān)的概念是本門課程后面各章內(nèi)容的基礎(chǔ)，讀者務(wù)必熟練的掌握。

主要內(nèi)容如下：集合及其表示方法集合間的關(guān)系集合的運算和運算定律集合成員表集合的分劃與覆蓋第二頁，共四十八頁，2022年，8月28日又例如

所有的正整數(shù)組成一個集合，每一個正整數(shù)均是這個集

合的元素。例如

全體中國人可組成一個集合，每一個中國人均是這個集合的

元素第三章集合與關(guān)系集合及其表示方法一、集合和元素把一些確定的、彼此不同的事物作為一個整體來

看待時，這個整體便稱為是一個集合。

組成集合的那些個體稱為集合的元素。

通常用大寫英文字母來標記集合，用小寫英文字母標記組成集合的個體若個體a是集合A的元素，則記作“a∈A”若a不是集合A的元素，則記作“aA”第三頁，共四十八頁，2022年，8月28日幾個常見的集合的表示符號：N：所有正整數(shù)的集合。Q：所有有理數(shù)的集合。Z：所有非負整數(shù)的集合。R：所有實數(shù)的集合。I：所有整數(shù)的集合。Nm：從1到m，這m個正整數(shù)的集合。P：所有素數(shù)的集合。Zm：從0到m-1，這m個非負整數(shù)的集合。

于是2∈N，2.5N，-3N，但2.5∈Q，-3∈I。

第四頁，共四十八頁，2022年，8月28日二、集合的表示方法(1)列舉法：按任意順序逐一列舉集合中的元素于花括號內(nèi)，元素之間用逗號隔開。例如：A={2,a,b,9},B={4,5,6,7,8}(2)描述法：給定一個條件P(x)，當且僅當個體a使P(a)成立時，a∈A。其一般形式為A={a∣P(a)}例如上述集合B={a∣a∈N且4≤a≤8}

又如C={2i∣i∈Z},即C={20,21,22,23,…}D={2x∣x∈Z且x≤50},即D={0,2,4,6,…,98,100}第五頁，共四十八頁，2022年，8月28日三、集合的基數(shù)集合A中不同元素的個數(shù)稱為集合A的基數(shù)，記作#A，或|A|。例如上頁中的集合，#A=4，#B=5，#D=51，集合C有無窮多個元素，因此C的基數(shù)是無窮大。若#A是有限數(shù)，則稱A為有限集，否則稱A為無限集。例如

N,Z,I,R等均為無限集。

四、空集定義3-1不含有任何元素的集合，稱為空集，記作φ。

例如

A={x|x∈R且x2+8=0}=φ

第六頁，共四十八頁，2022年，8月28日練習(xí)3-1

用列舉法表示下列集合（1）A={a|a∈P且a<20}（2）B={a||a|<4且a為奇數(shù)}2.用描述法表示下列集合(1)A={0,2,4,…,200}(2)B={2,4,8,…,1024}{2,3,5,7,11,13,17,19}{-3,-1,1,3}{2x|x∈Z且x≤100}{2n|n∈N且n≤10}

第七頁，共四十八頁，2022年，8月28日集合間的關(guān)系集合的包含和相等是集合間的兩個基本關(guān)系。例如

設(shè)A={a,b,c,d},B={a,e,x,y,z},C={a,x}BA，AB。則，CA，一、集合的包含定義3-2

設(shè)有集合A、B，如果A的每一個元素都是B的元素，則稱A是B的子集或B是A的包含集，記。如果A不是B的子集，則記作AB。

第八頁，共四十八頁，2022年，8月28日集合的包含關(guān)系具有如下幾條性質(zhì)：證明性質(zhì)（1）

（反證法）假設(shè)

A，（1）對任意集合A，；

（2）對任意集合A，；（3）對任意集合A、B、C，若

，，則。

則至少有一個元素，但，這與空集的定義相矛盾，因此成立。第九頁，共四十八頁，2022年，8月28日二、集合的相等例如

設(shè)A={x|x∈N且x能整除24}，B={1,2,3,4,6,8,12,24}則A=B=又例如

（1）{a,b,c}{b,c,a}（2）{a,b,c,c}{a,b,c}（3）{a,{b,c}}{{a,b},c}（4）{}=≠≠定義3-3

設(shè)有集合A、B，若且

，則稱集合A與B相等，記作A=B。

第十頁，共四十八頁，2022年，8月28日例如

設(shè)A={0，1}，B={0，1，2}，C={0}則但四、空集的唯一性定理3-1

空集是唯一的

因為空集被包含于每一個集合中，三、集合的真包含定義3-4

設(shè)有集合A、B，若,且A≠B，則稱A是B的真子集，記作，若A不是B的真子集，則記作。

證明

假設(shè)有兩個空集和，

所以有，，

由定義3-3，,故空集是唯一的。

第十一頁，共四十八頁，2022年，8月28日五、冪集定義3-5

設(shè)有集合A，由A的所有子集組成的集合，稱為集合A的冪集，記作2A即例1

設(shè)A={a}

則0個元素的子集：

1個元素的子集：{a}因此

設(shè)B={a,b}

則0個元素的子集：

1個元素的子集：{a},2個元素的子集：{a,b}因此

設(shè)C={a,b,c}

則0個元素的子集：；1個元素的子集：{a},,{c}2個元素的子集：{a,b},{a,c},{b,c}

3個元素的子集：{a,b,c}因此

第十二頁，共四十八頁，2022年，8月28日定理3-2

設(shè)A是有限集，則#(2A)=2#A

在二項式定理

中，令x=y=1,便有

因此

#(2A)=2n即#(2A)=2#A::{a1},:{a2},…{an}:{a1,a2},{a1,a3}…:{a1,a2,…,

an}…證明

設(shè)A={a1,a2,…,

an},從n個元素中選取m個元素的方法有種，所以A的子集個數(shù)為第十三頁，共四十八頁，2022年，8月28日例2

設(shè),

求2A和2B

解

對于集合A，它只有一個子集，

即

對于集合B，有

1個元素的子集：，{a}，{{a}}

2個元素的子集：,,3個元素的子集：

0個元素的子集：

因此

第十四頁，共四十八頁，2022年，8月28日答案：ABD答案：ABC練習(xí)3-2

B.C.D.

1試判斷下列各式是否正確，并將正確的題號填入括號內(nèi)。

2設(shè),試判斷下列各式是否正確，并將正確的題號填入括號內(nèi)。

B.C.D.

第十五頁，共四十八頁，2022年，8月28日3設(shè),

，判斷下列論斷是否正確，并將“Y”或“N”填入相應(yīng)論斷后面的括號中。

(1)(2)(3)(4)()()()()()()()()YYYYYYNN令則第十六頁，共四十八頁，2022年，8月28日集合的運算和運算定律二、文氏圖定義3-6

如果在某個問題中，所討論的一切集合均是某個集合的子集，則稱這個集合是該問題的全集合。記作U（或E）。

一、全集合例如

UAAB第十七頁，共四十八頁，2022年，8月28日三、集合的運算1.并運算

定義3-7

設(shè)有集合A、B，屬于A或?qū)儆贐的所有元素組成的集合稱為A與B的并集，記作。即例如

設(shè)A={a,b,c},B={c,d,f},C={b,e}則

由定義1-7知，

AB第十八頁，共四十八頁，2022年，8月28日2.交運算

定義3-8

設(shè)有集合A、B，屬于A同時又屬于B的所有元素組成的集合稱為A與B的交集，記作。即例如

設(shè)A={a,b,c,d},B={d,f,a},C={e,f,g}則

由定義1-8可知，

AB第十九頁，共四十八頁，2022年，8月28日3.相對補運算定義3-9

設(shè)有集合A、B，所有屬于B而不屬于A的元素組成的集合，稱為A相對于B的補集，記作B-A。即例如

設(shè)A={a,b,c,d},B={d,f,a},C={e,f,g}則B-A={f},C-A={e,f,g}=CBA32頁第二十頁，共四十八頁，2022年，8月28日2.絕對補運算

定義3-10

集合A相對于全集合U的補集稱為A的絕對補集，簡稱為A的補集，記作。即AA′~A第二十一頁，共四十八頁，2022年，8月28日例如設(shè)U={1，2，3，4，…，10}，A={2，4，6，8，10}則又例如

設(shè)U=I（I是整數(shù)集），

則第二十二頁，共四十八頁，2022年，8月28日四、集合運算的定律1.集合運算的十條定律對于全集合U的任意子集A、B、C，有：

交換律結(jié)合律分配律同一律第二十三頁，共四十八頁，2022年，8月28日互補律對合律等冪律零一律吸收律德?摩根律第二十四頁，共四十八頁，2022年，8月28日1.集合恒等式的幾種證明方法（1）根據(jù)定義進行證明若要證明集合S=H，根據(jù)集合相等關(guān)系的定義，我們需證明且例1

證明證明

若,則，因此或者于是或者從而，則反之若，故或者。因此，或者,于是，從而，故有。由上證得，。

第二十五頁，共四十八頁，2022年，8月28日例2

證明證明

若則且，即且，因此，故。反之若，則且，即且，因此。故。由上證得，第二十六頁，共四十八頁，2022年，8月28日（2）利用已有的集合恒等式證明新的恒等式例如假設(shè)交換律、分配律、同一律和零一律都成立，則可以證明吸收律也成立。

證明（由同一律）

（由分配律）（由交換律）

（由零一律）

（由同一律）

又例如證明等冪律

證明==A(3)利用下一節(jié)介紹的集合成員表證明集合恒等式

第二十七頁，共四十八頁，2022年，8月28日D若，則A=B練習(xí)3-3

1設(shè)A、B、C是任意集合，判斷下述論斷是否正確，并將正確的題號填入括號內(nèi)。

A若，則B=CB若，則B=CC若A-B=A-C，則B=C()D反例設(shè)A={a,b,c},B={b,d},C={c,d}則但23頁第二十八頁，共四十八頁，2022年，8月28日2設(shè)U={1，2，3，4，5}，A={2，4}，B={4，3，5}，C={2，5，3}，確定下列集合的元素，將其填入相應(yīng)的花括號內(nèi)。

(1){}(2){}(3){}(4){}(5}21,42,3,4,54第二十九頁，共四十八頁，2022年，8月28日3設(shè)U表示劉平擁有的所有書的集合，，其中A是離散數(shù)學(xué)參考書的集合，B是操作系統(tǒng)參考書的集合，C是今年出版的新書的集合，D是從圖書館借來的書的集合?，F(xiàn)知道如下情形：（1）所有離散數(shù)學(xué)參考書都是今年出版的新書。（）（2）所有操作系統(tǒng)參考書都是從圖書館借來的。（）（3）今年出版的新書不是從圖書館借來的。（）（4）沒有一本操作系統(tǒng)的參考書是今年出版的。（

）

3157試用集合的方法分別表示上述四種情形，可供選擇的答案如下，請從下述答案中挑選出相應(yīng)表達式的編號填入每一種情形后面的括號中。2.3.4.5.6.7.第三十頁，共四十八頁，2022年，8月28日4判斷下列論斷是否正確，對正確的論斷在相應(yīng)題后的括號中標入“Y”，對錯誤的論斷在相應(yīng)題后的括號中標入“N”。1）若，則（）2）若，則（）3）若，則（）4）若，則（）5）若，則()6）若，則()7）若，則()8）若，則()YYYYNNNN第三十一頁，共四十八頁，2022年，8月28日集合成員表一、并、交和補集的成員表根據(jù)集合的并和交運算的定義，全集合U中的元素u可分為如下四種情形：（1），（2），（3），（4），AB00

01

10

1100

10

10

11第三十二頁，共四十八頁，2022年，8月28日設(shè)A是全集合U的子集，根據(jù)補集的定義，全集合U中的元素可分為兩種情形，（1）若，則（2）若，則的成員表

A0110第三十三頁，共四十八頁，2022年，8月28日二、由集合A1、A2、…、Ar所產(chǎn)生的集合的成員表。設(shè)A1、A2、…、Ar是全集合U的子集，對這些集合以及Φ和U有限次地施加補、并、交運算，可以產(chǎn)生出一些新的集合，這樣產(chǎn)生的集合稱為是由A1、A2、…、Ar所產(chǎn)生的集合。例如S第三十四頁，共四十八頁，2022年，8月28日例1

構(gòu)造T=的成員表

AB0001011011110100010第三十五頁，共四十八頁，2022年，8月28日例2構(gòu)造S的成員表

ABC00000101001100101110111S110011000100010010101010001000100110011000000110第三十六頁，共四十八頁，2022年，8月28日三、利用集合成員表證明集合恒等式例３

設(shè)A、B、C是任意集合，試問等式S=T是否成立？

ABC000

001

010

011

100

101

110

111ST1

1

1

1

00

0

00

0

1

1

1

1

1

11

1

1

1

0

1

0

10

0

1

1

0

1

0

10

0

1

1

0

0

0

00

0

0

0

0

1

0

10

0

1

1

0

1

0

1

其中

S=,T=分別構(gòu)造S和T的成員表如下：

解第三十七頁，共四十八頁，2022年，8月28日集合的分劃與覆蓋一、集合的分劃定義3-11

設(shè)有非空集合A，H={A1、A2、…、Am}，其中，且（i=1，2，…，m），若

（1），當i≠j時

(2)例1

設(shè)A={1，2，3，4}

則H1={{1}，{2}，{3，4}}H2={{2，3}，{1，4}}H3={{1}，{2}，{3}，{4}}。

都是A的分劃則稱H是集合A的一個分劃，每一個稱為這個分劃的一個分塊。第三十八頁，共四十八頁，2022年，8月28日例2設(shè)A={2，3，4，8，9，10，15}

定義A的如下子集：

試問是否A的一個分劃。

解

根據(jù)題意{2，4，8，10}

{3，9，15}{10，15}

不是A的分劃，可成為A的一個分劃。

第三十九頁，共四十八頁，2022年，8月28日二、集合的覆蓋定義3-12

設(shè)有非空集合A，,其中

且（i=1，2，…，m），若，

則稱S是集合A的一個覆蓋。

例如

例2中是A的分劃，也是A的覆蓋。是A的覆蓋，但不是A的分劃。第四十頁，共四十八頁，2022年，8月28日練習(xí)3-5

1設(shè)A={a，b，c，d，e，f}，指出下列哪些是A的分劃（在相應(yīng)括號內(nèi)填入“1”），哪些是A的覆蓋（在相應(yīng)括號內(nèi)填入“2”），哪些既不是分劃，也不是覆蓋（在相應(yīng)括號內(nèi)填入“0”）H1={{a，b}，{c，d}，{a，e，f}}（）H2={{c，e}，{c，d，f}，}（）H3={{a，b，c，d}，{e，f}}（）