工学离散数学第7章-二元关系课件

第七章二元关系第七章二元关系1主要内容有序对与笛卡儿积二元关系的定义与表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系主要内容2第一节有序对与笛卡儿积

一.有序对定义7.1由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作<x,y>.有序对性质:(1)有序性<x,y><y,x>（当xy时）(2)<x,y>与<u,v>相等的充分必要条件是<x,y>=<u,v>

x=uy=v.第一节有序对与笛卡儿积一.有序对3定义7.2设A,B为集合，A与B的笛卡儿积记作AB，且AB={<x,y>|xAyB}.例1A={1,2,3},B={a,b,c}AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}A={},B=P(A)A={<,>,<{},>}P(A)B=

定义7.2设A,B为集合，A与B的笛卡儿积记作AB，且42.笛卡尔积的性质(1)不适合交换律ABBA(AB,A,B)(2)不适合结合律(AB)CA(BC)(A,B,C)(3)对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)2.笛卡尔积的性质5(4)若A或B中有一个为空集，则AB就是空集.A=B=

(5)若|A|=m,|B|=n,则|AB|=mn[工学]离散数学第7章-二元关系课件6证明A(BC)=(AB)(AC)证任取<x,y><x,y>∈A×(B∪C)x∈A∧y∈B∪Cx∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)<x,y>∈A×B∨<x,y>∈A×C<x,y>∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).证明A(BC)=(AB)(AC)证任取<7例2

(1)证明A=B,C=DAC=BD(2)AC=BD是否推出A=B,C=D?为什么？解(1)任取<x,y><x,y>ACxAyCxByD<x,y>BD(2)不一定.反例如下：A={1}，B={2},C=D=,则AC=BD但是AB.例2解(1)任取<x,y>8第二节二元关系

一、二元关系的定义定义7.3如果一个集合满足以下条件之一：(1)集合非空,且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系,简称为关系，记作R.如果<x,y>∈R,可记作xRy；如果<x,y>R,则记作x

y实例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,a

c等.第二节二元关系一、二元关系的定义9二、从A到B上的关系与A的关系定义7.4：设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例3A={0,1},B={1,2,3},那么R1={<0,2>},R2=A×B,R3=,R4={<0,1>}R1,R2,R3,R4是从A到B的二元关系,R3和R4也是A上的二元关系.

二、从A到B上的关系与A的关系例3A={0,1},B10计数:|A|=n,|A×A|=n2,A×A的子集有个.所以A上有个不同的二元关系.例如|A|=3,则A上有=512个不同的二元关系.计数:|A|=n,|A×A|=n2,A×A的子集有11A中重要关系的实例定义7.5设A为集合,(1)是A上的关系，称为空关系(2)全域关系EA={<x,y>|x∈A∧y∈A}=A×A

恒等关系IA={<x,x>|x∈A}小于等于关系LA={<x,y>|x,y∈A∧x≤y},A为实数子集

整除关系DB={<x,y>|x,y∈B∧x整除y},A为非0整数子集

包含关系R={<x,y>|x,y∈A∧xy},A是集合族.A中重要关系的实例12例如,A={1,2},则EA={<1,1>,<1,2>,<2,1>,<2,2>}IA={<1,1>,<2,2>}例如A={1,2,3},B={a,b},则

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

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}例如A=P(B)={,{a},{b},{a,b}},则A上的包含关系是R={<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}

