離散數(shù)學(xué)教案 (800字) - 數(shù)學(xué)教案 - 書(shū)業(yè)網(wǎng)

1、離散數(shù)學(xué)教案 (800字) - 數(shù)學(xué)教案 - 書(shū)業(yè)網(wǎng) 第3章 集合與關(guān)系 學(xué)習(xí)目標(biāo)： 1深刻理解序偶、笛卡爾積、關(guān)系、集合的劃分與覆蓋、等價(jià)關(guān)系、等價(jià)類(lèi)、商集、相容關(guān)系、（最大）相容類(lèi)、偏序關(guān)系、極大元、極小元、上（下）界、上（下）確界、最大（?。┰?、全序關(guān)系、良序關(guān)系等概念； 2掌握集合的交、并、差、補(bǔ)、對(duì)稱(chēng)差的運(yùn)算及其運(yùn)算規(guī)律； 3掌握關(guān)系的交、并、逆、復(fù)合運(yùn)算、閉包運(yùn)算及其性質(zhì)； 4掌握關(guān)系的矩陣表示和關(guān)系圖； 5深刻理解關(guān)系的自反性、反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性和傳遞性，掌握其判別方法； 6掌握集合的覆蓋與劃分的聯(lián)系與區(qū)別； 7掌握偏序關(guān)系的判別及其哈斯圖的畫(huà)法；會(huì)求偏序集中給定集合的極

2、大元、極小元、上（下）界、上（下）確界、最大（?。┰?主要內(nèi)容： 1集合的基本概念及其運(yùn)算 2序偶與笛卡爾積 3關(guān)系及其表示 4關(guān)系的性質(zhì)及其判定方法 5復(fù)合關(guān)系和逆關(guān)系 6關(guān)系的閉包運(yùn)算 7等價(jià)關(guān)系與相容關(guān)系 8偏序關(guān)系 重點(diǎn)： 1關(guān)系的性質(zhì)及其判別； 2關(guān)系的復(fù)合運(yùn)算及其性質(zhì)； 3等價(jià)關(guān)系與等價(jià)類(lèi)、等價(jià)關(guān)系與集合的劃分的聯(lián)系； 4偏序關(guān)系判別及其哈斯圖的畫(huà)法、偏序集中特異位置元素的理解。 難點(diǎn)： 1關(guān)系的傳遞性及其判別； 2等價(jià)關(guān)系的特性； 3偏序關(guān)系的哈斯圖的畫(huà)法；偏序集中特異位置元素的求法。 教學(xué)手段： 通過(guò)多個(gè)實(shí)例的精講幫助同學(xué)理解重點(diǎn)和難點(diǎn)的內(nèi)容，并通過(guò)大量的練習(xí)使同學(xué)們鞏固和掌

3、握關(guān)系的性質(zhì)及其判別、關(guān)系的復(fù)合運(yùn)算及其性質(zhì)、等價(jià)關(guān)系的特性、偏序關(guān)系的哈斯圖的畫(huà)法及偏序集中特異位置元素的求法。 習(xí)題： 習(xí)題3.1：4，6；習(xí)題3.2：3（8），4（12），6（m）；習(xí)題3.4：1 （2）、(4)，3； 習(xí)題3.5：1，4；習(xí)題3.6：2，5，6；習(xí)題3.7：2，5，6；習(xí)題3.8：1（1）-（6）；習(xí)題3.9：3（2）、（4），4（3）；習(xí)題3.10：1 ，4，5。 3.1 集合的基本概念 集合(set)（或稱(chēng)為集）是數(shù)學(xué)中的一個(gè)最基本的概念。所謂集合，就是指具有共同性質(zhì)的或適合一定條件的事物的全體，組成集合的這些“事物”稱(chēng)為集合的元素。 集合常用大寫(xiě)字母表示，集合的元

4、素常用小寫(xiě)字母表示。若A是集合，a是A的元素，則稱(chēng)a屬于A，記作a?A；若a不是A的元素，則稱(chēng)a不屬于A，記作。若組成集合的元素個(gè)數(shù)是有限的，則稱(chēng)該集合為有限集(Finite Set)，否則稱(chēng)為無(wú)限集(Infinite Set)。 常見(jiàn)集合專(zhuān)用字符的約定： N自然數(shù)集合(非負(fù)整數(shù)集) I (或Z)整數(shù)集合(I?，I?) Q有理數(shù)集合(Q?，Q?) F分?jǐn)?shù)集合(F?，F(xiàn)?) C復(fù)數(shù)集合 O奇數(shù)集合 R實(shí)數(shù)集合(R?，R?) 腳標(biāo)+和-是對(duì)正、負(fù)的區(qū)分 P素?cái)?shù)集合 E偶數(shù)集合 冪集 定義3.1.1 對(duì)于每一個(gè)集合A，由A的所有子集組成的集合，稱(chēng)為集合A的冪集(Power Set)，記為 P(A)或

