離散數學及其應用第5章-關系模型與理論(下)課件

1、2022/7/19計算機應用技術研究所11離散數學Discrete Mathematics 汪榮貴 教授合肥工業(yè)大學計算機與信息學院2022/7/19計算機應用技術研究所2第5章 關系模型與理論(下)2022/7/19 關系的基本性質3 關系模型的應用5 關系的性質閉包4 本章學習內容2022/7/19計算機應用技術研究所4關系的基本性質 關系的基本性質 關系的自反與反自反 關系的對稱與反對稱 關系的傳遞性 關系性質的判定2022/7/19 自反與反自反2022/7/19 例題2022/7/19 例題2022/7/19 例題2022/7/19 例題2022/7/19 例題2022/7/19 小

2、 結 關系的基本性質 關系的自反與反自反 關系的對稱與反對稱 關系的傳遞性 關系性質的判定2022/7/19 對稱與反對稱2022/7/19 例 題2022/7/19 例 題2022/7/19 例 題2022/7/19 例題【例題】試判斷下列關系是否具有對稱性和反對稱性.（1）對任意集合A，其冪集Q（A）上的包含關系；（2）整數集Z上的整除關系.【分析】（1）當兩個集合不相等時，如果有其中一個集合包含于另一個，則反過來必然沒有包含關系，故有反對稱性但沒有對稱性；（2）當整數a和整數b不等時，若a整除b，則必有b不能整除a，故有反對稱性但沒有對稱性.【解】對任意集合A，其冪集P(A)上的包含關系

3、具有反對稱性；整數集Z上的整除關系具有反對稱性.2022/7/19 小 結 關系的基本性質 關系的自反與反自反 關系的對稱與反對稱 關系的傳遞性 關系性質的判定2022/7/19 傳遞性的定義2022/7/19 例 題2022/7/19 例 題2022/7/19 例 題2022/7/19 小 結 關系的基本性質 關系的自反與反自反 關系的對稱與反對稱 關系的傳遞性 關系性質的判定2022/7/19 關系性質的判斷2022/7/19 關系性質的判斷2022/7/19 關系性質的判斷2022/7/19 關系性質的判定2022/7/19 關系性質的判定2022/7/19 關系性質的判定2022/7/

4、19 例 題【例題】試舉例說明下列事實： R和S是反自反、反對稱和傳遞的，但是RS不一定具有反自反性和反對稱性；RS不一定具有反對稱性和傳遞性；【解】設A=1,2,3，R和S是定義在A上的兩個關系：R=1,2,2,3,1,3； S=3,2,3,1,2,1顯然R，S都是反自反的、反對稱和傳遞的. 但RS=1,1,2,2,2,1,1,2不具有反自反性和反對稱性；RS=1,2,2,3,1,3,3,2,3,1,2,1不具有反對稱性和傳遞性.2022/7/19 例 題【例題】試舉例說明下列事實： R和S是自反、對稱和傳遞的，但是RS不一定具有對稱性和傳遞性；R-S不一定具有自反性和傳遞性.【解】設A=1

5、,2,3，R和S是定義在A上的兩個關系：R=1,1,2,2,3,3,1,2,2,1； S=1,1,2,2,3,2,2,3顯然R，S都是自反、對稱和傳遞的. 但是：RS=1,1,2,2,3,3,2,3,3,21,2,2,1,1,3不具有對稱性和傳遞性；R-S=1,2,2,1不具有自反性和傳遞性.2022/7/19 例 題【例題】試判斷下圖關系的性質【解】圖a的關系在集合1,2,3上是對稱的，因為結點1與2，1與3之間的有向邊是成對出現且方向相反；因為有的點有自環(huán)，有的點沒有自環(huán)，故不是自反的，也不是反自反的；因為2,1R，1,3R，若是傳遞關系，必有2,3R. 然而結點2沒有一條指向結點3的有向

6、邊，故不是傳遞的；因為2,1R且1,2R，但 12，故不是反對稱的.2022/7/19 例 題【解】圖b的關系是反自反的，因為每個頂點都沒有自環(huán)；是反對稱的，因為兩條邊都是單向邊；是傳遞的，因為不存在頂a,b,c1,2,3，使得a到b有邊，b到c有邊，但a到c沒有邊. 同理可知，圖c的關系是自反的、反對稱的，但不是傳遞的.2022/7/19 例 題【例題】設A=1,2,3,4,6,12，A上的整除關系記為R，則R是自反的、對稱的、反自反的、反對稱的、傳遞的嗎？畫出A中關系R的關系.【解】關系R是A中的關系，所以它的關系圖如下圖所示.從圖中容易看出，R是自反、反對稱和傳遞的，不是反自反的，也不是

