離散數(shù)學文檔第三章

1、第三章集合論集合論是現(xiàn)代數(shù)學的基礎，是數(shù)學不可或缺的基本描述工具?？梢赃@樣講，現(xiàn)代數(shù)學與離散數(shù)學的“大廈”是建立在集合論的基礎之上的。集合論的研究起源于對數(shù)學的基礎研究：對數(shù)學的對象、性質及其發(fā)生、發(fā)展的一般規(guī)律進行的科學研究。德國數(shù)學家康托爾從1874年始，發(fā)表了一系列集合論方面的著作，從而創(chuàng)立了集合論。在自然科學中，除了研究處于孤立的個體之外，更重要的是將一些相關的個體放在一起進行研究，這就直觀地產(chǎn)生了引入集合這一概念的要求。隨著計算機時代的到來，集合的元素已由傳統(tǒng)的“數(shù)集”和“點集”拓展成包含文字、符號、圖形、圖表和聲音等多媒體信息，構成了各種數(shù)據(jù)類型的集合。從而集合論在編譯原理、開關理

2、論、信息檢索、形式語言等各個領域得到了廣泛的應用。3.1 集合一個集合是作為整體識別的、確定的、互相區(qū)別的一些事物的全體。嚴格地講，這只是一種描述，不能算是集合的定義。類似于幾何中的點、線、面等概念，在樸素集合論中，集合也是一種不加定義而直接引入的最基本的原始概念(一給出定義就要引入悖論)。而集合論中的其他概念，則都是從它出發(fā)給予了嚴格的定義。構成集合的每個事物稱為這個集合的元素或成員。集合一般用大寫字母表示，元素用小寫字母表示。但這也不是絕對的，因為一個集合可以是另外一個集合的元素。例3.1.1英文字母的集合，c語言的基本字符集，全體實數(shù)，計算機內存單元集合。例3.1.21，2，32，1，3

3、3，1，2。例3.1.3常用集合：n，i(i，i)，p，q(q，q)，r(r，r)，c。集合的表示：(1)枚舉法；(2)性質描述法：sx | p(x) ； (3)文氏圖法：用于描述集合間的關系及其運算，其特點是直觀、形象、信息量大且富有啟發(fā)性。一般用矩形表示全集u，用圓表示u的子集a，b，c等等。集合中的事物稱為集合的元素，通常用小寫英文字母表示。如果x是集合s的一個元素，則稱x屬于s，記作xs；否則稱x不屬于s，記作xa。集合有三個重要的特性：互異性、無序性和確定性。例3.1.41n，0.5q，3.0r，1n，q。定義3.1.1 設a是任意集合，a中元素的個數(shù)稱為a的基數(shù)或勢，用|a|表示。

4、(1)基數(shù)為有限的集合稱為有限集，否則稱為無限集；(2)若a0，則稱a為空集，記作或。否則稱a是非空集合。例3.1.5n，i，q，r，c都是無限集；大于3且小于1的整數(shù)集是空集，hx | xr 且x2+x+1=0是空集；偶質數(shù)集是有限非空集。|=0，|0,1|=2，|=1，|n|=，|r|=。定義3.1.2 設a和b是兩個集合。若a中的每個元素都是b的元素，則稱a是b的子集或稱b包含a、a包含于b，記作ab。若ab但ab，則稱a為b的真子集，記作ab，b稱為a的擴集或超集?？占侨魏渭系淖蛹?對任一集合a，有a)。對任一非空集合a，它至少有兩個不同的子集和a，稱它們?yōu)閍的平凡子集。例3.1.

5、6nqrc。集合的包含關系有如下性質：(1)自反性：aa；(2)反對稱性：ab，baab；(3)傳遞性：ab，bcac。而集合的真包含關系則只有傳遞性：ab，bcac。定義3.1.3 設 a和b是兩個集合。若ab且ba，則稱a與b相等，記為ab，否則稱a與b不等，記為ab。例3.1.7ax | x2-x=0 且xr，b0,1，則ab。例3.1.8判斷下列命題的真假：，定義3.1.4 在一定范圍內，若所有集合均為某一集合的子集，則稱該集合為全集，記為u。3.2集合的運算3.2.1集合的運算定義3.2.1 設有集合a與b，則(1)稱由a與b的公共元素組成的集合為a與b的交集，記作ab，即abx |

6、 xa且xb。若ab，則稱a與b不相交。(2)稱由a與b的所有元素組成的集合為a與b的并集，記作ab，即abx | xa 或xb。(3)稱由屬于a但不屬于b的元素組成的集合為b對a的相對補集，記作ab，即abx | xa且xb。特別地，若au，則稱ub為b的補集，記作。，。例3.2.1設a2，3，b1，5，8，c3，6，u1，10，求ab，cb，ab，ba，。定理3.2.1 (集合運算的性質)對全集u和任意集合a,b,c，有（1） aab，bab；aba，abb；（2） aba；ab=a；（3） ac，bcabc；ab，acabc；（4） ab。例3.2.2設a，b是任意集合，證明下列條件相互

7、等價：(1)ab；(2)abb；(3)aab。定義3.2.2 設a與b是集合，則稱由屬于a但不屬于b的元素或屬于b但不屬于a的元素組成的集合為a與b的對稱差，記作ab，即ab=x | (xa且xb)或(xb且xa)(ab)(ba)。例3.2.3設a2，3，b1，5，8，u1，10，求ab，ba，aa，a，ua。定義3.2.3 設a為一個集合，由a的所有子集作為元素組成的集合稱為a的冪集，記為(a)(p(a)或2a)，即(a)ssa。例3.2.4()=，()=，(a)=，a；設a0，1，則(a)，0，1，0,1；設b=0,1,2，則(b)=,0,1,2,0,1,0,2,1,2,b。定理3.2.2

8、 設a和b都是集合，則(1)(a)，a(a)；a； (2)(a)(b)(ab)；(3)(ab)= (a)(b)；(4 )若a是有限集，則|(a)|=2a。3.2.1集合合恒等式關于集合的運算，有下列基本規(guī)律：交換律：abba，abba；結合律：(ab)ca(bc)，(ab)ca(bc)；分配律：(ab)c=(ac)(bc)，(ab)c(ac)(bc)；同一律：aaaua;零一律：a，auu；排中律：au；矛盾律：a；等冪律：aaaaa；雙否律：a；吸收律：aa；德摩根律：，；例3.2.5(1)設a，b，c都是集合，且abac，abac，則bc；(2)對任意集合a，b，證明：abab。3.3集合中元素的計數(shù) 容斥原理設a，b，c，(i=1,2,)都是有限集，則|ab|=|a+|b-|ab|;|abc|=|a|+|b|+|c|-|ab|-|ac|-|bc|+|abc|;|=-+-+(-1)n-1。例3.3.1對100名大學生進行調查的結果是：3