離散數(shù)學(xué)(第六章)

1、6.1 集合的基本概念集合的基本概念6.2 集合的運(yùn)算集合的運(yùn)算6.3 集合恒等式集合恒等式 掌握：掌握：集合的概念，集合的表示方法，元集合的概念，集合的表示方法，元素與集合的關(guān)系，集合與集合的關(guān)系，素與集合的關(guān)系，集合與集合的關(guān)系，冪集，集合的交、并、相對(duì)補(bǔ)、絕對(duì)補(bǔ)冪集，集合的交、并、相對(duì)補(bǔ)、絕對(duì)補(bǔ)、對(duì)稱差運(yùn)算、對(duì)稱差運(yùn)算 6.1 集合的基本概念集合的基本概念1、集合與元素、集合與元素（1）集合：具有某種特殊性質(zhì)的客體的聚合。討論：一些不同的確定的對(duì)象之全體。客體：是泛指一切，可以是具體的、抽象的元素（成員）：屬于任何集合的任何客體。符號(hào)：用大寫英文字母A，B.表示集合，用小寫英文字母a，b

2、.或其它符號(hào)表示元素。元素與集合間的關(guān)系： a是集合S中的元素，則寫成a S ；b不是集S合中的元素，則寫成b S 。6.1 集合的基本概念集合的基本概念(2)本書中常用集合符: Im(m1) 有限個(gè)正數(shù)的集合1,2,3m Nm(m0) 有限個(gè)自然數(shù)的集合0,1,2m 以上是有限集合,下面是無限集合：N 然數(shù)集合 0,1,2I+ 正整數(shù)集合 1,2,3I 整數(shù)集合 -1,0,1,2P 素?cái)?shù)集合 大于1的正整數(shù)，只能被1和自己整除Q 有理數(shù)集合 i/j. i、j均為整數(shù)且j0R 實(shí)數(shù)集合 有理數(shù)、無理數(shù)C 復(fù)數(shù)集合 a+bi，a、b可為實(shí)數(shù) i= -1 6.1 集合的基本概念集合的基本概念(3)

3、集合的表示方法:(a)枚舉法 (列舉法) 把集合的元素列于花括號(hào)內(nèi)。 例： 命題的真假值組成的集合：S=T,F 自然數(shù)0,1,2,3,4五個(gè)元素的集合：P=0,1,2,3,4(b)謂詞公式描述法 所有集合均可用謂詞公式來表示：S=x | p(x) 6.1 集合的基本概念集合的基本概念例:大于10的整數(shù)的集合：S1=x | x I x10 偶整數(shù)集合：S2=x | y (y I x=2y) 有限個(gè)元素集合： S3=1,2,3,4,5=x | x I (1 x 5) S4=F,T=x | x=T x=F S5=1,4= x | (x-5x+4=0) (c)同一集合可以用多種不同的形式表示。(d)集

4、合也可作為某一集合的元素。 例：S=a,1,2,p,q 6.1 集合的基本概念集合的基本概念(4)三個(gè)特殊集合 全集：如果一個(gè)集合包含了所要討論的每一個(gè)集 合，則稱該集合為全集合，用E表示。 E=x | p(x) p(x) p(x)為任何謂詞公式 空集：不擁有任何元素的集合稱為空集（或稱零 集），用表示, =x | p(x) p(x) = 注意, 前者是空集，是沒有元素的集合； 后者是以作為元素的集合。6.1 集合的基本概念集合的基本概念 集合族：集合族：集合中的元素均為集合，稱這樣的集合為集合族。例A=a，b，c、d2、集合之間的關(guān)系、集合之間的關(guān)系 相等：相等：給定二個(gè)集合A和B，當(dāng)且僅當(dāng)

