離散數(shù)學基礎 第四章 關系.ppt

《離散數(shù)學基礎 第四章 關系.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第四章關系《離散數(shù)學基礎》——謝勝利1本章主要內(nèi)容關系定義及其表示關系的運算N元關系及其應用等價關系偏序關系2第一節(jié)關系定義及其表示3引言日常生活和科學技術(shù)中的“關系”：人與人之間有：父子關系、兄弟關系、師生關系兩數(shù)之間有：大于關系、等于關系、小于關系集合之間有：包含關系元素與集合之間有：屬于關系程序之間有：調(diào)用關系關系－－聯(lián)系:事物間的多值依賴。4一、關系的概念直觀地講，關系就是反映“多值依賴”的二維表，例如，學生－選課表：學生課程張三離散數(shù)學李四微積分張三高級語言……§1二元關系的基本概念5把學生選課表用集合來表示：R={<張三,離散數(shù)學>,<李四,微積分>,<張三,高級語言>,…}有

2、序?qū)Φ募蟁同樣也刻畫了學生集合｛張三，李四，…｝與課程集合｛離散數(shù)學，微積分，高級語言，…｝之間“多值依賴”的聯(lián)系，稱為二元關系。6若∈R,則稱a與b有關系R,記為aRb;若R,則稱a與b沒有關系R,記為aRb?！径x】設有兩個集合A和B，其笛卡兒積A×B的任意一個子集R稱為從A到B的一個二元關系。即:R?A×B特別地，當A＝B時，R稱為A上的關系,這時R?A2§1二元關系的基本概念7【示例】設A＝｛1,2,3,4,5｝,B＝｛a,b,c｝,則R1＝{<1,a>,<1,b>,<2,b>,<3,a>}是從A到B的關系R2＝{,,}是從B

3、到A的關系。【例】設A={雞蛋，奶，玉米}，B={奶牛，山羊，母雞}。我們可以定義由A到B的關系R={

4、a∈A,b∈B，a由b產(chǎn)生},即R={<雞蛋，母雞>，<奶，奶牛>，<奶，山羊>}。8補充：關系的應用:關系數(shù)據(jù)模型【定義】設有n個集合A1,A2,…,An,則笛卡兒積A1×A2×…×An的任意一個子集R稱為A1,A2,…,An上的一個n元關系。這些集合A1,A2,…,An叫做關系的域,n叫做它的階。若R?An,則稱R為A上的n元關系。9例設R是A×N×S×D×T的子集，其中A是所有航空公司的集合，N是航班號的集合，S是出發(fā)地的集合，D是目的地的集合，T是起飛時間的集合。則R是

5、由5元組組成的表示飛機航班的關系。例如，設R表示由國內(nèi)航空公司飛機航班構(gòu)成的關系，如果南方航空公司在15:00有從廣州到北京的2963航班，那么<南方航空，2963，廣州，北京，15:00>屬于R。10可以利用n元關系表示計算機的數(shù)據(jù)庫。數(shù)據(jù)庫由記錄組成，這些記錄是由字段構(gòu)成的n元組。字段是n元組的數(shù)據(jù)項。用于表示數(shù)據(jù)庫的關系叫做表，因為這些關系常常用表來給出。11例如，學生記錄的數(shù)據(jù)庫可以由包含學生的姓名、學號、專業(yè)、平均成績的字段構(gòu)成。關系數(shù)據(jù)模型把一個記錄表示成一個n元組。于是，學生記錄可以被表示成形如<學生姓名、學號、專業(yè)、GPA>的4元組。4個記錄

6、的一個數(shù)據(jù)庫樣本是：<王明，231455，計算機科學，85.8><張強，888323，物理學，73.4><周祥，102147，計算機科學，83.7><劉海，453876，經(jīng)濟學，69.4>12【定義】設R?A×A,1）當R＝Φ時,稱R為A上的空關系;2）當R＝A×A=A2時,稱R為集合A上的全域關系,用EA表示。顯然EA＝{

7、x∈A且y∈A}3）若R＝｛

8、x∈A｝,則稱R是A上的恒等關系,用ＩA表示。13【定義】設R是二元關系，由∈R的所有x組成的集合稱為R的前域，記作domR；由∈R的所有y組成的集合稱為R的值域，記作ranR。例如：A＝{a,b,

9、c,d,e},B={x,y,z}R={,,,}則domRranR＝{a,b,e}={x,y}14其它常用關系:1)小于等于關系LALA＝{

10、x,y∈A且x≤y},A?R2)整除關系DADA＝{

11、x,y∈A且x

12、y},A?Z+3)包含關系R?R?＝{

13、x,y∈A且x?y},A為集合族15【例】設A＝{1,2,3,4,5},R是A上的二元關系，其定義為：當a,b∈A且a能整除b時，∈R,求R。解：R＝{<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<2,2>,<2,4>,<3,3>,<4,4>,<5,

14、5>}16【例】設A＝{1,2,3,4,5,6},R是A上的二元關系，其定義為：當a,b∈A且a和b被3除后余數(shù)相同時，∈R,求R。解：R＝{<1,1>,<1,4>,<2,2>,<2,5>,<3,3>,<3,6>,<4,4>,<4,1>,<5,5>,<5,2>,<6,6>,<6,3>}17常見的關系表示方法有：1、集合表達式2、關系矩陣3、關系圖§2關系的表示18一、集合法：關系可以表示成序偶對的集合【例】R為