計(jì)算機(jī)數(shù)學(xué)15講課稿

1、第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)計(jì)算機(jī)數(shù)學(xué)15第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)基本要求基本要求掌握集合、子集、全集、空集和冪集等概念。熟悉常用的表示集合的方掌握集合、子集、全集、空集和冪集等概念。熟悉常用的表示集合的方法。能夠判定元素與集合、集合與集合之間的關(guān)系；熟練掌握兩個(gè)集合相法。能夠判定元素與集合、集合與集合之間的關(guān)系；熟練掌握兩個(gè)集合相等關(guān)系和包含關(guān)系的定義和性質(zhì)，能夠利用定義證明兩個(gè)集合相等。等關(guān)系和包含關(guān)系的定義和性質(zhì)，能夠利用定義證明兩個(gè)集合相等。 熟練掌握集合之間的各種運(yùn)算以及集合運(yùn)算的基本等式，能夠利用它們熟練掌握集合之間的各種運(yùn)算

2、以及集合運(yùn)算的基本等式，能夠利用它們來證明更復(fù)雜的集合等式。來證明更復(fù)雜的集合等式。掌握余集與集合笛卡兒乘積的概念以及掌握余集與集合笛卡兒乘積的概念以及De Morgan公式。公式。 第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)重點(diǎn)難點(diǎn)重點(diǎn)難點(diǎn)重點(diǎn)：重點(diǎn)：證明兩個(gè)集合相等的方法；證明兩個(gè)集合相等的方法； 運(yùn)用集合之間的各種運(yùn)算以及集合運(yùn)算的基本等式來證明更復(fù)雜運(yùn)用集合之間的各種運(yùn)算以及集合運(yùn)算的基本等式來證明更復(fù)雜的集合等式。的集合等式。 第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)15.1 15.1 集合集合 集合概念是數(shù)學(xué)中最基本的概念之一，它不具有嚴(yán)格精確的定義，只能

3、給出描述性定義。一般地，把一些確定的、彼此不同的事物作為一個(gè)整體來研究時(shí)，這個(gè)整體便稱為一個(gè)集合.組成這個(gè)集合的個(gè)別事物，稱為集合的元素。例如： 15.1.1 15.1.1 集合的概念與表示 方程方程 x210的實(shí)數(shù)解集合；的實(shí)數(shù)解集合； 26個(gè)英文字母的集合；個(gè)英文字母的集合； 坐標(biāo)平面上所有點(diǎn)的集合；坐標(biāo)平面上所有點(diǎn)的集合； 表示一個(gè)集合的方法通常有兩種：表示一個(gè)集合的方法通常有兩種：列舉法列舉法和和描述法描述法。 列舉法是列出集合的所有元素、或其規(guī)律。例如：列舉法是列出集合的所有元素、或其規(guī)律。例如：A =a,b,c,d ,B =1,2,3,4 描述法是將集合中元素的共同屬性描述出來，其

4、一般形式為：描述法是將集合中元素的共同屬性描述出來，其一般形式為： M =xx所具有的特征所具有的特征第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)例如：A =yy=sin x，xRB =(x，y)x2+y2=R2C =(x，y，z)z=x2-y2常見的幾個(gè)數(shù)集用特定的符號(hào)表示：常見的幾個(gè)數(shù)集用特定的符號(hào)表示：N=xx為自然數(shù)為自然數(shù)Z=xx為整數(shù)為整數(shù)Q=xx為有理數(shù)為有理數(shù)R=xx為實(shí)數(shù)為實(shí)數(shù)如果集合A的元素都是集合B的元素，即若xA，則有xB，則稱A是B的子集，B包含A，記為A B，或B A。例如N Z，Z Q，Q R。 若A A，且B A，則稱集合A與A相等，記為A=B。例如：

5、 如果：如果：A=xx2-1=0，B=1，-1，C=xx=1則有：則有：A=B=C 不含任何元素的集合稱為空集，記為不含任何元素的集合稱為空集，記為 .例如：例如： xx2+1=0，xR= 第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)在一個(gè)具體問題中，如果所涉及的集合都是某個(gè)集合的子集，則稱這個(gè)集合為全集全集，記為E。全集是一個(gè)相對(duì)性概念。由于研究的問題不同，所取的全集也不同，而且并非是惟一的，一般總是取一個(gè)比較方便的集合作為全集全集。例如：在研究函數(shù)定義域時(shí)，我們?nèi)∪疎=R。顯然對(duì)任一集合A有 A E設(shè)A是一個(gè)集合，由A的所有子集組成的集合，稱為集合A的冪集冪集，記為(A)或2A

