第二二元關(guān)系ppt課件

1、第二章 二元關(guān)系2-1 有序?qū)εc卡氏積2-2 二元關(guān)系2-3 關(guān)系矩陣和關(guān)系圖2-4 關(guān)系的性質(zhì)2-5 二元關(guān)系的冪運算2-6 關(guān)系的閉包2-7 等價關(guān)系和劃分2-8 序關(guān)系2-1 有序?qū)εc卡氏積1. 有序?qū)?序偶)的概念2. 卡氏(笛卡兒)積3. 笛卡兒積的性質(zhì)1、序偶的概念定義定義2.1 2.1 稱稱a,a,ba,a,b為由元素為由元素a a、b b構(gòu)成的有序構(gòu)成的有序?qū)蛐蚺?，記作對或序偶，記作。其中。其中a a稱為有序?qū)Φ牡谝粋€稱為有序?qū)Φ牡谝粋€元素，元素，b b稱為第二個元素，且稱為第二個元素，且a a，b b可以一樣?？梢砸粯印ＴS多事物是成對出現(xiàn)的，而且這種成對出現(xiàn)的事物，具有一定

2、的順序。例如：上、下；左、右；34；平面上的坐標等。普通地說，由兩個具有固定次序的客體組成，來表達兩個客體之間的關(guān)系。注：有序?qū)梢钥醋魇蔷哂袃蓚€元素的集合，與普通集合不同的是有序?qū)哂写_定的次序。定理定理2.1 =2.1 =，當且僅當，當且僅當a=c,b=da=c,b=d。引理引理1 x,a=x,b1 x,a=x,b，當且僅當，當且僅當a=ba=b。引理引理2 2 設(shè)設(shè)A,BA,B是非空的集族，假設(shè)是非空的集族，假設(shè)A=B,A=B,那么那么(1)A=B ; (2) A=B(1)A=B ; (2) A=B推論推論 a ab b時，時， 引理1的證明nx,a=x,bx,a=x,b當且僅當當且僅當

3、 a=ba=b。n證明：證明：a=b a=b x,a=x,b x,a=x,bnx=a, x,a=x,bx=a, x,a=x,ba,a=a,ba,a=a,bn a=a,b a=a,b b=a b=anx xa, aa, ax,a=x,bx,a=x,b a=b a=bn x,a=x,b x,a=x,b a=b a=b# #引理2的證明引理引理2 2 設(shè)設(shè)A,BA,B是非空的集族，假設(shè)是非空的集族，假設(shè)A=B,A=B,那么那么(1)A=B ; (2) A=B(1)A=B ; (2) A=B證明證明: (1): (1)x,x,x xA A z(zz(zA Ax xz)z)z(zz(zB Bx xz)z

4、)x xBB A = B A = B(2) (2) x,x,x xAAz(zz(zA Ax xz)z)z(zz(zB Bx xz)z)x xBB A = B A = B# #定理證明n=，當且僅當，當且僅當a=c,b=da=c,b=d。n證明：證明：=a,a,b=c,c,da,a,b=c,c,dna,a,b= c,c,da,a,b= c,c,da,b=c,da,b=c,dna,a,b=c,c,d a,a,b=c,c,d a,a,b= a,a,b= c,c,dc,c,da=c a=c a=c a=cn(a,b=c,d)(a,b=c,d)(a=c) (a=c) b=d b=dn = = a=c,b

5、=d a=c,b=d。 # #推論證明n 推論: ab n證明: (反證) =a=b,與ab矛盾. #序偶的概念可推行到三元組、四元組、序偶的概念可推行到三元組、四元組、 n n元組元組: : 有序三元組有序三元組(ordered triple)(ordered triple)表示序偶表示序偶,z;,z; 有序四元組有序四元組表示序偶表示序偶,w;,w; 有序有序n n元組元組表示序偶表示序偶x1,x2,xn-,xn 1,xn 定義定義2.2 2.2 一個有序一個有序n(nn(n2)2)元組是一個有序?qū)?，它的元組是一個有序?qū)?，它的第一個元素為有序的第一個元素為有序的(n-1)(n-1)元組元組

6、，第二個元素為第二個元素為anan，記為，記為。即。即,an = ,an = 定理定理2.2 = 2.2 = 當且當且僅當僅當ai=bi, i=1,2, n. ai=bi, i=1,2, n. 有序n元組注：注：n元組有嚴厲的集合定義，但我們關(guān)注的是有序?qū)霸M有嚴厲的集合定義，但我們關(guān)注的是有序?qū)坝行蛴行騨元組的次序性，不過多討論他們的集合表示。元組的次序性，不過多討論他們的集合表示。2、卡氏積(Cartesian product)n定義2.3 設(shè)A、B為集合，稱由A中元素為第一個元素，B中元素為第二個元素的一切有序?qū)M成的集合為A與B的卡氏積(笛卡兒積),記作AB,即AB=|xAyB 。

