1、 第二章第二章 二元關系二元關系 1 二元關系及其表示形式二元關系及其表示形式 2 二元關系的基本類型與判定方法二元關系的基本類型與判定方法 3 等價關系、相容關系和偏序關系等價關系、相容關系和偏序關系 4復合關系、逆關系和關系的閉包運算復合關系、逆關系和關系的閉包運算2.1 二元關系及其表示形式二元關系及其表示形式 相關相關 :按照某種規則，確定二個對象或多個對象之間有關系，稱這二個對象或多個對象是相關的。注意:相關性與指定的規則有關。 (1)撲克牌中的方塊與梅花 同花關系：不相關； 同點關系：相關 (2)父子二人 同輩關系：不相關； 父子關系：相關2.1.1、序言：、序言： 關系（相關）關

2、系（相關）注： 二元關系：二個對象之間的關系 多元關系：多個對象之間的關系 多元關系常化成二元關系來研究無序的二元關系：方塊與梅花，誰在前，誰在后都還是同點的。有序的二元關系：父子關系，不能交換父與子的次序又如: （1） 偶數，與是無序的 用，表示無序對 （2），與是有序的二元關系，叫作相關 于，記成，用（，）表示有序對 （3）無序的二元關系可用有序的二元關系表示 即（，）與（，）都屬于這種二元關系有序對有序對 ：設有二個集合與，中任取元素，中任取元素，與建立一種對應關系，記為（，），總是把中元素寫在前面，中元素寫在后面，稱（，）為有序對。 有序對的集合（，），b稱為對的直交積，記為，又稱叉積

3、，又稱叉積，笛笛卡兒卡兒（DescartesDescartes）乘積乘積。注：，不滿足交換律，也不存在結合律！笛卡兒積滿足分配律：（對， ）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）的證明：對（，）（） 且 ， （，），（，） （，）（）（） 即得（）（）（） 其次，對（，）（）（） （，）而（，）（） ，而 ， （，）（） 即得（）（）（） 因此，（）（）（）的幾何意義： 設，均為實閉區間則有序對（，），是平面上一個點（1）表示矩形區域，（2）應為矩形區域， 注： （1）當且僅當時，是正方形區域 （2）由于也是集合，它應滿足集合的一切性質 按照某種規定，定義了一個有

4、序對（，）的集合，其中，稱為到的一個二元關系。(顯然 R AB，即：即：AB的任意一個子集合都是的任意一個子集合都是A到到B的一的一個二元關系！個二元關系！)注意: 二元關系是指滿足某規律的有序對的全體。例：（,）,R, 其中R讀作相關于。二元關系的二元關系的 前域前域 和值域：若和值域：若R是是A到到B的二元關系的二元關系 前域前域： domR=x|（x，y）R 值域值域： ranR=y|（x，y）R空關系空關系 和和 全域關系：全域關系： （其他一般的二元關系？）（其他一般的二元關系？） 空關系：空關系： 全域關系：全域關系： AB 當時，是到的二元關系，稱為上的上的二元關系二元關系。（A

5、到A的二元關系）例：（，） |，是自然數集上的二元關系。（稱為“整除關系”）2.1.3 二元關系的幾種表示方法二元關系的表示二元關系的表示：因為，二元關系本身也是集合，也可用窮舉法，描述法來表示，還可用表格、圖示、矩陣法表示。例如： 張三，李四，王五，趙六 米，跳高，鉛球，足球，跨欄窮舉法表示： （張三，鉛球），（張三，足球）， （李四，米），（李四，跳高）， （王五，跨欄），（趙六，米）是運動會的報名表。*二元關系的表示：（1 ）集合法集合法 (窮舉法、描述法窮舉法、描述法 )（張三，鉛球），（張三，足球），（李四，米），（李四，跳高），（王五，跨欄），（趙六，米）是運動會的報名表，（2）表

