1、第二部分 集合論集合論是研究集合一般性質的數(shù)學分支，創(chuàng)始人是康托爾(G.Cantor 1845-1918)。現(xiàn)代數(shù)學中，每個對象(數(shù)，函數(shù)等)本質上都是集合，即可以用某種集合來示義，數(shù)學的各個分支本質上都是在研究某一種對象集合的性質，集合論的特點是研究對象的廣泛性，是計算機科學的基礎理論表達工具。第三章 集合代數(shù)3.1集合的基本概念1.集合的定義集合是現(xiàn)代數(shù)學中最重要的基本概念之一。我們知道，在任何一個數(shù)學理論中，不可能對其中的每個概念都嚴格定義，這樣的概念一般為數(shù)學理論中的原始概念，而稱其余的概念為它的派生概念。如歐幾里得幾何學中，“點”和“線”是原始概念，而“三角形”和“圓”則為派生概念。

2、今天我們介紹的“集合”也是一個不能嚴格定義的原始概念。但是為了理解上的方便，我們仍然給一個不嚴格的定義。3.1 集合的基本概念定義3.1：任何被稱為“成員”或“元素”的對象的聚集稱為集合(Set)。例如：自然數(shù)的全體N，有理數(shù)的全體Q，實數(shù)的全體R，復數(shù)的全體C，整數(shù)的全體Z，都是集合。通常情況下，用帶(或不帶)下標的大寫英文字母表示集合，而用帶(或不帶)下標的小寫英文字母表示集合的元素或成員。3.1 集合的基本概念2.集合的表示集合是由它所包含的元素完全確定的，有多種方法來表示一個集合。(1).枚舉法：當一個集合僅有有限個元素或元素之間有明顯的關系時，采用列出集合中全部元素或部分元素的方法，

3、叫枚舉法。例：A=1,2,3,4，B=a, b, c, x, y, z，N =0,1,2,3, 。這種方法實際上是一種顯示表示法，優(yōu)點是具有透明性，缺點是當集合中元素比較多時會占據(jù)大量內存。3.1 集合的基本概念3.集合與元素的關系元素和集合之間的關系是“隸屬關系”，即“屬于”或“不屬于”，“屬于”記作，不屬于記作。例：A=a，b，c，d，a A， b，c A，b A。例3-1：在一個很偏僻的孤島上，住著一些人家，島上只有一個理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉的人刮臉。那么該給這位理發(fā)師刮臉？3.1 集合的基本概念在離散數(shù)學中，我們僅討論界限清楚無二義性的元素與集合的隸屬關系，即元

4、素a要么屬于集合A，要么不屬于集合A，兩者必居其一。4.集合的特性(1).確定性：即aA或a A，兩者必居其一且僅居其一；(2).互異性：集合中相同的元素被視為同一元素，即：1，1，2，2與1，2相同；(3).無序性：集合中的元素順序并不重要，如1，2，3，4與2，3，4，1相同。3.1 集合的基本概念定義3.3：設A，B為集合，如果AB且BA，則稱A與B相等，記作A=B，如果A與B不相等，則記作AB。相等的符號化表示為：A=B ABBA例：A=x|xN，且x4，B=0，1，2，3，4則A=B。定義3.4：設A，B為集合，如果BA且BA，則稱B是A的真子集(Proper Subset)，記作B

5、A，稱“”為真包含關系(Properly Inclusion Relation)，如果B不是A的真子集，則記作BA3.1 集合的基本概念這時或者 ，或者B=A，符號化表示為：例： ，但 ，0,1，2,3是0,1,2,3的真子集，但1,4不是。定義3.5：不含任何元素的集合叫做空集(Empty Set)，記作?？占柣硎緸椋?x |x x。例：設 ，是方程 的實數(shù)解集，而該方程無實數(shù)解，所以A= 。3.1 集合的基本概念定理3.1：(1)：空集是一切集合的子集，(2)：空集是唯一的。例3-2：確定下列命題的真值：(1)：，(2)： ，(3)：，(4)： 。3.1 集合的基本概念定義3.6：在

6、一個具體問題中，如果涉及的集合都是某個集合的子集，則稱這個集合問全集(Universal Ser)，用U或E表示。全集是唯一的，它包含了該問題所涉及的所有元素。例：(1)在平面幾何中，全集是由平面上全體點組成； (2)在人口研究中，全集是由世界上的所有人組成定義3.7：集合中的所有元素的個數(shù)稱為集合的基數(shù)(Base Number)，記為|A|；如果一個集合的基數(shù)是有限的，則稱集合為有限集(Finite Set)，如果一個集合的基數(shù)是無限的，則稱集合為無限集(Infinite Set)。3.1 集合的基本概念例3-3：求集合A，B，C，D的基數(shù)：A=；B=1,2,3；C=1，2,3；D=。解：|

