集合的概念和表示法-集合與關(guān)系-離散數(shù)學

一、集合的概念集合（SET）：即是由一些確定的彼此不同的客體（事物）匯集到一起組成一個整體，稱為集合。討論：客體：泛指一切，可以是具體的、抽象的。元素(element，成員)：

即組成集合的客體，稱之為元素。二、集合的記法通常用帶(不帶)標號的大寫字母A、B、C、...、A1、B1、C1、...、X、Y、Z、...表示集合；通常用帶（不帶）標號的小寫字母a、b、c、...、a1、b1、c1、...、x、y、z、...表示元素。第一頁1第二頁，共27頁。固定的符號0,1,2,…自然數(shù)集合N…,-2,-1,0,1,2,…整數(shù)集合Ip/q,p,q是整數(shù)，且q≠0

有理數(shù)集合

Q

實數(shù)集合R復數(shù)集合

C第二頁2第三頁，共27頁。說明：集合中的元素都是不同的，凡是相同的元素，均視為同一個元素；{1,1,2}={1,2}一旦給定了集合A，對于任意客體a，可以準確地判定a是否在A中。

集合中的元素是沒有順序的。

{2,1}={1,2}集合的特性1、互異性－2、確定性－3、無序性－4、集合中的元素可以是集合。如S={a,{1,2},p,{q}}以集合為元素的集合稱為集合類或集合族。如S={{a},{1,2,3,4}}第三頁3第四頁，共27頁。三、集合與元素的關(guān)系客體a與集合A之間的關(guān)系只能是屬于和不屬于之一。a是集合A的元素或a屬于集合A，記為aA，稱a是A的成員，A包含a，a在A中。a不是集合A的元素或a不屬于集合A，記為aA，或者(aA)，稱a不是A的成員，A不包含a，a不在A中。例如，對元素2和自然數(shù)集合N，就有2屬于N，即2N，對元素-2和自然數(shù)集合N，就有-2不屬于N，即-2N。有限集：組成集合的元素個數(shù)是有限的。|A|：有限集合A中元素的個數(shù)。無限集：組成集合的元素個數(shù)是無限的。第四頁4第五頁，共27頁。四、集合的表示方法集合是由它包含的元素完全確定的，為了表示一個集合，通常有：

枚舉法（列舉法）謂詞表示法（隱式法、敘述法）文氏(Venn)圖-輔助的集合的表示方法第五頁5第六頁，共27頁。1、枚舉法（顯式表示法）就是把集合的元素（全部或部分）寫在花括號的里面，每個元素僅寫一次，不考慮順序，并用”,”分開。例

（1）命題的真假值組成的集合：S={T,F}

（2）A＝{a，e，i，o，u}第六頁6第七頁，共27頁。在使用中，分兩種情況：（1）當集合中元素個數(shù)有限且較少時，將元素全部寫出。例1：設集合A是由絕對值不超過3的整數(shù)組成。A={-3,-2,-1,0,1,2,3}（2）當集合A元素的個數(shù)無限或有限但個數(shù)較多時，不能或不需要一一列舉出來，只要寫出少數(shù)元素，以顯示出它的規(guī)律。（當規(guī)律不明確，不能用此方法）。例2：設集合B是由自然數(shù)的平方構(gòu)成的集合。B={0,1,4,9,16,…,n2,…}適用場景：一個集合僅含有限個元素。一個集合的元素之間有明顯關(guān)系。第七頁7第八頁，共27頁。2、謂詞表示法（隱式法、敘述法）用謂詞描述集合中元素的屬性，稱為謂詞表示法（敘述法、隱式法）一般表示方法：A＝{x|P(x)}若個體域內(nèi)，客體a使得P(a)為真，則a∈A，否則aA。例如：大于10的整數(shù)的集合：S={x|x∈I∧x>10)}命題的真假值組成的集合：S={F,T}={x|x=F∨x=T}適用場景：一個集合含有很多或無窮多個元素；一個集合的元素之間有容易刻畫的共同特征。其突出優(yōu)點是原則上不要求列出集合中全部元素，而只要給出該集合中元素的特性。P(x)是謂詞公式，x具有的性質(zhì)P代表元素第八頁8第九頁，共27頁。A3、文氏(Venn)圖-輔助的集合的表示方法文氏(Venn)圖是一種利用平面上的點構(gòu)成的圖形來形象展示集合的一種方法，用一個矩形的內(nèi)部表示全集，其他集合用矩形內(nèi)的園面或一封閉曲線圈成的面積來表示。文氏圖又稱韋恩圖，用它表示集合間的關(guān)系或運算，是一種非常直觀的圖示集合的工具，文圖只起示意作用，不能用以代替嚴格證明。U第九頁9第十頁，共27頁。同一個集合可以用不同的表示方法：

