數(shù)理邏輯與集合論：9-1 集合

1、第二部分 集合論n引例n有有10名學(xué)生參加一個(gè)名學(xué)生參加一個(gè)Party，一共要了，一共要了8瓶飲料和瓶飲料和6個(gè)雪個(gè)雪糕，已知有糕，已知有1人什么也沒要，其他人每種至多要人什么也沒要，其他人每種至多要1份，份，問：最后有多少人既要了飲料又要了雪糕？問：最后有多少人既要了飲料又要了雪糕？n集合論的功能是現(xiàn)代數(shù)學(xué)的重要基礎(chǔ)，集合不僅可用來表示數(shù)及是現(xiàn)代數(shù)學(xué)的重要基礎(chǔ)，集合不僅可用來表示數(shù)及運(yùn)算，更可用于非數(shù)值信息的表示和處理，如：運(yùn)算，更可用于非數(shù)值信息的表示和處理，如：n數(shù)據(jù)的維護(hù)數(shù)據(jù)的維護(hù)n數(shù)據(jù)間關(guān)系的描述數(shù)據(jù)間關(guān)系的描述n有些很難用傳統(tǒng)的數(shù)值計(jì)算來處理，但可用集合運(yùn)有些很難用傳統(tǒng)的數(shù)值計(jì)算來

2、處理，但可用集合運(yùn)算來處理算來處理集合論n 集合論的地位它在計(jì)算機(jī)科學(xué)領(lǐng)域中是不可或缺的數(shù)學(xué)工具，在它在計(jì)算機(jī)科學(xué)領(lǐng)域中是不可或缺的數(shù)學(xué)工具，在n形式語言形式語言n自動(dòng)機(jī)自動(dòng)機(jī)n人工智能人工智能n數(shù)據(jù)庫數(shù)據(jù)庫等領(lǐng)域中都卓有成效地應(yīng)用了集合論。等領(lǐng)域中都卓有成效地應(yīng)用了集合論。n 第二部分主要介紹集合論的基礎(chǔ)知識(shí)，如n集合的基本概念集合的基本概念n集合的運(yùn)算集合的運(yùn)算n集合的性質(zhì)集合的性質(zhì)n集合的關(guān)系集合的關(guān)系n集合的函數(shù)集合的函數(shù)等。等。第9章 集 合9.1 集合的概念和表示方法9.2 集合間的關(guān)系和特殊集合9.3 集合的運(yùn)算9.4 集合的圖形表示法9.5 集合運(yùn)算的性質(zhì)和證明9.6 有限集合

3、的基數(shù)9.1 集合的概念和表示方法n 集合是不能精確定義的基本的數(shù)學(xué)概念。n 一個(gè)集合一般指的是一些可確定的、可分辨的事物構(gòu)成的整體。n 集合的元素集合中的對(duì)象或個(gè)體。n 集合的構(gòu)成n集合可以由各種類型的事物構(gòu)成。集合可以由各種類型的事物構(gòu)成。 例如：例如： 26個(gè)英文字母的集合；個(gè)英文字母的集合； C+語言中保留字的集合；語言中保留字的集合； 坐標(biāo)平面上所有點(diǎn)的集合；坐標(biāo)平面上所有點(diǎn)的集合； 方程方程x210的實(shí)數(shù)解集合；的實(shí)數(shù)解集合； 集合的表示法n通常用大寫英文字母來標(biāo)記一些集合。n例如， N 代表代表自然數(shù)自然數(shù)集合集合(0N)，Z 代表代表整數(shù)整數(shù)集合，集合， Q 代表代表有理數(shù)有理

4、數(shù)集合，集合，R 代表代表實(shí)數(shù)實(shí)數(shù)集合，集合，C 代表代表復(fù)數(shù)復(fù)數(shù)集合。集合。集合的表示法列舉法n 列舉法（外延表示法）n列出集合的所有元素，元素之間用逗號(hào)隔開，并把它列出集合的所有元素，元素之間用逗號(hào)隔開，并把它們用花括號(hào)括起來。們用花括號(hào)括起來。n例如，例如，A=1,2,3,4,5其中其中1是是A的元素，記作的元素，記作1 A。 同樣有同樣有2 A , 4 A .。 但但6不是不是A的元素，可記作的元素，可記作6 A。n 注意：n對(duì)于任何集合對(duì)于任何集合 A 和元素和元素 x (可以是集合可以是集合)， x A和和 x A 兩者成立其一，且僅成立其一兩者成立其一，且僅成立其一互補(bǔ)律互補(bǔ)律.

