關(guān)系及其性質(zhì)

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

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

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

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

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

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

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

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

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