5、A和B具有同樣的元素（成員），則A和B相等，記作A=B, 并規(guī)定 ：（A=B）x (x A x B) 例：a, b, c=b, a, a, c, c 例：設(shè)P=1,2,4，Q=1,2,4，則PQ6.1 集合的基本概念集合的基本概念 包含包含：設(shè)A、B是任意二個(gè)集合，如果集合A的 每 一個(gè)元素都是B的一個(gè)元素，則稱A 是B的子集，或者說A包含于B，或者說B 包含A ，記作AB，或者BA。 并規(guī)定： ABBAx(x A x B) 例：A1=1,2,3 A2=0 A3=1,2,3,0 B=1,2,3,0 則A1、A2、A3均為B的子集合，并記為 A1B，A2B，A3B6.1 集合的基本概念集合的基本

6、概念集合的包含關(guān)系具有如下幾條性質(zhì)： （1）對(duì)任意集合）對(duì)任意集合A， ； （2）對(duì)任意集合）對(duì)任意集合A， ；（3）對(duì)任意集合）對(duì)任意集合A、B、C，若若 ， ，則，則 。 AAABACB CA6.1 集合的基本概念集合的基本概念真包含真包含:設(shè)A、B是任意二個(gè)集合，若AB且AB， 則稱 A是B的真子集，記作AB（A真包含 于B）,并規(guī)定：AB（AB AB） 注意區(qū)分“”和“”的關(guān)系： “”關(guān)系是指集合和該集合中元素間的關(guān)系 例：S=a,b,c 則a S，bS，c S 而“”關(guān)系是指二個(gè)集合之間的關(guān)系。 例：S1=a, b S2=a,b,1,2 則S1 S2 若A不包含于B，則也可表示成AB

7、6.1 集合的基本概念集合的基本概念 定理定理 設(shè)有空集和任一集合A，則A證明：設(shè)xA，要證明A，只要證：（x）(x xA)為“T”中沒有元素，x為假，（x）（x xA）為“T” 推論推論 是唯一的。證明：設(shè)有二個(gè)空集合1和2 是任何集合的子集（1 22 1） (1=2) 6.1 集合的基本概念集合的基本概念3、冪集 （1）子集： 例：S1=a 則子集為，a S2=1，2 則子集為，1，2，1，2 S3= 則子集有（而不是） 由此可見,給定一個(gè)集合S,則和S一定是S的子集 6.1 集合的基本概念集合的基本概念 冪集冪集:設(shè)A是集合，A的所有子集（作為元素）的集 合稱為A的冪集,記作(A)或2A

8、 ,且有： (A)(=2A)=x | x A 例： 若A1=，則(A1)= 若A2=a，則(A2)=，a 若A3=1，2,則(A3)=，1，2，1，2 6.2 集合的運(yùn)算集合的運(yùn)算1.交集（交運(yùn)算）交集（交運(yùn)算）交集交集:二個(gè)集合A和B的交集AB是由A和B所共有的 全部元素構(gòu)成的集合，即： AB=x | x A x B 例：A=a，b B=a，c AB=a 定理定理 集合的相交運(yùn)算是可交換的和可結(jié)合的，即 對(duì)于任何集合A，B，C有 AB=BA，（AB）C=A（BC）證明：設(shè)x是AB中任一元素 則x ABx x | x A x Bx x | x B x Ax BA AB=BA 6.2 集合的運(yùn)算

9、集合的運(yùn)算 定理定理 設(shè)A是E的任一子集，則有 （1）AA=A （2）A= （3）AE=A不相交不相交:A、B是二個(gè)集合，若AB=，則稱A和B 是不相交的，或者說A和B沒有相同的元素。 6.2 集合的運(yùn)算集合的運(yùn)算2.并集（并運(yùn)算）并集（并運(yùn)算） 定義定義 A、B是任意二個(gè)集合，A和B的并集AB是 由A和B的所有元素構(gòu)成的集合，即： AB=x xAxB。例：A=a, b, c B=1,2,3 則 AB=a,b,c,1,2,3 定理定理 集合的并運(yùn)算是可交換的和可結(jié)合的，即對(duì) 任何A，B，C,有 AB=BA和（AB）C=A（BC） 6.2 集合的運(yùn)算集合的運(yùn)算 定理定理 集合的并和交運(yùn)算，每一個(gè)