.例如,A={1,2},则13关系的表示1.关系矩阵若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中rij=1<xi,yj>R.2.关系图若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=<A,R>,其中A为结点集，R为边集.如果<xi,xj>属于关系R，在图中就有一条从xi到xj的有向边.关系的表示14注意：关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集）关系图适合表示有穷集A上的关系注意：15例4A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵MR和关系图GR如下：úúúúûùêêêêëé=0010000011000011RM例4úúúúûùêêêêëé=00100000110000116第三节关系的运算一、关系的基本运算与定义关系的基本运算定义7.6关系的定义域、值域与域分别定义为domR={x|y(<x,y>R)}ranR={y|x(<x,y>R)}fldR=domRranR例5R={<1,2>,<1,3>,<2,4>,<4,3>},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}第三节关系的运算一、关系的基本运算与定义例5R={<172.关系的逆与合定义7.7关系的逆运算R1={<y,x>|<x,y>R}定义7.8关系的合成运算RS={<x,z>|y(<x,y>R<y,z>S)}例6R={<1,2>,<2,3>,<1,4>,<2,2>}S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}R1={<2,1>,<3,2>,<4,1>,<2,2>}RS={<1,3>,<2,2>,<2,3>}SR={<1,2>,<1,4>,<3,2>,<3,3>}2.关系的逆与合例6R={<1,2>,<2,3>182.合成的图示方法：利用图示（不是关系图）方法求合成RS={<1,3>,<2,2>,<2,3>}SR={<1,2>,<1,4>,<3,2>,<3,3>2.合成的图示方法：193.限制与像定义7.9设R为二元关系,A是集合(1)R在A上的限制记作R↾A,其中

R↾A={<x,y>|xRy∧x∈A}(2)A在R下的像记作R[A],其中

R[A]=ran(R↾A)说明：R在A上的限制R↾A是R的子关系，即R↾ARA在R下的像R[A]是ranR的子集，即R[A]ranR3.限制与像20例7设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>},则

R↾{1}={<1,2>,<1,3>}

R↾=

R↾{2,3}={<2,2>,<2,4>,<3,2>}

R[{1}]={2,3}

R[]=

R[{3}]={2}例7设R={<1,2>,<1,3>,<2,2>,<2,421二、关系运算的性质定理7.1设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF证(1)任取<x,y>,由逆的定义有<x,y>∈(F1)1

<y,x>∈F1

<x,y>∈F.所以有(F1)1=F.二、关系运算的性质证(1)任取<x,y>,由逆的定义有22(2)任取xx∈domF1

y(<x,y>∈F1)

y(<y,x>∈F)x∈ranF所以有domF1=ranF.同理可证ranF1=domF.定理7.2设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1(2)任取x定理7.2设F,G,H是任意的关系,23证(1)任取<x,y>,<x,y>(FG)H

t(<x,t>∈FG∧<t,y>∈H)

t(s(<x,s>∈F∧<s,t>∈G)∧<t,y>∈H)

ts(<x,s>∈F∧<s,t>∈G∧<t,y>∈H)

s(<x,s>∈F∧t(<s,t>∈G∧<t,y>∈H))

s(<x,s>∈F∧<s,y>∈GH)

<x,y>∈F(GH)所以(FG)H=F(GH)证(1)任取<x,y>,24(2)任取<x,y>,

<x,y>∈(FG)1

<y,x>∈FG

t(<y,t>∈F∧<t,x>∈G)

t(<x,t>∈G1∧<t,y>∈F1)<x,y>∈G1F1

所以(F

G)1=G1F1

(2)任取<x,y>,

<x,y>∈(FG)25定理7.3设R为A上的关系,则

RIA=IAR=R证任取<x,y>

<x,y>∈RIA

t(<x,t>∈R∧<t,y>∈IA)

t(<x,t>∈R∧t=y∧y∈A)<x,y>∈R定理7.3设R为A上的关系,则

26定理7.4

(1)F(GH)=FG∪FH(2)(G∪H)F=GF∪HF(3)F(G∩H)FG∩FH(4)(G∩H)FGF∩HF只证(3)任取<x,y>,

<x,y>∈F(G∩H)

t(<x,t>∈F∧<t,y>∈G∩H)

t(<x,t>∈F∧<t,y>∈G∧<t,y>∈H)t((<x,t>∈F∧<t,y>∈G)∧(<x,t>∈F∧<t,y>∈H))

定理7.4只证(3)任取<x,y>,

<x,y>∈27

t(<x,t>∈F∧<t,y>∈G)∧t(<x,t>∈F∧<t,y>∈H)

<x,y>∈FG∧<x,y>∈FH

<x,y>∈FG∩FH所以有F(G∩H)=FG∩FHt(<x,t>∈F∧<t,y>∈G)∧t(<28定理7.4的结论可以推广到有限多个关系R(R1∪R2∪…∪Rn)=RR1∪RR2∪…∪RRn

(R1∪R2∪…∪Rn)R=R1R∪R2R∪…∪RnRR(R1∩R2∩…∩Rn)RR1∩RR2∩…∩RRn(R1∩R2∩…∩Rn)RR1R∩R2R∩…∩RnR定理7.4的结论可以推广到有限多个关系29定理7.5设F为关系,A,B为集合,则(1)F↾(A∪B)=F↾A∪F↾B(2)F[A∪B]=F[A]∪F[B](3)F↾(A∩B)=F↾A∩F↾B(4)F[A∩B]F[A]∩F[B]

定理7.5设F为关系,A,B为集合,则30证只证(1)和(4).(1)任取<x,y>

<x,y>∈F↾(A∪B)<x,y>∈F∧x∈A∪B<x,y>∈F∧(x∈A∨x∈B)(<x,y>∈F∧x∈A)∨(<x,y>∈F∧x∈B)<x,y>∈F↾A∨<x,y>∈F↾B<x,y>∈F↾A∪F↾B所以有F↾(A∪B)=F↾A∪F↾B.证只证(1)和(4).31(4)任取y,y∈F[A∩B]

x(<x,y>∈F∧x∈A∩B)

x(<x,y>∈F∧x∈A∧x∈B)

x((<x,y>∈F∧x∈A)∧(<x,y>∈F∧x∈B))

x(<x,y>∈F∧x∈A)∧x(<x,y>∈F∧x∈B)y∈F[A]∧y∈F[B]y∈F[A]∩F[B]

所以有F[A∩B]=F[A]∩F[B].(4)任取y,32三、A上关系的幂运算1.定义7.10设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0={<x,x>|x∈A}=IA(2)Rn+1=RnR注意：对于A上的任何关系R1和R2都有R10=R20=IA

对于A上的任何关系R都有R1=R三、A上关系的幂运算33例8设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次幂,分别用矩阵和关系图表示.解R与R2的关系矩阵分别是：例8设A={a,b,c,d},R={<a,b34R3和R4的矩阵是：因此M4=M2,即R4=R2.因此可以得到

R2=R4=R6=…，R3=R5=R7=…

R0的关系矩阵是R3和R4的矩阵是：35图3R0,R1,R2,R3,…的关系图如下图所示.

图3R0,R1,R2,R3,…的关系图如下图所示.36四、幂运算的性质定理7.6设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.证R为A上的关系,由于|A|=n,A上的不同关系只有个.列出R的各次幂R0,R1,R2,…,,…,必存在自然数s和t使得Rs=Rt四、幂运算的性质证R为A上的关系,37定理7.7设R是A上的关系,m,n∈N,则(1)RmRn=Rm+n(2)(Rm)n=Rmn

证用归纳法(1)对于任意给定的m∈N,施归纳于n.若n=0,则有RmR0=RmIA=Rm=Rm+0

假设RmRn=Rm+n,则有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1,所以对一切m,n∈N有RmRn=Rm+n.定理7.7设R是A上的关系,m,n∈N,则38(2)对于任意给定的m∈N,施归纳于n.若n=0,则有(Rm)0=IA=R0=Rm×0

假设(Rm)n=Rmn,则有(Rm)n+1=(Rm)nRm=(Rmn)Rn=Rmn+m=Rm(n+1)所以对一切m,n∈N有(Rm)n=Rmn.(2)对于任意给定的m∈N,施归纳于n.39定理7.8设R是A上的关系,若存在自然数s,t(s<t)使得Rs=Rt,则(1)对任何k∈N有Rs+k=Rt+k

(2)对任何k,i∈N有Rs+kp+i=Rs+i,其中p=ts(3)令S={R0,R1,…,Rt1},则对于任意的q∈N有Rq∈S定理7.8设R是A上的关系,40证(1)Rs+k=RsRk=RtRk=Rt+k(2)对k归纳.若k=0,则有Rs+0p+i=Rs+i假设Rs+kp+i=Rs+i,其中p=ts,则Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+iRp

=Rs+iRp=Rs+p+i=Rs+ts+i=Rt+i=Rs+i

由归纳法命题得证.证(1)Rs+k=RsRk=RtRk=41(3)令S={R0,R1,…,Rt1},则对于任意的q∈N有Rq∈S

证：任取q∈N,若q<t,显然有Rq∈S,若q≥t,则存在自然数k和i使得

q=s+kp+i,其中0≤i≤p1.于是

Rq=Rs+kp+i=Rs+i

而s+i≤s+p1=s+ts1=t1从而证明了Rq∈S.(3)令S={R0,R1,…,Rt1},则对于任意42第四节关系的性质

一、五种性质的定义1.自反与反自反定义7.11设R为A上的关系,(1)若x(x∈A→<x,x>R),则称R在A上是自反的.(2)若x(x∈A→<x,x>R),则称R在A上是反自反的.

实例：自反：全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系.

第四节关系的性质一、五种性质的定义实例：43A={1,2,3},R1,R2,R3是A上的关系,其中R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>}R2自反，R3反自反，R1既不是自反的也不是反自反的.A={1,2,3},R1,R2,R3是A上的关系,442.对称与反对称定义7.12设R为A上的关系,

（1）若xy(x,y∈A∧<x,y>∈R→<y,x>∈R),则称R为A上对称的关系.(2)若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),则称R为A上的反对称关系.2.对称与反对称45实例：对称关系：A上的全域关系EA,恒等关系IA和空关系反对称关系：恒等关系IA和空关系也是A上的反对称关系.设A＝{1,2,3},R1,R2,R3和R4都是A上的关系,其中R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}R3＝{<1,2>,<1,3>}，R4={<1,2>,<2,1>,<1,3>}R1：对称和反对称；R2：只有对称；R3：只有反对称；R4：不对称、不反对称实例：463.传递性定义7.13设R为A上的关系,若

xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),则称R是A上的传递关系.实例：A上的全域关系EA,恒等关系IA和空关系，小于等于和小于关系，整除关系，包含与真包含关系设A＝{1,2,3},R1,R2,R3是A上的关系,其中R1＝{<1,1>,<2,2>}R2＝{<1,2>,<2,3>}R3＝{<1,3>}R1和R3是A上的传递关系,R2不是A上的传递关系.3.传递性实例：A上的全域关系EA,恒等关系I47二、关系性质的等价描述五种性质成立的充分必要条件定理7.9设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当R∩IA=(3)R在A上对称当且仅当R=R1(4)R在A上反对称当且仅当R∩R1IA(5)R在A上传递当且仅当RRR二、关系性质的等价描述48证明只证(1)、(3)、(4)、(5)(1)必要性任取<x,y>,由于R在A上自反必有

