《離散數(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年，他引進了兩個集合具有相等的“勢”的概念。然而，樸素集合論中包含著悖論。第一個悖論是布拉利-福爾蒂的最大序數(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 集合的概念 集合不能精確定義。集合可以描述為：一個集合把世間萬物分成兩類,一些對象屬于該集合，是組成這個集合的成員，另一些對象不屬于該集合。可以說，由于一個集合的存在，世上的對象可分成兩類，任一對象或?qū)儆谠摷匣虿粚儆谠摷希弑鼐悠湟灰仓痪悠湟弧? 直觀地說，把一些事物匯集到一起組成一個整體就叫集合，而這些事物就是這個集合的元素或成員。 例如：方程x2－1＝0的實數(shù)解集合；26個英文字母的集合；坐標平面上所有點的集合；…… 集合通常用大寫的英文字母A,B,C,…,來標記，元素通常用小寫字母a,b,c,…,來表示。例如自然數(shù)集合N(在離散數(shù)學(xué)中認為0也是自然數(shù))，整數(shù)集合Z，有理數(shù)集合Q，實數(shù)集合R，復(fù)數(shù)集合C等。 集合的表示方法：表示一個集合的方法通常有三種：列舉法、描述法和歸納定義法。 (1) 列舉法 列出集合的所有元素，元素之間用逗號隔開，并把它們用花括號括起來。在能清楚地表示集合成員的情況下可使用省略號。 例如 A={a，b，c，…，z}，Z={0，±1，±2，…}都是合法的表示。 (2) 描述法 用謂詞來概括集合中元素的屬性來表示這個集合。 例如 B＝{x|x∈R∧x2－1＝0}表示方程x2－1＝0的實數(shù)解集。 許多集合可以用兩種方法來表示，如B也可以寫成{-1，1}。但是有些集合不可以用列元素法表示，如實數(shù)集合。 (3) 歸納定義法：1.3節(jié)再討論。 屬于、不屬于：元素和集合之間的關(guān)系是隸屬關(guān)系，即屬于或不屬于，屬于記作∈，不屬于記作。例如A＝{a，{b，c}，d，{6111666}}，這里a∈A，{b，c}∈A，d∈A，{6111661}∈A，但bA，1111661A。b和6661611是A的元素的元素。 外延公理：兩個集合A和B相等，當且僅當它們有相同的成員。 集合的元素是彼此不同的：如果同一個元素在集合中多次出現(xiàn)應(yīng)該認為是一個元素。 如 {1，1，2，2，3}＝{1，2，3}。 集合的元素是無序的：如{1，2，3}＝{3，1，2}。 1.1.2 集合間的關(guān)系 定義1.1.1 設(shè)A，B為集合，如果B中的每個元素都是A中的元素，則稱B是A的子集合，簡稱子集。這時也稱B被A包含，或A包含B，記作BA。稱B是A的擴集。 包含的符號化表示為：BAx(x∈B→x∈A)。如果B不被A包含，則記作BA。 例如 NZQRC，但ZN。顯然對任何集合A都有AA。 注意：屬于關(guān)系和包含關(guān)系都是兩個集合之間的關(guān)系，對于某些集合可以同時成立這兩種關(guān)系。例如A＝{a，{a}}和{a}，既有{a}∈A，又有{a}A。前者把它們看成是不同層次上的兩個集合，后者把它們看成是同一層次上的兩個集合，都是正確的。 定義1.1.2 設(shè)A，B為集合，如果BA且B≠A，則稱B是A的真子集，記作BA。如果B不是A的真子集，則記作BA。真子集的符號化表示為：BABA∧B≠A。 例如 NZQRC，但NN。 為方便起見，所討論的全部集合和元素是限于某一論述域中，即使這個論述域有時沒有明確地指出，但表示集合元素的變元只能在該域中取值。此論述域常用U表示，并稱為全集。 定義1.1.3 不含任何元素的集合叫空集，記作?？占梢苑柣硎緸椋絳x|x≠x}。 例如{x|x∈R∧x2+1=0}是方程x2+1=0的實數(shù)解集，因為該方程無實數(shù)解，所以是空集。 定理1.1-1 空集是一切集合的子集。 證：對任何集合A，由子集定義有，右邊的蘊涵式因前件為假而為真命題，所以也為真。 推論 空集是唯一的。 證：假設(shè)存在空集和，由定理6.1有，。根據(jù)集合相等的定義，有。 含有n個元素的集合簡稱n元集，它的含有m(m≤n)個元素的子集叫做它的m元子集。任給一個n元集，怎樣求出它的全部子集呢？舉例說明如下。 例1.1.1 A＝{1,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的子集：{a}A，a是A的元素：a∈A。 注意：不要寫成{a}∈A和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è)是論述域而是的子集，則的（絕對）補為： 當且僅當和。 2. 集合補運算的性質(zhì)： (1) 矛盾律 ； (2) 排中律 ； (3) 德摩根律 ， ， ， ； (4) 雙重否定律（的補的補是）：；(5) 若，則。 例：證明A－(B∪C)＝(A－B)∩( A－C)。 證對任意的x， x∈A－(B∪C) x∈A∧xB∪C x∈A∧┐(x∈B∨x∈C) x∈A∧(┐x∈B∧┐x∈C) x∈A∧xB∧xC (x∈A∧xB)∧(x∈A∧xC) x∈A－B)∧x∈A－C x∈(A－B)∩(A－C) 所以 A－(B∪C)＝(A－B)∩( A－C)。 例：證明A∩E＝A。 證對任意的x，x∈A∩Ex∈A∧x∈Ex∈A(因為x∈E是恒真命題)，所以A∩E＝A。 注意：以上證明的基本思想是：設(shè)P，Q為集合公式，欲證P＝Q，即證PQ∧QP為真。 也就是要證對于任意的x有 x∈Px∈Q和x∈Qx∈P成立。對于某些恒等式可以將這兩個方向的推理合到一起，就是 x∈Px∈Q。 不難看出，集合運算的規(guī)律和命題演算的某些規(guī)律是一致的，所以命題演算的方法是證明集合恒等式的基本方法。 證明集合恒等式的另一種方法是利用已知的恒等式來代入。 例：證明A∪(A∩B)＝A。 證 A∪(A∩B)＝(A∩E)∪(A∩B)＝A∩(E∪B)＝A∩(B∪E)＝A∩E＝A。 例：證明等式A－B＝A∩～B。 證對于任意的x，x∈A－Bx∈A∧xBx∈A∧x∈～Bx∈A∩～B， 所以A－B＝A∩～B。 注意：上式把相對補運算轉(zhuǎn)換成交運算，這在證明有關(guān)相對補的恒等式中是很有用的。 例：證明(A－B)∪B＝A∪B 證 (A－B)∪B＝(A∩～B)∪B＝(A∪B)∩(～B∪B)＝(A∪B)∩E＝A∪B。 例：證明命題A∪B＝BA∩B＝AA－B＝。 證 (1) 證A∪B＝BAB，對于任意的x， x∈Ax∈A∨x∈Bx∈A∪Bx∈B(因為A∪B＝B)，所以AB。 (2) 證ABA∩B＝A。顯然有A∩BA，下面證AA∩B，對于任意的x， x∈Ax∈A∧x∈Ax∈A∧x∈B(因為AB) x∈A∩B，由集合相等的定義有A∩B＝A。 (3) 證A∩B＝AA－B＝。 A－B＝A∩～B＝(A∩B)∩～B(因為A∩B＝A)＝A∩(B∩～B)＝A∩＝。 (4) 證A－B＝A∪B＝B。A∪B＝B∪(A－B)＝B∪＝B。 注意：上式給出了AB的另外三種等價的定義，這不僅為證明兩個集合之間的包含關(guān)系提供了新方法，同時也可以用于集合公式的化簡。 例：化簡((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)。 解因為A∪BA∪B∪C，AA∪(B－C)，故有 ((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)＝(A∪B)－A＝B－A。 定義：兩集合的環(huán)和（對稱差）定義為： 環(huán)和： 2. 環(huán)和與環(huán)積的性質(zhì)： (1) ， (2) ， ， (3) ， ； (4) ， ， (5) 例：已知AB＝AC，證明B＝C。 證 已知AB＝AC，所以有 A(AB)＝A(AC) (AA)B＝(AA)C B＝CB＝CB＝C。 3. 集合運算的文氏圖表示 注意：如果沒有特殊說明，任何兩個集合都畫成相交的。 冪集合 定義：設(shè)是一個集合，的冪集是的所有子集的集合，即。 若是元集，則有個元素。 例：若，則；若，則。 對任意集合：，。 集合運算的順序：為了使得集合表達式更為簡潔，我們對集合運算的優(yōu)先順序做如下規(guī)定：稱廣義交，廣義并，冪集，絕對補運算為一類運算，交，并，補，環(huán)和，環(huán)積運算為二類運算。一類運算優(yōu)先于二類運算；一類運算之間由右向左順序進行；二類運算之間由括號決定先后順序。  1.2 關(guān)系及其表示 1.2.1集合的笛卡兒積與二元關(guān)系 定義 1 由兩個元素x和y（允許x=y）組成的序列記作，稱為二重組或有序?qū)蛐蚺?，其中x是它的第一元素（分量），y是它的第二元素（分量）。 有序?qū)?x,y>具有以下性質(zhì)： 1．當x≠y時，≠； 2．=的充分必要條件是x=u且y=v。 注意：這些性質(zhì)是二元集{x,y}所不具備的。例如當x≠y時有{x,y}={y,x}。原因在于有序?qū)χ械脑厥怯行虻?，而集合中的元素是無序的。 例1 已知=<5,2x+y>，求x和y。 解 由有序?qū)ο嗟鹊某湟獥l件有x+2=5，2x+y=4，解得x=3，y=-2。 定義2 設(shè)是個元素，定義 為重組。 注意：重組是一個二重組，其中第一個分量是重組。如代表而不代表，按定義后者不是三重組，并且。 重組與相等當且僅當，。 定義3 設(shè)A，B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)?。所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積（叉積），記作A×B。 笛卡兒積的符號化表示為A×B={|x∈A∧y∈B}。 集合（）的叉積記為或，定義為 例2 設(shè)A={a,b}, B={0,1,2}，則 A×B={,,,,,}； B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}。 由排列組合的知識不難證明，如果|A|=m，|B|=n，則|A×B|=mn。 笛卡兒積的運算性質(zhì) (1).對任意集合A，根據(jù)定義有 A×=, ×A=； (2).一般地說，笛卡兒積運算不滿足交換律，即A×B≠B×A(當A≠∧B≠∧A≠B時)； (3)．笛卡兒積運算不滿足結(jié)合律，即(A×B)×C≠A×(B×C)(當A≠∧B≠∧C≠時)； (4).笛卡兒積運算對并和交運算滿足分配律，即 A×(B∪C)=(A×B)∪(A×C)； (B∪C)×A=(B×A)∪(C×A)； A×(B∩C)=(A×B)∩(A×C)； (B∩C)×A=(B×A)∩(C×A)。 我們證明其中第一個等式。 證 任取， ∈A×(B∪C) x∈A∧y∈B∪Cx∈A∧(y∈B∨y∈C) (x∈A∧y∈B)∨(x∈A∧y∈C)∈A×B∨∈A×C∈(A×B∪A×C) 所以有 A×(B∪C) = (A×B)∪(A×C)。 (5)．AC∧BDA×BC×D 性質(zhì)5的證明和性質(zhì)4類似，也采用命題演算的方法。 注意：性質(zhì)5的逆命題不成立，可分以下情況討論。 (a) 當A=B=時，顯然有AC和BD成立。 (b) 當A≠且B≠時，也有AC和BD成立。證明如下：任取x∈A，由于B≠,必存在y∈B，因此有x∈A∧y∈B∈A×B∈C×Dx∈C∧y∈Dx∈C， 從而證明了AC。同理可證BD。 (c) 當A=而B≠時，有AC成立，但不一定有BD成立。 反例：令A(yù)=，B={1}，C={3}，D={4}。 (d) 當A≠而B=時，有BD成立，但不一定有AC成立。反例類似于(c)。 例3 設(shè)A={1,2},求P(A)×A。 解 P(A)×A={,{1},{2},{1,2}}×{1,2} ={<,1>,<,2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>} 例4 設(shè)A，B，C，D為任意集合，判斷以下命題是否為真，并說明理由。 (1) A×B=A×CB=C； (2) A-(B×C)=(A-B)×(A-C)； (3) A=B∧C=DA×C=B×D； (4) 存在集合A，使得AA×A。 解(1) 不一定為真。當A=，B={1},C={2}時，有A×B==A×C，但B≠C。 (2) 不一定為真。當A=B={1},C={2}時有A-(B×C)={1}–{<1,2>}={1}， (A-B)×(A-C)= ×{1}= (3) 為真。由等量代入的原理可證。 (4) 為真。當A=時有AA×A成立。 定理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)系，特別地，當時，則叫做上的二元關(guān)系。的子集稱為上的一個元關(guān)系，當時稱為上的一個元關(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ū)Φ募?，因此對它可進行集合運算，運算結(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)系矩陣為單位矩陣：。 基于關(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)系）記為，定義如下： 當上的關(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é)果是很簡單的。 下面考慮的情況。 如果是用集合表達式給出的，可以通過次合成計算得到。 如果是用關(guān)系矩陣給出的，則的關(guān)系矩陣是，即個矩陣之積。與普通矩陣乘法不同的是，其中的相加是邏輯加，即。 如果R是用關(guān)系圖給出的，可以直接由圖得到的關(guān)系圖。的頂點集與相同。考察的每個頂點，如果在中從出發(fā)經(jīng)過步長的路徑到達頂點，則在中加一條從到的邊。當把所有這樣的邊都找到以后，就得到圖。 例3 設(shè)，，求的各次冪，分別用矩陣和關(guān)系圖表示。 解 的關(guān)系矩陣為，則的關(guān)系矩陣分別是 ，， 因此，，。所以可以得到，，而，即的關(guān)系矩陣為。至此，各次冪的關(guān)系矩陣都得到了。 用關(guān)系圖的方法得到的關(guān)系圖如下圖所示。 合成關(guān)系的矩陣表達 二元集上的布爾運算： ① ，； ，； ② ，； ，； ③ ，； ，； ④ 配合的其他性質(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)系進行合成和冪運算。 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) 是傳遞的 中若從到有一條路徑，則從到有一條弧。  自反性 反自反性 對稱性 反對稱性 傳遞性 邏 輯 表 達 式 集合 表達式 關(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)一站式需求 歡迎您的下載，資料僅供參考 -可編輯修改-