10、對(duì)另一個(gè)都是可 分配的。即： (1)A（BC）=（AB）（AC） (2)A（BC）=（AB）（AC） )()()()()()()()()(:CABAxCAxBAxCxAxBxAxCxBxAxCBxAxCBAx證明6.2 集合的運(yùn)算集合的運(yùn)算 定理定理 設(shè)A、B、C是全集E的任意子集，則有： (1)AA=A (2)A=A (3)AE=E6.2 集合的運(yùn)算集合的運(yùn)算3.相對(duì)補(bǔ)集：相對(duì)補(bǔ)集： 定義定義 設(shè)A和B是二個(gè)任意集合，B對(duì)A的相對(duì)補(bǔ) 集（A-B）是由A中且不屬于B的所有元素 組成的集合。即： A-B=xxAxB=xxAxB例：設(shè)A=0，1，2 B=2，3，4 則 A-B=0,1 B-A=3，

11、4注意，注意，A-BB-A。6.2 集合的運(yùn)算集合的運(yùn)算 定理定理 設(shè)A，B，C，D是E的子集，則有： (1 )A-BA， (2 )若AB和CD，則ACBD， (3 )若AB和CD，則AC BD， (4 ) 若AAB，則 BAB (5 ) 若ABA，則ABB (6 ) 若AB，則AB=B (7 ) 若AB，則AB=A (8 )A-=A (9 )A(B-A)= (10)A(B-A)=AB6.2 集合的運(yùn)算集合的運(yùn)算 (11)A-（BC）=（A-B）（A-C） (12)A-（BC）=（A-B）（A-C）() ()()()()()()()()()()xABCxAxBCxAxBCxAxBCxAxBxC

12、xAxBxCxAxBxAxCxABxACxABAC （12）6.2 集合的運(yùn)算集合的運(yùn)算4、絕對(duì)補(bǔ)集（補(bǔ)運(yùn)算、絕對(duì)補(bǔ)集（補(bǔ)運(yùn)算 ） 定義定義 設(shè)E是全集，任一集合A對(duì)E的相對(duì)補(bǔ)集稱 為A的絕對(duì)補(bǔ)集（或稱補(bǔ)集）記作A（或 A）。即： A=E-A=x| xExA=x| xA例：設(shè)E=a，b，c，d A=a，b 則A=c，d 6.2 集合的運(yùn)算集合的運(yùn)算 定理定理 A是E的任一子集，則有 (1)AA=E (2)AA= 定理定理設(shè)A、B是E的二個(gè)子集，當(dāng)且僅當(dāng) AB=E和AB=才有B= A（或A= B）證明： () 充分性：B= A （AB=E）（AB=）B=A AB=AA=E AB=AA=成立6.2

13、 集合的運(yùn)算集合的運(yùn)算 ()必要性： (AB=E)(AB=)B=A B=EB=(AA)B =(AB)(AB) =（AB） =（AA）（AB） =A（AB） =AE=A 6.2 集合的運(yùn)算集合的運(yùn)算補(bǔ)集的性質(zhì)：（1）（A）=A（2）（AB）=AB（3）（AB）=AB（4）=E（5）A-B=AB 例：設(shè)A=2，5，6，B=2，3，4，C=1，3，4， E=1，2，3，4，5，6則A-B=5，6=AB =2，5，61，5，6=5，66.2 集合的運(yùn)算集合的運(yùn)算5、對(duì)稱差、對(duì)稱差 定義定義 設(shè)A、B是任意二集合，A和B的對(duì)稱差記作 A B。即： A B=(A-B)(B-A)=(AB)(BA) 或者x(

14、A B)xx |xAxB 例：設(shè)A=2，5，6，B=2，3，4 則 AB=3，4，5，6 6.2 集合的運(yùn)算集合的運(yùn)算對(duì)稱差的性質(zhì)：(1)AB=BA (可交換)(2)(AB)C=A(BC) (可結(jié)合)(3)AB=(A-B)(B-A) =(AB)(BA)=(AB)(AB)(4)AA=(5)A=A(6)AB=(A(B)(B(A) =(AB)(BA)=(B-A)(A-B)=AB(7)A(BC)=(AB)(AC) (對(duì)可分配)6.2 集合的運(yùn)算集合的運(yùn)算 文氏圖可以用來描述集合間的關(guān)系及其運(yùn)算.在文氏圖中,全集用矩形表示,子集用圓形表示,陰影部分表示運(yùn)算結(jié)果的集合.6、文氏圖ABBABABAAB BA

15、B ABA 6.3 有窮集的計(jì)數(shù)有窮集的計(jì)數(shù)AB加法原理中，加法原理中，S1, S2 , , Sn兩兩不相交兩兩不相交，|S| = |S1| + |S2| + + |Sn|若取消兩兩不相交的限制，該如何計(jì)算？若取消兩兩不相交的限制，該如何計(jì)算？考慮兩個(gè)集合的情況考慮兩個(gè)集合的情況|AB| = |A| + |B| |AB|三個(gè)集合的情況三個(gè)集合的情況|A U B U C | = |A| + |B| + |C|AB|AC|BC| + |AB C |ABC6.3 有窮集的計(jì)數(shù)有窮集的計(jì)數(shù)v用數(shù)學(xué)歸納法證明 | S1S2Sn |對(duì)對(duì)n進(jìn)行歸納進(jìn)行歸納基礎(chǔ)步基礎(chǔ)步：n=1,2時(shí)，根據(jù)上面的驗(yàn)證，等式成立

16、時(shí)，根據(jù)上面的驗(yàn)證，等式成立；歸納步歸納步：假設(shè)：假設(shè)n=k (k1)時(shí)等式成立，則時(shí)等式成立，則n=k+1時(shí)時(shí)等式依然成立等式依然成立綜上，對(duì)任意自然數(shù)綜上，對(duì)任意自然數(shù)n 1，均有等式成立，均有等式成立 |.|1.|211111nnljnljiijnjiiniiSSSSSSSSS6.3 有窮集的計(jì)數(shù)有窮集的計(jì)數(shù)第七章第七章 二元關(guān)系二元關(guān)系7.1 有序?qū)εc笛卡爾積有序?qū)εc笛卡爾積7.2 二元關(guān)系二元關(guān)系7.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算7.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)7.5 關(guān)系的閉包關(guān)系的閉包7.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分7.7 偏序關(guān)系偏序關(guān)系 7.1 有序?qū)εc笛卡爾積有序?qū)εc笛卡爾積1.

