《離散數(shù)學(xué)》 教案.doc
《《離散數(shù)學(xué)》 教案.doc》由會員分享,可在線閱讀,更多相關(guān)《《離散數(shù)學(xué)》 教案.doc(25頁珍藏版)》請在裝配圖網(wǎng)上搜索。
_離散數(shù)學(xué)教案第一章 集合與關(guān)系集合是數(shù)學(xué)中最基本的概念,又是數(shù)學(xué)各分支、自然科學(xué)及社會科學(xué)各領(lǐng)域的最普遍采用的描述工具。集合論是離散數(shù)學(xué)的重要組成部分,是現(xiàn)代數(shù)學(xué)中占有獨特地位的一個分支。G. Cantor(康脫)是作為數(shù)學(xué)分支的集合論的奠基人。1870年前后,他關(guān)于無窮序列的研究導(dǎo)致集合論的系統(tǒng)發(fā)展。1874年他發(fā)表了關(guān)于實數(shù)集合不能與自然數(shù)集合建立一一對應(yīng)的有名的證明。1878年,他引進(jìn)了兩個集合具有相等的“勢”的概念。然而,樸素集合論中包含著悖論。第一個悖論是布拉利-福爾蒂的最大序數(shù)悖論。1901年羅素發(fā)現(xiàn)了有名的羅素悖論。1932年康脫也發(fā)表了關(guān)于最大基數(shù)的悖論。集合論的現(xiàn)代公理化開始于1908年策梅羅所發(fā)表的一組公理,經(jīng)過弗蘭克爾的加工,這個系統(tǒng)稱為策梅羅-弗蘭克爾集合論(ZF),其中包括1904年策梅羅引入的選擇公理。另外一種系統(tǒng)是馮諾伊曼-伯奈斯-哥德爾集合論。公理集合論中一個有名的猜想是連續(xù)統(tǒng)假設(shè)(CH)。哥德爾證明了連續(xù)統(tǒng)假設(shè)與策梅羅-弗蘭克爾集合論的相容性,科恩證明了連續(xù)統(tǒng)假設(shè)與策梅羅-弗蘭克爾集合論的獨立性。現(xiàn)在把策梅羅-弗蘭克爾集合論與選擇公理一起稱為ZFC系統(tǒng)。一、學(xué)習(xí)目的與要求本章目的是介紹集合的基本概念,講授集合運算的基本理論,關(guān)系的定義與運算。通過本章的學(xué)習(xí),使學(xué)生了解集合是數(shù)學(xué)的基本語言,掌握主要的集合運算方法和關(guān)系運算方法,為學(xué)習(xí)后續(xù)章節(jié)打下良好基礎(chǔ)。二、知識點1集合的基本概念與表示方法;2集合的運算;3序偶與笛卡爾積;4關(guān)系及其表示、關(guān)系矩陣、關(guān)系圖;5關(guān)系的性質(zhì),符合關(guān)系、逆關(guān)系;6關(guān)系的閉包運算;7集合的劃分與覆蓋、等價 關(guān)系與等價類;相容關(guān)系;8序關(guān)系、偏序集、哈斯圖。三、要求1識記集合的層次關(guān)系、集合與其元素間的關(guān)系,自反關(guān)系、對稱關(guān)系、傳遞關(guān)系的識別,復(fù)合關(guān)系、逆關(guān)系的識別。2領(lǐng)會領(lǐng)會下列概念:兩個集合相等的概念幾證明方法,關(guān)系的閉包運算,關(guān)系等價性證明。1.1 集合論的基本概念與運算1.1.1 集合的概念集合不能精確定義。集合可以描述為:一個集合把世間萬物分成兩類,一些對象屬于該集合,是組成這個集合的成員,另一些對象不屬于該集合??梢哉f,由于一個集合的存在,世上的對象可分成兩類,任一對象或?qū)儆谠摷匣虿粚儆谠摷?,二者必居其一也只居其一。直觀地說,把一些事物匯集到一起組成一個整體就叫集合,而這些事物就是這個集合的元素或成員。例如:方程x210的實數(shù)解集合;26個英文字母的集合;坐標(biāo)平面上所有點的集合;集合通常用大寫的英文字母A,B,C,來標(biāo)記,元素通常用小寫字母a,b,c,來表示。例如自然數(shù)集合N(在離散數(shù)學(xué)中認(rèn)為0也是自然數(shù)),整數(shù)集合Z,有理數(shù)集合Q,實數(shù)集合R,復(fù)數(shù)集合C等。集合的表示方法:表示一個集合的方法通常有三種:列舉法、描述法和歸納定義法。(1) 列舉法 列出集合的所有元素,元素之間用逗號隔開,并把它們用花括號括起來。在能清楚地表示集合成員的情況下可使用省略號。例如 A=a,b,c,z,Z=0,1,2,都是合法的表示。(2) 描述法 用謂詞來概括集合中元素的屬性來表示這個集合。例如 Bx|xRx210表示方程x210的實數(shù)解集。許多集合可以用兩種方法來表示,如B也可以寫成-1,1。但是有些集合不可以用列元素法表示,如實數(shù)集合。(3) 歸納定義法:1.3節(jié)再討論。屬于、不屬于:元素和集合之間的關(guān)系是隸屬關(guān)系,即屬于或不屬于,屬于記作,不屬于記作。例如Aa,b,c,d,d,這里aA,b,cA,dA,dA,但bA,dA。b和d是A的元素的元素。外延公理:兩個集合A和B相等,當(dāng)且僅當(dāng)它們有相同的成員。集合的元素是彼此不同的:如果同一個元素在集合中多次出現(xiàn)應(yīng)該認(rèn)為是一個元素。如 1,1,2,2,31,2,3。集合的元素是無序的:如1,2,33,1,2。1.1.2 集合間的關(guān)系定義1.1.1 設(shè)A,B為集合,如果B中的每個元素都是A中的元素,則稱B是A的子集合,簡稱子集。這時也稱B被A包含,或A包含B,記作BA。稱B是A的擴(kuò)集。包含的符號化表示為:BAx(xBxA)。如果B不被A包含,則記作BA。例如 NZQRC,但ZN。顯然對任何集合A都有AA。注意:屬于關(guān)系和包含關(guān)系都是兩個集合之間的關(guān)系,對于某些集合可以同時成立這兩種關(guān)系。例如Aa,a和a,既有aA,又有aA。前者把它們看成是不同層次上的兩個集合,后者把它們看成是同一層次上的兩個集合,都是正確的。定義1.1.2 設(shè)A,B為集合,如果BA且BA,則稱B是A的真子集,記作BA。如果B不是A的真子集,則記作BA。真子集的符號化表示為:BABABA。例如 NZQRC,但NN。為方便起見,所討論的全部集合和元素是限于某一論述域中,即使這個論述域有時沒有明確地指出,但表示集合元素的變元只能在該域中取值。此論述域常用U表示,并稱為全集。定義1.1.3 不含任何元素的集合叫空集,記作??占梢苑柣硎緸閤|xx。例如x|xRx2+1=0是方程x2+1=0的實數(shù)解集,因為該方程無實數(shù)解,所以是空集。定理1.1-1 空集是一切集合的子集。證:對任何集合A,由子集定義有,右邊的蘊涵式因前件為假而為真命題,所以也為真。推論 空集是唯一的。證:假設(shè)存在空集和,由定理6.1有,。根據(jù)集合相等的定義,有。含有n個元素的集合簡稱n元集,它的含有m(mn)個元素的子集叫做它的m元子集。任給一個n元集,怎樣求出它的全部子集呢?舉例說明如下。例1.1.1 A1,2,3,將A的子集分類:0元子集,也就是空集,只有一個:;1元子集,即單元集:1,2,3;2元子集:1,2,1,3,2,3; 3元子集:1,2,3。一般地說,對于n元集A,它的0元子集有個,1元子集有個,m元子集有個,n元子集有個。子集總數(shù)為個。全集與空集在本章中起重要作用,注意掌握它們的基本概念。注意:與的聯(lián)系與區(qū)別。(1) 表示集合的元素(可以為集合)與集合本身的從屬關(guān)系,(2) 表示兩個集合之間的包含關(guān)系。例如:對于集合A=a,b,c,a是A的子集:aA,a是A的元素:aA。注意:不要寫成aA和aA。,但;是一元集,而不是空集。,。1.1.3 集合的運算集合的交、并和差運算1. 集合交、并、差運算的定義(注意集合運算與邏輯運算的對應(yīng)關(guān)系)定義 設(shè)和是集合,(1) 和的交記為,定義為:;(2) 和的并記為,定義為:;(3) 和的差記為,定義為:。例:設(shè),則,定義:如果是兩個集合,那么稱和是不相交的。如果是一個集合的族,且中的任意兩個不同元素都不相交,那么稱是(兩兩)不相交集合的族。2. 集合的并和交運算的推廣(廣義交、廣義并)個集合 ,無窮可數(shù)個集合: ,一般情形: (),3. 集合交、并、差運算的性質(zhì):(1) 交換律 , ,(2) 結(jié)合律 , .(3) 分配律 , (4) 冪等律 , ,(5) 同一律 , ,(6) 零 律 ,(7) 吸收律 , ,(8) 德摩根律 (9) (a) , (b) , (c), (d),(e) 若,,則,,(f) 若,則, (g) 若,則,(h) 。證:利用運算的定義(與邏輯運算的關(guān)系)或已證明的性質(zhì)。 集合的補運算1. 集合的補運算的定義定義:設(shè)是論述域而是的子集,則的(絕對)補為:當(dāng)且僅當(dāng)和。2. 集合補運算的性質(zhì):(1) 矛盾律 ; (2) 排中律 ;(3) 德摩根律 , , , ;(4) 雙重否定律(的補的補是):;(5) 若,則。例:證明A(BC)(AB)( AC)。證對任意的x,xA(BC) xAxBC xA(xBxC) xA(xBxC) xAxBxC (xAxB)(xAxC) xAB)xAC x(AB)(AC)所以 A(BC)(AB)( AC)。例:證明AEA。證對任意的x,xAExAxExA(因為xE是恒真命題),所以AEA。注意:以上證明的基本思想是:設(shè)P,Q為集合公式,欲證PQ,即證PQQP為真。也就是要證對于任意的x有 xPxQ和xQxP成立。對于某些恒等式可以將這兩個方向的推理合到一起,就是 xPxQ。不難看出,集合運算的規(guī)律和命題演算的某些規(guī)律是一致的,所以命題演算的方法是證明集合恒等式的基本方法。證明集合恒等式的另一種方法是利用已知的恒等式來代入。例:證明A(AB)A。證 A(AB)(AE)(AB)A(EB)A(BE)AEA。例:證明等式ABAB。證對于任意的x,xABxAxBxAxBxAB,所以ABAB。注意:上式把相對補運算轉(zhuǎn)換成交運算,這在證明有關(guān)相對補的恒等式中是很有用的。例:證明(AB)BAB證 (AB)B(AB)B(AB)(BB)(AB)EAB。例:證明命題ABBABAAB。證(1) 證ABBAB,對于任意的x,xAxAxBxABxB(因為ABB),所以AB。(2) 證ABABA。顯然有ABA,下面證AAB,對于任意的x,xAxAxAxAxB(因為AB) xAB,由集合相等的定義有ABA。(3) 證ABAAB。ABAB(AB)B(因為ABA)A(BB)A。(4) 證ABABB。ABB(AB)BB。注意:上式給出了AB的另外三種等價的定義,這不僅為證明兩個集合之間的包含關(guān)系提供了新方法,同時也可以用于集合公式的化簡。例:化簡(ABC)(AB)(A(BC)A)。解因為ABABC,AA(BC),故有(ABC)(AB)(A(BC)A)(AB)ABA。定義:兩集合的環(huán)和(對稱差)定義為:環(huán)和: 2. 環(huán)和與環(huán)積的性質(zhì):(1) ,(2) , , (3) , ;(4) , ,(5) 例:已知ABAC,證明BC。證 已知ABAC,所以有A(AB)A(AC) (AA)B(AA)CBCBCBC。3. 集合運算的文氏圖表示注意:如果沒有特殊說明,任何兩個集合都畫成相交的。 冪集合定義:設(shè)是一個集合,的冪集是的所有子集的集合,即。若是元集,則有個元素。例:若,則;若,則。對任意集合:,。集合運算的順序:為了使得集合表達(dá)式更為簡潔,我們對集合運算的優(yōu)先順序做如下規(guī)定:稱廣義交,廣義并,冪集,絕對補運算為一類運算,交,并,補,環(huán)和,環(huán)積運算為二類運算。一類運算優(yōu)先于二類運算;一類運算之間由右向左順序進(jìn)行;二類運算之間由括號決定先后順序。1.2 關(guān)系及其表示1.2.1集合的笛卡兒積與二元關(guān)系定義 1 由兩個元素x和y(允許x=y)組成的序列記作,稱為二重組或有序?qū)蛐蚺迹渲衳是它的第一元素(分量),y是它的第二元素(分量)。有序?qū)哂幸韵滦再|(zhì):1當(dāng)xy時,; 2=的充分必要條件是x=u且y=v。注意:這些性質(zhì)是二元集x,y所不具備的。例如當(dāng)xy時有x,y=y,x。原因在于有序?qū)χ械脑厥怯行虻?,而集合中的元素是無序的。例1 已知=,求x和y。解 由有序?qū)ο嗟鹊某湟獥l件有x+2=5,2x+y=4,解得x=3,y=-2。定義2 設(shè)是個元素,定義為重組。注意:重組是一個二重組,其中第一個分量是重組。如代表而不代表,按定義后者不是三重組,并且。重組與相等當(dāng)且僅當(dāng),。定義3 設(shè)A,B為集合,用A中元素為第一元素,B中元素為第二元素構(gòu)成有序?qū)?。所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積(叉積),記作AB。笛卡兒積的符號化表示為AB=|xAyB。集合()的叉積記為或,定義為例2 設(shè)A=a,b, B=0,1,2,則AB=,;BA=,。由排列組合的知識不難證明,如果|A|=m,|B|=n,則|AB|=mn。笛卡兒積的運算性質(zhì)(1).對任意集合A,根據(jù)定義有 A=, A=;(2).一般地說,笛卡兒積運算不滿足交換律,即ABBA(當(dāng)ABAB時);(3)笛卡兒積運算不滿足結(jié)合律,即(AB)CA(BC)(當(dāng)ABC時);(4).笛卡兒積運算對并和交運算滿足分配律,即A(BC)=(AB)(AC); (BC)A=(BA)(CA);A(BC)=(AB)(AC); (BC)A=(BA)(CA)。我們證明其中第一個等式。證 任取,A(BC) xAyBCxA(yByC)(xAyB)(xAyC)ABAC(ABAC)所以有 A(BC) = (AB)(AC)。(5)ACBDABCD性質(zhì)5的證明和性質(zhì)4類似,也采用命題演算的方法。注意:性質(zhì)5的逆命題不成立,可分以下情況討論。(a) 當(dāng)A=B=時,顯然有AC和BD成立。(b) 當(dāng)A且B時,也有AC和BD成立。證明如下:任取xA,由于B,必存在yB,因此有xAyBABCDxCyDxC,從而證明了AC。同理可證BD。(c) 當(dāng)A=而B時,有AC成立,但不一定有BD成立。反例:令A(yù)=,B=1,C=3,D=4。(d) 當(dāng)A而B=時,有BD成立,但不一定有AC成立。反例類似于(c)。例3 設(shè)A=1,2,求P(A)A。解 P(A)A=,1,2,1,21,2=,例4 設(shè)A,B,C,D為任意集合,判斷以下命題是否為真,并說明理由。(1) AB=ACB=C; (2) A-(BC)=(A-B)(A-C);(3) A=BC=DAC=BD; (4) 存在集合A,使得AAA。解(1) 不一定為真。當(dāng)A=,B=1,C=2時,有AB=AC,但BC。(2) 不一定為真。當(dāng)A=B=1,C=2時有A-(BC)=1=1,(A-B)(A-C)= 1=(3) 為真。由等量代入的原理可證。(4) 為真。當(dāng)A=時有AAA成立。 定理1:若都是有限集合,則。定義4 如果一個集合滿足以下條件之一:(1)集合非空,且它的元素都是有序?qū)?;?)集合是空集;則稱該集合為一個二元關(guān)系,記作R。二元關(guān)系也可簡稱為關(guān)系。對于二元關(guān)系,若,則稱有關(guān)系,可記作;若,則記作。一般地,因此。例1 ,則是二元關(guān)系,不是二元關(guān)系,只是一個集合,除非將a和b定義為有序?qū)?。根?jù)以上記法可以寫成,等。定義5 設(shè)為集合,的任何子集所定義的二元關(guān)系叫做從到的二元關(guān)系,特別地,當(dāng)時,則叫做上的二元關(guān)系。的子集稱為上的一個元關(guān)系,當(dāng)時稱為上的一個元關(guān)系。例2 ,,那么,等都是從到的二元關(guān)系,而其中和同時也是上的二元關(guān)系。注:可把到的二元關(guān)系看成是上的二元關(guān)系或上的二元關(guān)系。二元關(guān)系的數(shù)目:集合上的二元關(guān)系的數(shù)目依賴于中的元素數(shù)。如果,那么,的子集就有個。每一個子集代表一個上的二元關(guān)系,所以上有個不同的二元關(guān)系。例如,則上有個不同的二元關(guān)系。如果,則,因此上有個不同的元關(guān)系。一些重要關(guān)系:(1) 空關(guān)系:若,則稱為空關(guān)系;(2) 全域關(guān)系:(3) 恒等關(guān)系:上的二元關(guān)系稱為恒等關(guān)系。(4) 小于或等于關(guān)系:,這里;(5) 上的整除關(guān)系:,這里(非零整數(shù)集);(6) 上的包含關(guān)系:,這里是集合族。例3 設(shè),則,上的包含關(guān)系:。類似的還可以定義大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等等。關(guān)系是有序?qū)Φ募?,因此對它可進(jìn)行集合運算,運算結(jié)果定義一個新的關(guān)系。例如:設(shè)和是給定集合上的關(guān)系,則,分別稱為關(guān)系與的并關(guān)系,交關(guān)系,差關(guān)系和R的補關(guān)系。這樣一來,可以從已知關(guān)系派生出各種新關(guān)系。 二元關(guān)系到的二元關(guān)系可以用一個圖來形象地表示。定義6 設(shè)是到的一個二元關(guān)系,則叫著關(guān)系的前域,叫著關(guān)系的陪域;稱為關(guān)系的定義域;稱為關(guān)系的值域。關(guān)于關(guān)系的定義域、值域的一些性質(zhì):;。證明 (證明第一個式子,其余類似)1.2.2關(guān)系矩陣與關(guān)系圖(1) 集合表示法:非空關(guān)系都是元素為有序?qū)Φ募稀?2) 關(guān)系圖:設(shè),是上的關(guān)系,令圖,其中頂點集合,邊集為,對于,滿足,則稱圖為的關(guān)系圖,記作。(3)關(guān)系矩陣:設(shè),是上的關(guān)系,令,則稱為關(guān)系的關(guān)系矩陣,記作。例 空關(guān)系的關(guān)系矩陣為全矩陣:; 全域關(guān)系的關(guān)系矩陣為全矩陣,記為;相等關(guān)系的關(guān)系矩陣為單位矩陣:?;陉P(guān)系與關(guān)系矩陣互相唯一決定的特性,可用關(guān)系矩陣有效地刻畫關(guān)系的許多性質(zhì)。如對于有限集A上的任意關(guān)系與:;。1.3關(guān)系的運算1.3.1關(guān)系的逆定義1 設(shè)是從到的二元關(guān)系,關(guān)系的逆(的逆關(guān)系)記為,定義如下:當(dāng)上的關(guān)系具有對稱性時,。相等關(guān)系的逆是相等關(guān)系;空關(guān)系的逆是空關(guān)系;全域關(guān)系的逆是全域關(guān)系。列舉法:把中每個有序?qū)Φ牡谝缓偷诙煞侄技右越粨Q,就可得到逆關(guān)系的所有元素。對和來說,這意味著。關(guān)系矩陣:將的行和列交換即可得到,即(表示的轉(zhuǎn)置)。關(guān)系圖:顛倒的關(guān)系圖中的每條?。ㄓ邢蜻叄┑募^,就得到的關(guān)系圖。逆關(guān)系的性質(zhì):(1) 設(shè)都是從到的二元關(guān)系,則(a) ;(b) ;(c) ;(d) ;(e) ,(); (f) ;(2) 設(shè)是從到的關(guān)系,是從到的關(guān)系,則。1.3.2關(guān)系的合成定義2 設(shè)是從到的關(guān)系,是從到的關(guān)系,則與的合成(右復(fù)合)為從到的關(guān)系,記為或(其中表示合成運算),定義為。例1 設(shè),是從到的關(guān)系,是從到的關(guān)系:,。分別用列舉法、圖示法、關(guān)系矩陣表示關(guān)系的合成,。例2 設(shè),和都是上的二元關(guān)系,如果,分別用列舉法、圖示法、關(guān)系矩陣表示關(guān)系的合成,等。合成關(guān)系的性質(zhì):(1) 設(shè)是從到的關(guān)系,分別是上的相等關(guān)系,則;(2) 如果關(guān)系的值域與的定義域的交集為空集,則合成關(guān)系是空關(guān)系;(3) 關(guān)系的合成關(guān)于交和并的分配律:設(shè)是從到的關(guān)系,是從到的關(guān)系,是從到的關(guān)系,則(a) ,(b) ;(c) ,(d) ;(4) 關(guān)系的合成滿足結(jié)合律:設(shè)分別是從到,到,到的關(guān)系,則。1.3.3 關(guān)系的冪定義3設(shè)是集合上的二元關(guān)系,為任一自然數(shù),則的次冪記為,定義為:(1) 為上的相等關(guān)系, (2) 。關(guān)系的冪運算的性質(zhì):(1) 對上的任意關(guān)系有:,;(2) 設(shè)是集合上的二元關(guān)系,則,;(3) 設(shè),是集合上的一個二元關(guān)系,則存在和,使;(4) 循環(huán)性質(zhì):設(shè)是集合上的二元關(guān)系,若存在和,使,則(a) 對所有,; (b) 對所有,(其中);(c) 令,則的每一次冪是的元素,即對,。關(guān)系的冪的計算:給定上的關(guān)系和自然數(shù),怎樣計算呢?若是或,結(jié)果是很簡單的。下面考慮的情況。如果是用集合表達(dá)式給出的,可以通過次合成計算得到。如果是用關(guān)系矩陣給出的,則的關(guān)系矩陣是,即個矩陣之積。與普通矩陣乘法不同的是,其中的相加是邏輯加,即。如果R是用關(guān)系圖給出的,可以直接由圖得到的關(guān)系圖。的頂點集與相同??疾斓拿總€頂點,如果在中從出發(fā)經(jīng)過步長的路徑到達(dá)頂點,則在中加一條從到的邊。當(dāng)把所有這樣的邊都找到以后,就得到圖。例3 設(shè),求的各次冪,分別用矩陣和關(guān)系圖表示。解 的關(guān)系矩陣為,則的關(guān)系矩陣分別是,因此,。所以可以得到,而,即的關(guān)系矩陣為。至此,各次冪的關(guān)系矩陣都得到了。用關(guān)系圖的方法得到的關(guān)系圖如下圖所示。合成關(guān)系的矩陣表達(dá)二元集上的布爾運算: ,; ,; ,; ,; ,; ,; 配合的其他性質(zhì)(結(jié)合律、分配律等)可計算更復(fù)雜的式子。注 關(guān)于上述兩個運算構(gòu)成二元數(shù)域。-矩陣的布爾運算:對于的矩陣,定義下列運算:,;對和的矩陣和:。例4 對全矩陣,全矩陣有零律:,; 同一律:,。用關(guān)系矩陣的布爾運算研究關(guān)系的運算:定理1.3-1:設(shè),是到的關(guān)系,是矩陣,是到的關(guān)系,是矩陣,則,這里,。設(shè)是到的關(guān)系,是運算后得到新關(guān)系的關(guān)系矩陣的元素,則, ;, ;, ;, 。定理1.3-2:關(guān)系矩陣的乘法是可結(jié)合的。證明:利用關(guān)系合成的可結(jié)合律:。借助關(guān)系矩陣及其運算還可導(dǎo)出其他一些結(jié)論,如:為上的傳遞關(guān)系;為上的自反關(guān)系。本節(jié)要求:1. 掌握關(guān)系的合成運算、關(guān)系的冪運算的概念及性質(zhì);2. 能分別利用關(guān)系的不同的表示方法(集合的表示法、圖示法、關(guān)系矩陣、關(guān)系圖)對關(guān)系進(jìn)行合成和冪運算。1.4關(guān)系的性質(zhì)定義1 設(shè)是上的一個二元關(guān)系,(1) 若對中的每一,則稱是自反的;(2) 若對中的每一,則稱是反自反的;(3) 若對每一,蘊含著,則稱是對稱的;(4) 若對每一,蘊含著,則稱是反對稱的;(5) 若對每一,蘊含著,則稱是傳遞的。對于上的任意關(guān)系,對應(yīng)于不同的關(guān)系特性的關(guān)系圖和關(guān)系矩陣的性質(zhì)(如下表):(1) 是自反的 主對角元全為每一節(jié)點有自回路;(2) 是反自反的主對角元全為每一節(jié)點無自回路(3) 是對稱的 是對稱矩陣有向邊是成對出現(xiàn)的(若有從到的弧,則必有從到的?。?4) 是反對稱的;中若有從到的弧,則必沒有從到的?。?5) 是傳遞的 中若從到有一條路徑,則從到有一條弧。自反性反自反性對稱性反對稱性傳遞性邏輯表達(dá)式集合表達(dá)式關(guān)系矩陣主對角線元素全是主對角線元素全是矩陣是對稱矩陣若,且,則對中所在位置,中相應(yīng)的位置都是關(guān)系圖每個頂點都有環(huán)每個頂點都沒有環(huán)如果兩個頂點之間有邊,一定是一對方向相反的邊(無單邊)如果兩點之間有邊,一定是一條有向邊(無雙向邊)如果頂點到有邊,到有邊,則從到也有邊關(guān)系的性質(zhì)和運算之間的聯(lián)系:設(shè)和是上的關(guān)系,它們都具有某些共同的性質(zhì)。在經(jīng)過并,交,相對補,求逆或復(fù)合運算以后,所得到的新關(guān)系,等是否還能保持原來關(guān)系的性質(zhì)呢?有關(guān)的結(jié)論給在下表中,其中的和分別表示“能保持”和“不一定能保持”的含義。自反性反自反性對稱性反對稱性傳遞性THANKS !致力為企業(yè)和個人提供合同協(xié)議,策劃案計劃書,學(xué)習(xí)課件等等打造全網(wǎng)一站式需求歡迎您的下載,資料僅供參考-可編輯修改-- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
32 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 離散數(shù)學(xué) 離散數(shù)學(xué) 教案
鏈接地址:http://www.szxfmmzy.com/p-1273773.html