關系及其性質(zhì)

1、,,,下面研究與笛卡兒積密切相關的一個重要概念 ——關系。所謂二元關系即集合中兩個元素之間的某種相關性。例如：甲、乙、丙3個人進行乒乓球比賽，如果任何兩人之間都要賽一場，那么共要賽三場。假設三場比賽的結(jié)果是乙勝甲、甲勝丙、乙勝丙，這個結(jié)果可以記做{(乙,甲),(甲,丙),(乙,丙)}，

2、其中(x,y)表示x勝y。 這個集合表示了集合{甲，乙，丙}中元素之間的一種勝負關系。,第5章 關系5.1 關系及其性質(zhì)5.2 n元關系及其應用5.3 關系的表示5.4 關系的閉包5.5 等價關系基礎5.6 偏序,5.1 關系及其性質(zhì),,5.1 關系及其性質(zhì),,5.1.1引言,剛才的例子： {(乙,甲),(甲,丙),(乙,丙)}，其中(x,y)表示x勝y。

3、這個集合表示了集合{甲，乙，丙}中元素之間的一種勝負關系。,令A= {甲，乙，丙}，則A×A=？,{(甲,甲),(甲,乙),(甲,丙),(乙,甲),(乙,乙),(乙,丙),(丙,甲),(丙,乙),(丙,丙)},可見，上者是下者的一個子集,Def 二元關系：設A和B是集合，稱A×B的子集為從A到B的二元關系。,5.1.1引言,若記某二元關系為R，則有序?qū)?a,b)?R，記作aRb，稱a與b有關系R。,例1 選修關系

4、 例2 城市歸屬關系 （自看）,5.1 關系及其性質(zhì),,{(1,1),(2,4),(-2,4),(3,9)}是集合{1,2,-2,3}到集合{1,4,9}的一個二元關系，由于滿足對任意x都有唯一的y與之配對，因此這種關系可以看作函數(shù)。,5.1 關系及其性質(zhì),Def 關系：對集合A，稱從A到A的二元關系為集合A的關系。——即A×A的子集,5.1.3集合的關系,例4 設A是集合{1,2,3,4},寫出A上的

5、關系R={(a,b)|a整除b}？,解 R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)},例6 n元集上可定義多少個關系？,解 即問A×A有多少個子集，,5.1 關系及其性質(zhì),,,,設R是A上的關系，R的性質(zhì)主要有以下5種：1）自反性2）反自反性3）對稱性4）反對稱性5）傳遞性,,5.1.4 關系的性質(zhì),補充內(nèi)容,5.1.4 關系的性質(zhì),

6、,,1）自反性,,判斷以下關系是否是自反的？Eg {(1,1),(1,2),(2,2),(3,3)}Eg 正整數(shù)集合上的“整除”關系,,,2）反自反性,,判斷以下關系是否是反自反的？Eg 對于集合{1,2,3}上的關系{(1,2),(1,3),(2,2),(2,3)}Eg 集合的“真包含”關系,5.1.4 關系的性質(zhì),,,3）對稱性,,判斷以下關系是否是對稱的？Eg 對于集合{1,2,3}上的關系{(1,2),(2,1)

7、,(2,2),(3,3)}Eg 人類的“朋友”關系,5.1.4 關系的性質(zhì),,,4）反對稱性,,判斷以下關系是否是反對稱的？Eg {(1,1),(1,2),(2,2),(3,3)}Eg 正整數(shù)集合上的“整除”關系,5.1.4 關系的性質(zhì),5）傳遞性,判斷以下關系是否是傳遞的？Eg {(1,1),(1,2),(2,3),(1,3)}Eg 實數(shù)集合上的“小于”關系Eg 人類的“朋友”關系,5.1.4 關系的性質(zhì),,

8、自反、反對稱、傳遞,反自反、對稱,對稱、反對稱、傳遞,對稱,反自反、反對稱、傳遞,對稱、反對稱、傳遞,反自反,5.1.4 關系的性質(zhì),5.1 關系及其性質(zhì),,5.1.5 關系的組合,對從A到B的兩個關系R、S，考慮以下表達式代表什么意思？,R∪S=？R∩S=？R-S=?,若給定A={學校的所有學生}，B={學校的所有課程}，R={(a,b)|學生a選了課程b}，S={(a,b)|學生a的必修課包括b}，重新考察上述表達

9、式的意義？,,,關系的組合方式之一,若關系R={(a,b)|學生a選了課程b}， 關系S={(b,c)|課程b在教室c}，則關系P={(a,c)|學生a在教室c上課}與上面有什么聯(lián)系呢？,5.1.5 關系的組合,關系的另一種組合方式,,關系的合成,Def 關系F與G的合成 F?G={(x,y)|?z(xGz?zFy)}Eg,5.1.5 關系的組合,Eg 設F、G是N上的關系，其定義為,Eg 設