《離散數(shù)學(xué)》-教案

1、?離散數(shù)學(xué)?教案第一章 集合與關(guān)系集合是數(shù)學(xué)中最根本的概念， 又是數(shù)學(xué)各分支、 自然科學(xué)及社會(huì)科學(xué)各領(lǐng)域的最普 遍采用的描述工具。 集合論是離散數(shù)學(xué)的重要組成局部， 是現(xiàn)代數(shù)學(xué)中占有獨(dú)特地位的 一個(gè)分支。G. Cantor 康脫是作為數(shù)學(xué)分支的集合論的奠基人。 1870 年前后，他關(guān)于無(wú)窮序 列的研究導(dǎo)致集合論的系統(tǒng)開展。 1874 年他發(fā)表了關(guān)于實(shí)數(shù)集合不能與自然數(shù)集合建 立一一對(duì)應(yīng)的有名的證明。 1878 年，他引進(jìn)了兩個(gè)集合具有相等的“勢(shì)的概念。然 而，樸素集合論中包含著悖論。第一個(gè)悖論是布拉利- 福爾蒂的最大序數(shù)悖論。 1901年羅素發(fā)現(xiàn)了有名的羅素悖論。 1932 年康脫也發(fā)表了關(guān)于

2、最大基數(shù)的悖論。集合論的現(xiàn) 代公理化開始于 1908 年策梅羅所發(fā)表的一組公理，經(jīng)過弗蘭克爾的加工，這個(gè)系統(tǒng)稱 為策梅羅-弗蘭克爾集合論ZF，其中包括1904年策梅羅引入的選擇公理。另外一種 系統(tǒng)是馮諾伊曼-伯奈斯-哥德爾集合論。公理集合論中一個(gè)有名的猜測(cè)是連續(xù)統(tǒng)假設(shè)CH。哥德爾證明了連續(xù)統(tǒng)假設(shè)與策梅羅-弗蘭克爾集合論的相容性， 科恩證明了連續(xù)統(tǒng)假設(shè)與策梅羅 - 弗蘭克爾集合論的獨(dú)立性。 現(xiàn)在把策梅羅 -弗蘭克爾集合論與選擇公理 一起稱為ZFC系統(tǒng)。一、學(xué)習(xí)目的與要求本章目的是介紹集合的根本概念，講授集合運(yùn)算的根本理論，關(guān)系的定義與運(yùn)算。 通過本章的學(xué)習(xí)， 使學(xué)生了解集合是數(shù)學(xué)的根本語(yǔ)言， 掌

3、握主要的集合運(yùn)算方法和關(guān)系 運(yùn)算方法，為學(xué)習(xí)后續(xù)章節(jié)打下良好根底。二、知識(shí)點(diǎn)1 集合的根本概念與表示方法；2集合的運(yùn)算；3序偶與笛卡爾積；4關(guān)系及其表示、關(guān)系矩陣、關(guān)系圖； 5關(guān)系的性質(zhì)，符合關(guān)系、逆關(guān)系；6關(guān)系的閉包運(yùn)算；7集合的劃分與覆蓋、等價(jià)關(guān)系與等價(jià)類；相容關(guān)系；8序關(guān)系、偏序集、哈斯圖。三、要求1識(shí)記集合的層次關(guān)系、 集合與其元素間的關(guān)系， 自反關(guān)系、 對(duì)稱關(guān)系、 傳遞關(guān)系的識(shí)別， 復(fù)合關(guān)系、逆關(guān)系的識(shí)別。2領(lǐng)會(huì)領(lǐng)會(huì)以下概念： 兩個(gè)集合相等的概念幾證明方法， 關(guān)系的閉包運(yùn)算， 關(guān)系等價(jià)性證 明。1.1 集合論的根本概念與運(yùn)算1.1.1 集合的概念 集合不能精確定義。集合可以描述為：一

4、個(gè)集合把世間萬(wàn)物分成兩類 , 一些對(duì)象屬 于該集合，是組成這個(gè)集合的成員，另一些對(duì)象不屬于該集合。 可以說(shuō)，由于一個(gè)集合 的存在， 世上的對(duì)象可分成兩類， 任一對(duì)象或?qū)儆谠摷匣虿粚儆谠摷希?二者必居其 一也只居其一。直觀地說(shuō)， 把一些事物聚集到一起組成一個(gè)整體就叫 集合 ，而這些事物就是這個(gè)集 合的元素 或成員 。例如：方程X2 1 = 0的實(shí)數(shù)解集合；26個(gè)英文字母的集合；坐標(biāo)平面上所有點(diǎn)的 集合；集合通常用大寫的英文字母 A,B,C,來(lái)標(biāo)記，元素通常用小寫字母 a,b,c,來(lái) 表示。例如自然數(shù)集合 N(在離散數(shù)學(xué)中認(rèn)為 0也是自然數(shù))，整數(shù)集合Z,有理數(shù)集合 Q,實(shí)數(shù)集合R,復(fù)數(shù)集合C

