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

05十一月2022離散數(shù)學(xué)第四章二元關(guān)系和函數(shù)02十一月2022離散數(shù)學(xué)第四章二元關(guān)系和函數(shù)1內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)內(nèi)容提綱集合的笛卡爾積與二元關(guān)系2序偶定義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}

序偶定義4.1:由兩個(gè)元素x和y（允許x=y）按一定的順序排3有序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元組．有序n元組定義4.2:一個(gè)有序n元組(3≤n)是一個(gè)有序?qū)?笛卡兒積定義4.3:設(shè)A,B為集合,用A中的元素為第一元素,B中元素為第二元素，構(gòu)成有序?qū)Γ羞@樣的有序?qū)M成的集合叫做A和B的笛卡爾積，記作AxB,符號(hào)化表示為

AxB={<x,y>|xAΛyB}。例如: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笛卡兒積定義4.3:設(shè)A,B為集合,用A中的元素為第一元素,5笛卡兒積運(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ì)(1)若A,B中有一個(gè)空集,則它們的笛6笛卡兒積運(yùn)算具有的性質(zhì)(2)笛卡兒積運(yùn)算對(duì)或運(yùn)算滿足分配律,

Ax(BC)=(AxB)(AxC)

(BC)xA=(BxA)(CxA)

Ax(BC)=(AxB)(AxC)