6、格法用表格表示一目了然（3）圖示法 用字母數字來代替這些元素 a，b，c，d，1，2，3，4，5關系圖，直觀！(a, 3), (a, 4), (b, ), (b, 2),（c, 5),（d, 1）（4）矩陣法： 把，集合內元素排好序: 若（，），稱為恒等關系，常用 IA表示。說明：對于一個給定的有限集合，其上的恒等關系 IA是唯一確定的。而且，恒等關系一定是A上的上的。例：A=1，2，3，4上的恒等關系為： IA =(1,1), (2,2), (3,3), (4,4)2.2 二元關系的基本類型與判定 設是上的二元關系， （1） 若對任意aA，(a,a)，則稱為A上的自反關系。 自反的二元關系的

7、關系矩陣對角元均為，即ii （，）。 （2）若對任意aA,(a,a) ，則稱為A上的反自反關系。 的關系矩陣對角元素均為，即ii （i=1，2，3，n）2.2.1 二元關系的基本類型自反關系任意(a,a) R反自反關系任意(a,a) R既不是自反的，也不是既不是自反的，也不是反自反的二元關系！反自反的二元關系！注意注意：不是自反的不一定是反自反的，不是反自反的也不一定是自反的。自反性與反自及性是互斥的，但不互補。 如下圖： 對稱關系與反對稱關系對稱關系與反對稱關系 若（，），則有（，），則稱這樣的二元關系為對稱關系。此時的相關矩陣是對稱矩陣，即ijji 若（a,b） ,，則有（，） ，則稱這樣

8、的二元關系為反對稱關系。此時的關系矩陣滿足ijji0（）對稱關系若(a,b) R則(b, a) R（ab）反對稱關系若(a,b) R則(b, a) R（ab）既不是對稱的，也不是既不是對稱的，也不是反對稱的二元關系！反對稱的二元關系！注意注意：對稱與反對稱,既不互斥，又不互補。即:不是對稱的，不一定是反對稱的；反之依然。 如下圖： （5）傳遞關系 設R是A上的二元關系，若滿足當(a，b)R 且 (b，c)時，有(a，c)，則稱這樣的為A上傳遞關系。 例: 若A=1,2,3,4,下面哪個是A上的傳遞關系? R1=(1,2); R2=(1,2),(2,3),(1,3) R3=(1,1),(2,2)

9、; R4=(1,2),(2,3),(3,4),(3,1) R5=AA二元關系的性質二元關系的性質：對應于關系圖，有：（1）自反關系：每個頂點都有自回路，（2）反自反關系：每個頂點都沒有自回路；（3）對稱關系：任意兩個頂點間或沒有邊，或有兩條相向邊；（4）反對稱關系：任二頂點至多只有一條有向邊；（5）傳遞關系：若到有邊，到有邊， 則到必有邊。 思考思考 那么，它們的那么，它們的關系矩陣又有什么特點關系矩陣又有什么特點？例：1（，）， ， 是自反的，rii=1; 不是對稱的，(1,2) R1,而(2,1) R1 是反對稱的，是傳遞的。 注：將改為，則無自反性，且是反自反的。例：2（，）整除， 是自

10、反的，不是對稱的，是反對稱的，是可傳遞的。例：3（1，2）12，1，2(). 其中()是的冪集。 3是自反的，不是對稱的，是反對稱的，是傳遞的。 注：若改為，則無自反性。例：4( a, b ) | a+b=偶數，a, 4是自反的，對稱的，傳遞的， 因偶，偶， 則（）（）偶數。 所以, 4是傳遞的! 例：5(a,), b 互素，b 5 是 對稱的，但不是自反的，也無傳遞性。 1）定義法定義法：驗證：若（a，b）R 且（b，c）是否都都有（a，c）。有一個例外就不是！2）矩陣法矩陣法： 方法方法1：若AR=（aij），B=A2=（bij），則R可傳遞當且僅當 bij=1時必有aij=1。其中 方法