5、等。集合的表示方法 ：表示一個(gè)集合的方法通常有三種： 列舉法、描述法 和歸納定義 法。(1) 列舉法 列出集合的所有元素， 元素之間用逗號(hào)隔開， 并把它們用花括號(hào)括起 來(lái)。在能清楚地表示集合成員的情況下可使用省略號(hào)。例如 A=a , b, c,，z, Z=0 ,± 1 ,± 2,都是合法的表示。(2) 描述法 用謂詞來(lái)概括集合中元素的屬性來(lái)表示這個(gè)集合。 例如 B = x|x RAX 1 = 0表示方程 X 1 = 0的實(shí)數(shù)解集。許多集合可以用兩種方法來(lái)表示，如B也可以寫成-1 , 1。但是有些集合不可以用列元素法表示 ,如實(shí)數(shù)集合。(3) 歸納定義法： 1.3 節(jié)再討論。

6、屬于、不屬于 ：元素和集合之間的關(guān)系是隸屬關(guān)系,即 屬于或不屬于 ,屬于記作 ,不屬于記作 。例如 A= a , b, c , d, d ,這里 a A, b , c A, d A, d A,但b A, d Ao b和d是A的元素的元素。外延公理：兩個(gè)集合A和B相等，當(dāng)且僅當(dāng)它們有相同的成員。 集合的元素是彼此不同的 ：如果同一個(gè)元素在集合中屢次出現(xiàn)應(yīng)該認(rèn)為是一個(gè)元 素。如 1 , 1, 2, 2, 3=1, 2, 3。集合的元素是無(wú)序的：如1 , 2, 3 = 3 , 1, 2。集合間的關(guān)系定義設(shè)A, B為集合，如果B中的每個(gè)元素都是 A中的元素，那么稱B是A的 子集合，簡(jiǎn)稱子集。這時(shí)也稱B

7、被A包含，或A包含B,記作B A。稱B是A的擴(kuò)集。包含的符號(hào)化表示為：B A x(x Bx A)。如果 B不被A包含，那么記作BAo例如N Z Q R C,但ZN。顯然對(duì)任何集合 A都有A Ao注意：屬于關(guān)系和包含關(guān)系都是兩個(gè)集合之間的關(guān)系，對(duì)于某些集合可以同時(shí)成立這兩種關(guān)系。例如 A= a , a和a，既有a A,又有a A。前者把它們看成是 不同層次上的兩個(gè)集合，后者把它們看成是同一層次上的兩個(gè)集合，都是正確的。定義1.1.2設(shè)A, B為集合，如果B A且BM A,那么稱B是A的真子集，記作B A。如果B不是A的真子集，那么記作B A。真子集的符號(hào)化表示為：B A B AA BmA。例如N

8、 Z Q R C,但NN。為方便起見，所討論的全部集合和元素是限于某一論述域中，即使這個(gè)論述域有時(shí)沒有明確地指出，但表示集合元素的變?cè)荒茉谠撚蛑腥≈怠４苏撌鲇虺Ｓ?U表示，并稱為全集。定義1.1.3不含任何元素的集合叫 空集，記作。空集可以符號(hào)化表示為=x|x M x。例如x|x RAx 2+仁0是方程x2+1=0的實(shí)數(shù)解集，因?yàn)樵摲匠虩o(wú)實(shí)數(shù)解， 所以是空 集。定理1.1-1空集是一切集合的子集。因前件為假而為真命題，所以A也為真。推論空集是唯一的。證：假設(shè)存在空集1和2，由定理6.1有12 , 21。根據(jù)集合相等證：對(duì)任何集合 A由子集定義有A x(xx A)，右邊的蘊(yùn)涵式的定義，有 集。