<x,y>∈IA

x,y∈A∧x=y<x,y>∈R从而证明了IAR充分性.任取x,有

x∈A<x,x>∈IA

<x,x>∈R因此R在A上是自反的.证明只证(1)、(3)、(4)、(5)49(3)必要性.

任取<x,y>,

<x,y>∈R<y,x>∈R<x,y>∈R所以R=R1充分性.任取<x,y>,由R=R1得

<x,y>∈R<y,x>∈R1

<y,x>∈R所以R在A上是对称的(3)必要性.50(4)必要性.任取<x,y>,有

<x,y>∈R∩R1

<x,y>∈R∧<x,y>∈R1

<x,y>∈R∧<y,x>∈Rx=yx,yA

<x,y>∈IA这就证明了R∩R1IA充分性.任取<x,y>,<x,y>∈R∧<y,x>∈R

<x,y>∈R∧<x,y>∈R1

<x,y>∈R∩R1<x,y>∈IAx=y从而证明了R在A上是反对称的.

(4)必要性.任取<x,y>,有

<51(5)必要性.任取<x,y>有<x,y>∈RR

t(<x,t>∈R∧<t,y>∈R)<x,y>∈R所以RRR充分性.

任取<x,y>,<y,z>∈R,则

<x,y>∈R∧<y,z>∈R

