《《離散數(shù)學(xué)》 教案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《《離散數(shù)學(xué)》 教案.doc（25頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

______________________________________________________________________________________________________________ 《離散數(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)發(fā)展。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)于最大基數(shù)的悖論。集合論的現(xiàn)代公理化開始于1908年策梅羅所發(fā)表的一組公理，經(jīng)過(guò)弗蘭克爾的加工，這個(gè)系統(tǒng)稱為策梅羅-弗蘭克爾集合論（ZF），其中包括1904年策梅羅引入的選擇公理。另外一種系統(tǒng)是馮·諾伊曼-伯奈斯-哥德?tīng)柤险?。公理集合論中一個(gè)有名的猜想是連續(xù)統(tǒng)假設(shè)（CH）。哥德?tīng)栕C明了連續(xù)統(tǒng)假設(shè)與策梅羅-弗蘭克爾集合論的相容性，科恩證明了連續(xù)統(tǒng)假設(shè)與策梅羅-弗蘭克爾集合論的獨(dú)立性?，F(xiàn)在把策梅羅-弗蘭克爾集合論與選擇公理一起稱為ZFC系統(tǒng)。 一、學(xué)習(xí)目的與要求 本章目的是介紹集合的基本概念，講授集合運(yùn)算的基本理論，關(guān)系的定義與運(yùn)算。通過(guò)本章的學(xué)習(xí)，使學(xué)生了解集合是數(shù)學(xué)的基本語(yǔ)言，掌握主要的集合運(yùn)算方法和關(guān)系運(yùn)算方法，為學(xué)習(xí)后續(xù)章節(jié)打下良好基礎(chǔ)。 二、知識(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 集合的概念 集合不能精確定義。集合可以描述為：一個(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等。 集合的表示方法：表示一個(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∈R∧x2－1＝0}表示方程x2－1＝0的實(shí)數(shù)解集。 許多集合可以用兩種方法來(lái)表示，如B也可以寫成{-1，1}。但是有些集合不可以用列元素法表示，如實(shí)數(shù)集合。 (3) 歸納定義法：1.3節(jié)再討論。 屬于、不屬于：元素和集合之間的關(guān)系是隸屬關(guān)系，即屬于或不屬于，屬于記作∈，不屬于記作。例如A＝{a，{b，c}，d，{mzebxcnn0}}，這里a∈A，{b，c}∈A，d∈A，{mzebxcnn0}∈A，但bA，mzebxcnn0A。b和mzebxcnn0是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}。 1.1.2 集合間的關(guān)系 定義1.1.1 設(shè)A，B為集合，如果B中的每個(gè)元素都是A中的元素，則稱B是A的子集合，簡(jiǎn)稱子集。這時(shí)也稱B被A包含，或A包含B，記作BA。稱B是A的擴(kuò)集。 包含的符號(hào)化表示為：BAx(x∈B→x∈A)。如果B不被A包含，則記作BA。 例如 NZQRC，但ZN。顯然對(duì)任何集合A都有AA。 注意：屬于關(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為集合，如果BA且B≠A，則稱B是A的真子集，記作BA。如果B不是A的真子集，則記作BA。真子集的符號(hào)化表示為：BABA∧B≠A。 例如 NZQRC，但NN。 為方便起見(jiàn)，所討論的全部集合和元素是限于某一論述域中，即使這個(gè)論述域有時(shí)沒(méi)有明確地指出，但表示集合元素的變?cè)荒茉谠撚蛑腥≈?。此論述域常用U表示，并稱為全集。 定義1.1.3 不含任何元素的集合叫空集，記作?？占梢苑?hào)化表示為＝{x|x≠x}。 例如{x|x∈R∧x2+1=0}是方程x2+1=0的實(shí)數(shù)解集，因?yàn)樵摲匠虩o(wú)實(shí)數(shù)解，所以是空集。 定理1.1-1 空集是一切集合的子集。 證：對(duì)任何集合A，由子集定義有，右邊的蘊(yùn)涵式因前件為假而為真命題，所以也為真。 推論 空集是唯一的。 證：假設(shè)存在空集和，由定理6.1有，。根據(jù)集合相等的定義，有。 含有n個(gè)元素的集合簡(jiǎn)稱n元集，它的含有m(m≤n)個(gè)元素的子集叫做它的m元子集。任給一個(gè)n元集，怎樣求出它的全部子集呢？舉例說(shuō)明如下。 例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元子集有個(gè)，1元子集有個(gè)，…，m元子集有個(gè)，…，n元子集有個(gè)。子集總數(shù)為個(gè)。 全集與空集在本章中起重要作用，注意掌握它們的基本概念。 注意：∈與的聯(lián)系與區(qū)別。 (1) ∈表示集合的元素（可以為集合）與集合本身的從屬關(guān)系， (2) 表示兩個(gè)集合之間的包含關(guān)系。 例如：對(duì)于集合A={a,b,c},{a}是A的子集：{a}A，a是A的元素：a∈A。 注意：不要寫成{a}∈A和aA。 ，但；是一元集，而不是空集。，。 1.1.3 集合的運(yùn)算 集合的交、并和差運(yùn)算 1. 集合交、并、差運(yùn)算的定義（注意集合運(yùn)算與邏輯運(yùn)算的對(duì)應(yīng)關(guān)系） 定義 設(shè)和是集合， (1) 和的交記為，定義為：； (2) 和的并記為，定義為：； (3) 和的差記為，定義為：。 例：設(shè)，，則 ，，， 定義：如果是兩個(gè)集合，，那么稱和是不相交的。如果是一個(gè)集合的族，且中的任意兩個(gè)不同元素都不相交，那么稱是（兩兩）不相交集合的族。 2. 集合的并和交運(yùn)算的推廣（廣義交、廣義并） 個(gè)集合 ， ， 無(wú)窮可數(shù)個(gè)集合： ， 一般情形： （）， 3. 集合交、并、差運(yùn)算的性質(zhì)： (1) 交換律 ， ， (2) 結(jié)合律 ， . (3) 分配律 ， (4) 冪等律 , , (5) 同一律 , ， (6) 零 律 , (7) 吸收律 ， ， (8) 德摩根律 (9) (a) , (b) , (c), (d), (e) 若，,則，, (f) 若，則, (g) 若，則， (h) 。 證：利用運(yùn)算的定義（與邏輯運(yùn)算的關(guān)系）或已證明的性質(zhì)。 集合的補(bǔ)運(yùn)算 1. 集合的補(bǔ)運(yùn)算的定義 定義：設(shè)是論述域而是的子集，則的（絕對(duì)）補(bǔ)為： 當(dāng)且僅當(dāng)和。 2. 集合補(bǔ)運(yùn)算的性質(zhì)： (1) 矛盾律 ； (2) 排中律 ； (3) 德摩根律 ， ， ， ； (4) 雙重否定律（的補(bǔ)的補(bǔ)是）：；(5) 若，則。 例：證明A－(B∪C)＝(A－B)∩( A－C)。 證對(duì)任意的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。 證對(duì)任意的x，x∈A∩Ex∈A∧x∈Ex∈A(因?yàn)閤∈E是恒真命題)，所以A∩E＝A。 注意：以上證明的基本思想是：設(shè)P，Q為集合公式，欲證P＝Q，即證PQ∧QP為真。 也就是要證對(duì)于任意的x有 x∈Px∈Q和x∈Qx∈P成立。對(duì)于某些恒等式可以將這兩個(gè)方向的推理合到一起，就是 x∈Px∈Q。 不難看出，集合運(yùn)算的規(guī)律和命題演算的某些規(guī)律是一致的，所以命題演算的方法是證明集合恒等式的基本方法。 證明集合恒等式的另一種方法是利用已知的恒等式來(lái)代入。 例：證明A∪(A∩B)＝A。 證 A∪(A∩B)＝(A∩E)∪(A∩B)＝A∩(E∪B)＝A∩(B∪E)＝A∩E＝A。 例：證明等式A－B＝A∩～B。 證對(duì)于任意的x，x∈A－Bx∈A∧xBx∈A∧x∈～Bx∈A∩～B， 所以A－B＝A∩～B。 注意：上式把相對(duì)補(bǔ)運(yùn)算轉(zhuǎn)換成交運(yùn)算，這在證明有關(guān)相對(duì)補(bǔ)的恒等式中是很有用的。 例：證明(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，對(duì)于任意的x， x∈Ax∈A∨x∈Bx∈A∪Bx∈B(因?yàn)锳∪B＝B)，所以AB。 (2) 證ABA∩B＝A。顯然有A∩BA，下面證AA∩B，對(duì)于任意的x， x∈Ax∈A∧x∈Ax∈A∧x∈B(因?yàn)锳B) x∈A∩B，由集合相等的定義有A∩B＝A。 (3) 證A∩B＝AA－B＝。 A－B＝A∩～B＝(A∩B)∩～B(因?yàn)锳∩B＝A)＝A∩(B∩～B)＝A∩＝。 (4) 證A－B＝A∪B＝B。A∪B＝B∪(A－B)＝B∪＝B。 注意：上式給出了AB的另外三種等價(jià)的定義，這不僅為證明兩個(gè)集合之間的包含關(guān)系提供了新方法，同時(shí)也可以用于集合公式的化簡(jiǎn)。 例：化簡(jiǎn)((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)。 解因?yàn)锳∪BA∪B∪C，AA∪(B－C)，故有 ((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)＝(A∪B)－A＝B－A。 定義：兩集合的環(huán)和（對(duì)稱差）定義為： 環(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. 集合運(yùn)算的文氏圖表示 注意：如果沒(méi)有特殊說(shuō)明，任何兩個(gè)集合都畫成相交的。 冪集合 定義：設(shè)是一個(gè)集合，的冪集是的所有子集的集合，即。 若是元集，則有個(gè)元素。 例：若，則；若，則。 對(duì)任意集合：，。 集合運(yùn)算的順序：為了使得集合表達(dá)式更為簡(jiǎn)潔，我們對(duì)集合運(yùn)算的優(yōu)先順序做如下規(guī)定：稱廣義交，廣義并，冪集，絕對(duì)補(bǔ)運(yùn)算為一類運(yùn)算，交，并，補(bǔ)，環(huán)和，環(huán)積運(yùn)算為二類運(yùn)算。一類運(yùn)算優(yōu)先于二類運(yùn)算；一類運(yùn)算之間由右向左順序進(jìn)行；二類運(yùn)算之間由括號(hào)決定先后順序。  1.2 關(guān)系及其表示 1.2.1集合的笛卡兒積與二元關(guān)系 定義 1 由兩個(gè)元素x和y（允許x=y）組成的序列記作，稱為二重組或有序?qū)蛐蚺?，其中x是它的第一元素（分量），y是它的第二元素（分量）。 有序?qū)?x,y>具有以下性質(zhì)： 1．當(dāng)x≠y時(shí)，≠； 2．=的充分必要條件是x=u且y=v。 注意：這些性質(zhì)是二元集{x,y}所不具備的。例如當(dāng)x≠y時(shí)有{x,y}={y,x}。原因在于有序?qū)χ械脑厥怯行虻?，而集合中的元素是無(wú)序的。 例1 已知=<5,2x+y>，求x和y。 解 由有序?qū)ο嗟鹊某湟獥l件有x+2=5，2x+y=4，解得x=3，y=-2。 定義2 設(shè)是個(gè)元素，定義 為重組。 注意：重組是一個(gè)二重組，其中第一個(gè)分量是重組。如代表而不代表，按定義后者不是三重組，并且。 重組與相等當(dāng)且僅當(dāng)，。 定義3 設(shè)A，B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)?。所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積（叉積），記作A×B。 笛卡兒積的符號(hào)化表示為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>}。 由排列組合的知識(shí)不難證明，如果|A|=m，|B|=n，則|A×B|=mn。 笛卡兒積的運(yùn)算性質(zhì) (1).對(duì)任意集合A，根據(jù)定義有 A×=, ×A=； (2).一般地說(shuō)，笛卡兒積運(yùn)算不滿足交換律，即A×B≠B×A(當(dāng)A≠∧B≠∧A≠B時(shí))； (3)．笛卡兒積運(yùn)算不滿足結(jié)合律，即(A×B)×C≠A×(B×C)(當(dāng)A≠∧B≠∧C≠時(shí))； (4).笛卡兒積運(yùn)算對(duì)并和交運(yùn)算滿足分配律，即 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)。 我們證明其中第一個(gè)等式。 證 任取， ∈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) 當(dāng)A=B=時(shí)，顯然有AC和BD成立。 (b) 當(dāng)A≠且B≠時(shí)，也有AC和BD成立。證明如下：任取x∈A，由于B≠,必存在y∈B，因此有x∈A∧y∈B∈A×B∈C×Dx∈C∧y∈Dx∈C， 從而證明了AC。同理可證BD。 (c) 當(dāng)A=而B≠時(shí)，有AC成立，但不一定有BD成立。 反例：令A(yù)=，B={1}，C={3}，D={4}。 (d) 當(dāng)A≠而B=時(shí)，有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為任意集合，判斷以下命題是否為真，并說(shuō)明理由。 (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) 不一定為真。當(dāng)A=，B={1},C={2}時(shí)，有A×B==A×C，但B≠C。 (2) 不一定為真。當(dāng)A=B={1},C={2}時(shí)有A-(B×C)={1}–{<1,2>}={1}， (A-B)×(A-C)= ×{1}= (3) 為真。由等量代入的原理可證。 (4) 為真。當(dāng)A=時(shí)有AA×A成立。 定理1：若都是有限集合，則。 定義4 如果一個(gè)集合滿足以下條件之一：（1）集合非空，且它的元素都是有序?qū)?；?）集合是空集；則稱該集合為一個(gè)二元關(guān)系，記作R。二元關(guān)系也可簡(jiǎn)稱為關(guān)系。 對(duì)于二元關(guān)系，若，則稱有關(guān)系，可記作；若，則記作。一般地，因此。 例1 ，，則是二元關(guān)系，不是二元關(guān)系，只是一個(gè)集合，除非將a和b定義為有序?qū)?。根?jù)以上記法可以寫成，等。 定義5 設(shè)為集合，的任何子集所定義的二元關(guān)系叫做從到的二元關(guān)系，特別地，當(dāng)時(shí)，則叫做上的二元關(guān)系。的子集稱為上的一個(gè)元關(guān)系，當(dāng)時(shí)稱為上的一個(gè)元關(guān)系。 例2 ,，那么，，，等都是從到的二元關(guān)系，而其中和同時(shí)也是上的二元關(guān)系。 注：可把到的二元關(guān)系看成是上的二元關(guān)系或上的二元關(guān)系。 二元關(guān)系的數(shù)目：集合上的二元關(guān)系的數(shù)目依賴于中的元素?cái)?shù)。如果，那么，的子集就有個(gè)。每一個(gè)子集代表一個(gè)上的二元關(guān)系，所以上有個(gè)不同的二元關(guān)系。例如，則上有個(gè)不同的二元關(guān)系。如果，則，因此上有個(gè)不同的元關(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ū)Φ募?，因此?duì)它可進(jìn)行集合運(yùn)算，運(yùn)算結(jié)果定義一個(gè)新的關(guān)系。例如：設(shè)和是給定集合上的關(guān)系，則，，，分別稱為關(guān)系與的并關(guān)系，交關(guān)系，差關(guān)系和R的補(bǔ)關(guān)系。這樣一來(lái)，可以從已知關(guān)系派生出各種新關(guān)系。 二元關(guān)系 到的二元關(guān)系可以用一個(gè)圖來(lái)形象地表示。 定義6 設(shè)是到的一個(gè)二元關(guān)系，則叫著關(guān)系的前域，叫著關(guān)系的陪域；稱為關(guān)系的定義域；稱為關(guān)系的值域。 關(guān)于關(guān)系的定義域、值域的一些性質(zhì)： ；； ；。 證明 （證明第一個(gè)式子，其余類似） 1.2.2關(guān)系矩陣與關(guān)系圖　 (1) 集合表示法：非空關(guān)系都是元素為有序?qū)Φ募稀? (2) 關(guān)系圖：設(shè)，是上的關(guān)系，令圖，其中頂點(diǎn)集合，邊集為，對(duì)于，滿足，則稱圖為的關(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ì)。如對(duì)于有限集A上的任意關(guān)系與：；。 1.3關(guān)系的運(yùn)算 1.3.1關(guān)系的逆 定義1 設(shè)是從到的二元關(guān)系，關(guān)系的逆（的逆關(guān)系）記為，定義如下： 當(dāng)上的關(guān)系具有對(duì)稱性時(shí)，。 相等關(guān)系的逆是相等關(guān)系；空關(guān)系的逆是空關(guān)系；全域關(guān)系的逆是全域關(guān)系。 列舉法：把中每個(gè)有序?qū)Φ牡谝缓偷诙煞侄技右越粨Q，就可得到逆關(guān)系的所有元素。 對(duì)和來(lái)說(shuō)，這意味著。 關(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)系，記為或（其中表示合成運(yù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)系的冪運(yùn)算的性質(zhì)： (1) 對(duì)上的任意關(guān)系有：，； (2) 設(shè)是集合上的二元關(guān)系，，則，； (3) 設(shè)，是集合上的一個(gè)二元關(guān)系，則存在和，使； (4) 循環(huán)性質(zhì)：設(shè)是集合上的二元關(guān)系，若存在和，，使，則 (a) 對(duì)所有，； (b) 對(duì)所有，（其中）；(c) 令，則的每一次冪是的元素，即對(duì)，。 關(guān)系的冪的計(jì)算： 給定上的關(guān)系和自然數(shù)，怎樣計(jì)算呢？若是或，結(jié)果是很簡(jiǎn)單的。 下面考慮的情況。 如果是用集合表達(dá)式給出的，可以通過(guò)次合成計(jì)算得到。 如果是用關(guān)系矩陣給出的，則的關(guān)系矩陣是，即個(gè)矩陣之積。與普通矩陣乘法不同的是，其中的相加是邏輯加，即。 如果R是用關(guān)系圖給出的，可以直接由圖得到的關(guān)系圖。的頂點(diǎn)集與相同?？疾斓拿總€(gè)頂點(diǎn)，如果在中從出發(fā)經(jīng)過(guò)步長(zhǎng)的路徑到達(dá)頂點(diǎn)，則在中加一條從到的邊。當(dāng)把所有這樣的邊都找到以后，就得到圖。 例3 設(shè)，，求的各次冪，分別用矩陣和關(guān)系圖表示。 解 的關(guān)系矩陣為，則的關(guān)系矩陣分別是 ，， 因此，，。所以可以得到，，而，即的關(guān)系矩陣為。至此，各次冪的關(guān)系矩陣都得到了。 用關(guān)系圖的方法得到的關(guān)系圖如下圖所示。 合成關(guān)系的矩陣表達(dá) 二元集上的布爾運(yùn)算： ① ，； ，； ② ，； ，； ③ ，； ，； ④ 配合的其他性質(zhì)(結(jié)合律、分配律等)可計(jì)算更復(fù)雜的式子。 注 關(guān)于上述兩個(gè)運(yùn)算構(gòu)成二元數(shù)域。 -矩陣的布爾運(yùn)算： 對(duì)于的矩陣，，定義下列運(yùn)算： ，，； 對(duì)和的矩陣和：。 例4 對(duì)全矩陣，全矩陣有 零律：，； 同一律：，。 用關(guān)系矩陣的布爾運(yùn)算研究關(guān)系的運(yùn)算： 定理1.3-1：設(shè)，，，是到的關(guān)系，是矩陣，是到的關(guān)系，是矩陣，則，這里，，。 設(shè)是到的關(guān)系，，，是運(yùn)算后得到新關(guān)系的關(guān)系矩陣的元素，則 ， ； ， ； ， ； ， 。 定理1.3-2：關(guān)系矩陣的乘法是可結(jié)合的。 證明：利用關(guān)系合成的可結(jié)合律： 。 借助關(guān)系矩陣及其運(yùn)算還可導(dǎo)出其他一些結(jié)論，如： 為上的傳遞關(guān)系； 為上的自反關(guān)系。 本節(jié)要求： 1. 掌握關(guān)系的合成運(yùn)算、關(guān)系的冪運(yùn)算的概念及性質(zhì)； 2. 能分別利用關(guān)系的不同的表示方法（集合的表示法、圖示法、關(guān)系矩陣、關(guān)系圖）對(duì)關(guān)系進(jìn)行合成和冪運(yùn)算。 1.4關(guān)系的性質(zhì) 定義1 設(shè)是上的一個(gè)二元關(guān)系， (1) 若對(duì)中的每一，，則稱是自反的； (2) 若對(duì)中的每一，，則稱是反自反的； (3) 若對(duì)每一，蘊(yùn)含著，則稱是對(duì)稱的； (4) 若對(duì)每一，，蘊(yùn)含著，則稱是反對(duì)稱的； (5) 若對(duì)每一，，蘊(yùn)含著，則稱是傳遞的。 對(duì)于上的任意關(guān)系，對(duì)應(yīng)于不同的關(guān)系特性的關(guān)系圖和關(guān)系矩陣的性質(zhì)（如下表）： (1) 是自反的 主對(duì)角元全為每一節(jié)點(diǎn)有自回路； (2) 是反自反的主對(duì)角元全為每一節(jié)點(diǎn)無(wú)自回路 (3) 是對(duì)稱的 是對(duì)稱矩陣 有向邊是成對(duì)出現(xiàn)的（若有從到的弧，則必有從到的弧）； (4) 是反對(duì)稱的 ； 中若有從到的弧，則必沒(méi)有從到的?。? (5) 是傳遞的 中若從到有一條路徑，則從到有一條弧。  自反性 反自反性 對(duì)稱性 反對(duì)稱性 傳遞性 邏 輯 表 達(dá) 式 集合 表達(dá)式 關(guān)系 矩陣 主對(duì)角線 元素全是 主對(duì)角線 元素全是 矩陣是對(duì)稱矩陣 若，且， 則 對(duì)中所在位置，中相應(yīng)的位置都是 關(guān)系圖 每個(gè)頂點(diǎn) 都有環(huán) 每個(gè)頂點(diǎn) 都沒(méi)有環(huán) 如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊(無(wú)單邊) 如果兩點(diǎn)之間有邊，一定是一條有向邊(無(wú)雙向邊) 如果頂點(diǎn)到有邊，到有邊，則從到也有邊 關(guān)系的性質(zhì)和運(yùn)算之間的聯(lián)系： 設(shè)和是上的關(guān)系，它們都具有某些共同的性質(zhì)。在經(jīng)過(guò)并，交，相對(duì)補(bǔ)，求逆或復(fù)合運(yùn)算以后，所得到的新關(guān)系，，，，等是否還能保持原來(lái)關(guān)系的性質(zhì)呢？有關(guān)的結(jié)論給在下表中，其中的√和×分別表示“能保持”和“不一定能保持”的含義。  自反性 反自反性 對(duì)稱性 反對(duì)稱性 傳遞性 √ √ √ √ √ √ √ √ √ √ √ √ √ × × × √ √ √ × √ × × × ×  THANKS !!! 致力為企業(yè)和個(gè)人提供合同協(xié)議，策劃案計(jì)劃書，學(xué)習(xí)課件等等 打造全網(wǎng)一站式需求 歡迎您的下載，資料僅供參考 -可編輯修改-