9、任給一個(gè)n元集，怎樣求出它的全部子集呢？舉例說(shuō)明如下。含有n個(gè)元素的集合簡(jiǎn)稱n元集，它的含有m(mc n)個(gè)元素的子集叫做它的m兀子例1.1.1 A =1,2,3，將A的子集分類：0元子集，也就是空集，只有一個(gè)：；1元子集，即單元集：1 , 2 , 3;2 元子集：1,2 , 1,3 , 2,3 ;3 元子集：1,2,3。一般地說(shuō)，對(duì)于n元集A,它的0元子集有C；個(gè)，1元子集有Q1個(gè)，m元子集有cm個(gè)，n元子集有c：個(gè)。子集總數(shù)為co cn | cn 2個(gè)。 全集與空集在本章中起重要作用，注意掌握它們的根本概念。注意：與 的聯(lián)系與區(qū)別。(1) 表示集合的元素可以為集合與集合本身的附屬關(guān)系，(2

10、) 表示兩個(gè)集合之間的包含關(guān)系。例如：對(duì)于集合 A=a,b,c,a是A的子集：a A, a是A的元素：a A。注意：不要寫成a A和a A。a a，但a a ； 是一元集，而不是空集。|1, | 0。集合的運(yùn)算集合的交、并和差運(yùn)算1. 集合交、并、差運(yùn)算的定義注意集合運(yùn)算與邏輯運(yùn)算的對(duì)應(yīng)關(guān)系定義設(shè)A和B是集合，(1) A和B的交記為A口 B，定義為：A|Bx|xAxB;(2) A和B的并記為aUb，定義為：aUbx|xAxB;(3) A和B的差記為A B，定義為：A Bx|xAxB。例：設(shè) A a,b,c,d , B b, c,e，那么AB b,c,人壯a(bǔ),b,c,d,e, A B a,d ,

11、 B A eC是兩兩不相交集定義：如果A,B是兩個(gè)集合， AB ，那么稱A和B是不相交的。如果C是 一個(gè)集合的族，且 C中的任意兩個(gè)不同元素都不相交，那么稱 合的族。2.集合的并和交運(yùn)算的推廣廣義交、廣義并n個(gè)集合A A A2 pEplAn x|xX An,A A A2U'-'UAn X|XAn,無(wú)窮可數(shù)個(gè)集合:S(SS x| S(S C x S)3.(1)集合交、并、差運(yùn)算的性質(zhì)：AplB 叩 A，Ap|B川C A|Bp|C，交換律結(jié)合律AbIJc) (Ap|B)J(Ap|C)冪等律同一律吸收律(8)A (Bp|c)(A(9) (a)(e)假設(shè)(h)假設(shè)AP"AU小

12、X S)aJbUc aUbLc.人加卞aUbBa|Jc，A A,A,aUAluU UL1人佃A，ApAAA，A律A(A B) A，A A,摩 根B)U(A C)A (B C)(A B)口 (A C)A, (b) A B A, (c) A AB, (d)D,那么(Ag (BUD)，(Ap|C)那么 B A, (g) 假設(shè) A B，那么 B B，B B AB 。B A,(BD),證：利用運(yùn)算的定義與邏輯運(yùn)算的關(guān)系或已證明的性質(zhì)。集合的補(bǔ)運(yùn)算1. 集合的補(bǔ)運(yùn)算的定義定義：設(shè)U是論述域而 A是U的子集，那么 A的絕對(duì)補(bǔ)為：A U A x|x U x A x|x AB A當(dāng)且僅當(dāng) 人口 B U和B 。2

13、. 集合補(bǔ)運(yùn)算的性質(zhì)：矛盾律 a|A ；排中律aA u ；(3) 德摩根律一 U , U ， ajb AnB，喬 AUB ；(4) 雙重否認(rèn)律A的補(bǔ)的補(bǔ)是 A： A A ； (5)假設(shè)A B，那么B A。例：證明 A- (B U C) = (A B) A ( A C)。證對(duì)任意的x,x A (B U C) x AA x BU C x AAn (x BV x C)x AA (n x BAq x C) x AA x BA x C(x AA x B) A (x AA x C) x A B) A x A Cx (A B) A (A C)所以 A (B U C) = (A B) A ( A C)。例：證