5、2即P(A)?BB?A。 例如：A?a,b,c, P(A)?,a,b,c,a,b,b,c,a,c,a,b,c。 定理3.1.1 如果有限集A有n個(gè)元素，則其冪集P(A)有2個(gè)元素。 證明 A的所有由k個(gè)元素組成的子集數(shù)為從n個(gè)元素中取k個(gè)的組合數(shù)。 n A n(n?1)(n?2)?(n?k?1) k! 另外，因?A，故P(A)的元素個(gè)數(shù)N可表示為 kCn? k N?1?C?C?C?C?Cn 1 n 2n kn nn k?0 n 又因 (x?y)?令 x?y?1 得 2? n n ?C k?0 n kn xkyn?k ?C k?0 n kn n 故P(A)的元素個(gè)數(shù)是2。 人們常常給有限集A的子

6、集編碼，用以表示A的冪集的各個(gè)元素。具體方法是： 設(shè)A?a1,a2,?,an，則A子集B按照含ai記1、不含ai記0(i?1,2,?,n)的規(guī)定依次寫(xiě)成一個(gè)n位二進(jìn)制數(shù)，便得子集B的編碼。 例如，若B?a1,an，則B的編碼是100?01，當(dāng)然還可將它化成十進(jìn)制數(shù)。如果n?4，那么這個(gè)十進(jìn)制數(shù)為9，此時(shí)特別記B?a1,a4為B9。 3.2 集合的對(duì)稱(chēng)差運(yùn)算 定義3.2.1 設(shè)A、B是兩個(gè)集合，要么屬于A，要么屬于B，但不能同時(shí)屬于A和B的所有元素組成的集合，稱(chēng)為A和B的對(duì)稱(chēng)差集，記為A?B。即 A?B?(A?B)?(B?A)?xx?A?x?B? 例如，若A?1,2,c,d，B?1,b,3,d，

7、則A?B?2,c,b,3。 對(duì)稱(chēng)差的定義如圖3-1所示。 圖3-1 由對(duì)稱(chēng)差的定義容易推得如下性質(zhì)： （1）A?B?B?A （2）A?A （3）A?A? （4）A?B?(A?)?(?B) （5）(A?B)?C?A?(B?C) 證明 （5）(A?B)?C ?(A?B)?(A?B?C) ?(A?)?(?B)?(A?)?(?B)?C ?(A?)?(?B?)?(?B)?(A?)?C 但 (?B)?(A?)?C =(?B)?A?(?B)?C ?(?A)?(A?B)?(?)?(B?)?C ?(A?B)?(?)?C ?(A?B?C)?(?C) 故 (A?B)?C ?(A?)?(?B?)?(A?B?C)?(?

8、C) 又 A?(B?C) ?(A?B?C)?(B?C) ?A?(B?)?(?C)?(B?)?(?C) ?A?(?C)?(B?)?(?B?)?(?C) 因?yàn)?A?(?C)?(B?) ?A?(?B)?(?)?(C?B)?(C?) ?A?(?)?(C?B) ?(A?)?(A?C?B) 故 A?(B?C) ?(A?)?(A?B?C)?(?B?)?(?C) 因此 (A?B)?C?A?(B?C) 對(duì)稱(chēng)差運(yùn)算的結(jié)合性亦可用圖3-2說(shuō)明。 A?B B? C (A?B)?C?A?(B?C) 圖3-2 對(duì)稱(chēng)差運(yùn)算的結(jié)合性 從文氏圖3-3亦可以看出以下關(guān)系式成立。 A?B?(A?)?(B?)?(A?B) ? B )