17、序偶： 定義定義 由二個(gè)具有給定次序的客體所組成的序列稱 為序偶。記作x，y例：XY二維平面上點(diǎn)的坐標(biāo)x，y就是序偶。說明：在序偶中二個(gè)元素要有確定的排列次序。即： 若ab時(shí)，則a，bb，a 若x，y=a，b（x=ay=b）7.1 有序?qū)εc笛卡爾積有序?qū)εc笛卡爾積2.笛卡爾乘積 定義定義 設(shè)A，B為二個(gè)任意集合，若序偶的第一個(gè)成 員（左元素）是A的一個(gè)元素，序偶的第 二個(gè)成員（右元素）是B的一個(gè)元素，則所 有這樣的序偶的集合稱為A和B的笛卡爾乘積 記作：AB=x，y|（xA）（yB）例：設(shè)A=1，2 B=a，b 則AB=,2,b BA=, ABBA 即即“ ”是不滿足交換律。是不滿足交換律。7

18、.1 有序?qū)εc笛卡爾積有序?qū)εc笛卡爾積例：設(shè)A=a，b，B=1，2，C=z 則 (AB)C=,z =, A ( BC ) =a,b1,z,2,z =a,a,b,b, （AB）CA（BC）“ ”不滿足結(jié)合不滿足結(jié)合律律7.1 有序?qū)εc笛卡爾積有序?qū)εc笛卡爾積 性質(zhì)性質(zhì) 若A，B，C是三個(gè)集合，則有： (1)A（BC）=（AB）（AC） (2)A（BC）=（AB）（AC） (3)（AB）C=（AC）（BC） (4)（AB）C=（AC）（BC）7.1 有序?qū)εc笛卡爾積有序?qū)εc笛卡爾積證明：（2）設(shè)是A(BC)中的任一元素,則A（BC） x,y |xAyBC |xAyByC |(xAyB)(xAyC)