6、。例15.1.1設(shè)設(shè): A= ，B=1，C=a，b，c求求: A、B、C的冪集解解: (A)= (B)= ，1 (C)= ，a，b，c，a，ba，c，b，c，a，b，c 第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)定理定理15.1 如果有限集合如果有限集合A中元素的個(gè)數(shù)中元素的個(gè)數(shù)( ( 稱為集合稱為集合A的元數(shù)的元數(shù) ) )為為n，則冪集，則冪集(A)的元數(shù)為的元數(shù)為2 n。證證：n元集合元集合A，它的，它的0 0元子集有元子集有C0n個(gè)個(gè)( (即即 ) )，1 1元子集有元子集有C1n 個(gè)，個(gè)， ，m元子集有元子集有C mn個(gè)，個(gè)，n元子集有元子集有C nn個(gè)，全部子集共有個(gè)，全

7、部子集共有Cn0+Cn1+C nm+C nn=2 n即：冪集即：冪集(A)的元數(shù)為的元數(shù)為2n第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè) 15.1.2 15.1.2 集合的運(yùn)算集合的運(yùn)算定義定義17.1 設(shè)有全集設(shè)有全集E，A和和B是其中兩個(gè)任意集合。是其中兩個(gè)任意集合。(1) (1) 所有屬于所有屬于A A或?qū)儆诨驅(qū)儆贐 B的元素組成的集合稱為集合的元素組成的集合稱為集合A A與與B B的并集，記為的并集，記為AB。即即 AB=xxA 或或 xB(2) (2) 屬于屬于A同時(shí)又屬于同時(shí)又屬于B的所有元素組成的集合，稱為的所有元素組成的集合，稱為A與與B的交集，記為的交集，記為AB

8、。即。即 AB=xxA 且且 xB(3) (3) 屬于屬于A而不屬于而不屬于B的所有元素組成的集合，稱為的所有元素組成的集合，稱為A與與B的差集，的差集，記為記為A-B。即。即 A-B=xxA 且且x B(4) (4) 由由E E中所有不屬于中所有不屬于A A的元素組成的集合稱為的元素組成的集合稱為A A的補(bǔ)集，記為的補(bǔ)集，記為 。即。即 =xxE 且且 x A第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)例 15.1.1設(shè): E=R，A=xx3，B=x0 x5則：AB=x-3x5AB=x0 x3A-B=x-3x0 例15.1.2 若：A B則：AB=B，AB=A，A-B= 為了直觀，

9、有時(shí)我們用文氏圖(Venn)來表示集合，即用矩形圈起來的平面上的點(diǎn)表示E，用封閉曲線圈起來的圓表示集。則集合的四種運(yùn)算的文氏圖表示即為圖所示。=xx-3或或x3ABABA-B 第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè) 圖與實(shí)數(shù)運(yùn)算滿足一些運(yùn)算律類似，集合的運(yùn)算也具有許多運(yùn)算律.設(shè)A，B，C為任意集合，則有恒等式如下：l(1) 交換律AB=BA，AB=BAl(2) 結(jié)合律A(BC)=(AB)C，A(BC)=(AB)Cl(3) 分配律A(BC)=(AB)(AC)，A(BC)=(AB)(AC)l(4) 等冪律AA=A，AA=Al(5) 同一律A =A，AE=Al(6) 零一律A = ，

10、AE=El(7) 互補(bǔ)律A =E，A = l(8) 吸收律A(AB)=A，A(AB)=Al(9) 摩根律 l(10) 對(duì)合律 =A例15.1.3有：有：A-B=A 試證：試證：A-(B-C)=(A-B)(AC)證：證：A-(B-C)=A(BC)=A(C)=A(C)(A-B)(AC)=(A)(AC)=A(C)故：故：A-(B-C)=(A-B)(AC) 第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)15.2 關(guān)系關(guān)系 定義定義15.2 兩元素按給定順序排列組成的二元組合稱為一個(gè)有序?qū)?，記為x，y。其中x是它的第一元素，y是它的第二元素.對(duì)于有序?qū)，b和c，d，當(dāng)且僅當(dāng)a=c且b=d 時(shí)，

11、才稱a，b與c，d相等，記為a，b=c，d。當(dāng)ab時(shí)，有序?qū)，bb，a。例如，平面上的點(diǎn)(x，y)就是一個(gè)有序?qū)Α?定義定義15.3 設(shè)A、B是兩個(gè)集合，xA，yB，則所有有序?qū)，y的集合，稱為A和B的笛卡爾乘積，記為AB。15.2.1 15.2.1 笛卡爾乘積 第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)例例15.2.1設(shè): A=1，2，B=a，b，c，則則: AB=1，a，1，b，1，c，2，a，2，b，2，cBA=a，1，b，1，c，1，a，2，b，2，c，2AA=1，1，2，2，1，2，2，1BB=a，a，a，b，a，c，b，a，b，b，b，c，c，a，c，b，c，c 第