14、明AA E= Ao證 對(duì)任意的x, x AA Ex AA x E x A(因?yàn)閤 E是恒真命題)，所以AA E= Ao注意：以上證明的根本思想是：設(shè)P, Q為集合公式，欲證P= Q,即證P QA Q P為真。也就是要證對(duì)于任意的x有x P x Q和x Q x P成立。對(duì)于某些恒等式可以將這兩個(gè)方向的推理合到一起，就是x Px Qo不難看出，集合運(yùn)算的規(guī)律和命題演算的某些規(guī)律是一致的，所以命題演算的方法是證明集合恒等式的根本方法。證明集合恒等式的另一種方法是利用的恒等式來(lái)代入 。例：證明 AU (A n B) = A證 AU (A n B) = (A n E) U (A n B) = An (E

15、 U B) = An (B U E) = An E=Ao例：證明等式A- B= AnBo證 對(duì)于任意的 x, x A B x AA x B x AA x B x An B, 所以A B= AnBo注意：上式把相對(duì)補(bǔ)運(yùn)算轉(zhuǎn)換成交運(yùn)算，這在證明有關(guān)相對(duì)補(bǔ)的恒等式中是很有用的。例：證明(A B) U B= AU B證(A B) U B= (A n B) U B= (A U B) n (BU B) = (A U B) n E= AU Bo例：證明命題 AU B= BAn B= AA B=。證(1) 證AU B= B A B,對(duì)于任意的 x,x A x AV x B x AU B x B(因?yàn)?AU B

16、= B)，所以 A Bo(2) 證A B An B= A。顯然有 An B A,下面證 A An B,對(duì)于任意的 x,x A x AA x A x AA x B(因?yàn)?A B)x An B,由集合相等的定義有An B= Ao(3) 證 An B= A A B=oa b= An b= (A n B) n b(因?yàn)?An b= a) = An (b n b) = An=。(4) 證 A B=AU B= Bo AU B= BU (A B) = BU = B。注意：上式給出了 A B的另外三種等價(jià)的定義，這不僅為證明兩個(gè)集合之間的包 含關(guān)系提供了新方法，同時(shí)也可以用于集合公式的化簡(jiǎn)。例：化簡(jiǎn)(A U

17、BU C)n (A U B) (A U (B C) n A) o解 因?yàn)?AU B AU BU C, A AU (B C)，故有(A U BU C) n (A U B) (A U (B C) n A) = (A U B) A= B A定義：兩集合 代B的環(huán)和對(duì)稱差定義為：環(huán)和：A B (A B)J(B A) x|x A x B x A x B2. 環(huán)和與環(huán)積的性質(zhì)：(1) A B (AjB)p|(AUB) (4)B) (41B),ABA B，,BAAB ,(AB)CA (B C),CP|(AB)(C*) (Cp|B)；AAAA,ABA CB C例:AB= AC,證明B= Co證AB= AC,所

18、以有A(AB)=A (AC)(A A)B= (AA)CB=CB= CB= Co3. 集合運(yùn)算的文氏圖表示注意：如果沒有特殊說(shuō)明，任何兩個(gè)集合都畫成相交的。幕集合A。定義：設(shè)A是一個(gè)集合，A的幕集是A的所有子集的集合，即(A) B|B假設(shè)A是n元集，那么(A)有2n個(gè)元素。例：假設(shè)A，那么(A) ;假設(shè) A 1,2，那么(A),1,2,1,2。做如下，環(huán)積二類運(yùn)對(duì)任意集合 A:(A)，A (A)。集合運(yùn)算的順序：為了使得集合表達(dá)式更為簡(jiǎn)潔，我們對(duì)集合運(yùn)算的優(yōu)先順序規(guī)定：稱廣義交，廣義并，幕集，絕對(duì)補(bǔ)運(yùn)算為一類運(yùn)算，交，并，補(bǔ)，環(huán)和運(yùn)算為二類運(yùn)算。一類運(yùn)算優(yōu)先于二類運(yùn)算；一類運(yùn)算之間由右向左順序進(jìn)

19、行；算之間由括號(hào)決定先后順序。1.2關(guān)系及其表示集合的笛卡兒積與二元關(guān)系定義1 由兩個(gè)元素x和y允許x=y丨組成的序列記作<x,y>，稱為二重組或有 序?qū)蛐蚺迹渲衳是它的第一元素分量，y是它的第二元素分量。有序?qū)?lt;x,y>具有以下性質(zhì)：1.當(dāng) xm y 時(shí)，<x,y> 豐 <y,x> ; 2 . <x,y>=<u,v> 的充分必要條件是 x=u 且 y=v。注意：這些性質(zhì)是二元集x,y所不具備的。例如當(dāng) xm y時(shí)有x,y=y,x。原因 在于有序?qū)χ械脑厥怯行虻?，而集合中的元素是無(wú)序的。例 1 <x+2,4&g