7、A|=0；|B|=3；|C|=2；|D|=1。定義3.8：含有n個元素的集合A稱為n元集，它的含義m個(m n)元素的子集稱作它的m元子集。例3-4：設A=1,2,3，求A的全部子集：解：將A的全部子集按從小到大進行分類： 0元子集：即空集，有C03個：； 1元子集：即單元素，有 C13個：1，2，3； 2元子集：有C23個：1,2，1,3，2,3； 3元子集：有C33個：1,2,3。3.1 集合的基本概念集合A=1,2,3的全部子集共有：一般來說，對于n元集A，它的m(0mn)元子集有個，所以它的不同子集總數(shù)為：定義3.9：設A為集合，把A的全體子集構成的集合叫做A的冪集(Power Set

8、)，記作P(A)或2A，符號化為：P(A)=x|x A。例：設A=1,2,3，則P(A)= ，1，2，3，1,2，1,3，2,3，1,2,3，|P(A)|=2n3.2 集合的運算為了更好的研究集合的性質，我們定義了集合的幾個基本運算。定義3.10：設A，B是兩個集合，則A與B的并集(Union)定義為： ，“”稱為并運算(Union Operation)。例：1,2,3,43,4,5=1,2,3,4,5，QN=Q。定義3.11：設A，B是兩個集合，則A與B的交集(Intersection)定義為： ，“”稱為交運算(Intersection Operation)。例：1,2,3,4 3,4,5

9、=3,4，a, b = ， QN=N。3.2 集合的運算可以將以上定義推廣到n個甚至無窮個集合的并集或交集：例：1,22,30,1=0,1,2,3； 1,2 2,3 0,1= 。3.2 集合的運算定義3.14：設A，B是兩個集合，A與B的對稱差集(Symmetric Differences)定義為：“”稱為對稱差運算(Symmetric Differences Operation)。例：1,2,3,4 3,4,5,6=1,2,5,6； a, b, c =a, b, c。定理3.2：集合恒等式：等冪律：A A=A，A A=A;結合律：(AB)C=A(BC)，(A B) C=A (B C)；交換律

10、：A B=B A，A B=B A；3.2 集合的運算分配律：A(BC)=(A B) (A C)，A (B C)=(A B)(A C)；同一律：A =A，A U=A；零律：A U=U，A = ；排中律： ；矛盾律： ；吸收律：A(A B)=A， A (A B)=A；德摩根律：(AB)=A B，(A B)=AB雙重否定律： ；補交轉換律： 。3.2 集合的運算例3-6：證：(3):A，B為集合，已知A-B=B-A，證明：A=B。證：(1):3.2 集合的運算(2):(3): 同理：A B，A=B。3.3 有限集合的計數(shù)1. 鴿籠原理(Pigeonhole Principle)定理3.3：若有n+1

11、個鴿子住進n個鴿籠，則至少有一個鴿籠至少住進2只鴿子。證明：(用反證法)假設每個鴿籠至多只住進1只鴿子，則n個鴿籠至多住進n只鴿子，這與有n+1只鴿子矛盾。命題成立。例3-7：求證：設有n+1個正整數(shù) ，則總可以找到一對數(shù) (1ijn+1)使得它們的差能被n整除。證明： 取被n整除的余數(shù)，若n個余數(shù)互不相同，則必有一個為0，不妨設為 則 能被n整除。否則，由鴿籠原理，必有2個3.3 有限集合的計數(shù)余數(shù)相同，不妨設為 ，則 能被n整除。定理3.4：(鴿籠原理的推廣)若有n只鴿子住進m個鴿籠，則至少有一個鴿籠至少住進 只鴿子2.容斥原理(包含排斥原理)所謂容斥，是指我們計算某類物的數(shù)目時，要排斥那些不應包含在這個計數(shù)中的數(shù)目，但同時要包含那些被錯誤地排斥了的數(shù)目，以此補償，這種原理稱為容斥原理(The Principle of Inclusion-exclusion)，又稱為包含排斥原理。定理3.5：設A和B是任意有限集合，則|AB|=|A|+|B|-|AB|。3.3 有限集合的計數(shù)定理3.6：設 是任意有限集合，則推論3.2：設U為全集， 則證明：用數(shù)學歸納法。3.3 有限集合的計數(shù)例3-8：某軟件公司的程序員都熟悉Java或VB，其中熟悉Java的共47人，熟悉VB的共35人，兩者都熟悉的共23人，問該軟件公司共有多少程序員？解：設A，B分別表示