7、 例1 設(shè)A =a,b， B =1，2，3, 求AB， BA。解：AB=,。 BA=,。 由此例可知，笛卡兒積不滿足交換律。#3、笛卡兒積的性質(zhì)設(shè)設(shè)A、B、C為恣意集合，那么笛卡兒積的運算有如下性質(zhì)：為恣意集合，那么笛卡兒積的運算有如下性質(zhì)：1A=，A=2不適宜交換律：不適宜交換律：AB BA當當A B A B時時3不適宜結(jié)合律：不適宜結(jié)合律：(AB)C A(BC)當當A B C 時時4分配律：分配律：A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 后四個式子按集合相等的概念可以證明。后四個式子按集合相等的概念可以證明。笛

8、卡兒積的性質(zhì)例 證明(B C)A=(BA) (CA) 證:在集合(BC)A中任取，那么 (BC)A x(BC)yA (xBxC)yA xByAxCyA (xByA)(xCyA) (BA)(CA) (BA)(CA)(BC)A=(BA)(CA)。#(卡氏積圖示)3、笛卡兒積的性質(zhì)(續(xù)1)5假設(shè)假設(shè)C ,那么那么 AB (AC BC) (CA CB)證證: 證證, 任取任取 AC，有，有 AC xAyC xByC BC因此，因此， AC BC。證證, 假設(shè)假設(shè)A= , 那么那么AB. 假設(shè)假設(shè)A ,C , AC BC, 取取yC ，那么有，那么有xA xAyC 已設(shè)已設(shè)yC ，故，故yC 為真為真

9、AC BC xByC xB因此，因此， AB類似可證：類似可證： AB (CA CB)。 #6設(shè)設(shè)A、B、C、D為恣意非空集合，那么為恣意非空集合，那么 (AB CD) AC BD 證明與性質(zhì)證明與性質(zhì)5的證明方法類似，從略的證明方法類似，從略3、笛卡兒積的性質(zhì)(續(xù)2)例 證明(A-B)C=(AC)-(BC)。證：證：(A-B)C x(A-B)yC xAxB yC (x AyC xB) (xAyC yC) (x AyC) (xByC) (x AyC) (xByC) (x AyC)(xByC) ACBC (AC)-(BC)所以，所以，(A-B)C=(AC)-(BC)。#n維卡氏積n定義2.4 設(shè)

10、A1,A2,An為n個集合(n2)，稱集合n|x1A1x2A2 xnAn n為n維卡氏積，記作A1 A2An ，當A1=A2=An=A時，記A生成的n維卡氏積為Ann設(shè)A1,A2,An均為有窮集合，并設(shè)|Ai|=ni, i=1,2,n，那么 |A1 A2An|=n1 n2 nnn性質(zhì)：例如nAB(CD)=(ABC)(ABD)nABC= A= B= C= .2.2 二元關(guān)系 事物之間存在著各式各樣的關(guān)系，例如，三名學(xué)生A、B、C選修、四門課，設(shè)A選和，B選，C選和，那么，學(xué)生選課的對應(yīng)關(guān)系可記作 ： R=,這個序偶的集合R反映了學(xué)生集合S=A,B,C與課程集合T=,之間的關(guān)系。關(guān)系的概念關(guān)系的運

