二元關系和函數——理學院數學系仝輝內容提綱集合的笛卡爾積與二元關系關系的運算關系的性質關系的閉包等價關系和偏序關系函數的定義和性質函數的復合和反函數序偶定義4.1:由兩個元素x和y（允許x=y）按一定的順序排列成的二元組叫作有序對(也稱序偶),記作<x,y>(也可記作(x,y)).其中x是它的第一元素,y是它的第二元素.例如平面直角的坐標:<1,-1>,<2,0>,<1,1>,他的特性是:

當x≠y時,<x,y>≠<y,x>

<x,y>=<u,v>等充分必要條件是x=u,y=v.序偶與集合的關系,<x,y>≠<y,x>,但{x,y}={y,x}

有序n元組定義4.2:一個有序n元組(3≤n)是一個有序對,其中第一個元素是一個有序n-1元組，一個有序n元組記作＜x1,x2,…,xn,>,即

＜x1,x2,…,xn,>=<<x1,x2,…,xn-1,>,xn>

例如:<1,-1,3>,<2,4.5,0>是三元組.例如:n維空間中的點的坐標.例如:n維向量是n元組．笛卡兒積定義4.3:設A,B為集合,用A中的元素為第一元素,B中元素為第二元素，構成有序對，所有這樣的有序對組成的集合叫做A和B的笛卡爾積，記作AxB,符號化表示為

AxB={<x,y>|xAΛy

B}。例如:A={a,b},B={0,1,2},則

AxB={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>};

BxA={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}.如果A中的元素為m個元素，B中的元素為n個元素，則AxB和BxA中有mn個元素．＜x,y>AxB,則xA,yB,＜x,y>AxB,則xA或yB笛卡兒積運算具有的性質(1)若A,B中有一個空集,則它們的笛卡兒積是空集,即

xB=Ax=當A≠B且A,B都不是空集時,有

AxB≠BxA

笛卡兒積不適合交換律當A,B,C都不是空集時,有

(AxB)xC≠Ax(BxC)

笛卡兒積不適合結合律<<x,y>,z>(AxB)xC,<x,<y,z>>Ax(BxC),<x,<y,z>>(AxB)xC.笛卡兒積運算具有的性質(2)笛卡兒積運算對或運算滿足分配律,

Ax(BC)=(AxB)(AxC)

(BC)xA=(BxA)(CxA)

Ax(BC)=(AxB)(AxC)

(BC)xA=(BxA)(CxA)證明:對任意的<x,y>

<x,y>Ax(BC)

xAΛy(BC)

xAΛ(yByC)

(xAyB)(xAyC)<x,y>(AxB)<x,y>(AxC)<x,y>(AxB)(AxC)所以：Ax(BC)=(AxB)(AxC)成立.例題(1)設A={1,2},求P(A)xA

P(A)xA={,{1},{2},{1,2}}x{1,2}

={<,1>,<,2>,<{1},1>,<{1},2>,

<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>}判斷下列命題的真假若AC且BD,則有AxBCxD;(真)若AxBCxD,則有AC且BD.(假)n階笛卡兒積定義4.4設A1,A2,…,An,是集合(n2),它們的n階笛卡兒積記作A1xA2x…xAn,其中

A1xA2x…xAn＝{<x1,x2,…,xn>|x1A1,x2

A2,...,xnAn}當A1＝A2＝…＝An

＝A時可記為An例題:A={a,b,c},則

A3={<a,a,a>,<a,a,b>,<a,a,c>,<a,b,a>,<a,b,b>,<a,b,c>,<a,c,a>,<a,c,b>,<a,c,c>,…}二元關系定義4.5:如果一個集合為空集或者它的元素都是有序對,則稱這個集合是一個二元關系,一般記作R,對于二元關系R,如果<x,y>R,則記作xRy;<x,y>R,記作xRy.本書涉及二元關系，（其它n元關系不在本書之列），書中涉及的關系全為二元關系．A到B的二元關系定義4.6：設A,B為集合，AxB的任何子集所定義的二元關系稱作從A到B的二元關系，特別當A=B時,則叫做A上的二元關系.如果|A|=n,則|AxA|=n2.AxA的子集有個,每一個子集代表一個A上的關系.

其中之一是空集,稱做空關系.另外兩種就是全域關系EA和恒等關系IA.定義4.7:對任何集合A,

EA={<x,y>|xAyA}=AxA.

IA={<x,x>|xA}.

例如,A={0,1,2},則

EA={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,

<2,2>}IA={<0,0>,<1,1>,<2,2>}關系實例設A為實數集R的某個子集,則A上的小于等于關系定義為