19、 (AB)(AC)即 A(BC)=(AB)(AC)7.1 有序?qū)εc笛卡爾積有序?qū)εc笛卡爾積例：設(shè)A=1，B=1，2，C=2，3 則A（BC） =11，2，3 =1，1，1，2，1，3 （AB）（AC）=11，212，3 =1，1，1，2，1，3 A（BC）=12=1，2 （AB）（AC） =1,1,1，21,2,1,3 =1，2 7.2 二元關(guān)系二元關(guān)系序偶a，b實(shí)際上反映了二個(gè)元素之間的關(guān)系，關(guān)系反映了事物的結(jié)構(gòu)。1.關(guān)系：指事物之間（客體之間）的相互聯(lián)系。日常生活中：父子關(guān)系，母子關(guān)系，兄弟關(guān)系等均為二個(gè)客體之間的關(guān)系。而祖孫關(guān)系是三個(gè)客體之間的關(guān)系（父子關(guān)系和父子關(guān)系的合成）。n元笛卡爾

20、積A1A2An是n元關(guān)系。 7.2 二元關(guān)系二元關(guān)系 定義 若若R AB,則R是一個(gè)二元關(guān)系。 即：序偶作為元素的 任何集合都是一個(gè)二元關(guān)系。關(guān)系表示方法關(guān)系表示方法（1）枚舉法（直觀法、列舉法）設(shè)R表示二元關(guān)系，用 xRy表示特定的序偶， 若 ，則也可寫成：x R y。,byAxyxBARyx ,Ryx ,7.2 二元關(guān)系二元關(guān)系例：二元關(guān)系定義如圖： 可寫成：由定義可見：關(guān)系是一個(gè)集合，定義集合的方法都可以來定義關(guān)系。（2）謂詞公式表示法前面講述，一個(gè)集合可用謂詞公式來表達(dá)，所以關(guān)系也可用謂詞公式來表達(dá)。, 4, 3, 2, 1dcbaR7.2 二元關(guān)系二元關(guān)系例：實(shí)數(shù)集合R上的“”關(guān)系可

21、表達(dá)為： 大于關(guān)系：“”= 父子關(guān)系：“F”=（3）關(guān)系矩陣表示法 規(guī)定：(a)二元關(guān)系中的序偶中左元素表示行，右元素表示列；(b)若xiRyi，則在對(duì)應(yīng)位置記上“1”，否則為“0”。)( |,yxRyRxyx|,的父親是yxyx7.2 二元關(guān)系二元關(guān)系例1：設(shè)并定義為列出關(guān)系矩陣：1 , 22 , 31 , 33 , 42 , 41 , 41R11101100100000001RM的關(guān)系是R,4 , 3 , 2 , 13.關(guān)系圖表示法關(guān)系圖表示法關(guān)系圖由結(jié)點(diǎn)和邊組成關(guān)系圖由結(jié)點(diǎn)和邊組成 例如，例如， 例例7 7中的中的 ， , ,AB8 , 4 , 3 , 2A7 , 5 , 1B7 , 4

22、,5 , 4,7 , 3,5 , 3,7 , 2,5 , 2則則 的關(guān)系圖如下的關(guān)系圖如下例如例如 的關(guān)系圖如下：的關(guān)系圖如下： 4 , 3 , 2 , 1A4 , 4,3 , 3,4 , 2,2 , 2,4 , 1,3 , 1,2 , 1,1 , 1，稱為全域關(guān)系。對(duì)任意集合定義AAAyxyxEA,|, A. 5稱為恒等關(guān)系。|,AxxxIA.,. 4簡(jiǎn)稱空關(guān)系）上二元空關(guān)系到（或?yàn)榭占xBAA二、特殊關(guān)系上的小于等于關(guān)系。稱為A,|,RAyxAyxyxLA上的整除關(guān)系整除BZByxByxyxDB,|,*上的包含關(guān)系為集合族，為AAyxAyxyxR,|.7.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算顯然有顯