<x,z>∈RR<x,z>∈R所以R在A上是传递的(5)必要性.52自反性反自反性对称性反对称性传递性集合IARR∩IA=R=R1R∩R1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0M2中1位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环两点之间有边,是一对方向相反的边两点之间有边,是一条有向边点xi到xj有边,xj到xk有边,则xi到xk也有边关系性质的三种等价条件自反性反自反性对称性反对称性传递性集合IARR∩IA=53[工学]离散数学第7章-二元关系课件54自反性反自反性对称性反对称性传递性R11

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1R2

×√√√×R1

R2

√××××关系性质与运算之间的联系自反性反自反性对称性反对称性传递性R11√√√√√R1∩55第五节关系的闭包

主要内容闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质第五节关系的闭包主要内容56一、闭包的定义定义7.14设R是非空集合A上的关系,R的自反(对称或传递)闭包是A上的关系R,使得R满足以下条件：(1)R是自反的(对称的或传递的)(2)RR(3)对A上任何包含R的自反(对称或传递)关系R有RR，R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).

一、闭包的定义57定理7.10设R为A上的关系,则有(1)r(R)=R∪R0(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…说明：对有穷集A(|A|=n)上的关系,(3)中的并最多不超过Rn定理7.10设R为A上的关系,则有58证只证(1)和(3).(1)由IA=R0R∪R0知R∪R0是自反的,且满足RR∪R0设R是A上包含R的自反关系,则有RR和IAR.从而有R∪R0R.R∪R0满足闭包定义,所以r(R)=R∪R0.证只证(1)和(3).59(1)先证R∪R2∪…t(R)成立.用归纳法证明对任意正整数n有Rnt(R).n=1时有R1=Rt(R).假设Rnt(R)成立,那么对任意的<x,y>

<x,y>∈Rn+1=RnR

t(<x,t>∈Rn∧<t,y>∈R)

t(<x,t>∈t(R)∧<t,y>∈t(R))<x,y>∈t(R)这就证明了Rn+1t(R).由归纳法命题得证.

(1)先证R∪R2∪…t(R)成立.60再证t(R)R∪R2∪…成立,为此只须证明R∪R2∪…传递.任取<x,y>,<y,z>,则

<x,y>∈R∪R2∪…∧<y,z>∈R∪R2∪…

t(<x,y>∈Rt)∧s(<y,z>∈Rs)

ts(<x,z>∈RtRs)

ts(<x,z>∈Rt+s)

<x,z>∈R∪R2∪…从而证明了R∪R2∪…是传递的.再证t(R)R∪R2∪…成立,为此只须证明R∪R261二、闭包的矩阵表示和图表示设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt

则Mr=M+EMs=M+M'Mt=M+M2+M3+…E是单位矩阵,M'是转置矩阵，相加时使用逻辑加.二、闭包的矩阵表示和图表示62设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新的边：(1)考察G的每个顶点,若没环就加一个环，得到Gr

(2)考察G的每条边,若有一条xi到xj的单向边,i≠j,则在G中加一条xj到xi的反向边,得到Gs(3)考察G的每个顶点xi,找xi可达的所有顶点xj(允许i=j)，如果没有从xi到xj

的边,就加上这条边,得到图Gt设关系R,r(R),s(R),t(R)的关系图分别记为63例9设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)的关系图如下图所示.