LA={<x,y>|x,yA,xy}.

例4.4設A={a,b},R是P(A)上的包含關系,R={<x,y>|x,yP(A),xy},

則有

P(A)={,{a},{b},A}.R={<,>,<,{a}>,<,{b}>,<,A>,

<{a},{a}>,<{a},A>,<{b},{b}>,<{b},A>,<A,A>}.關系矩陣設A={x1,x2,...,xn},R是A上的關系,令

ri,j=1若xiRxj0若xiRxjri,j=r11

r12...r1n...r21

r22...r2nrn1

rn2...rnnri,j=是關系矩陣例題設A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}

的關系圖和關系矩陣為:110

000

1100

0001

00關系圖設V是頂點的集合,E是有向邊的集合,令V={x1,x2,...,xn},如果xiRxj,則有<xi,xj>E,那么G=<V,E>就是R的關系圖.例題設A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}

的關系圖和關系矩陣為:110

000

1100

0001

001243內容提綱集合的笛卡爾積與二元關系關系的運算關系的性質關系的閉包等價關系和偏序關系函數的定義和性質函數的復合和反函數關系的定義域和值域定義4.8:關系R的定義域domR,值域ranR和域fldR分別是:

domR={x|y(<x,y>R)}.

ranR={y|x(<x,y>R)}.

fldR=domRranR.例題例題4.8:下列關系都是整數集Z上的關系,分別求出它們的定義域和值域.R1={<x,y>|x,yZxy};R2={<x,y>|x,yZx2+y2=1};domR1=ranR1=Z.

R={<0,1>,<0,-1>,<1,0>,<-1,0>}

domR2=ramR2={0,1,-1}圖解方法10-110-1R2domR2ranR2逆、合成、限制和象定義4.9:設F,G為任意的關系,A為集合,則F的逆記作F-1,F-1={<x,y>|yFx};F與G的合成記作FoG={<x,y>|z（xGzzFy）};F在A上的限制記作FA={<x,y>|xFyxA};A在F下的象F[A]=ran(FA).例題設F,G是N上的關系,其定義為

F={<x,y>|x,yNy=x2};

G={<x,y>|x,yNy=x+1},

求G-1,FoG,F{1,2},F[{1,2}]解:G-1={<1,0>,<2,1>,<3,2>,...,<x+1,x>,...};z((z=x+1)y=z2)

FoG={<x,y>|x,yNy=(x+1)2}F{1,2}={<1,1>,<2,4>}F[{1,2}]=ran(F{1,2})={1,4}等式(1)定理4.1:設F,G,H是任意的關系,則有(F-1)-1=FdomF-1=ranF,ranF-1=domF;(FoG)OH=Fo(GoH);(FoG)-1=G-1oF-1證明(4)任取<x,y>,

<x,y>(FoG)-1

<y,x>(FoG)

z((<y,z>G)(<z,x>F))

z((<z,y>G-1)(<x,z>F-1))

<x,y>G-1OF-1等式(2)定理4.2設F,G,H為任意的關系,則有Fo(GH)=FoGFoH;Fo(GH)FoGFoH;(GH)Of=GoFHoF;(GH)oFGoFHoF;證明(1)取<x,y>Fo(GH)

z(<x,z>GH<z,y>F)

z((<x,z>G<x,z>H)<z,y>F)