9、 ?(A?B)?(A 圖3-3 A?B 3.4 序偶與笛卡爾積 3.4.1 序偶 在日常生活中，有許多事物是成對(duì)出現(xiàn)的，而且這種成對(duì)出現(xiàn)的事物，具有一定的順序。 例如，上，下；1?2；男生9名而女生6；中國(guó)地處亞洲；平面上點(diǎn)的坐標(biāo)等。一般的說(shuō)，兩個(gè)具有固定次序的客體組成一個(gè)序偶(Ordered Pair)，記作x,y。上述各例可分別表示為上，下；9,6；中國(guó)，亞洲；a,b等。 序偶可以看作是具有兩個(gè)元素的集合，但它與一般集合不同的是序偶具有確定的次序。在集合中，?a,b?b,a?，但對(duì)序偶，當(dāng)a?b時(shí)，a,b?b,a。 定義3.4.1 兩個(gè)序偶相等，x,y?u,v，當(dāng)且僅當(dāng)x?u,y?v。 這

10、里指出：序偶a,b中兩個(gè)元素不一定來(lái)自同一個(gè)集合，它們可以代表不同類(lèi)型的事物。例如，a代表操作碼，b代表地址碼，則序偶a,b就代表一條單地址指令；當(dāng)然亦可將a代表地址碼，b代表操作碼，a,b仍代表一條單地址指令。但上述這種約定，一經(jīng)確定，序偶的次序就不能再予以變化了。在序偶a,b中，a稱(chēng)第一元素，b稱(chēng)第二元素。 序偶的概念可以推廣到有序三元組的情況。 有序三元組是一個(gè)序偶，其第一元素本身也是一個(gè)序偶，可形式化表示為序偶相等的定義，可以知 道 x,y,z。由 x,y,?u,當(dāng)且僅 當(dāng)x,y?u,z，即?w x?u,y?v,z?w，我們約定有序三元組可記作x,y,z。注意：x,y,z?x,y,z，

11、因 為x,y,z 不是有序三元組。同理，有序四元組被定義為一個(gè)序偶，其第一元素為有序三元 組，故有序四元組有形式為 x,y,z,w，可記作x,y,z,w，且 x,y,z,w?p,q,r,s?x?p?y?q?z?r?w?s 這樣，有序n元組(Ordered n-tuple) 定義為 x1,x2,?,xn?1,xn，記作x1,x2,?,xn?1,xn，且 x1,x2,?,xn?y1,y2,?,yn?x1?y1?x2?y2?xn?yn 一般地，有序n元組x1,x2,?,xn中的xi稱(chēng)作有序n元組的第i個(gè)坐標(biāo)。 3.4.2 笛卡爾積 定義3.4.2 設(shè)A和B是任意兩個(gè)集合，若序偶的第一個(gè)成員是A的元素

12、，第二個(gè)成員是B 的元素，所有這樣的序偶集合，稱(chēng)為集合A和B的笛卡爾乘積或直積(Cartesian Product)，記作A?B。即 A?B?x,yx?A?y?B 例3.4.1 若A?1,2,B?a,b,c, 求A?B,B?B以及(A?B)?(B?A) 解 A?B?,a,b,1,c,2,a,2,b,2,c B?B?a,a,a,b,a,c,b,a,b,b,b,c,c,a,c,b,c,c B?A?a,1,a,2,b,1,b,2,c,1,c,2 (A?B)?(B?A)? 顯然，我們有： （1）A?B?B?A； （2）如果A?m,B?n，則A?B?B?A?AB?mn。 我們約定：若A?或B?，則A?B

13、?。 由笛卡爾積定義可知： (A?B)?C?x,y,zx,y?A?B?z?C x?A?y,z?B?C x,y,zx?A?y?B?z?C A?(B?C)?x,y,z 由于x,y,z 不是三元組，所以 (A?B)?C?A?(B?C) 定理3.4.1 設(shè)A、B和C為任意三個(gè)集合，則有 （1）A?(B?C)?(A?B)?(A?C) （2）A?(B?C)?(A?B)?(A?C) （3）(A?B)?C?(A?C)?(B?C) （4）(A?B)?C?(A?C)?(B?C) 證明 （1）設(shè)x,y?A?(B?C)?x?A?y?B?C ?x?A?(y?B?y?C) ?(x?A?y?B)?(x?A?y?C) ?x,y?A?B?x,y?A?C ?x,y?(A?B)?(A?C) 因此， A?(B?C)?(A?B)?(A?C)。 （4）設(shè)x,y?(A?B)?C?x?A?B?y?C ?(x?A?x?B)?y?C ?(x?A?y?C)?(x?B?y?C) ?x,y?A?C?x,y?B?C ?x,y?(A?C)?(B?C) 因此， (A?B)?C?(A?C)?(B?C)。 定理3.4.2 設(shè)A、B和C為三個(gè)非空集合，則有 A?B?A?C?B?C?C?A?C ? 證明 設(shè)A?B，對(duì)任意的x,y， x,y?A?C?x?A?y?C ?x?B?y?C ?x,y?B?C 因此， A?C?B?C。 反之，