20、t;=<5,2x+y>，求 x 和 y。解 由有序?qū)ο嗟鹊某湟獥l件有x+2=5, 2x+y=4，解得x=3 , y=-2。定義2設(shè)a,a2j|,an是n(n 2)個(gè)元素，定義a1, a2 J | |> an 1 , an知 a2 ,卅,an 1,an為n重組。注意：n重組是一個(gè)二重組，其中第一個(gè)分量是n 1重組。如 2,3,5 代表2,3 ,5 而不代表 2,3,5 ，按定義后者不是三重組，并且2,3 ,52, 3,5。n重組厲月2,|同1,an與d,b2,|,bn1,bn相等當(dāng)且僅當(dāng)aib ,1 i n。定義3 設(shè)A B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成有

21、序 對(duì)。所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積叉積，記作AX B。笛卡兒積的符號(hào)化表示為AX B=<x,y>|x AA y B。集合A,Aj|,A! n 2丨的叉積記為 A 入| A或j A，定義為A(A1 宀 | A.1)An例2 設(shè) A=a,b, B=0,1,2 ，那么Ax B=<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>Bx A=<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>。

22、由排列組合的知識(shí)不難證明，如果|A|=m , |B|=n，那么|A x B|=mn。笛卡兒積的運(yùn)算性質(zhì)(1) .對(duì)任意集合A,根據(jù)定義有A x =, x A=;(2) . 一般地說(shuō)，笛卡兒積運(yùn)算不滿足交換律，即Ax BM Bx A(當(dāng)AMAA A豐B時(shí))；(3) .笛卡兒積運(yùn)算不滿足結(jié)合律，即(A x B) x CM Ax (B x C)(當(dāng)AMA BmACM 時(shí) ) ；(4) . 笛卡兒積運(yùn)算對(duì)并和交運(yùn)算滿足分配律,即Ax (B U C)=(A x B) U (A x C) ； (B U C) x A=(Bx A) U (C x A);Ax (B n C)=(A x B) n (A x C)

23、 ； (B n C) x A=(Bx A) n (C x A)。 我們證明其中第一個(gè)等式。證 任取 <x,y> ,<x,y> Ax (B U C) x AA y BU C x AA (y BV y C)(x AA y B) V (x AA y C) <x,y> Ax BV <x,y> Ax C<x,y> (A xBU Ax C)所以有 Ax(BUC) = (A xB)U(AxC)。(5) A CA B DAx B Cx D性質(zhì) 5的證明和性質(zhì) 4 類似,也采用命題演算的方法。 注意：性質(zhì) 5的逆命題不成立,可分以下情況討論。(a) 當(dāng)

24、A=B= 時(shí)，顯然有 A C和B D成立。(b) 當(dāng)AM 且B#時(shí)，也有 A C和B D成立。證明如下：任取 x A,由于Bm ,必存在 y B,因此有 x AA y B <x,y> Ax B <x,y> Cx D x CA y D x C,從而證明了 A C。同理可證 B Db(c) 當(dāng)A=而BM時(shí)，有AC成立，但不一定有BD成立。反例：令 A= , B=1, C=3 , D=4。(d) 當(dāng)AM 而B=時(shí)，有BD成立，但不一定有AC成立。反例類似于(c)。例 3 設(shè) A=1,2,求 P(A) X Ao解 P(A) X A=,1,2,1,2 X 1,2=< ,1&

25、gt;,< ,2>,<1,1>,<1,2>,<2,1>,<2,2>,<1,2,1>,<1,2,2>例4設(shè)A, B, C, D為任意集合，判斷以下命題是否為真，并說(shuō)明理由。(1) A X B=AX CB=C (2) A-(B X C)=(A-B) X (A-C);(3) A=B A C=D AX C=BX D (4) 存在集合 A,使得 A AX Ao解(1)不一定為真。當(dāng) A= , B=1,C=2時(shí)，有 AX B= =AX C,但 B G(2) 不一定為真。當(dāng) A=B=1,C=2時(shí)有 A-(B X C)=1 -

26、 <1,2>=1,(A-B) X (A-C)= X 1=(3) 為真。由等量代入的原理可證。(4) 為真。當(dāng)A= 時(shí)有A AX A成立。定理 1: 假設(shè) A(i 1,2,|,n)都是有限集合，那么IA A2 III Ad |Al|A2|ui|An|o定義4如果一個(gè)集合滿足以下條件之一：1集合非空，且它的元素都是有序?qū)Γ?集合是空集；那么稱該集合為一個(gè)二元關(guān)系，記作R。二元關(guān)系也可簡(jiǎn)稱為 關(guān)系。對(duì)于二元關(guān)系 R，假設(shè) x,y R，那么稱x,y有關(guān)系R，可記作xRy ；假設(shè)x, y R，那么記作xRy。一般地 x, yy,x ，因此 xRy yRx。 1,2a,b , R2 1,2R2