例方程x2-1=0的所有實數(shù)解的集合A；謂詞法：A={x|xR∧x2-1=0}或A={x|x是實數(shù)且x2-1=0}枚舉法：A={1，-1}第十頁10第十一頁，共27頁。五、集合與集合的關(guān)系（一）包含關(guān)系（二）相等關(guān)系（三）真包含關(guān)系第十一頁11第十二頁，共27頁?！鞍P(guān)系”的謂詞表示：

ABBA(

x)(x∈Ax∈B)（一）包含關(guān)系例：設A={ADA,BASIC,PASCAL}，B={BASIC,PASCAL,ADA,C,JAVA}定義：

A包含在B內(nèi)，A包含于B，B包含A設A，B是任意兩個集合，若A的每個元素都是B的元素，則稱A是B的子集(Subset)，也稱A包含在B內(nèi)，B包含A，記作BA或AB，若A不被B所包含，則記作A

B。顯然，對任意集合A，都有AA。

AB第十二頁12第十三頁，共27頁。（二）相等關(guān)系定義A＝B當且僅當A與B具有相同的元素，否則，A

B。即集合A,B中的元素完全相同，稱這樣的兩個集合相等。

{1,2,4}={1,4,2}≠{1,{2,4}}定理3-1.1

設A和B是任意兩個集合，A=B

A

B且B

A。集合相等的謂詞表示：A=B(x)(x∈Ax∈B)第十三頁13第十四頁，共27頁。定理3-1.1

A=B

AB且BA。證明：(1)證：若AB且BA，則A=B。(反證法)

已知AB且BA，假設A≠B，則至少有一個元素x，使得x∈A而xB；或者x∈B而xA。如果x∈A而xB，則與AB矛盾。如果x∈B而xA，則與BA矛盾。

所以A=B。(2)證：若A=B

，則AB且BA

。若A=B，則兩個集合有相同的元素，即(x)(x∈A

x∈B)為真，且(x)(x∈B

x∈A)為真，即必有AB且BA。所以，A=B

AB且BA。該定理是證明兩個集合相等的基本思路和依據(jù)。第十四頁14第十五頁，共27頁。集合相等的謂詞定義A=BAB∧BA(x)(x∈Ax∈B)∧(x)(x∈Bx∈A)(x)((x∈Ax∈B)∧(x∈Bx∈A))(x)(x∈A

x∈B)A=B(

x)(x∈Ax∈B)第十五頁15第十六頁，共27頁。（三）真包含關(guān)系定義1.2.2

：A真包含于B設A,B是任意兩個集合，集合A中的每一個元素都屬于B，但集合B中至少有一個元素不屬于A。則稱A是B的真子集(ProperSubset)，記作A

B，如果A不是B的真子集，則記作AB?！罢姘P(guān)系”的謂詞表示：ABAB∧A≠BA

B

(x)(x∈Ax∈B)∧(x)(xB∧xA)對任意x，如x

A，則x

B，并且存在xB，但是xA。第十六頁16第十七頁，共27頁。自學真包含關(guān)系的謂詞定義：ABAB∧A≠B(x)(x∈Ax∈B)∧

(x)(x∈Ax∈B)(x)(x∈Ax∈B)∧

((x)(x∈Ax∈B)∨

(x)(x∈Bx∈A))