12、十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)關(guān)系是使用非常廣泛的一個(gè)詞，例如人與人之間有朋友關(guān)系，夫妻關(guān)系，同學(xué)關(guān)系，師生關(guān)系等；兩個(gè)數(shù)之間有大小關(guān)系，相等關(guān)系，整除關(guān)系，運(yùn)算關(guān)系等；計(jì)算機(jī)的程序之間有調(diào)用關(guān)系等。現(xiàn)在我們將這些關(guān)系抽象，用有序?qū)砜坍嫛?15.2.2 關(guān)系的概念關(guān)系的概念 定義定義 15.4 若若A和和B是兩個(gè)集合，則是兩個(gè)集合，則AB的任何子集都定義了一個(gè)二元關(guān)系，簡(jiǎn)的任何子集都定義了一個(gè)二元關(guān)系，簡(jiǎn)稱關(guān)系。記稱關(guān)系。記R，即即R AB若若a，bR，可記為，可記為aRb；否則，則記為；否則，則記為ab.例如：例如：自然數(shù)之間的大于關(guān)系自然數(shù)之間的大于關(guān)系=x，yx，

13、yN，且，且xy；人群中人群中的父子關(guān)系的父子關(guān)系=x，yx，y是人，并且是人，并且x是是y的父親。的父親。第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)定義定義 15.5 設(shè)設(shè)R 為集合為集合A上的關(guān)系上的關(guān)系.若若R= ，則稱，則稱R為為空關(guān)系空關(guān)系，記為，記為 A.若若R=AA，則稱則稱R為為全關(guān)系全關(guān)系，記為，記為EA；若；若R=a，aaA，則稱則稱R為為恒等關(guān)系恒等關(guān)系，記為記為IA。例例15.2.2若若:A=1，2，3則則:EA=1，1，1，2，1，3，2，1，2，2，2，3，3，1，3，2，3，3，IA=1，1，2，2，3，3第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)

14、前頁(yè)前頁(yè)15.2.3 關(guān)系的性質(zhì)關(guān)系的性質(zhì) 定義定義15.6設(shè)R是集合A上的關(guān)系(1) 若對(duì)于每一個(gè)aA，均有aRa，則稱關(guān)系R是自反的自反的(2) 對(duì)于任意的a，bA，若有aRb，就有bRa，則稱R是對(duì)稱的對(duì)稱的(3) 對(duì)于任意的a，bA，若有aRb且bRa，必有a=b，則稱R是反對(duì)稱的反對(duì)稱的(4) 對(duì)于任意的a，b，cA，若有aRb且bRc，就有aRc，則稱R是傳遞的傳遞的例例15.2.5設(shè):A=1，2，3，4，5，R是A上的關(guān)系，定義為R=x，yx 整除y，x，yA.試判斷R的性質(zhì)。解:R=1，1，2，2，3，3，4，4，5，5，1，2，1，3，1，4，1，5，2，4.由定義可知，R是

15、自反的，反對(duì)稱的，傳遞的。 第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè) 注意：注意：(1) 不是對(duì)稱的，并非就是反對(duì)稱的。也就是說，對(duì)于某個(gè)關(guān)系，可能既不是對(duì)稱關(guān)系，也不是反對(duì)稱關(guān)系。例如，集合A=1，2，3上的關(guān)系R=1，2，2，3，3，2，R既不是對(duì)稱的，也不是反對(duì)稱的。(2) 對(duì)于某種關(guān)系，可能既是對(duì)稱的，又是反對(duì)稱的.例如，集合A=1，2，3上的恒等關(guān)系IA=1，1，2，2，3，3，就是既是對(duì)稱的，也是反對(duì)稱的。 第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)定義定義15.7 設(shè)R是集合A上的關(guān)系，如果關(guān)系R同時(shí)具有自反性、對(duì)稱性、傳遞性，則稱R是等價(jià)關(guān)系等價(jià)關(guān)系.此時(shí)的aRb，又稱為a等價(jià)于b，記為a b。 定義定義15.8 設(shè)設(shè) 是是A上的等價(jià)關(guān)系，上的等價(jià)關(guān)系，M是是A的一個(gè)非空子集，若滿足條件：的一個(gè)非空子集，若滿足條件：(1) 若若aM，bM，則，則a b；(2) 若若aM，b M，則，則a與與b不等價(jià)。不等價(jià)。則稱子集則稱子集M為為A在關(guān)系在關(guān)系R上的一個(gè)等價(jià)類。上的一個(gè)等價(jià)類。第十五章集合論第十五章集合論 后頁(yè)后頁(yè)首頁(yè)首頁(yè)前頁(yè)前頁(yè)例例 15.2.8整數(shù)集整數(shù)集Z 上關(guān)系上關(guān)系 Rx，yx，yZ，xy被被3整