23、然有 BRAD,domRA ranRB |(,)domRxyx yR |(,)ranRyxx yR 定義定義1：設(shè)：設(shè)R R是由是由A到到B的一個(gè)關(guān)系，的一個(gè)關(guān)系，R R的定的定義域或前域記作義域或前域記作domdomR R，R R的值域記作的值域記作ranranR R，分，分別定義為：別定義為：1定義域和值域定義域和值域 例3:設(shè)A=1,2,3,4,5,6,B=a,b,c,d,R=,求domR,ranR.解:domR=2,3,4,6ranR=a,b,d7.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算ABRRRRbaabBAR11, ,|,. 2且記作的逆關(guān)系稱為關(guān)系則設(shè)定義R=,R-1=,討論定義：（1）只要將

24、R中每一個(gè)序偶中的元素全部調(diào)換位置，就可得到R的逆關(guān)系 （2）關(guān)系矩陣為原始關(guān)系矩陣的轉(zhuǎn)置 （3）在R的關(guān)系圖中，只要把所有箭頭改換方向就可得到（自回路箭頭改變與否無關(guān)） 2逆關(guān)系逆關(guān)系 7.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算 定義定義3:設(shè)設(shè)R1是由是由A到到B的關(guān)系，的關(guān)系， R2是由是由B到到C的的關(guān)系，則關(guān)系，則R1和和R2的復(fù)合關(guān)系是一個(gè)由的復(fù)合關(guān)系是一個(gè)由A到到C 的關(guān)系，的關(guān)系，用用R1R2 表示，定義為：當(dāng)且僅當(dāng)存在元素表示，定義為：當(dāng)且僅當(dāng)存在元素b，使，使得得b C時(shí)，有時(shí)，有 aR1 R2c這種由這種由R1和和R2 求復(fù)合關(guān)系求復(fù)合關(guān)系R1R2的運(yùn)算稱為關(guān)系的復(fù)合運(yùn)算。的運(yùn)算稱為關(guān)

25、系的復(fù)合運(yùn)算。 由定義可知由定義可知:1212,RRa cba bRb cR3復(fù)合關(guān)系復(fù)合關(guān)系 7.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算于是復(fù)合關(guān)系于是復(fù)合關(guān)系 例例2 2 設(shè)設(shè) 是由是由 到到 的關(guān)的關(guān) 系。系。 是由是由 B B 到到 的關(guān)系。的關(guān)系。 分別定義為：分別定義為：12 , 4 , 3 , 2 , 1A4 , 3 , 2B6 , 5 , 3C2 , 4,3 , 3,4 , 26|,1baba6 , 3,3 , 3,6 , 2|,2cbcb整除6 , 4,6 , 3,3 , 3212. A=1，2，3，4，5，R，S是A上的二元關(guān)系R=，S=，5 , 2,2 , 3,5 , 1SR4 , 1,2 , 3,2 , 4RS2 , 3)(RSR2 , 3)(RSR合成關(guān)系不滿足交換律，滿足結(jié)合律。合成關(guān)系不滿足交換律，滿足結(jié)合律。7.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算關(guān)系是以序偶為元素的集合，故可對(duì)關(guān)系進(jìn)行集合的運(yùn)算以產(chǎn)生新的關(guān)系。作為關(guān)系，絕對(duì)補(bǔ)運(yùn)算是對(duì)全關(guān)系而言的。.,).5(;,).4(;)( ,)( ,).(3(;),().(2(;)( ,)().1 (,. 1111111111111111111domRranRranRdomRSRRSRSRSSRSRSRSRSRSRRRRRRRBASR則有的二元關(guān)系到是集