二部分集合論課件

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

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

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

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

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

6、一個(gè)具體問(wèn)題中，如果涉及的集合都是某個(gè)集合的子集，則稱這個(gè)集合問(wèn)全集(Universal Ser)，用U或E表示。全集是唯一的，它包含了該問(wèn)題所涉及的所有元素。例：(1)在平面幾何中，全集是由平面上全體點(diǎn)組成； (2)在人口研究中，全集是由世界上的所有人組成定義3.7：集合中的所有元素的個(gè)數(shù)稱為集合的基數(shù)(Base Number)，記為|A|；如果一個(gè)集合的基數(shù)是有限的，則稱集合為有限集(Finite Set)，如果一個(gè)集合的基數(shù)是無(wú)限的，則稱集合為無(wú)限集(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個(gè)元素的集合A稱為n元集，它的含義m個(gè)(m n)元素的子集稱作它的m元子集。例3-4：設(shè)A=1,2,3，求A的全部子集：解：將A的全部子集按從小到大進(jìn)行分類： 0元子集：即空集，有C03個(gè)：； 1元子集：即單元素，有 C13個(gè)：1，2，3； 2元子集：有C23個(gè)：1,2，1,3，2,3； 3元子集：有C33個(gè)：1,2,3。3.1 集合的基本概念集合A=1,2,3的全部子集共有：一般來(lái)說(shuō)，對(duì)于n元集A，它的m(0mn)元子集有個(gè)，所以它的不同子集總數(shù)為：定義3.9：設(shè)A為集合，把A的全體子集構(gòu)成的集合叫做A的冪集(Power Set

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

9、=3,4，a, b = ， QN=N。3.2 集合的運(yùn)算可以將以上定義推廣到n個(gè)甚至無(wú)窮個(gè)集合的并集或交集：例：1,22,30,1=0,1,2,3； 1,2 2,3 0,1= 。3.2 集合的運(yùn)算定義3.14：設(shè)A，B是兩個(gè)集合，A與B的對(duì)稱差集(Symmetric Differences)定義為：“”稱為對(duì)稱差運(yùn)算(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;結(jié)合律：(AB)C=A(BC)，(A B) C=A (B C)；交換律

10、：A B=B A，A B=B A；3.2 集合的運(yùn)算分配律：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雙重否定律： ；補(bǔ)交轉(zhuǎn)換律： 。3.2 集合的運(yùn)算例3-6：證：(3):A，B為集合，已知A-B=B-A，證明：A=B。證：(1):3.2 集合的運(yùn)算(2):(3): 同理：A B，A=B。3.3 有限集合的計(jì)數(shù)1. 鴿籠原理(Pigeonhole Principle)定理3.3：若有n+1

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