27、不是元關(guān)系，只是一個(gè)集合，除非將a和b定義為有序?qū)?。根?jù)以上記法可以寫成1R12 , aRb 等o定義5設(shè)A,B為集合，A B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系，特別地，當(dāng)A B時(shí)，那么叫做A上的二元關(guān)系。A A |代的子集稱為 A A III An上的一個(gè)n元關(guān)系，當(dāng)A A III An時(shí)稱為A上的一個(gè)n元關(guān)系。例 2 A 0,1, B 1,2,3，那么 R 0,2 , R2A B, R3R4 0,1 等都是從A到B的二元關(guān)系，而其中 民和R4同時(shí)也是A上的二元關(guān) 系。注：可把A到B的二元關(guān)系看成是aUb上的二元關(guān)系或AB2上的二元關(guān)系。元關(guān)系的數(shù)目：集合A上的二元關(guān)系的數(shù)目依

28、賴于 A中的元素?cái)?shù)。如果|A| n ,2那么|A A| n2，A A的子集就有2n個(gè)。每一個(gè)子集代表一個(gè) A上的二元關(guān)系，所 2o2以A上有2n個(gè)不同的二元關(guān)系。例如|A| 3，那么A上有23512個(gè)不同的二元關(guān)系。如果IA丨m，那么IAA2IIIAn Imm2川m.,因此A A |An上有2m1ml|mn個(gè)不同的n元關(guān)系。一些重要關(guān)系：(1)空關(guān)系：假設(shè)R，那么R稱為空關(guān)系；(2)全域關(guān)系：EA x,y 1| x A y BA B(3)恒等關(guān)系：A上的二元關(guān)系I a x,x |x A稱為恒等關(guān)系。小于或等于關(guān)系：Lax, y | x, y Ax y，這里A R ；(5)B上的整除關(guān)系：Dbx

29、, y |x, y Bx整除y，這里A Z 非零整數(shù)集；(6)A上的包含關(guān)系：Rx, y |x,y Ax y,這里A是集合族。例3設(shè) A 1,2,3，Ba,b，C(B) ,a, b, a,b，貝VLa 1,1 ,1,2 ,1,3 , 2,2 ,2,3 ,3,3 ,Da 1,1J1,2,1,3 , 2,2,2,3C上的包含關(guān)系:R ,a ,b ,a,b , a,aa, a,b , b, b , b, a,b , a,b, a,b 。類似的還可以定義 大于等于關(guān)系，小于關(guān)系，大于關(guān)系，真包含關(guān)系等等。關(guān)系是有序?qū)Φ募?，因此?duì)它可進(jìn)行集合運(yùn)算，運(yùn)算結(jié)果定義一個(gè)新的關(guān)系。例 如：設(shè)R和S是給定集合上

30、的關(guān)系， 那么RS，RS，R S，R分別稱為關(guān)系R與 S的并關(guān)系，交關(guān)系，差關(guān)系和R的補(bǔ)關(guān)系。這樣一來(lái)，可以從關(guān)系派生出各種 新關(guān)系。¥ 方-丿元關(guān)系A(chǔ)到B的二元關(guān)系可以用一個(gè)圖來(lái)形象地表示。定義6設(shè)R是A到B的一個(gè)二元關(guān)系，那么A叫著關(guān)系R的前域，B叫著關(guān)系R的陪域；D(R) x| y( x, yR)稱為關(guān)系R的定義域；R(R) y| x( x,yR)稱為關(guān)系R的值域。關(guān)于關(guān)系的定義域、值域的一些性質(zhì)：D(R(Js)D(R)Ud(S) ； D(R|S) D(R)p)D(S);R(rUs)R(R)IJr(S) ； D(Rp|S) R(R)f|R(S)。證明證明第一個(gè)式子，其余類似x