11、算定理定義定義2.5 2.5 假設(shè)集合假設(shè)集合F F中的全體元素均為有序的中的全體元素均為有序的n(nn(n2)2)元組，那么稱元組，那么稱F F為為n n元關(guān)系。當元關(guān)系。當n=2n=2時，稱時，稱F F為二元關(guān)系為二元關(guān)系, ,簡稱為關(guān)系。簡稱為關(guān)系。對于二元關(guān)系對于二元關(guān)系F F，假設(shè)，假設(shè) F F，記作，記作 xFyxFy表示方法：表示方法：( (中綴，前綴，后綴中綴，前綴，后綴規(guī)定空集規(guī)定空集為為n n元空關(guān)系，簡稱空關(guān)系元空關(guān)系，簡稱空關(guān)系n元關(guān)系續(xù)n例1: F1=,F1是4元關(guān)系. # n例2:F2=, F2是3元關(guān)系. #n例3:R1=, R1是2元關(guān)系. # n例4:R2=,

12、 R2是2元關(guān)系. # n例5:A=,a,1, A不是關(guān)系. #關(guān)系的概念(續(xù)1)定義2.6 設(shè)A和B是兩個恣意集合，卡氏積AB的任一子集R稱為A到B的二元關(guān)系。RABRP(AB)假設(shè)|A|=m,|B|=n, 那么|AB|=mn, 故|P(AB)|=2mn即A到B不同的二元關(guān)系共有2mn個關(guān)系舉例例 設(shè)A=1，2，3，4，求A上的小于等于關(guān)系LA解：LA=|x,yAxy = , , , , , #關(guān)系舉例n設(shè)A=a1,a2, B=b,n那么A到B的二元關(guān)系共有4個:nR1=, R2=, R3=,nR4=,. nB到A的二元關(guān)系也有4個:nR5= , R6=, R7=,nR8=,. # A上的二

13、元關(guān)系A(chǔ)上的二元關(guān)系: 是AA的恣意子集R是A上的二元關(guān)系RAARP(AA) 例 設(shè)集合A有n個元素,問A上能夠的二元關(guān)系有多少個？解：集合A上的二元關(guān)系與AA的子集個數(shù)一樣。假設(shè)|A|=n，那么|AA|=n2, AA的子集個數(shù)就有2的n2次方個。所以A上不同的二元關(guān)系有2的n2次方個。 例如，集合A=a,b上的二元關(guān)系有16個關(guān)系的概念(續(xù)4)關(guān)系的概念(續(xù)3)求：集合求：集合A=a,bA=a,b上的上的1616個二元關(guān)系。個二元關(guān)系。R1= R1= ( (空關(guān)系空關(guān)系) ;) ;R2=, R3=, R4=, R5=;R2=, R3=, R4=, R5=;R6= , (R6= , (恒等關(guān)系

14、恒等關(guān)系IA)IA)，R7=, R8=,R7=, R8=,R 9 = , , R 1 0 = , , R 9 = , , R 1 0 = , , R11=,;R11=,;R12=, R13=,R12=, R13=,R14=, R15=,;R14=, R15=,;R16= , (R16= , (全域關(guān)系全域關(guān)系EA) EA) 。幾種特殊的關(guān)系稱稱EA= ( EA= ( x x A A y y A) =AA) =AA A 是是A A上的全域關(guān)系。上的全域關(guān)系。稱稱IA= ( IA= ( x x A) A) 是是A A上的恒等關(guān)系。上的恒等關(guān)系。假設(shè)假設(shè)A A是實數(shù)集或其子集，是實數(shù)集或其子集，稱稱

15、DA= (DA= (x x A A y y A A x|y) x|y) 是是A A上的整除關(guān)系。上的整除關(guān)系。稱稱LA= (LA= (x x A A y y A A x xy) y) 是是A A上的小于等上的小于等于關(guān)系。于關(guān)系。假設(shè)假設(shè)A A為恣意的集合為恣意的集合稱稱A= (A= (x xA A y yA A x x y) y) 是是P(A)P(A)上的包含上的包含關(guān)系。關(guān)系。稱稱A= (A= (x xA A y yA A x x y) y) 是是P(A)P(A)上的真包上的真包含關(guān)系含關(guān)系整除關(guān)系舉例例: A=1,2,3,4,5,6, 那么DA=, , , , , , , ,.#二元關(guān)系

16、相關(guān)概念n 定義域, 值域, 域n 逆, 合成(復(fù)合)n 限制, 象n 單根, 單值關(guān)系相關(guān)的概念定義2.7 設(shè)R為任一集合，稱domR = xy (R) 為R的定義域，稱ranR = yx (R) 為R的值域， 稱fldR = domR ranR為R的域。例：設(shè)R1=a,b,R2=a,b, R3=,解：當a,b不是有序?qū)r, R1和R2不是關(guān)系.由定義得domR1=, ranR1=, fldR1=,domR2=c,e,ranR2=d,f,fldR2=c,e,d,f,domR3=1,3,5,ranR3=2,4,6,fldR3=1,2,3,4,5,6#關(guān)系的運算定義2.8 設(shè)F,G,A為3個集合

17、，F(xiàn)的逆(inverse):稱F-1=|F(2) F與G的合成或復(fù)合(composite): FG=|z(G F)GxzyFn留意n(1) 當R中無有序?qū)r，domR,ranR,fldR均為n(2) FG的合成為逆序合成限制和像FA=|FxA為為F在在A上的限制上的限制(restriction)FA=ran(FA)為為A在在F下的像下的像FA=y|x(xA xRy) 單根假設(shè)對于恣意的假設(shè)對于恣意的yranF,獨一地存在著獨一地存在著xdomF, 使得使得F，那么稱，那么稱F是單根是單根(single rooted)的的y( yran F !x( xdomF xFy) )(yran F)(!x

18、domF)(xFy) !表示表示“存在獨一的存在獨一的單值(single valued)n假設(shè)對于恣意的xdomF,獨一地存在著yranF，使得F，那么稱F是單值的n x( xdomF !y( yran F xFy) (xdomF)(!yran F)(xFy)舉例設(shè)A=a,b,c,d, B=a,b, R=, F=, , G=,，求(1) A-1,B-1,R-1. (2) BR-1, GB, GR, RG. (3) F a, F a, F a,a, F-1 a.(4) Fa, Fa,a, F-1a, F-1a解:(1) A-1=, B-1=,R-1=,.(2) BR-1=, GB=, GR=,

19、RG=.(3) F a=,F a=, F a,a=F, F-1 a=.(4) Fa=b,a, Fa,a=b,a,a,a, F-1a= , F-1a=a#n定理2.3 定義域和值域相關(guān)的定理n定理2.4逆的定義域和值域相關(guān)定理n定理2.5合成的結(jié)合律n定理2.6合成相關(guān)的分配律n定理2.7逆合成定理n定理2.8限制相關(guān)的定理n定理2.9像相關(guān)的定理定理定理2.3 設(shè)設(shè)F,G為二集合，那么為二集合，那么dom(FG) = domFdomG; ran(FG) = ranFranG; dom(FG) domFdomG;ran(FG) ranFranG; domFdomG dom(F G);ranFra

20、nG ran(F G).定理2.3的證明證：dom(FG) = domFdomG證明：x, xdom(FG)y( FG)y( F)(G)y( F) y(G)xdom(F) xdom(G)x (dom(F) dom(G) dom(FG) = domFdomG#證：ran(FG) ranFranG證明：y, yran(FG)x( FG)x(FG)x(F)x(G)(P7)yran(F)yran(G)y(ranF ranG) ran(FG) ranFranG#定理2.3的證明(續(xù))證：domFdomG dom(F G)證明：x, x(domF-domG)(xdomF)(xdomG)y(F)z(G) y

21、(F-G)x dom(F-G) domFdomG dom(F G)定理2.3的證明(續(xù))逆的定義域和值域相關(guān)定理定理2.4 設(shè)F為任一集合，那么domF-1=ranF;ranF-1=domF;(F-1)-1F,當F為關(guān)系時，等號成立定理2.4(1)的證明(1) 證明: x, xdomF-1yF-1yFxranFdomF-1=ranF#定理2.4(3)的證明(3) (F-1)-1F, 當F是關(guān)系時, 等號成立.證明: (1) 設(shè)F是關(guān)系, 那么,(F-1)-1 x(F-1)-1y yF-1xxFy.這時(F-1)-1= F. 當F不是關(guān)系時,(F-1)-1F, 例如, 設(shè)F=,a, 那么F-1=

22、, (F-1)-1= F(F-1)-1F. #合成運算的結(jié)合律定理定理2.5 設(shè)設(shè)R1,R2,R3為三個集合，那么為三個集合，那么(R1 R2)R3 = R1(R2R3)證明：證明： , (R1 R2)R3 z(R3(R1 R2)z(R3 t(R2 R1)z t(R3R2 R1)t(z (R3R2 R1)t(R2 R3 R1) R1 (R2 R3)(R1 R2)R3 = R1(R2R3)#xyztR3R2R1合成運算的分配律定理定理2.6設(shè)設(shè)R1,R2,R3為三個集合，那么為三個集合，那么R1(R2 R3)=R1R2 R1R3;(R1R2)R3 =R1R3R2R3;R1(R2R3) R1R2 R1R3;(R1R2)R3 R1R3 R2R3.分配律的證明R1(R2 R3)=R1R2 R1R3證明： , R1(R2 R3)z(R2 R3)R1)z(R2R3)R1)z(R2 R1) (R3R1)z(R2 R1) z(R3R1) R1R2 R1R3(R1R2 R1R3) R1(R2 R3)=R1R2 R1R3#分配律的證明(續(xù))R1(R2R3) R1R2 R1R3證明：, R1(R2R3)z(R2R3)R1)z(R2 R3)R1)z(R2 R1) (R3R1)z(R2 R1)