z((<x,z>G<z,y>F)(<x,z>H<z,y>F)

<x,y>FoGFoH

<x,y>FoGFoH

n次冪定義4.10設R為A上的關系,n為自然數,則R的n次冪規定如下:R0={<x,x>|xA};Rn=Rn-1oR,n1.由上可知:RoR0=R=R0oR例題(關系圖法)設A={a,b,c,d},R={<a,b><b,a>,<b,c>,<c,d>},求R0,R1,R2,R3,R4,R5.解:abcdabcdabcdabcdR0R=R1R2=R4R3=R5例題(關系矩陣運算法)設A={a,b,c,d},R={<a,b><b,a>,<b,c>,<c,d>},求R0,R1,R2,R3,R4,R5.解:rij=ri1.r1j+ri2.r2j+ri3.r3j+ri4.r4j0+0=0;0+1=1,1+0=1,1+1=1010010100001000001001010000100000100101000010000..101001010000000001001010000100000101101000000000==.等式(3)定理4.3:設R為A上的關系,m,n是自然數,則下面的等式成立.RmoRn=Rm+n(Rm)n=Rmn證明任意給定m,對n進行歸納.(1)n=0,RmoR0=Rm=Rm+0假設RmoRn=Rm+n,則

RmoRn+1=Rmo(RnoR)=(RmoRn)oR=Rm+noR=Rm+n+1(2)n=0,(Rm)0=R0=Rm.0.假設(Rm)n=Rmn,則

(Rm)n+1=(Rm)noRm=RmnoRm=Rm(n+1)內容提綱集合的笛卡爾積與二元關系關系的運算關系的性質關系的閉包等價關系和偏序關系函數的定義和性質函數的復合和反函數關系的性質自反性反自反性對稱性反對稱性傳遞性定義自反性反自反性對稱性反對稱性傳遞性定義xA,有<x,x>RxA,有<x,x>R若<x,y>R則<y,x>R若<x,y>R,且xy,則<y,x>R若<x,y>R且<y,z>R則<x,z>R關系矩陣特點主對角線的元素全為1主對角線的元素全為0矩陣為對稱矩陣如果rij=1,且xy則rji=0關系圖特點圖中每個節點都有環圖中每個節點都沒有環如果兩個頂點之間有邊,一定是一對方向相反的邊.如果兩個頂點之間有邊,一定是一條有向邊.如果xi到xj有邊，xj到xk有邊，則xi到xk一定有邊．例題（１）設A為非空集合，A上的關系可以是自反的，反自反的，或則兩者都不是．A={1,2,3}R1={<1,1>,<2,2>,<3,3>,<1,2>}(自反)

R2={<2,3>,<3,2>}(反自反)

R3={<1,1>,<2,2>}(兩者都不是)例題（２）設A為非空集合，A上的關系可以是對稱的，反對稱的，或則兩者都是,兩者都不是．A={1,2,3}R4={<1,2>,<2,1>,<3,3>}(對稱)

R5={<1,2>,<1,3>}(反對稱)

R6={<1,1>}(兩者都是)R7={<1,2>,<2,1>,<1,3>}(兩者都不是)性質自反/反自反自反關系包含著恒等關系.即IAR.反自反關系R一定與IA不交,即IAR=如果IAR且IAR,則兩者都不是.對稱/反對稱A上的對稱關系滿足R-1=R.反對稱關系滿足RR-1IA.如果兩者都是RIA傳遞滿足RoRR例題(3)判斷下面關系的性質123123123關系演算后的性質自反性反自反性對稱性反對稱性傳遞性R-1R1R2R1R2R1-R2R1oR2運算原有性質證明(1)設R1,R2為A上的對稱關系,證明R1R2也是A上的對稱關系.證明:對任意的<x,y>,<x,y>R1R2<x,y>R1<x,y>R2<y,x>R1<y,x>R2<y,x>R1R2證明(2)R1,R2是A上的反對稱關系,則R1R2不一定是A上的反對稱關系,例如A={x1,x2},R1={<x1,x2>},R2={<x2,x1>}.

R1R2={<x1,x2>,<x2,x1>}.內容提綱集合的笛卡爾積與二元關系關系的運算關系的性質關系的閉包等價關系和偏序關系函數的定義和性質函數的復合和反函數自反閉包,對稱閉包,傳遞閉包定義4.11:設R是非空集合A上的關系,R的自反閉包(對稱閉包或傳遞閉包)是A上的關系R’,且R’滿足以下條件:R’是自反的(對稱的或傳遞的);RR’;對A上的任何包含R的自反關系(對稱或傳遞關系)R’’都有R’R’’.一般將R的自反閉包記作r(A),對稱閉包s(A),傳遞閉包t(A)例題例4.10設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},則R和r(A),s(A),t(A)的關系圖如下:abcdabcdabcdabcdRr(R)s(R)t(R)定理定理4.4:設R為非空集合A上的關系,則有r(R)=RR0;s(R)=RR-1;t(R)=RR2R3....求各種閉包R={<a,b>,<b,a>,<b,c>,<c,d>},求r(A),s(A),t(A)r(A)=RR0={<a,b>,<b,a>,<b,c>,<c,d>}{<a,a>,<b,b>,<c,c>,<d,d>}={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<c,c>,<d,d>}s(A)=RR-1={<a,b>,<b,a>,<b,c>,<c,d>}

{<b,a>,<a,b>,<c,b>,<d,c>}=

{<a,b>,<b,a>,<b,c>,<c,d>,<c,b>,<d,c>}t(A)=RR2R3={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,a>,<b,b>,<a,c>,<b,d>}{<a,b>,<a,d>,<b,a>,<b,c>}

