1、1,第七章 二元關(guān)系和函數(shù),2,本章主要內(nèi)容:,集合的笛卡爾積與二元關(guān)系 關(guān)系的運(yùn)算 關(guān)系的性質(zhì) 關(guān)系的閉包 等價(jià)關(guān)系和偏序關(guān)系,3,7.1 有序?qū)εc集合的笛卡兒積,定義7.1 由兩個(gè)元素x和y(允許x=y)按一定的順序排列成的二元組叫做一個(gè)有序?qū)?也稱序偶),記作,其中x是它的第一元素,y是它的第二元素。 平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)就是有序?qū)?例如,(1,1), (1,1) ,都代表坐標(biāo)系中不同的點(diǎn)。,4,有序?qū)Φ奶攸c(diǎn)： 1.當(dāng)xy時(shí),。 2.兩個(gè)有序?qū)ο嗟?即 的充分必要條件是xu且yv。,5,定義7.2 一個(gè)有序n元組(n3)是一個(gè)有序?qū)?其中第一個(gè)元素是一個(gè)有序n1元組,一個(gè)有序n元組記

2、作,即 , xn 例如,空間直角坐標(biāo)系中點(diǎn)的坐標(biāo) , 等 都是有序3元組。 n維空間中點(diǎn)的坐標(biāo)或n維向量都是有序n元組。,6,定義7.3 設(shè)A,B為集合,用A中元素為第一元素,B中元素為第二元素,構(gòu)成有序?qū)?所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積,記作AB。符號(hào)化表示為 AB(x,y)|xAyB. 例如,Aa, b ,B 0, 1, 2,則 AB ,； BA , ,。,7,如果A中有m個(gè)元素,B中有n個(gè)元素, 則AB和BA中都有多少個(gè)元素? mn個(gè) 若AB,則有 xA和yB。 若AB,則有 xA或者y B.,8,笛卡兒積運(yùn)算的性質(zhì): 1.若A,B中有一個(gè)空集,則它們的笛卡兒積是空集,

3、即 BB 2.當(dāng)AB且A,B都不是空集時(shí),有 ABBA。 所以,笛卡兒積運(yùn)算不適合交換律。 3.當(dāng)A,B,C都不是空集時(shí),有 (AB)CA(BC). 所以,笛卡兒積運(yùn)算不適合結(jié)合律。,9,4.笛卡兒積運(yùn)算對(duì)或運(yùn)算滿足分配律即 A(BC)(AB)(AC)； (BC)A (BA)(CA)； A(BC)(AB)(AC)； (BC)A (BA)(CA)。,10,證明 A(BC)(AB)(AC) 證明 對(duì)于任意的, A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (x,y)(AB)(AC). 所以 A(BC)(AB)(AC)。,11,例7.1 設(shè)A=1,2,求P(A)A 解

4、 P(A)A ,1,2,1,21,2 , ,12,例7.2 設(shè)A,B,C,D為任意集合,判斷以下等式是否成立,說明為什么。 (1) (AB)(CD)(AC)(BD)； (2) (AB)(CD)(AC)(BD)； (3) (AB)(CD)(AC)(BD)； (4) (AB) (CD) (AC) (BD)。,13,解.(1)成立.因?yàn)閷?duì)于任意的, (AB)(CD) xAByCD xAxB yCyD AC BD (AC)(BD) (2)不成立。 舉一反例如下：若AD,BC1 則有： (AB)(CD)BC, (AC)(BD)。 (3)和(4)都不成立,14,例7.3 設(shè)A,B,C,D為任意集合,判斷以

5、下命題的真假. (1)若AC且BD,則有ABCD。 (2)若ABCD,則有AC且BD. 解 (1)命題為真。請(qǐng)思考：為什么？ (2)命題為假.當(dāng)AB時(shí),或者A且B時(shí),該命題的結(jié)論是成立的。但是當(dāng)A和B之中僅有一個(gè)為時(shí),結(jié)論不一定成立,例如,令A(yù)CD,B1,這時(shí)ABCD,但BD。,15,定義7.4 設(shè)A1,A2, , An是集合(n2),它們的n階笛卡兒積,記作A1A2An,其中 AlA2An|x1Alx2A2xnAn。 例如: A=a,b,則 A3= , , , ,16,7.2 二元關(guān)系Relation,所謂二元關(guān)系就是在集合中兩個(gè)元素之間的某種相關(guān)性. 例如,甲、乙、丙三個(gè)人進(jìn)行乒乓球比賽,

6、如果任何兩個(gè)人之間都要賽一場(chǎng),那么共要賽三場(chǎng)。假設(shè)三場(chǎng)比賽的結(jié)果是乙勝甲、甲勝丙、乙勝丙,這個(gè)結(jié)果可以記作 ,其中表示x勝y。它表示了集合甲,乙,丙中元素之間的一種勝負(fù)關(guān)系.,17,例子.有A,B,C三個(gè)人和四項(xiàng)工作,已知A可以從事工作,B可以從事工作,C可以從事工作,。那么人和工作之間的對(duì)應(yīng)關(guān)系可以記作 R,。 這是人的集合A,B,C到工作的集合,之間的關(guān)系。,18,定義7.5 如果一個(gè)集合為空集或者它的元素都是有序?qū)? 則稱這個(gè)集合是一個(gè)二元關(guān)系,一般記作R。 對(duì)于二元關(guān)系R, 如果R,則記作xRy； 如果R,則記作,19,定義7.6 設(shè)A,B為集合,AB的任何子集所定義的二元關(guān)系稱作從A

7、到B的二元關(guān)系,特別當(dāng)AB時(shí),則叫做A上的二元關(guān)系。 關(guān)系RAB, R is a relation from A to B. RAA, R is a relation on A. A上有多少個(gè)不同的二元關(guān)系? |A|=n |AA|=n2 |P(AA)|=2n2 每一個(gè)子集代表一個(gè)A上的關(guān)系,共2n2個(gè)關(guān)系.,20,對(duì)于任何集合A都有3種特殊的關(guān)系: 其中之一就是空集,稱做空關(guān)系。 另外兩種就是全域關(guān)系EA和恒等關(guān)系IA。 定義7.7 對(duì)任何集合A, EAxAyAAA。 IAxA。 例如：A=0,1,2,則 EA, IA,2,2)。,21,常用的關(guān)系:小于等于關(guān)系、整除關(guān)系,例如: 設(shè)A為實(shí)數(shù)集R的某個(gè)子集,則A上的小于等于關(guān)系定義為 LAx,yAxy 設(shè)B為正整數(shù)集Z的某個(gè)子集,則B上的整除關(guān)系定義為 DBx,yBxy.,22,例如: A=4,0.5,-1,B=1,2,3,6,則,LA , , , , DB , , , .,23,例7.4 設(shè)Aa, b ,R是P(A)上的包含關(guān)系, R|x, y P(A) x y, 則有 P(A),a, b, A。 R ,.,24,有窮集A上的關(guān)系R, 可用關(guān)系矩陣和關(guān)系圖給出。 設(shè)A1,2,3,4, A上的關(guān)系 R, 。 R的關(guān)系矩陣和關(guān)系圖如圖,關(guān)系矩陣和關(guān)系圖,25,26,關(guān)系矩陣和關(guān)系圖,設(shè)V是頂點(diǎn)的集合,E是有向邊的集合,令VAx1,