11、方法2：對于關系矩陣AR中的每一個每一個aij=1作如下操作：將AR中的第j行元素對應加（布爾加）到第i行元素上，若操作后矩陣無變化，則R是可傳遞的；否則，R不是可傳遞的。）（kjiknkijaab1例見教材P30 (例2.6，2.7，2.8） 2.3 等價關系、相容關系 和偏序關系 2.3.1 等價關系 上的二元關系, 如果是 (1)自反的；(2)對稱的；(3) 傳遞的， 則稱為（A上的）等價關系, 若(,)則稱與等價，記作aRb (或）。 2.3.2 等價關系的特征2、等價關系的矩陣表示 按等價關系來調整有限集中元素的順序可使等價關系的矩陣表示的對角線上有若干個小方陣，這些小方正的元素都為

12、1 1000000010000000110000011000000011100001110000111例如1、等價關系的表格及圖形表示（p34，p35) 2.3.3 等價類和商集1 1、等價類、等價類:若R是A上的等價關系，aA，由中的所有與a等價的元素構成的集合，稱為a的等價類。a的等價類記為aR， 即 aR=x| xA且aRx注：注：等價關系把的元素分為若干類，各類之間沒有公共元素。 把集合分為若干非空子集1,2,An滿足：（1）當時, ij（2）A，使i（=1，2，n）, 即:niiAA1則集合Pr()1,2,n稱為的一個劃分劃分。 2.3.4 2.3.4 集合的劃分集合的劃分定理定理1

13、：上的等價關系確定了A的一種劃分; 反之,給定了集合的任一種劃分，也總可以找到上的一個等價關系。注：（）Pr（）（）當且僅當 Pr(） ， （）非空時Pr（）P（）P（）（的冪集）時， P（） 例：例： 張撲克 1（，）撲克與同花 2（，）撲克與同點 則: 1把分為四類同花類， 2把分為類同點類。例：設例：設，（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，）則是等價關系是等價關系，但不直觀，用關系圖表示。 三個不連通的圖三個不連通的圖 二元關系R是自反的，對稱的，傳遞的，且把分成了三個等價類，A/R， 商集的元素個數（即在下的等價類

14、個數）稱為的秩.2、等價關系R將A分成若干等價類，每個類選個代表組成新的集合稱為A關于R的商集，表示為A/R。 即: 以集合A上的等價關系R確定的所有互不相同的等價類作為元素而構成的集合, 稱為A關于等價關系R的商集.例：在上例中 A/RR ，R ，R 例例: : 設Aa,b,c,d，給定1,2,3,4,5,6,如下：1=a,b,c,d 2=a,b,c,d 3=a,a,b,c,d 4=a,b,c 5= ,a,b,c,d 6=a,a,b,c,d 則1和2是A的劃分，其它都不是A的劃分。因為3中的子集a和a,b,c,d有交，4A，5中含有空集，而6根本不是A的子集族。 例例4 4： （，） （mo

15、d ），是整數集合上模同余的二元關系. 證明R是等價關系。證明：由于當（）時,（）(1)因 （）， 自反性(2)若（），則（）對稱性(3)若（），（），則 （）（）（） 滿足傳遞性,故是等價關系商集： I/R R，R ，R 其中 R ， R ， R ，小結： 給定集合A上的一個等價關系總可以通過尋求互不相同的等價類找到集合A的一個劃分； 反之反之，若給定了集合A的一個劃分，若指定位于同一個子集中的兩個元素是相關的，則這個關系一定是等價關系。 簡言之，等價關系與劃分可以相互確定。 上的二元關系，若是自反的，對稱的，稱為A上的相容關系。注注：等價關系必然是相容關系。*2.3.5 相容關系 定理：設

16、C是集合A的一個覆蓋，設R為A上的二元關系，其定義為Rba),(當且僅當元素ba,屬于同一覆蓋快，則R是A上的相容關系。我們可記上述定理中的由C確定的相容關系為R=R(C)。 若R是非空集合上的相容關系，B是相容類，在差集A-B中沒有一個元素能和B中所有元素都是相關的，稱B是由相容關系R產生的一個最大相容類。例：課本P40 最大相容類求法：課本P40-41 （1）畫出（簡化的）相容關系圖。 （2）找出所有互不相同的最大完全多邊形。 最大完全多邊形：孤立點、懸掛邊、三邊形、完全四邊形、完全五邊形. 由所有最大相容類所構成的集合稱為集合A上的相容關系R所確定的完全覆蓋，記為CR(A).例、已知集合

17、A=129，134，345，275，347，348，當a，bA，且a，b至少有一個數碼相同時（a，b）R，求R的所有最大相容類。 解：易知該二元關系為相容關系。其次，畫出（簡化的）關系圖。最后，在圖中找出所有最大的完全多邊形，分別以這些最大的完全多邊形的頂點作為元素構成的集合即為所求。R的所有最大相容類為（4個）：129，134，129，275，345，275，347，134，345，347，348小結： 給定集合A上的一個相容關系總可以通過尋求最大相容類找到集合A的一個完全覆蓋；反之，若給定了集合A的一個完全覆蓋，若指定位于同一個子集中的兩個元素是相關的，則這個關系一定是相容關系。 簡言之簡

18、言之，相容關系與完全覆蓋可以相互確定。 2.3.8 偏序關系 設是上的二元關系，如果滿足：(1) 自反的； (2）反對稱的；(3) 傳遞的,則稱是上的偏序關系（半序關系）。例：， ， 1（，）， 2（，）|， 3（1，2）|12，1，2P()注：（1）用矩陣表示偏序關系，不能明顯看到二元關系的特征。（2）用簡化的關系圖表示較適合。 簡化的關系圖： (1)自反性：每個頂點都有自回路，省去。 (2)反對稱性：兩個頂點間只可能有一個箭頭 從左右，或從下上的方向 從小到大安置頂點，可省略箭頭。 (3)傳遞性：由于有（a,b),(b,c)R,則(a,c)R 故只畫（a,b),(b,c)對應的邊,省略邊(

19、a,c)。HasseHasse圖圖（哈斯圖） 設是上的一個偏序關系，如果，則將畫在下面，且不，使，(此時此時也稱也稱b b是是a a的蓋住元素的蓋住元素, , 或稱或稱a a被被b b蓋蓋住住)，則，間用直線連接。符合簡化的關系圖的繪制，稱這樣得到的關系圖為哈斯圖。例中: 偏序關系R1的哈斯圖如右：R1哈斯圖的畫法：哈斯圖的畫法：1）確定最底層元素（均為極小元！即不是蓋住元素的元素不是蓋住元素的元素）2）第i層是第i-1層元的蓋住元素，層層向上。3）相鄰層的頂點根據蓋住關系進行連線。4）檢查有無錯漏連線。畫哈斯圖時的注意事項：畫哈斯圖時的注意事項：1）圖中不應該出現三角形。2）圖中不應該出現水

20、平線。3）應盡量減少線的交叉，使圖清晰。例題: 哈斯圖的畫法已知A=1,2,3,4,5,6,8,10,12,16,24, R是A上的整除關系. 第五層第四層第三層第二層第一層 上偏序關系，如果，都有，或，則稱為上的全序關系。注：（1）全序的含義：中每兩個元素均能比大小，即任何兩個元素都相關。（2）偏序則是部分有序。（3）“小于或等于”關系1是全序，“整除”關系 2和“包含于”關系3都是偏序。在整除關系2中，,，,，都排成了序，但與，與，與等在整除的意義上來說無法排出大小來。 集合及上的一個偏序關系組成的二元組（，）稱為偏序集，也記之為（，）。注： 同一集合上的兩個不同的偏序關系，可構成多個偏序

21、集， 如前例1和2都定義在 ，上，其中1是小于或等于關系，2是整除關系，但（,1）與(,2）是不一樣的偏序集。 若偏序集（，）的偏序關系是上的全序關系，則稱（，）為全序集。 （，1）是全序集。顯然，全序集是偏序集的特例。又如：（，）實數全體，在下是全序集。平面上點集，也可以規定一種，模長大的大，模長相等的情況下，以幅角的大小來比大小，因此，平面上點集也是全序集。（，）當然也是全序集。注:實數全體，平面點集是無法用哈斯圖表示的。一般來說，對有限集用哈斯圖比較好，對可列集只能示意一下，對不可列無限集是沒法表示的，因為任二個數之間一定還有別的數。 設（，）是偏序集，是的子集合，若（，）是全序集，則稱

22、為（，）中的鏈。 當是有限集時，的基數稱為鏈長。例： 在上例哈斯圖（，2）中，取11，2，4，8，2|（整除），則 （1，2）是全序關系，1是偏序集（，|）中鏈長為的鏈。 2，3， 4，5，也都是（，|）中的鏈。 設（，）為偏序集，是的子集合，且對，（）,都有（，）且（，），則稱為（，）中的反鏈。 當為有限集時，為反鏈的長度。注： 反鏈中的元素都互不相關。反鏈中的元素都互不相關。例如：，2是整除關系，在（，2）中，1， 12， 23，3都是反鏈。 設（A，）是偏序集，若，且在中找不到一個元素（），使（），則稱為中的極大元（極小元）。例：（，|）是偏序集，|是整除關系， ，則 中極大元：， 中極

23、小元：，注注1 1：極大元，極小元必須是子集中的元素。注注2 2：極大元，極小元并不要求唯一，且同一元素，可以既是極大元，又是極小元，如，。 設（A，）是偏序集，若存在某個，對都有(或），則稱為的最大元（最小元）。例：例：上例，其哈斯圖如下： 子集中是不存在最大元（最小元）的。注： 最大元（最小元）本身應屬于子集，且與中任一元素都有關系。 設（A，）是偏序集，BA，若A，對 B都有（或）稱為B的上界（下界）。注：（1）上例中，無最大元，但存在的上界。（2）無最小元，1是的下界（3）最大（?。┤舸嬖冢瑒t是的一個上（下）界（4）上（下）界可以不唯一，也可以不存在 設（A，）是偏序集，BA，若是B的

24、一個上界（下界），而對任意B的上界（下界）b，都有ab（或ba），稱是B的上確界（下確界）。注注： 上確界：最小上界 下確界：最大下界 如果存在上/下確界，則上/下確界一定是唯一的。 存在上/下界，但不一定存在上/下確界。例：試求出上面兩個哈斯圖中的最大例：試求出上面兩個哈斯圖中的最大/小、極大小、極大/小元素，以小元素，以及左圖中子集及左圖中子集2，3，4的上的上/下界以及上下界以及上/下確界。下確界。2.4 復合關系、逆關系、復合關系、逆關系、 和關系的閉包運算和關系的閉包運算2.4.2.4.1 1 復合關系復合關系復合關系復合關系：若R是A到B的二元關系，S是B到C的二元關系，復合關系的

25、求法復合關系的求法：（1） 關系圖法：RS是由從A到C的所有通路兩端點元素構成的有序對作為元素的集合。（2）矩陣法：設R、S的關系矩陣分別為MR、MS， 則： MRS=MR*MS例：課本P48-50易見RS為A到C的二元關系。),( ,),( ,B| ),(ScbRbabcaSRR與S復合記為RS，其定義為顯然： 若1和2是到的二元關系，則（1）12(,b)|(a,b)1或 (,)2（2）12(,b)|(a,b)1且(,)2 （3）1-2(,b)|(a,b)1 但 (a,b) 2 （5）12(a,b)|(a,b)12 但(a,b)12逆關系逆關系 ：若R是A到B的二元關系，則稱 =（b，a）|

26、（a，b）R 是R的逆關系，即B到A的二元關系。例：設A=1，2，3，4，B=x，y，z R=（1，x），（1，y），（2，z）則R的逆關系為： =（x，1），（y，1），（z，2） 顯然，它是一個B到A的二元關系。2.4.2.4.2 2 逆關系逆關系R的逆關系也常常記為1-R逆關系的求法：（1）集合法：有序對元素前后調換位置。（2）矩陣法：矩陣轉置。（3）關系圖：每條有向邊取反向。2.4.2.4.3 3 關系的閉包運算關系的閉包運算 設R是A上的關系，我們希望R具有某些有用的性質，比如說自反性。如果R不具有自反性，我們通過在R中添加一部分有序對來改造R，得到新的關系R ，使得R具有自反性。但

27、又不希望R與R相差太多，換句話說，添加的有序對要盡可能的少。滿足這些要求的R就稱為R的自反閉包自反閉包。通過添加有序對來構造的閉包除自反閉包外還有對稱閉包對稱閉包和傳遞閉包傳遞閉包。 設R是非空集合A上的關系，若存在A上的二元關系R同時滿足下面兩個條件：（1）R是自反的（對稱的或傳遞的）（2）R R（3）對A上任何包含R的自反（對稱或傳遞）關系R有R R。 則稱R是R在A上的自反閉包自反閉包（對稱閉包或傳遞閉包) 一般將R的自反閉包記作r(R)，對稱閉包記作s(R)，傳遞閉包記作t(R)。1iiRniiR1 如果關系R是自反的和對稱的，那么經過求閉包的運算以后所得到的關系仍就是自反的和對稱的。

28、但是對于傳遞的關系則不然。它的自反閉包仍舊保持傳遞性，而對稱閉包就有可能失去傳遞性。 例如A=1，2，3，R=(2, 3)是A上的傳遞關系， R的對稱閉包 s(R)=s(t(R)=(2, 3), (3, 2), 而 t(s(R)= (2, 3), (3,2), (2,2), (3,3) , 顯然s(R)不再是A上的傳遞關系。從這里可以看出，如果計算關系R的自反、對稱、傳遞的閉包，為了不失去傳遞性，傳遞閉包運算應該放在對稱閉包運算的后邊，若令tsr(R)表示R的自反、對稱、傳遞閉包，我們能證明 tsr(R)=t(s(r(R) 例：例：若R是對稱的，則Rn也是對稱的，其中n是任何正整數。證明：證明

29、：用歸納法用歸納法。 (1)當n=1，R1=R,顯然是對稱的。 當n=2時，若(x, y) R2, 由復合關系的定義知: 必存在zA,使得(x, z)R且(z, y)R,又因R是對稱的,所以(y, z) R且 (z,x) R. 再有由復合關系的定義知: (y, x) R2. 所以R2也是對稱的.(2) 假設Rk是對稱的，則對任意的(x,y)Rk+1,由復合關系的定義知: 必存在元素t , 使得: (x,t)Rk且(t,y)R又因為Rk, R均為對稱的, 所以: (y,t) R 且 (t,x) Rk再由復合關系的定義知: (y,x)R.Rk, 即 (y,x)R1+k = Rk+1所以Rk+1是對稱的。綜上(1)(2),由歸納法,命題得證。定理定理： 設R是非空集合A上的關系，（1）若R是自反的，則s(R)與t(R)也是自反的。（2）若R是對稱的，則r(R)與t(R)也是對稱的。（3）若R是傳遞的，則r(R)是傳遞的。 證：證： 只證（2），其余留作練習。 由于R是A上的對稱關系，所以R=R-1，同時IA=IA-1。 得：(R