离散数学-第四章二元关系和函数

二元关系和函数——理学院数学系仝辉内容提纲集合的笛卡尔积与二元关系关系的运算关系的性质关系的闭包等价关系和偏序关系函数的定义和性质函数的复合和反函数序偶定义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},{d}};(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,