={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}采用關系矩陣求閉包設R的關系矩陣為M,求相應的自反、對稱、傳遞閉包的矩陣為Mr，Ms，Mt，則有Mr=M+E；Ms=M+M’Mt=M+M2+M3+...E表示同階的單位矩陣,M’為M的轉置,而+均表示矩陣中對應元素的邏輯加.Mr01000100001000010000100001000011100111000110001+=Mr=Ms01000100001000001001000010000100100101001010010+=Ms=Mt01000100001000010100101010000000101101000000000++Mt=1111111100010000=內容提綱集合的笛卡爾積與二元關系關系的運算關系的性質關系的閉包等價關系和偏序關系等價關系定義４.12設R為非空集合A上的關系,如果R是自反的、對稱的和傳遞的，則稱R為A上的等價關系。對任何x，yA，如果<x,y>等價關系R，則記作xy。例題(1)例4.11:A={1,2,...,8},R={<x,y>|x,yAxy(mod3)},其中xy(mod3)為x-y被3整除.R為A上的等價關系.14725836

推廣:對任何正整數n,可以給定整數集合Z上的模n的等價關系:R={<x,y>|x,yZxy(modn)}.例題(2),相容關系在一群人的集合上,年齡相等是等價關系,而朋友關系不一定是等價關系,因為它可能不是傳遞的.一般這種自反的對稱的關系為相容關系.顯然等價關系都是相容關系.動物是按種屬分類的,”具有相同種屬”的關系是動物集合上的等價關系.集合上的恒等關系和全域關系是等價關系.等價類定義4.13:設R是非空集合A上的等價關系,對任意的xA,令[x]R={y|yAxRy},則稱為x關于R的等價類,簡稱[x]R為x關于R的等價類,簡記為[x].

14725836[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}等價類的性質(1)定理4.5:設R是非空集合A上的等價關系,對任意的x,yA,下面的結論成立.[x],且[x]A;若xRy,則[x]=[y];若xRy,則[x][y]=;.商集定義4.14:設R為非空集合A上的等價關系,以R的不交的等價類為元素的集合叫做A在R下的商集,記作A/R,即

A/R={[x]R|xA}.A/R={{1,4,7},{2,5,8},{3,6}}.

例題非空集合A上的全域關系EA是A上的等價關系,對任意xA有[x]=A,商集A/EA={A}.非空集合A上的恒等關系IA是A上的等價關系,任意xA有[x]={x},商集A/IA={{x}|xA}.在整數集合Z上模n的等價關系,其等價類是[0]={....,-2n,-n,0,n,2n,...}={nz|zZ}=Nz,.....劃分,劃分塊定義4.15:設A是非空集合,如果存在一個A的子集族π(πP(A))滿足以下條件π,π中任意兩個元素不交;π中所有元素的并集等于A;則稱π為A的一個劃分,且稱π中的元素為劃分塊.例題考慮集合A={a,b,c,d}的下列子集族{{a},{b,c},eby1d6q};(A的劃分){{a,b,c,d}};(A的劃分){{a,b},{c},{a,d}};{不是A的劃分}{,{a,b},{c,d}};{不是A的劃分}{{a},{b,c}};{不是A的劃分}R是A上的等價關系,則A/R是一個劃分,等價關系和劃分是一一對應的.例題例題4.15:設A={1,2,3},求出A上所有的等價關系.解:先求A的各種劃分:1劃分塊的,2劃分塊的,3劃分塊的.213π1213π2213π3213π4213π5求等價關系R5={<1,1>,<2,2>,<3,3>}=IAR1={<1,2>,<1,3>,<2,1>,<2,3>,<3,1>,<3,2>}IA=EA.R2={<2,3>,<3,2>}IA

R3={<1,3>,<3,1>}IA

R4={<1,2>,<2,1>}IA偏序關系(偏序)定義4.16:設R為非空集合A上的關系,如果R是自反的,反對稱的和傳遞的,則稱R為A上的偏序關系,簡稱偏序,記作.任何集合A上的恒等關系,集合的冪集P(A)上的包含關系,實數集上的小于等于關系,正整數集上的整除關系都是偏序關系.={<3,3>,<3,2>,<3,1>,<2,2>,,<2,1>,<1,1>}32,22,31偏序集定義4.17:一個集合A與A上偏序關系R一起叫做偏序集,記作<A,R>.例如<Z,R>,<P(A),R>都是偏序集.可比,蓋住定義4.18:設<A,>為偏序集,對于任意的x,yA,如果xy或者yx成立,則稱x與y是可比的,如果x<y(即xyxy),且不存在zA使得x<z<y,則稱y蓋住x.<A,>是A={1,2,