離散數(shù)學(xué)-第四章二元關(guān)系和函數(shù)

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

當(dāng)x≠y時(shí),<x,y>≠<y,x>

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

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

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

例如:<1,-1,3>,<2,4.5,0>是三元組.例如:n維空間中的點(diǎn)的坐標(biāo).例如:n維向量是n元組．笛卡兒積定義4.3:設(shè)A,B為集合,用A中的元素為第一元素,B中元素為第二元素，構(gòu)成有序?qū)?，所有這樣的有序?qū)M成的集合叫做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個(gè)元素，B中的元素為n個(gè)元素，則AxB和BxA中有mn個(gè)元素．＜x,y>AxB,則xA,yB,＜x,y>AxB,則xA或yB笛卡兒積運(yùn)算具有的性質(zhì)(1)若A,B中有一個(gè)空集,則它們的笛卡兒積是空集,即

xB=Ax=當(dāng)A≠B且A,B都不是空集時(shí),有

AxB≠BxA

笛卡兒積不適合交換律當(dāng)A,B,C都不是空集時(shí),有

(AxB)xC≠Ax(BxC)

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

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)設(shè)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設(shè)A1,A2,…,An,是集合(n2),它們的n階笛卡兒積記作A1xA2x…xAn,其中

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

A2,...,xnAn}當(dāng)A1＝A2＝…＝An

＝A時(shí)可記為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>,…}二元關(guān)系定義4.5:如果一個(gè)集合為空集或者它的元素都是有序?qū)?則稱這個(gè)集合是一個(gè)二元關(guān)系,一般記作R,對于二元關(guān)系R,如果<x,y>R,則記作xRy;<x,y>R,記作xRy.本書涉及二元關(guān)系，（其它n元關(guān)系不在本書之列），書中涉及的關(guān)系全為二元關(guān)系．A到B的二元關(guān)系定義4.6：設(shè)A,B為集合，AxB的任何子集所定義的二元關(guān)系稱作從A到B的二元關(guān)系，特別當(dāng)A=B時(shí),則叫做A上的二元關(guān)系.如果|A|=n,則|AxA|=n2.AxA的子集有個(gè),每一個(gè)子集代表一個(gè)A上的關(guān)系.

其中之一是空集,稱做空關(guān)系.另外兩種就是全域關(guān)系EA和恒等關(guān)系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>}關(guān)系實(shí)例設(shè)A為實(shí)數(shù)集R的某個(gè)子集,則A上的小于等于關(guān)系定義為

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

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

則有

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

<{a},{a}>,<{a},A>,<,>,<,A>,<A,A>}.關(guān)系矩陣設(shè)A={x1,x2,...,xn},R是A上的關(guān)系,令

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

r12...r1n...r21

r22...r2nrn1

rn2...rnnri,j=是關(guān)系矩陣?yán)}設(shè)A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}

的關(guān)系圖和關(guān)系矩陣為:110

000

1100

0001

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

的關(guān)系圖和關(guān)系矩陣為:110

000

1100

0001

001243內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)關(guān)系的定義域和值域定義4.8:關(guān)系R的定義域domR,值域ranR和域fldR分別是:

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

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