例9设A={a,b,c,d},R={<a,b>,<64三、闭包的性质定理7.11设R是非空集合A上的关系,则(1)R是自反的当且仅当r(R)=R.(2)R是对称的当且仅当s(R)=R.(3)R是传递的当且仅当t(R)=R.定理7.12设R1和R2是非空集合A上的关系,且R1R2,则(1)r(R1)r(R2)(2)s(R1)s(R2)(3)t(R1)t(R2)三、闭包的性质定理7.12设R1和R2是非空集合A上的关系65定理7.13设R是非空集合A上的关系,(1)若R是自反的,则s(R)与t(R)也是自反的(2)若R是对称的,则r(R)与t(R)也是对称的(3)若R是传递的,则r(R)是传递的.说明：如果需要进行多个闭包运算，比如求R的自反、对称、传递的闭包tsr(R)，运算顺序如下：tsr(R)=rts(R)=trs(R)定理7.13设R是非空集合A上的关系,667.6等价关系与划分主要内容等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应7.6等价关系与划分67一、等价关系的定义与实例定义7.15设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若<x,y>∈R,称x等价于y,记做x～y.实例设A={1,2,…,8},如下定义A上的关系R：

R={<x,y>|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.一、等价关系的定义与实例实例设A={1,2,…,8}68不难验证R为A上的等价关系,因为(1)x∈A,有x≡x(mod3)(2)x,y∈A,若x≡y(mod3),则有y≡x(mod3)(3)x,y,z∈A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3)

不难验证R为A上的等价关系,因为69图6图670二、等价类及其性质定义7.16设R为非空集合A上的等价关系,x∈A，令[x]R={y|y∈A∧xRy}称[x]R为x关于R的等价类,简称为x的等价类,简记为[x]或实例A={1,2,…,8}上模3等价关系的等价类：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}二、等价类及其性质71定理7.14设R是非空集合A上的等价关系,则(1)xA,[x]是A的非空子集(2)x,yA,如果xRy,则[x]=[y](3)x,yA,如果xy,则[x]与[y]不交(4)∪{[x]|xA}=A定理7.14设R是非空集合A上的等价关系,则72证(1)由定义,xA有[x]A.又x[x],即[x]非空.(2)任取z,则有

z∈[x]

<x,z>∈R

<z,x>∈R<z,x>R∧<x,y>R

<z,y>R