5、元素與集合的關(guān)系元素與集合的關(guān)系 隸屬關(guān)系隸屬關(guān)系屬屬 于于 不屬于不屬于 集合的表示法描述法n 描述法(內(nèi)涵表示法) 用用謂詞謂詞概括集合中元素的屬性。概括集合中元素的屬性。n例如例如: 集合集合 B=x|P(x)， 表示表示B由使由使P(x)為真的全體為真的全體x構(gòu)成。構(gòu)成。nB=x|x Z 3 x 6 ，則則B=4,5,6。n 注意n謂詞謂詞P(x)的范圍一定要明確清楚，否則集合無法構(gòu)造。的范圍一定要明確清楚，否則集合無法構(gòu)造。n如：如：A=x|P(x)，P(x)：x是公園里的美麗的花。是公園里的美麗的花。n諸如諸如: P(x)：x x 這樣的謂詞不能作為定義集合的性質(zhì)這樣的謂詞不能作為

6、定義集合的性質(zhì)條件。條件。n若用這樣的謂詞來確定集合會(huì)產(chǎn)生若用這樣的謂詞來確定集合會(huì)產(chǎn)生悖論悖論。 如：如：我只給不給自己理發(fā)的人理發(fā)。我只給不給自己理發(fā)的人理發(fā)。集合的元素n集合的元素可以是任何類型的事物。n一個(gè)集合也可以作為另一個(gè)集合的元素。n例如，集合集合A=a, b, c,d, e 。n其中：其中：a A，c,d A, e A,n但是：但是：c A, e A。 n在集合論中規(guī)定n元素之間是彼此相異的，并且是沒有次序關(guān)系的元素之間是彼此相異的，并且是沒有次序關(guān)系的。n如：如：3,4,5, 3,4,4,5, 5,3,4都是同一個(gè)集合。都是同一個(gè)集合。 A只有只有4個(gè)元素，個(gè)元素，表示成表示

7、成|A|=4。元素與集合隸屬關(guān)系的層次結(jié)構(gòu)例例 ：A= a, b,c, d, d b,c A d A d A b A d An元集元集含有含有n個(gè)元素的集合的簡稱；個(gè)元素的集合的簡稱；一個(gè)集合的含有一個(gè)集合的含有m個(gè)元素的子集稱作它的個(gè)元素的子集稱作它的m元子集。元子集。9.2 集合間的關(guān)系和特殊集合n 定義n設(shè)設(shè)A, B為集合，如果為集合，如果B中的每個(gè)元素都是中的每個(gè)元素都是A中的元素，則中的元素，則稱稱B為為A的的子集合子集合，簡稱，簡稱子集子集。n這時(shí)也稱這時(shí)也稱B被被A包含包含，或，或A包含包含B。記作。記作B A 或或 A B。n “BA”的符號(hào)化表示為：n B A x(x Bx

8、A)n 如果不被包含，則記作B A ，符號(hào)化為：n B A x (x B x A) n 如：A=0,1,2, B=0,1, C=1,2 則有nB A, C A,n但但C B。因?yàn)榇嬖?。因?yàn)榇嬖?，2 C 但但 2 B。集合相等的定義n集合相等的定義： 設(shè)設(shè)A、B為任意集合，為任意集合，n如果如果A B且且B A，則稱，則稱A與與B相等。記為相等。記為A=B。n如果如果A與與B不相等，記為不相等，記為AB。n集合相等的謂詞公式表示 A=B A BB A ( x)(x Ax B)( x)(x Bx A) ( x)(x Ax B)結(jié)論：兩個(gè)集合相等的充要條件是它們互為子集。集合間的關(guān)系n例如：n設(shè)設(shè)

9、 A=1, 2，B=1, 2 ，C=2, 1 則則nA=CnABn集合相等有下列性質(zhì)：設(shè)設(shè)A、B、C為任意集合為任意集合自自 反反 性性: A A A=A。反對(duì)稱性反對(duì)稱性: （A B B A） B = A。傳傳 遞遞 性性: （A B B C） A C。集合之間的關(guān)系n 集合與集合的關(guān)系n 包含包含 A B x (x A x B)n 不包含不包含 A B x(x A x B)n 相等相等 A = B A B B A x(x A x B)n 不相等不相等 A B ( x)(x Bx A)n 真包含真包含 A B A B A B ( x)(x Ax B)( x)(x Bx A)n 不真包含不真包含 A Bn 思考：思考： 和和 的定義的定義 空集與全集n 空集空集 不含任何元素的集合。n如：如：A= x | x2+1=0 x R =n 定理定理：空集是任何集合的子集。n A x (xx A) T n 推論：推論：空集是惟一的空集是惟一的.n 全集全集 En在一定范圍內(nèi)，在一定范圍內(nèi)，如果所涉及的集合均是某個(gè)集合的子如果所涉及的集合均是某個(gè)集合的子集，則稱此集合為全集（集，則稱此集合為全集（E）。）。n 在給定問題中，全集包含任何集合，即在給定問題中，全集包含任何集合，即 A (A E )n全集的概念相當(dāng)于論域。全集的概念相當(dāng)于