31、D(rUs)y(x(S)y) y(xRy xSy) y(xRy) y(xSy)x D(R) x D(S) x D(R)Jd(S)關(guān)系矩陣與關(guān)系圖(1) 集合表示法：非空關(guān)系都是元素為有序?qū)Φ募稀?2) 關(guān)系圖：設(shè)A x1,x2J|(,xn , R是A上的關(guān)系，令圖G V,E ，其中頂點(diǎn)集合V A，邊集為E，對(duì)于 x , xj V，滿足 xi, xjExi Rxj，那么稱圖G為R的關(guān)系圖，記作Gr。關(guān)系矩陣：設(shè)A 為必,卅Xn, R是A上的關(guān)系，令用1 xi RXj0 xi Rxj那么(rj)ri1ri2r21r22rnirn 2j即稱為關(guān)系R的關(guān)系矩陣，記作MrIK rn(i, j 12川,

32、n)例 空關(guān)系的關(guān)系矩陣為全 0矩陣：Ma 0 ;全域關(guān)系的關(guān)系矩陣為全1矩陣,記為J ；相等關(guān)系的關(guān)系矩陣為單位矩陣：M I。1 A基于關(guān)系R與關(guān)系矩陣Mr互相唯一決定的特性，可用關(guān)系矩陣有效地刻畫關(guān)系的許 多性質(zhì)。如對(duì)于有限集 A上的任意關(guān)系R與S : R S Mr Ms ；RS M R Ms。1.3關(guān)系的運(yùn)算關(guān)系的逆定義1設(shè)R是從A到B的二元關(guān)系，關(guān)系 R的逆R的逆關(guān)系記為 R，定義 如下：R x,y | x,y R當(dāng)A上的關(guān)系R具有對(duì)稱性時(shí)，R R。相等關(guān)系的逆是相等關(guān)系；空關(guān)系的逆是空關(guān)系；全域關(guān)系的逆是全域關(guān)系。列舉法：把R中每個(gè)有序?qū)Φ牡谝缓偷诙煞侄技右越粨Q，就可得到逆關(guān)系R的

33、所有元素。對(duì)x A和y B來(lái)說(shuō)，這意味著xRy yRx。關(guān)系矩陣：將Mr的行和列交換即可得到 Mr，即Mr MR M R表示Mr的轉(zhuǎn) 置。關(guān)系圖：顛倒R的關(guān)系圖中的每條弧有向邊的箭頭，就得到R的關(guān)系圖。逆關(guān)系的性質(zhì)：(1) 設(shè)R, R,R2都是從A到B的二元關(guān)系，那么(R) R； (b) R0R2 R1UR2 ； (c) R1 舟R2 RflR?； (d) r 押 R R ；(e) R R, R A B R；(f) RR2R R2 ；(2) 設(shè)R是從A到B的關(guān)系，R2是從B到C的關(guān)系，那么(吋&) R2 R。關(guān)系的合成定義2設(shè)R是從A到B的關(guān)系，R2是從B到C的關(guān)系，那么 R與R2的合

34、成右復(fù)合為從A到C的關(guān)系，記為R1R2 或 R|R2其中表示合成運(yùn)算，定義為RR2 a,c |a A cC b(bBa,b R b,cR2)。例 1 設(shè) A 1,2,3,4 , B2,3,4,C1,2,3 , R是從A到B的關(guān)系，R,是從B到C的關(guān)系：R x,y |x y 6 2,4 ,3,3,4,2 ,R y,z |y z 1 2,1 , 3,2,4,3 。分別用列舉法、圖示法、關(guān)系矩陣表示關(guān)系的合成。例2設(shè)A 1,2,3,4,5 , R和R2都是A上的二元關(guān)系，如果R1,2, 3,4, 2,2，R24,2, 2,5 , 3,1,1,3 ，分別用列舉法、圖示法、關(guān)系矩陣表示關(guān)系的合成RR,，