fldR=domRranR.例題例題4.8:下列關(guān)系都是整數(shù)集Z上的關(guān)系,分別求出它們的定義域和值域.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:設(shè)F,G為任意的關(guān)系,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).例題設(shè)F,G是N上的關(guā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:設(shè)F,G,H是任意的關(guān)系,則有(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設(shè)F,G,H為任意的關(guān)系,則有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設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪規(guī)定如下:R0={<x,x>|xA};Rn=Rn-1oR,n1.由上可知:RoR0=R=R0oR例題(關(guān)系圖法)設(shè)A={a,b,c,d},R={<a,b><b,a>,<b,c>,<c,d>},求R0,R1,R2,R3,R4,R5.解:abcdabcdabcdabcdR0R=R1R2=R4R3=R5例題(關(guān)系矩陣運(yùn)算法)設(shè)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:設(shè)R為A上的關(guān)系,m,n是自然數(shù),則下面的等式成立.RmoRn=Rm+n(Rm)n=Rmn證明任意給定m,對n進(jìn)行歸納.(1)n=0,RmoR0=Rm=Rm+0假設(shè)RmoRn=Rm+n,則

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

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

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

R3={<1,1>,<2,2>}(兩者都不是)例題（２）設(shè)A為非空集合，A上的關(guān)系可以是對稱的，反對稱的，或則兩者都是,兩者都不是．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>}(兩者都不是)性質(zhì)自反/反自反自反關(guān)系包含著恒等關(guān)系.即IAR.反自反關(guān)系R一定與IA不交,即IAR=如果IAR且IAR,則兩者都不是.對稱/反對稱A上的對稱關(guān)系滿足R-1=R.反對稱關(guān)系滿足RR-1IA.如果兩者都是RIA傳遞滿足RoRR例題(3)判斷下面關(guān)系的性質(zhì)123123123關(guān)系演算后的性質(zhì)自反性反自反性對稱性反對稱性傳遞性R-1R1R2R1R2R1-R2R1oR2運(yùn)算原有性質(zhì)證明(1)設(shè)R1,R2為A上的對稱關(guān)系,證明R1R2也是A上的對稱關(guān)系.證明:對任意的<x,y>,<x,y>R1R2<x,y>R1<x,y>R2<y,x>R1<y,x>R2<y,x>R1R2證明(2)R1,R2是A上的反對稱關(guān)系,則R1R2不一定是A上的反對稱關(guān)系,例如A={x1,x2},R1={<x1,x2>},R2={<x2,x1>}.

R1R2={<x1,x2>,<x2,x1>}.內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)自反閉包,對稱閉包,傳遞閉包定義4.11:設(shè)R是非空集合A上的關(guān)系,R的自反閉包(對稱閉包或傳遞閉包)是A上的關(guān)系R’,且R’滿足以下條件:R’是自反的(對稱的或傳遞的);RR’;對A上的任何包含R的自反關(guān)系(對稱或傳遞關(guān)系)R’’都有R’R’’.一般將R的自反閉包記作r(A),對稱閉包s(A),傳遞閉包t(A)例題例4.10設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},則R和r(A),s(A),t(A)的關(guān)系圖如下:abcdabcdabcdabcdRr(R)s(R)t(R)定理定理4.4:設(shè)R為非空集合A上的關(guān)系,則有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>}采用關(guān)系矩陣求閉包設(shè)R的關(guān)系矩陣為M,求相應(yīng)的自反、對稱、傳遞閉包的矩陣為Mr，Ms，Mt，則有Mr=M+E；Ms=M+M’Mt=M+M2+M3+...E表示同階的單位矩陣,M’為M的轉(zhuǎn)置,而+均表示矩陣中對應(yīng)元素的邏輯加.Mr01000100001000010000100001000011100111000110001+=Mr=Ms01000100001000001001000010000100100101001010010+=Ms=Mt01000100001000010100101010000000101101000000000++Mt=1111111100010000=內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系等價(jià)關(guān)系定義４.12設(shè)R為非空集合A上的關(guān)系,如果R是自反的、對稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系。對任何x，yA，如果<x,y>等價(jià)關(guān)系R，則記作xy。例題(1)例4.11:A={1,2,...,8},R={<x,y>|x,yAxy(mod3)},其中xy(mod3)為x-y被3整除.R為A上的等價(jià)關(guān)系.14725836

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

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

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

例題非空集合A上的全域關(guān)系EA是A上的等價(jià)關(guān)系,對任意xA有[x]=A,商集A/EA={A}.非空集合A上的恒等關(guān)系IA是A上的等價(jià)關(guān)系,任意xA有[x]={x},商集A/IA={{x}|xA}.在整數(shù)集合Z上模n的等價(jià)關(guān)系,其等價(jià)類是[0]={....,-2n,-n,0,n,2n,...}={nz|zZ}=Nz,.....劃分,劃分塊定義4.15:設(shè)A是非空集合,如果存在一個(gè)A的子集族π(πP(A))滿足以下條件π,π中任意兩個(gè)元素不交;π中所有元素的并集等于A;則稱π為A的一個(gè)劃分,且稱π中的元素為劃分塊.例題考慮集合A={a,b,c,d}的下列子集族{{a},{b,c},ipvauvt};(A的劃分){{a,b,c,d}};(A的劃分){{a,b},{c},{a,d}};{不是A的劃分}{,{a,b},{c,d}};{不是A的劃分}{{a},{b,c}};{不是A的劃分}R是A上的等價(jià)關(guān)系,則A/R是一個(gè)劃分,等價(jià)關(guān)系和劃分是一一對應(yīng)的.例題例題4.15:設(shè)A={1,2,3},求出A上所有的等價(jià)關(guān)系.解:先求A的各種劃分:1劃分塊的,2劃分塊的,3劃分塊的.213π1213π2213π3213π4213π5求等價(jià)關(guān)系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偏序關(guān)系(偏序)定義4.16:設(shè)R為非空集合A上的關(guān)系,如果R是自反的,反對稱的和傳遞的,則稱R為A上的偏序關(guān)系,簡稱偏序,記作.任何集合A上的恒等關(guān)系,集合的冪集P(A)上的包含關(guān)系,實(shí)數(shù)集上的小于等于關(guān)系,正整數(shù)集上的整除關(guān)系都是偏序關(guān)系.={<3,3>,<3,2>,<3,1>,<2,2>,,<2,1>,<1,1>}32,22,31偏序集定義4.17:一個(gè)集合A與A上偏序關(guān)系R一起叫做偏序集,記作<A,R>.例如<Z,R>,<P(A),R>都是偏序集.可比,蓋住定義4.18:設(shè)<A,>為偏序集,對于任意的x,yA,如果xy或者yx成立,則稱x與y是可比的,如果x<y(即xyxy),且不存在zA使得x<z<y,則稱y蓋住x.<A,>是A={1,2,