<y,z>R从而证明了z∈[y].综上所述必有[x][y].同理可证[y][x].这就得到了[x]=[y].证(1)由定义,xA有[x]A.又x[x],73(3)假设[x]∩[y]≠,则存在z[x]∩[y],从而有z[x]∧z[y],即<x,z>R∧<y,z>R成立.根据R的对称性和传递性必有<x,y>R,与xy矛盾(3)假设[x]∩[y]≠,则存在z[x]∩[y74先证∪{[x]|xA}A.任取y,y∪{[x]|xA}

x(xA∧y[x])y[x]∧[x]AyA从而有∪{[x]|x∈A}A再证A∪{[x]|x∈A}.任取y,yAy[y]∧yAy∈∪{[x]|xA}从而有∪{[x]|x∈A}A成立.综上所述得∪{[x]|xA}=A.

先证∪{[x]|xA}A.75三、商集与集合的划分定义7.17设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,

A/R={[x]R|x∈A}实例设A={1,2,…,8}，A关于模3等价关系R的商集为

A/R={{1,4,7},{2,5,8},{3,6}}A关于恒等关系和全域关系的商集为：A/IA={{1},{2},…,{8}}，A/EA={{1,2,…,8}}三、商集与集合的划分76定义7.18设A为非空集合,若A的子集族π(πP(A))满足:(1)

π(2)xy(x,yπ∧x≠y→x∩y=)(3)∪π=A则称π是A的一个划分,称π中的元素为A的划分块.定义7.18设A为非空集合,若A的子集族π(πP(77

例10设A＝{a,b,c,d},给定1,2,3,4,5,6如下：

1={{a,b,c},{d}}

2={{a,b},{c},{d}}

3={{a},{a,b,c,d}}

4={{a,b},{c}}

5={,{a,b},{c,d}}

6={{a,{a}},{b,c,d}}

则1和2是A的划分,其他都不是A的划分.例10设A＝{a,b,c,d},给定78例11给出A＝{1,2,3}上所有的等价关系1231

12351232123412331对应EA,5对应IA,2,3和4分别对应R2,R3和R4.

R2={<2,3>,<3,2>}∪IA

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

R4={<1,2>,<2,1>}∪IA解先做出A的划分,从左到右分别记作1,2,3,4,5.例11给出A＝{1,2,3}上所有的等价关系123797.7偏序关系主要内容偏序关系偏序关系的定义偏序关系的实例偏序集与哈斯图偏序集中的特殊元素及其性质极大元、极小元、最大元、最小元上界、下界、最小上界、最大下界7.7偏序关系80一、偏序关系定义与实例定义7.19

偏序关系：非空集合A上的自反、反对称和传递的关系，记作≼.设≼为偏序关系,如果<x,y>∈≼,则记作x≼y,读作x“小于或等于”y.实例集合A上的恒等关系IA是A上的偏序关系.小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.一、偏序关系定义与实例81定义7.20设R为非空集合A上的偏序关系,(1)x,y∈A,x与y可比x≼y∨y≼x(2)任取元素x和y,可能有下述几种情况发生：

x≺y(或y≺x),x＝y,x与y不是可比的定义7.21R为非空集合A上的偏序关系,(1)x,y∈A,x与y都是可比的，则称R为全序（或线序）实例：数集上的小于或等于关系是全序关系,整除关系不是正整数集合上的全序关系定义7.20设R为非空集合A上的偏序关系,定义7.82定义7.22x,y∈A,如果x≺y且不存在z∈A使得x≺z≺y,则称y覆盖x.例如{1,2,4,6}集合上整除关系,2覆盖1,4和6覆盖2,4不覆盖1.定义7.22x,y∈A,如果x≺y且不存在z∈83二、偏序集与哈斯图定义7.23集合A和A上的偏序关系≼一起叫做偏序集,记作<A,≼>.实例:<Z,≤>,<P(A),R>哈斯图:利用偏序关系的自反、反对称、传递性进行简化的关系图特点：(1)每个结点没有环 (2)两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前(3)具有覆盖关系的两个结点之间连边二、偏序集与哈斯图哈斯图:利用偏序关系的自反、反对称、传递84例12偏序集<{1,2,3,4,5,6,7,8,9},R整除>和<P({a,b,c}),R>的哈斯图.

例12偏序集<{1,2,3,4,5,6,7,8,9},85例13已知偏序集<A,R>的哈斯图如下图所示,试求出集合A和关系R的表达式.

解A={a,b,c,d,e,f,g,h}R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA例13已知偏序集<A,R>的哈斯图如下图所示,试求出集86三、偏序集中的特殊元素定义7.24设<A,≼>为偏序集,BA,y∈B(1)若x(x∈B→y≼x)成立,则称y为B的最小元(2)若x(x∈B→x≼y)成立,则称y为B的最大元(3)若x(x∈B∧x≼y→x=y)成立,则称y为B的极小元(4)若x(x∈B∧y≼x→x=y)成立,则称y为B的极大元性质：(1)对于有穷集，极小元和极大元一定存在，可能存在多个.(2)最小元和最大元不一定存在，如果存在一定惟一.(3)最小元一定是极小元；最大元一定是极大元.(4)孤立结点既是极小元，也是极大元.三、偏序集中的特殊元素性质：87定义7.25设<A,≼>为偏序集,BA,y∈A(1)若x(x∈B→x≼y)成立,则称y为B的上界(2)若x(x∈B→y≼x)成立,则称y为B的下界(3)令C＝{y|y为B的上界},C的最小元为B的最小上或上确界(4)令D＝{y|y为B的下界},D的最大元为B的最大下界或下确界定义7.25设<A,≼>为偏序集,BA,y∈A88性质：(1)下界、上界、下确界、上确界不一定存在(2)下界、上界存在不一定惟一(3)下确界、上确界如果存在，则惟一(4)集合的最小元是其下确界，最大元是其上确界；反之不对.性质：89例14设偏序集<A,≼>，求A的极小元、最小元、极大元、最大元，设B＝{b,c,d},求B的下界、上界、下确界、上确界.解极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在；上界有d和f,最小上界为d.

例14设偏序集<A,≼>，求A的极小元、最小元、极大元90例15设X为集合,A＝P(X)－{}－{X},且A≠.若|X|=n,n≥2.问：(1)偏序集<A,R>是否存在最大元？(2)偏序集<A,R>是否存在最小元？(3)偏序集<A,R>中极大元和极小元的一般形式是什么？并说明理由.解(1)<A,R>不存在最小元和最大元,因为n≥2.(2)<A,R>的极小元就是X的所有单元集,即{x},x∈X.(3)<A,R>的极大元恰好比X少一个元素,即X{x},x∈X.例15设X为集合,A＝P(X)－{}－{X},且A91第七章习题课

主要内容有序对与笛卡儿积的定义与性质二元关系、从A到B的关系、A上的关系关系的表示法：关系表达式、关系矩阵、关系图关系的运算：定义域、值域、域、逆、合成、限制、像、幂关系运算的性质:A上关系的自反、反自反、对称、反对称、传递的性质A上关系的自反、对称、传递闭包A上的等价关系、等价类、商集与A的划分A上的偏序关系与偏序集第七章习题课主要内容92基本要求

基本概念要清楚熟练掌握关系的三种表示法能够判定关系的性质（等价关系或偏序关系）掌握含有关系运算的集合等式掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念以下基本运算要熟练计算AB,domR,ranR,fldR,R1,RS,Rn,r(R),s(R),t(R)求等价类和商集A/R给定A的划分，求出所对应的等价关系求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界

基本要求93掌握基本的证明方法证明涉及关系运算的集合等式证明关系的性质、证明关系是等价关系或偏序关系[工学]离散数学第7章-二元关系课件94二、练习1．设A={1,2,3},R={<x,y>|x,yA且x+2y6}S={<1,2>,<1,3>,<2,2>},求:(1)R的集合表达式(2)R1(3)domR,ranR,fldR(4)RS,R3(5)r(R),s(R),t(R)二、练习95解：(1)R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}(2)R1={<1,1>,<2,1>,<1,2>,<2,2>,<1,3>}(3)domR={1,2,3},ranR={1,2},fldR={1,2,3}(4)RS={<1,2>,<1,3>,<2,2>,<2,3>,<3,2>,<3,3>}R3={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}(5)r(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,3>}s(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<1,3>}t(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}解：962．设A={1,2,3,4}，在AA上定义二元关系R：<<x,y>,<u,v>>Rx+y=u+v，求R导出的划分.AA={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}根据<x,y>中的x+y=2,3,4,5,6,7,8将A划分成等价类：A/R={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<2,3>,<3,2>,<4,1>},{<2,4>,<3,3>,<4,2>},{<3,4>,<4,3>},{<4,4>}}2．设A={1,2,3,4}，在AA上定义二元关系R：973．设R是Z上的模n等价关系,即xy

x

y(modn),试给出由R确定的Z的划分.解设除以n余数为r的整数构成等价类[r]，则[r]={kn+r|kZ},r=0,1,…,n1

={[r]|r=0,1,…,n1}

3．设R是Z上的模n等价关系,即解设除以n余984．设偏序集<A,R>的哈斯图如图所示.(1)写出A和R的集合表达式(2)求该偏序集中的极大元、极小元、最大元、最小元解

(1)A={a,b,c,d,e}R={<d,b>,<d,a>,<d,c>,<e,c>,<e,a>,<b,a>,<c,a>}IA

(2)极大元和最大元是a,极小元是d,e；没有最小元.4．设偏序集<A,R>的哈斯图如图所示.解995．设R是A上的二元关系，设S={<a,b>|c(<a,c>R<c,b>R)}.证明如果R是等价关系，则S也是等价关系。证

R是A上的等价关系.(1)证自反任取x,xA<x,x>R

x(<x,x>R<x,x>R)<x,x>S(2)证对称任取<x,y>,<x,y>S

c(<x,c>R<c,y>R)

c(<c,x>R<y,c>R)<y,x>S

5．设R是A上的二元关系，设证R是A上的等价关系.100(3)证传递任取<x,y>,<y,z>,<x,y>S<y,z>S

c(<x,c>R<c,y>R)

d(<y,d>R<d,z>R)<x,y>R<y,z>

R<x,z>S(3)证传递任取<x,y>,<y,z>,1016．设偏序集<A,R>和<B,S>，定义AB上二元关系T:<x,y>T<u,v>

xRu

ySv证明T为偏序关系.证(1)自反性任取<x,y>,<x,y>AB

xAyB

xRxySy<x,y>T<x,y>(2)反对称性任取<x,y>,<u,v><x,y>T<u,v><u,v>T<x,y>

xRu

ySv

uRx

vSy(xRu

uRx)(ySv

vSy)

x=u

y=v<x,y>=<u,v>6．设偏序集<A,R>和<B,S>，定义AB上二元关系T:102(3)传递性任取<x,y>,<u,v>,<w,t><x,y>T<u,v><u,v>T<w,t>

xRu

ySv

uRw

vSt(xRu

uRw)(ySv

vSt)

xRw

ySt<x,y>T<w,t>(3)传递性任取<x,y>,<u,v>,<w,t>1031.证明R在A上自反任取x,xA……..….…….<x,x>R前提推理过程结论2.证明R在A上对称任取<x,y>，

<x,y>R……<y,x>R

前提推理过程结论关系性质的证明方法1.证明R在A上自反关系性质的证明方法1043.证明R在A上反对称任取<x,y>，<x,y>R<y,x>R……..x=y前提推理过程结论4.证明R在A上传递任取<x,y>,<y,z>，<x,y>R<y,z>R…<x,z>R前提推理过程结论3.证明R在A上反对称1057．R,S为A上的关系，证明RS

t(R)t(S)证只需证明对于任意正整数n,RnSn.对n归纳.n=1,显然为真.假设对于n，命题为真，任取<x,y><x,y>Rn+1<x,y>Rn∘R

t(<x,t>Rn<t,y>R)

t(<x,t>Sn<t,y>S)<x,y>Sn∘S<x,y>Sn+1

7．R,S为A上的关系，证明RSt(R)t106关系等式或包含式的证明方法数学归纳法（主要用于幂运算）证明中用到关系运算的定义和公式,如：xdomR

y(<x,y>R)yranR

x(<x,y>R)<x,y>R<y,x>R1<x,y>R∘S

t(<x,t>R<t,y>S)<x,y>R↾AxA<x,y>RyRA]