((x)(x∈Ax∈B)∧(x)(x∈Ax∈B))

∨

((x)(x∈Ax∈B)∧(x)(x∈Bx∈A))(x)(x∈Ax∈B)∧(x)(x∈B∧xA)集合A中的每一個元素都屬于B，但集合B中至少有一個元素不屬于A。第十七頁17第十八頁，共27頁。六、幾個特殊集合1、全集2、空集3、冪集第十八頁18第十九頁，共27頁。1、全集定義

在一個相對固定的范圍內(nèi)，包含此范圍內(nèi)所有客體的集合，稱為全集或論集(UniversalSet)，用U或E表示。

E={x|P(x)∨

P(x)}其中：P(x)為任何謂詞。用文氏圖描述如下:U六、幾個特殊集合一般地，根據(jù)討論問題的范圍，選擇對問題討論方便的集合作為全集。在實際應用中，常常把某個適當大的集合看成全集。第十九頁19第二十頁，共27頁。2、空集定義：不含任何元素的集合叫做空集(EmptySet)，記作Φ?？占梢苑柣癁?/p>

Φ={x|P(x)∧

P(x)}={}其中：P(x)為任何謂詞。例

設A={x|(x∈R)∧(x2<0)}，試列舉A中的所有元素。解：A=Φ。Φ與{Φ}:Φ是不含任何元素的集合，{Φ}是含一個元素Φ的集合。

{Φ}={{}}，|Φ|=0，|{Φ}|=1，Φ∈{Φ}定理3-1.2（1）空集是一切集合的子集；（2）空集是絕對唯一的。第二十頁20第二十一頁，共27頁。反證法（1）空集是一切集合的子集；ΦA證明：因為(x)(x∈Φx∈A)為永真式，所以ΦA。（2）空集是絕對唯一的。分析：對“唯一性”的證明通常采用反證法。即假設“不唯一”，得出矛盾，從而說明結(jié)論正確。證明：（反證法）假設空集不唯一，即存在Φ1和Φ2兩個空集，且Φ1≠Φ2，因為是Φ1空集，則由性質(zhì)1得Φ1

Φ2

。因為是Φ2空集，則由性質(zhì)1得Φ2

Φ1

。所以Φ1=Φ2

。與假設矛盾，所以空集是唯一的。定理3-1.2的證明Φ

{Φ}第二十一頁21第二十二頁，共27頁。3、冪集

引例：求集合的子集及子集的個數(shù)例A子集子集個數(shù)ΦΦ1{a}Φ,{a}2{a,b}Φ,{a},,{a,b}4{a,b,c}Φ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}8一般來說，對于n個元素的集合A，它的不同的子集總數(shù)有：＝(1+1)n＝2n所以，n元集共有2n個子集。Cn2＋……Cn0Cn1Cnn＋＋＋第二十二頁22第二十三頁，共27頁。一般來說，對于n個元素的集合A，它的不同的子集總數(shù)有

Cn2＋……Cn0Cn1Cnn＋＋＋Cn2＋…Cn0Cn1Cnn＋＋＋xn-1yxn-2y2xnynCn2＋……Cn0Cn1Cnn＋＋＋而(x+y)n=令x=y=1時得

2n=所以不同子集總數(shù)有2n第二十三頁23第二十四頁，共27頁。冪集定義：冪集(powerset)給定集合A，由A的所有子集為元素組成的集合稱為A的冪集(powerset)，記為ρ(A)

。冪集的符號化表示為ρ(A)＝{x|xA}例如：計算下列冪集:(1)ρ(Φ)；(2)ρ({a});(3)ρ({Φ})。解：(1)ρ(Φ)={Φ}；(2)ρ({a})={Φ,{a}}(3)ρ({Φ})={Φ,{Φ}}；定理3-1.3若有限集合Ａ有n個元素，則其冪集ρ(A)共有2n個元素。|A|=n,|ρ(A)|=2n第二十四頁24第二十五頁，共27頁。子集Bijk編碼Ａ＝{a,b,c}

ijk是二進制數(shù)，

Bi

jk

A,i=1，