(BC)xA=(BxA)(CxA)證明:對(duì)任意的<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)成立.笛卡兒積運(yùn)算具有的性質(zhì)(2)笛卡兒積運(yùn)算對(duì)或運(yùn)算滿足分配7例題(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.(假)例題(1)設(shè)A={1,2},求P(A)xA

P(A)xA=8n階笛卡兒積定義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>,…}n階笛卡兒積定義4.4設(shè)A1,A2,…,An,是集合(9二元關(guān)系定義4.5:如果一個(gè)集合為空集或者它的元素都是有序?qū)?則稱這個(gè)集合是一個(gè)二元關(guān)系,一般記作R,對(duì)于二元關(guān)系R,如果<x,y>R,則記作xRy;<x,y>R,記作xRy.本書涉及二元關(guān)系，（其它n元關(guān)系不在本書之列），書中涉及的關(guān)系全為二元關(guān)系．二元關(guān)系定義4.5:如果一個(gè)集合為空集或者它的元素都是有序10A到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:對(duì)任何集合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到B的二元關(guān)系定義4.6：設(shè)A,B為集合，AxB的任何子集11關(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í)例設(shè)A為實(shí)數(shù)集R的某個(gè)子集,則A上的小于等于關(guān)系定義為12關(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)系矩陣關(guān)系矩陣設(shè)A={x1,x2,...,xn},R是A上的13例題設(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例題設(shè)A={1,2,3,4},R={<1,1>,<1,2>,14關(guān)系圖設(shè)V是頂點(diǎn)的集合,E是有向邊的集合,令V={x1,x2,...,xn},如果xiRxj,則有<xi,xj>E,那么G=<V,E>就是R的關(guān)系圖.關(guān)系圖設(shè)V是頂點(diǎn)的集合,E是有向邊的集合,令V={x1,x15例題設(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例題設(shè)A={1,2,3,4},R={<1,1>,<1,2>,16內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)內(nèi)容提綱集合的笛卡爾積與二元關(guān)系17關(guān)系的定義域和值域定義4.8:關(guān)系R的定義域domR,值域ranR和域fldR分別是:

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

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

fldR=domRranR.關(guān)系的定義域和值域定義4.8:關(guān)系R的定義域domR,值域r18例題例題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.8:下列關(guān)系都是整數(shù)集Z上的關(guān)系,分別求出它們的19逆、合成、限制和象定義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).逆、合成、限制和象定義4.9:設(shè)F,G為任意的關(guān)系,A為集20例題設(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}例題設(shè)F,G是N上的關(guān)系,其定義為

F={<x,y>|x,y21等式(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等式(1)定理4.1:設(shè)F,G,H是任意的關(guān)系,則有22等式(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

等式(2)定理4.2設(shè)F,G,H為任意的關(guān)系,則有23n次冪定義4.10設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪規(guī)定如下:R0={<x,x>|xA};Rn=Rn-1oR,n1.由上可知:RoR0=R=R0oRn次冪定義4.10設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次24例題(關(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)系圖法)設(shè)A={a,b,c,d},R={<a,b>25例題(關(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==.例題(關(guān)系矩陣運(yùn)算法)設(shè)A={a,b,c,d},R={<a26等式(3)定理4.3:設(shè)R為A上的關(guān)系,m,n是自然數(shù),則下面的等式成立.RmoRn=Rm+n(Rm)n=Rmn證明任意給定m,對(duì)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)等式(3)定理4.3:設(shè)R為A上的關(guān)系,m,n是自然數(shù),則27內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)內(nèi)容提綱集合的笛卡爾積與二元關(guān)系28關(guān)系的性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性關(guān)系的性質(zhì)自反性29定義自反性反自反性對(duì)稱性反對(duì)稱性傳遞性定義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)主對(duì)角線的元素全為1主對(duì)角線的元素全為0矩陣為對(duì)稱矩陣如果rij=1,且xy則rji=0關(guān)系圖特點(diǎn)圖中每個(gè)節(jié)點(diǎn)都有環(huán)圖中每個(gè)節(jié)點(diǎn)都沒有環(huán)如果兩個(gè)頂點(diǎn)之間有邊,一定是一對(duì)方向相反的邊.如果兩個(gè)頂點(diǎn)之間有邊,一定是一條有向邊.如果xi到xj有邊，xj到xk有邊，則xi到xk一定有邊．定義自反性反自反性對(duì)稱性反對(duì)稱性傳遞性定義xA,有<x,30例題（１）設(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)系可以是自反的，反自反的，31例題（２）設(shè)A為非空集合，A上的關(guān)系可以是對(duì)稱的，反對(duì)稱的，或則兩者都是,兩者都不是．A={1,2,3}R4={<1,2>,<2,1>,<3,3>}(對(duì)稱)R5={<1,2>,<1,3>}(反對(duì)稱)R6={<1,1>}(兩者都是)R7={<1,2>,<2,1>,<1,3>}(兩者都不是)例題（２）設(shè)A為非空集合，A上的關(guān)系可以是對(duì)稱的，反對(duì)稱的，32性質(zhì)自反/反自反自反關(guān)系包含著恒等關(guān)系.即IAR.反自反關(guān)系R一定與IA不交,即IAR=如果IAR且IAR,則兩者都不是.對(duì)稱/反對(duì)稱A上的對(duì)稱關(guān)系滿足R-1=R.反對(duì)稱關(guān)系滿足RR-1IA.如果兩者都是RIA傳遞滿足RoRR性質(zhì)自反/反自反33例題(3)判斷下面關(guān)系的性質(zhì)123123123例題(3)判斷下面關(guān)系的性質(zhì)12312312334關(guān)系演算后的性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R-1R1R2R1R2R1-R2R1oR2運(yùn)算原有性質(zhì)關(guān)系演算后的性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R-135證明(1)設(shè)R1,R2為A上的對(duì)稱關(guān)系,證明R1R2也是A上的對(duì)稱關(guān)系.證明:對(duì)任意的<x,y>,<x,y>R1R2<x,y>R1<x,y>R2<y,x>R1<y,x>R2<y,x>R1R2證明(1)設(shè)R1,R2為A上的對(duì)稱關(guān)系,證明R1R2也是A36證明(2)R1,R2是A上的反對(duì)稱關(guān)系,則R1R2不一定是A上的反對(duì)稱關(guān)系,例如A={x1,x2},R1={<x1,x2>},R2={<x2,x1>}.

R1R2={<x1,x2>,<x2,x1>}.證明(2)R1,R2是A上的反對(duì)稱關(guān)系,則R1R2不一定是37內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)內(nèi)容提綱集合的笛卡爾積與二元關(guān)系38自反閉包,對(duì)稱閉包,傳遞閉包定義4.11:設(shè)R是非空集合A上的關(guān)系,R的自反閉包(對(duì)稱閉包或傳遞閉包)是A上的關(guān)系R’,且R’滿足以下條件:R’是自反的(對(duì)稱的或傳遞的);RR’;對(duì)A上的任何包含R的自反關(guān)系(對(duì)稱或傳遞關(guān)系)R’’都有R’R’’.一般將R的自反閉包記作r(A),對(duì)稱閉包s(A),傳遞閉包t(A)自反閉包,對(duì)稱閉包,傳遞閉包定義4.11:設(shè)R是非空集合A39例題例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.10設(shè)A={a,b,c,d},R={<a,b40定理定理4.4:設(shè)R為非空集合A上的關(guān)系,則有r(R)=RR0;s(R)=RR-1;t(R)=RR2R3....定理定理4.4:設(shè)R為非空集合A上的關(guān)系,則有41求各種閉包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={<a,b>,<b,a>,<b,c>,<c,d42采用關(guān)系矩陣求閉包設(shè)R的關(guān)系矩陣為M,求相應(yīng)的自反、對(duì)稱、傳遞閉包的矩陣為Mr，Ms，Mt，則有Mr=M+E；Ms=M+M’Mt=M+M2+M3+...E表示同階的單位矩陣,M’為M的轉(zhuǎn)置,而+均表示矩陣中對(duì)應(yīng)元素的邏輯加.采用關(guān)系矩陣求閉包設(shè)R的關(guān)系矩陣為M,求相應(yīng)的自反、對(duì)稱、傳43Mr01000100001000010000100001000011100111000110001+=Mr=Mr01001000144Ms01000100001000001001000010000100100101001010010+=Ms=Ms01000100045Mt01000100001000010100101010000000101101000000000++Mt=1111111100010000=Mt01001010046內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系內(nèi)容提綱集合的笛卡爾積與二元關(guān)系47等價(jià)關(guān)系定義４.12設(shè)R為非空集合A上的關(guān)系,如果R是自反的、對(duì)稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系。對(duì)任何x，yA，如果<x,y>等價(jià)關(guān)系R，則記作xy。等價(jià)關(guān)系定義４.12設(shè)R為非空集合A上的關(guān)系,如果R是48例題(1)例4.11:A={1,2,...,8},R={<x,y>|x,yAxy(mod3)},其中xy(mod3)為x-y被3整除.R為A上的等價(jià)關(guān)系.14725836推廣:對(duì)任何正整數(shù)n,可以給定整數(shù)集合Z上的模n的等價(jià)關(guān)系:R={<x,y>|x,yZxy(modn)}.例題(1)例4.11:A={1,2,...,8},R49例題(2),相容關(guān)系在一群人的集合上,年齡相等是等價(jià)關(guān)系,而朋友關(guān)系不一定是等價(jià)關(guān)系,因?yàn)樗赡懿皇莻鬟f的.一般這種自反的對(duì)稱的關(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)系.例題(2),相容關(guān)系在一群人的集合上,年齡相等是等價(jià)關(guān)系,而50等價(jià)類定義4.13:設(shè)R是非空集合A上的等價(jià)關(guān)系,對(duì)任意的xA,令[x]R={y|yAxRy},則稱為x關(guān)于R的等價(jià)類,簡(jiǎn)稱[x]R為x關(guān)于R的等價(jià)類,簡(jiǎn)記為[x].

14725836[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}等價(jià)類定義4.13:設(shè)R是非空集合A上的等價(jià)關(guān)系,對(duì)任意的51等價(jià)類的性質(zhì)(1)定理4.5:設(shè)R是非空集合A上的等價(jià)關(guān)系,對(duì)任意的x,yA,下面的結(jié)論成立.[x],且[x]A;若xRy,則[x]=[y];若xRy,則[x][y]=;.等價(jià)類的性質(zhì)(1)定理4.5:設(shè)R是非空集合A上的等價(jià)關(guān)系,52商集定義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}}.

商集定義4.14:設(shè)R為非空集合A上的等價(jià)關(guān)系,以R的不交的53例題非空集合A上的全域關(guān)系EA是A上的等價(jià)關(guān)系,對(duì)任意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,.....例題非空集合A上的全域關(guān)系EA是A上的等價(jià)關(guān)系,對(duì)任意xA54劃分,劃分塊定義4.15:設(shè)A是非空集合,如果存在一個(gè)A的子集族π(πP(A))滿足以下條件π,π中任意兩個(gè)元素不交;π中所有元素的并集等于A;則稱π為A的一個(gè)劃分,且稱π中的元素為劃分塊.劃分,劃分塊定義4.15:設(shè)A是非空集合,如果存在一個(gè)A的子55例題考慮集合A={a,b,c,d}的下列子集族{{a},{b,c},qiaiygg};(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)系和劃分是一一對(duì)應(yīng)的.例題考慮集合A={a,b,c,d}的下列子集族56例題例題4.15:設(shè)A={1,2,3},求出A上所有的等價(jià)關(guān)系.解:先求A的各種劃分:1劃分塊的,2劃分塊的,3劃分塊的.213π1213π2213π3213π4213π5例題例題4.15:設(shè)A={1,2,3},求出A上所有的等價(jià)57求等價(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求等價(jià)關(guān)系R5={<1,1>,<2,2>,<3,3>}=IA58偏序關(guān)系(偏序)定義4.16:設(shè)R為非空集合A上的關(guān)系,如果R是自反的,反對(duì)稱的和傳遞的,則稱R為A上的偏序關(guān)系,簡(jiǎ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偏序關(guān)系(偏序)定義4.16:設(shè)R為非空集合A上的關(guān)系,如果59偏序集定義4.17:一個(gè)集合A與A上偏序關(guān)系R一起叫做偏序集,記作<A,R>.例如<Z,R>,<P(A),R>都是偏序集.偏序集定義4.17:一個(gè)集合A與A上偏序關(guān)系R一起叫做偏序集60可比,蓋住定義4.18:設(shè)<A,>為偏序集,對(duì)于任意的x,yA,如果xy或者yx成立,則稱x與y是可比的,如果x<y(即xyxy),且不存在zA使得x<z<y,則稱y蓋住x.<A,>是A={1,2,3,4,5}上的整除關(guān)系,1和任意元素有整除關(guān)系,所以1和1,2,3,4,5是可比的.但2不能整除3,所以2和3是不可比的.1<2并且不存在一個(gè)z使得1<z<2,所以2蓋住1,同樣4蓋住2,但4不蓋住1.可比,蓋住定義4.18:設(shè)<A,>為偏序集,對(duì)于任意的x61全序關(guān)系,全序集定義4.19:設(shè)<A,>為偏序集,若對(duì)任意的x,yA,x和y都可比,則稱為A上的全序關(guān)系,且稱<A,>為全序集.如{1,2,3,4,5}上的小于等于關(guān)系.全序關(guān)系,全序集定義4.19:設(shè)<A,>為偏序集,若對(duì)任意62哈斯圖畫出<{1,2,...,12},R整除>和<P({a,b,c}),R>的哈斯圖.171193612248510{c}{a}{b,c}{a,b}{a,c}{a,b,c}哈斯圖畫出<{1,2,...,12},R整除>和<P({a,63例題設(shè)偏序集<A,>的哈斯圖如圖4.10所示,求出集合A的偏序.解A={a,b,c,d,e,f,g,h}

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

<d,e>,<f,g>}IA.由哈斯圖可以看出全序集是一條直線.abcdefgh例題設(shè)偏序集<A,>的哈斯圖如圖4.10所示,求出集合A的64最小元,最大元,極小元,極大元定義4.20:設(shè)<A,>為偏序集,BA.若yB,使得x(xByx)成立,則稱y是B的最小元;若yB,使得x(xBxy)成立,則稱y是B的最大元;若yB,使得x(xBx<y)成立,則稱y是B的極小元.若yB,使得x(xBy<x)成立,則稱y是B的極大元.最小元,最大元,極小元,極大元定義4.20:設(shè)<A,>為偏65例題:說(shuō)出最大/小元和極大/小元abcdefgh171193612248510{c}{a}{b,c}{a,b}{a,c}{a,b,c}<{1,2,...,12},R整除><P({a,b,c}),R>例題:說(shuō)出最大/小元和極大/小元abcdefgh17119366上界,下界,最小上界,最大下界定義4.21:設(shè)<A,>為偏序集,BA.若yA,使得x(xBxy)成立,則稱y是B的上界;若yA,使得x(xByx)成立,則稱y是B的下界;令C={y|y為B的上界},則稱C的最小元為B最小上界,或上確界.令C={y|y為B的下界},則稱C的最大元為B最大下界,或下確界.上界,下界,最小上界,最大下界定義4.21:設(shè)<A,>為偏67例題:說(shuō)出上界/下界等abcdefgh171193612248510{c}{a}{b,c}{a,b}{a,c}{a,b,c}<{1,2,...,12},R整除><P({a,b,c}),R>例題:說(shuō)出上界/下界等abcdefgh171193612246805十一月2022離散數(shù)學(xué)第四章二元關(guān)系和函數(shù)02十一月2022離散數(shù)學(xué)第四章二元關(guān)系和函數(shù)69內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)內(nèi)容提綱集合的笛卡爾積與二元關(guān)系70序偶定義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}

序偶定義4.1:由兩個(gè)元素x和y（允許x=y）按一定的順序排71有序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元組．有序n元組定義4.2:一個(gè)有序n元組(3≤n)是一個(gè)有序?qū)?2笛卡兒積定義4.3:設(shè)A,B為集合,用A中的元素為第一元素,B中元素為第二元素，構(gòu)成有序?qū)?，所有這樣的有序?qū)M成的集合叫做A和B的笛卡爾積，記作AxB,符號(hào)化表示為

AxB={<x,y>|xAΛyB}。例如: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笛卡兒積定義4.3:設(shè)A,B為集合,用A中的元素為第一元素,73笛卡兒積運(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ì)(1)若A,B中有一個(gè)空集,則它們的笛74笛卡兒積運(yùn)算具有的性質(zhì)(2)笛卡兒積運(yùn)算對(duì)或運(yùn)算滿足分配律,

Ax(BC)=(AxB)(AxC)

(BC)xA=(BxA)(CxA)

Ax(BC)=(AxB)(AxC)

(BC)xA=(BxA)(CxA)證明:對(duì)任意的<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)成立.笛卡兒積運(yùn)算具有的性質(zhì)(2)笛卡兒積運(yùn)算對(duì)或運(yùn)算滿足分配75例題(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.(假)例題(1)設(shè)A={1,2},求P(A)xA

P(A)xA=76n階笛卡兒積定義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>,…}n階笛卡兒積定義4.4設(shè)A1,A2,…,An,是集合(77二元關(guān)系定義4.5:如果一個(gè)集合為空集或者它的元素都是有序?qū)?則稱這個(gè)集合是一個(gè)二元關(guān)系,一般記作R,對(duì)于二元關(guān)系R,如果<x,y>R,則記作xRy;<x,y>R,記作xRy.本書涉及二元關(guān)系，（其它n元關(guān)系不在本書之列），書中涉及的關(guān)系全為二元關(guān)系．二元關(guān)系定義4.5:如果一個(gè)集合為空集或者它的元素都是有序78A到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:對(duì)任何集合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到B的二元關(guān)系定義4.6：設(shè)A,B為集合，AxB的任何子集79關(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í)例設(shè)A為實(shí)數(shù)集R的某個(gè)子集,則A上的小于等于關(guān)系定義為80關(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)系矩陣關(guān)系矩陣設(shè)A={x1,x2,...,xn},R是A上的81例題設(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例題設(shè)A={1,2,3,4},R={<1,1>,<1,2>,82關(guān)系圖設(shè)V是頂點(diǎn)的集合,E是有向邊的集合,令V={x1,x2,...,xn},如果xiRxj,則有<xi,xj>E,那么G=<V,E>就是R的關(guān)系圖.關(guān)系圖設(shè)V是頂點(diǎn)的集合,E是有向邊的集合,令V={x1,x83例題設(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例題設(shè)A={1,2,3,4},R={<1,1>,<1,2>,84內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)內(nèi)容提綱集合的笛卡爾積與二元關(guān)系85關(guān)系的定義域和值域定義4.8:關(guān)系R的定義域domR,值域ranR和域fldR分別是:

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

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

fldR=domRranR.關(guān)系的定義域和值域定義4.8:關(guān)系R的定義域domR,值域r86例題例題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.8:下列關(guān)系都是整數(shù)集Z上的關(guān)系,分別求出它們的87逆、合成、限制和象定義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).逆、合成、限制和象定義4.9:設(shè)F,G為任意的關(guān)系,A為集88例題設(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}例題設(shè)F,G是N上的關(guān)系,其定義為

F={<x,y>|x,y89等式(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等式(1)定理4.1:設(shè)F,G,H是任意的關(guān)系,則有90等式(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

等式(2)定理4.2設(shè)F,G,H為任意的關(guān)系,則有91n次冪定義4.10設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪規(guī)定如下:R0={<x,x>|xA};Rn=Rn-1oR,n1.由上可知:RoR0=R=R0oRn次冪定義4.10設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次92例題(關(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)系圖法)設(shè)A={a,b,c,d},R={<a,b>93例題(關(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==.例題(關(guān)系矩陣運(yùn)算法)設(shè)A={a,b,c,d},R={<a94等式(3)定理4.3:設(shè)R為A上的關(guān)系,m,n是自然數(shù),則下面的等式成立.RmoRn=Rm+n(Rm)n=Rmn證明任意給定m,對(duì)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)等式(3)定理4.3:設(shè)R為A上的關(guān)系,m,n是自然數(shù),則95內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)內(nèi)容提綱集合的笛卡爾積與二元關(guān)系96關(guān)系的性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性關(guān)系的性質(zhì)自反性97定義自反性反自反性對(duì)稱性反對(duì)稱性傳遞性定義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)主對(duì)角線的元素全為1主對(duì)角線的元素全為0矩陣為對(duì)稱矩陣如果rij=1,且xy則rji=0關(guān)系圖特點(diǎn)圖中每個(gè)節(jié)點(diǎn)都有環(huán)圖中每個(gè)節(jié)點(diǎn)都沒有環(huán)如果兩個(gè)頂點(diǎn)之間有邊,一定是一對(duì)方向相反的邊.如果兩個(gè)頂點(diǎn)之間有邊,一定是一條有向邊.如果xi到xj有邊，xj到xk有邊，則xi到xk一定有邊．定義自反性反自反性對(duì)稱性反對(duì)稱性傳遞性定義xA,有<x,98例題（１）設(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)系可以是自反的，反自反的，99例題（２）設(shè)A為非空集合，A上的關(guān)系可以是對(duì)稱的，反對(duì)稱的，或則兩者都是,兩者都不是．A={1,2,3}R4={<1,2>,<2,1>,<3,3>}(對(duì)稱)R5={<1,2>,<1,3>}(反對(duì)稱)R6={<1,1>}(兩者都是)R7={<1,2>,<2,1>,<1,3>}(兩者都不是)例題（２）設(shè)A為非空集合，A上的關(guān)系可以是對(duì)稱的，反對(duì)稱的，100性質(zhì)自反/反自反自反關(guān)系包含著恒等關(guān)系.即IAR.反自反關(guān)系R一定與IA不交,即IAR=如果IAR且IAR,則兩者都不是.對(duì)稱/反對(duì)稱A上的對(duì)稱關(guān)系滿足R-1=R.反對(duì)稱關(guān)系滿足RR-1IA.如果兩者都是RIA傳遞滿足RoRR性質(zhì)自反/反自反101例題(3)判斷下面關(guān)系的性質(zhì)123123123例題(3)判斷下面關(guān)系的性質(zhì)123123123102關(guān)系演算后的性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R-1R1R2R1R2R1-R2R1oR2運(yùn)算原有性質(zhì)關(guān)系演算后的性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R-1103證明(1)設(shè)R1,R2為A上的對(duì)稱關(guān)系,證明R1R2也是A上的對(duì)稱關(guān)系.證明:對(duì)任意的<x,y>,<x,y>R1R2<x,y>R1<x,y>R2<y,x>R1<y,x>R2<y,x>R1R2證明(1)設(shè)R1,R2為A上的對(duì)稱關(guān)系,證明R1R2也是A104證明(2)R1,R2是A上的反對(duì)稱關(guān)系,則R1R2不一定是A上的反對(duì)稱關(guān)系,例如A={x1,x2},R1={<x1,x2>},R2={<x2,x1>}.

R1R2={<x1,x2>,<x2,x1>}.證明(2)R1,R2是A上的反對(duì)稱關(guān)系,則R1R2不一定是105內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)內(nèi)容提綱集合的笛卡爾積與二元關(guān)系106自反閉包,對(duì)稱閉包,傳遞閉包定義4.11:設(shè)R是非空集合A上的關(guān)系,R的自反閉包(對(duì)稱閉包或傳遞閉包)是A上的關(guān)系R’,且R’滿足以下條件:R’是自反的(對(duì)稱的或傳遞的);RR’;對(duì)A上的任何包含R的自反關(guān)系(對(duì)稱或傳遞關(guān)系)R’’都有R’R’’.一般將R的自反閉包記作r(A),對(duì)稱閉包s(A),傳遞閉包t(A)自反閉包,對(duì)稱閉包,傳遞閉包定義4.11:設(shè)R是非空集合A107例題例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.10設(shè)A={a,b,c,d},R={<a,b108定理定理4.4:設(shè)R為非空集合A上的關(guān)系,則有r(R)=RR0;s(R)=RR-1;t(R)=RR2R3....定理定理4.4:設(shè)R為非空集合A上的關(guān)系,則有109求各種閉包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={<a,b>,<b,a>,<b,c>,<c,d110采用關(guān)系矩陣求閉包設(shè)R的關(guān)系矩陣為M,求相應(yīng)的自反、對(duì)稱、傳遞閉包的矩陣為Mr，Ms，Mt，則有Mr=M+E；Ms=M+M’Mt=M+M2+M3+...E表示同階的單位矩陣,M’為M的轉(zhuǎn)置,而+均表示矩陣中對(duì)應(yīng)元素的邏輯加.采用關(guān)系矩陣求閉包設(shè)R的關(guān)系矩陣為M,求相應(yīng)的自反、對(duì)稱、傳111Mr01000100001000010000100001000011100111000110001+=Mr=Mr010010001112Ms01000100001000001001000010000100100101001010010+=Ms=Ms010001000113Mt01000100001000010100101010000000101101000000000++Mt=1111111100010000=Mt010010100114內(nèi)容提綱集合的笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系內(nèi)容提綱集合的笛卡爾積與二元關(guān)系115等價(jià)關(guān)系定義４.12設(shè)R為非空集合A上的關(guān)系,如果R是自反的、對(duì)稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系。對(duì)任何x，yA，如果<x,y>等價(jià)關(guān)系R，則記作xy。等價(jià)關(guān)系定義４.12設(shè)R為非空集合A上的關(guān)系,如果R是116例題(1)例4.11:A={1,2,...,8},R={<x,y>|x,yAxy(mod3)},其中xy(mod3)為x-y被3整除.R為A上的等價(jià)關(guān)系.14725836推廣:對(duì)任何正整數(shù)n,可以給定整數(shù)集合Z上的模n的等價(jià)關(guān)系:R={<x,y>|x,yZxy(modn)}.例題(1)例4.11:A={1,2,...,8},R117例題(2),相容關(guān)系在一群人的集合上,年齡相等是等價(jià)關(guān)系,而朋友關(guān)系不一定是等價(jià)關(guān)系,因?yàn)樗赡懿皇莻鬟f的.一般這種自反的對(duì)稱的關(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)系.例題(2),相容關(guān)系在一群人的集合上,年齡相等是等價(jià)關(guān)系,而118等價(jià)類定義4.13:設(shè)R是非空集合A上的等價(jià)關(guān)系,對(duì)任意的xA,令[x]R={y|yAxRy},則稱為x關(guān)于R的等價(jià)類,簡(jiǎn)稱[x]R為x關(guān)于R的等價(jià)類,簡(jiǎn)記為[x].

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

A/R={[x]R|xA}.A/R={{1,4,7},{