x(xA<x,y>R)r(R)=RIAs(R)=RR1t(R)=RR2…关系等式或包含式的证明方法107

第七章二元关系第七章二元关系108主要内容有序对与笛卡儿积二元关系的定义与表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系主要内容109第一节有序对与笛卡儿积

一.有序对定义7.1由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作<x,y>.有序对性质:(1)有序性<x,y><y,x>（当xy时）(2)<x,y>与<u,v>相等的充分必要条件是<x,y>=<u,v>

x=uy=v.第一节有序对与笛卡儿积一.有序对110定义7.2设A,B为集合，A与B的笛卡儿积记作AB，且AB={<x,y>|xAyB}.例1A={1,2,3},B={a,b,c}AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}A={},B=P(A)A={<,>,<{},>}P(A)B=

定义7.2设A,B为集合，A与B的笛卡儿积记作AB，且1112.笛卡尔积的性质(1)不适合交换律ABBA(AB,A,B)(2)不适合结合律(AB)CA(BC)(A,B,C)(3)对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)2.笛卡尔积的性质112(4)若A或B中有一个为空集，则AB就是空集.A=B=

(5)若|A|=m,|B|=n,则|AB|=mn[工学]离散数学第7章-二元关系课件113证明A(BC)=(AB)(AC)证任取<x,y><x,y>∈A×(B∪C)x∈A∧y∈B∪Cx∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)<x,y>∈A×B∨<x,y>∈A×C<x,y>∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).证明A(BC)=(AB)(AC)证任取<114例2

(1)证明A=B,C=DAC=BD(2)AC=BD是否推出A=B,C=D?为什么？解(1)任取<x,y><x,y>ACxAyCxByD<x,y>BD(2)不一定.反例如下：