7、對稱的. 容易驗證，一般正整數集合中整除關系都具有自反性、反對稱性、傳遞性，而不具有反自反性和對稱性.2022/7/19 例 題2022/7/19 例 題2022/7/19本節(jié)內容到此結束謝謝大家！2022/7/19 關系的基本性質3 關系模型的應用5 關系的性質閉包4 本章學習內容2022/7/19計算機應用技術研究所42關系的性質閉包 關系的閉包運算 關系閉包的概念 傳遞閉包的構造 關系閉包的性質2022/7/19 關系閉包的概念2022/7/19 構造方法2022/7/19 例 題2022/7/19 例 題2022/7/19 構造方法2022/7/19 例 題2022/7/19 例 題2

8、022/7/19 例 題【例題】設集合A=1,2,3,4，R是A上的關系，且有：R=1,2,2,2,3,4. 試畫出R的關系圖，并根據關系圖求出r(R)，s(R)和t(R).【解】R的關系圖如左圖所示. 從關系圖上看，如果每個結點都有自環(huán)，那么該關系就具有自反性. 故可在R的關系圖的結點1，3和4處添加自環(huán)，即得到r(R)的關系圖，如右圖所示，故有：r(R)=1,2,2,2,2,3,3,4,1,1,3,3,4,4. 2022/7/19 例 題【解】如果關系圖的任何一對結點之間要么有方向相反的兩條邊，要么沒有邊，那么該關系的關系就具有對稱性. 故可在R的關系圖中添加2到1、3到2和4到3的有向邊

9、，即得到s(R)的關系圖，如下圖所示，故有：s(R)=1,2,2,2,2,3,3,4,2,1,3,2,4,3；2022/7/19 例 題2022/7/19 總 結 關系的閉包運算 關系閉包的概念 傳遞閉包的構造 關系閉包的性質2022/7/19 傳遞閉包的構造2022/7/19 傳遞閉包的構造2022/7/19例題2022/7/19例題2022/7/19 沃舍爾算法2022/7/19 沃舍爾算法2022/7/19 沃舍爾算法2022/7/19 沃舍爾算法2022/7/19例題2022/7/19例題 關系的閉包運算 關系閉包的概念 傳遞閉包的構造 關系閉包的性質2022/7/19 閉包的性質【定

10、理】若R是A上關系，則（1）R是自反的，當且僅當r(R)=R；（2）R是對稱的，當且僅當s(R)=R；（3）R是傳遞的，當且僅當t(R)=R.【證明】（1）必要性：顯然有Rr(R)，又因R是包含了R的自反關系，根據自反閉包定義有r（R）R，從而得到r(R)=R. 充分性顯然成立. （2）（3）的證明同（1）.2022/7/19 閉包的性質【定理】若R是A上關系，則（1）R是自反的，則s(R)和t(R)也是自反的；（2）R是對稱的，則r(R)和t(R)也是對稱的；（3）R是傳遞的，則r(R)也是傳遞的.2022/7/19 閉包的性質2022/7/19 閉包的性質2022/7/19 閉包與集合運算

11、2022/7/19 閉包與集合運算2022/7/19 多重閉包的性質2022/7/19 多重閉包的性質2022/7/19本章內容到此結束謝謝大家！2022/7/19 關系的基本性質3 關系模型的應用5 關系的性質閉包4 本章學習內容 關系模型的應用關系代數模型關系演算模型2022/7/19關系代數模型 關系數據模型是一種以二維表的方式表示數據的多元關系結構以及相關的關系操作。二維表又稱表，它由表框架及表元組兩部分組成。表框架由表名及若干個命名屬性列構成。表中每行數據稱為元組。元組由若干個分量組成，其每個分量對應表框架中的一個屬性值，一個表框架可以儲存若干個元組，它們構成了一個完整的二維表。20

12、22/7/19關系代數模型 關系數據模型中的基本操作共有六種，三種定位操作與三種執(zhí)行操作，即：表的列指定、表的行選擇、兩表的合并、選擇操作、刪除操作、插入操作。二維表上的六種基本操作可對應關系的五種運算，因為選擇操作不涉及邏輯運算，可在關系代數中忽略。其中一些操作可以關系的集合運算與復合運算實現。 關系模型的應用 關系代數模型 關系演算模型2022/7/19關系演算模型 對于任意給定的一個二維表，可用一個多元謂詞對其進行表示。其中謂詞中個體變元即是表的屬性，而表中的元組就是使該謂詞為真的賦值，不在表中元組則是使該謂詞為假的賦值。例如，對于下表的學生基本信息表，其中表中屬性sno、sn、sd、 sa分別表示學生對象的學號、姓