35、R,R，(RR2)R,，Ri (R2 R)， Ri R ， R2 R2 等。合成關(guān)系的性質(zhì)：(1) 設(shè)R是從A到B的關(guān)系，|人，冷分別是代B上的相等關(guān)系，貝UIa R R Ib R；(2) 如果關(guān)系R的值域與R的定義域的交集為空集，那么合成關(guān)系R R2是空關(guān)系；(3) 關(guān)系的合成關(guān)于交和并的分配律：設(shè)Ri是從A到B的關(guān)系，R2,Rj是從B到C的關(guān)系，R4是從C到D的關(guān)系，那么(a)尺侃慶)(RR2)L(RiR3)，(b) R(Rp|R3)(RR2)n(RR；(C) (RR3)R4 (陰川(詠)，(d)(訓(xùn)民)艮 (師川侃尺)；(4) 關(guān)系的合成滿足結(jié)合律：設(shè)RbRR分別是從A到B , B到C

36、, C到D的關(guān)系，那么(RiR2)R3 Ri(R2&)。1.3.3 關(guān)系的幕定義3設(shè)R是集合A上的二元關(guān)系，n N為任一自然數(shù)，那么R的n次幕記為Rn ,定義為：(1) R0為A上的相等關(guān)系，R0 x,x| x ARn 1Rn R。關(guān)系的幕運(yùn)算的性質(zhì)：(1)對(duì)A上的任意關(guān)系尺，&有：R0瑁Ia，R1R0r iA R1R ；(2)設(shè)R是集合A上的二元關(guān)系，m,n N ,那么 Rm RnRm n，(Rm)n Rmn ；(3)設(shè)| A| n , R是集合A上的一個(gè)二元關(guān)系，那么存在 i和j，02i j 2n 使Ri Rj ；(4) 循環(huán)性質(zhì)：設(shè)R是集合A上的二元關(guān)系，假設(shè)存在i和j，

37、i j，使RiRj，那么(a)對(duì)所有 k 0，Ri k Rj k ； (b)對(duì)所有 k,m 0，Ri mdk Ri k其中 d j i；(c)令S R°,R1,R2,|,Rj 1，那么R的每一次幕是S的元素，即對(duì) n N , Rn S。關(guān)系的幕的計(jì)算：給定A上的關(guān)系R和自然數(shù)n，怎樣計(jì)算Rn呢？假設(shè)n是0或1，結(jié)果是很簡(jiǎn)單 的。F面考慮n 2的情況。如果R是用集合表達(dá)式 給出的，可以通過 n 1次合成計(jì)算得到 Rn。如果R是用關(guān)系矩陣M給出的，貝V Rn的關(guān)系矩陣是M n，即n個(gè)矩陣M之積。與普通矩陣乘法不同的是，其中的相加是邏輯加，即1 1 1,1 0 0 1 1,0 0 0。如果

38、R是用關(guān)系圖G給出的，可以直接由圖G得到Rn的關(guān)系圖G。G的頂點(diǎn)集 與G相同?？疾霨的每個(gè)頂點(diǎn)xi，如果在G中從x出發(fā)經(jīng)過n步長(zhǎng)的路徑到達(dá)頂點(diǎn)Xj,那么在G中加一條從x到Xj的邊。當(dāng)把所有這樣的邊都找到以后，就得到圖G。例 3 設(shè) A a,b,c,d , R a,bb, a , b,c , c,d ，求 R 的各次幕，分別用矩陣和關(guān)系圖表示。1010234，那么r2,r3,r4的關(guān)系矩陣分別是000100000 10 0解R的關(guān)系矩陣為M101001010101 3 21010,M3M2M0000000000000000M2 MM10 10M4 M3M0 10 10 0 0 00 0 0 0因

39、此M4 M 2, R5R3, -。所以可以得到R2R4R6| ,R5R7III，而 R0，即Ia的關(guān)系矩陣為M10000100 宀。至此，R各001000 0 0 1次幕的關(guān)系矩陣都得到了。合成關(guān)系的矩陣表達(dá)用關(guān)系圖的方法得到R0,R1, R2, R3,|的關(guān)系圖如以下列圖所示。二兀集T,F1,0上的布爾運(yùn)算：1 00 1 1 1 1 ,TFF T TT T , F FF ;000 ；TFF TFFF , T TT ;1 00 1 0 0 0,111；?TF ,?F T ;?1 0, ?0 1 ；配合的其他性質(zhì)結(jié)合律、分配律等可計(jì)算更復(fù)雜的式子。注0,1關(guān)于上述兩個(gè)運(yùn)算構(gòu)成二元數(shù)域。Sjmn，

40、定義以下運(yùn)算:0,1-矩陣的布爾運(yùn)算:對(duì)于 m n 的(0,1)矩陣 M r(rij )mn，Ms?Mr(?ij )mn , M r M s(CjSj )mn , M RMs (rjSj)對(duì)mn和n p的0,1矩陣M R(rij ) mn 和 M S(rij ) np :M r M sn(k 1(rikskj ) mp。例4對(duì)全0矩陣0，全1矩陣J有零律：0 M M 0 0 , J M M JJ ；同一律：0 M M , J M M。用關(guān)系矩陣的布爾運(yùn)算研究關(guān)系的運(yùn)算：定理 1.3-1 :設(shè) X X!,X2,川,Xm，丫 ywf, Z 乙厶,川已 , R是X到Y(jié)的關(guān)系，Mr (ajj)mn是m n矩陣，S是Y到Z的關(guān)系，MS (bj )np是n p矩陣，那么 Mrs (Cj) Mr Ms,這里 qnk 1(aikbkj) , i 1,2,|, m ,j 1,2j(|,p。設(shè)R,S是X到Y(jié)的關(guān)系，Mr (a0),系矩陣的元素，那么M rsMrMs ,GjM rJsMrMs ,CjM