资源描述
P85:3(4)n指出下列推演中的错误，并改正之 (x)P(x)=F (x)P(x)(x)P(x)改为：改为：n(x)P(x)=F (x)P(x)(x)P(x)或n(x)P(x)=F (x)P(x)(x)P(x)必有必有(x)P(x)=F不一定有不一定有(x)P(x)=F必有必有(x)P(x)=F P85:3(4)指出下列推演中的错误，并改正之必有(x)P195:1(4)n列出下列各集合所有的元素：A=z|z=x,y x Z y Z 0 x2 -2y1A=0,-2,0,-1,0,0,0,1 1,-2,1,-1,1,1 2,-2,2,-1,2,0,2,1 P195:1(4)列出下列各集合所有的元素：第10章 关 系10.1 二元关系10.2 关系矩阵和关系图10.3 关系的逆、合成、限制和象10.4 关系的性质10.5 关系的闭包10.6 等价关系和划分10.7 相容关系和覆盖10.8 偏序关系第10章 关 系关系的合成运算 F G=|z(G F)x1 1x2 2z3 3z2 2z1 1y1 1y2 2F GFG关系的合成运算 FG=|z(x关系基本运算的性质 n定理定理10.3.1设设X,Y,Z是集合是集合,R XY,S YZ1.dom(R 1)=ran(R)2.ran(R 1)=dom(R)3.(R 1)1=R4.(S R)1=R 1 S 1n证证 (4)对任取对任取 x,z(S R)-1 z,x(R S)(y)(z,yS y,xR)(y)(y,zS-1 x,yR-1)x,zS-1 R-1R 1=|R F G=|z(G F)关系基本运算的性质 定理10.3.1设X,Y,Z是集合,关系基本运算的性质n定理定理10.3.2 设X，Y，Z，W是集合，QXY，SYZ，R ZW，则(R S)Q=R(S Q)n证明：证明：对任取对任取(R S)Q (y)(x,yQ y,wR S)(y)(x,yQ)(z)(y,zS z,wR)(y)(z)(x,yQ)z,wR y,zS)(z)(y)(z,wR x,yQ y,zS)(z)(z,wR)(y)(x,yQ y,zS)(z)(z,wR x,zS Q)x,wR(S Q)n所以所以(R S)Q=R(S Q)F G=|z(G F)关系基本运算的性质定理10.3.2 设X，Y，Z，W是集合关系基本运算的性质n 定理10.3.3 设X,Y,Z是集合,S、TXY,R YZ,则1.R(S T)=R S R T2.(R S)T=R T S T3.R(ST)R SR T4.(RS)T R TS Tn证明：仅证明仅证明，类似地可证明，类似地可证明、和和。x,zR(ST)(y)(y,zR x,yST)(y)(y,zR(x,yS x,yT)(y)(y,zR x,yS)(y,zR x,yT)(y)(y,zR x,yS)(y)(y,zR x,yT)x,yR S x,yR T x,yR SR Tn故故 R(ST)R SR T关系基本运算的性质 定理10.3.3 设X,Y,Z是10.4 关系的性质n关系的自反性定义:设RAA，(x)(x A x,xR)，则称，则称R在在A上是自反上是自反的的。n自反关系的特点n其关系矩阵其关系矩阵M(R)的主对角线全为的主对角线全为1；n其关系图中每一个结点上都有自回路。其关系图中每一个结点上都有自回路。n实例：设A=1,2,3，A上的二元关系R R=1,1,2,2,3,3,1,2 自反关系自反关系全域关系全域关系EA恒等关系恒等关系IA 小于等于关系小于等于关系LA 整除关系整除关系DA10.4 关系的性质关系的自反性定义:设RAA，自反关关系的反自反性n定义：设RAA，(x)(x A x,xR)，则称，则称R在在X上是上是反自反反自反的的。n反自反关系的特点n其关系矩阵其关系矩阵M(R)的主对角线全为的主对角线全为0；n其关系图中每一个结点上都没有自回路。其关系图中每一个结点上都没有自回路。n实例：设A=1,2,3，X上的二元关系 R=1,2,2,3,3,1，反自反关系反自反关系实数集上的小于关系实数集上的小于关系幂集上的真包含关幂集上的真包含关关系的反自反性定义：设RAA，反自反关系实例例例1 A=1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中 R1,R2 R3,R1自反自反,R2反自反反自反,R3既不是自反也不是反自反的既不是自反也不是反自反的实例例1 A=1,2,3,R1,R2,R3是关系的对称性n定义：设RAA，(x)(y)(x A y A x,yR y,xR)则称则称R在在A上是对称的上是对称的。n对称关系的特点n其关系矩阵其关系矩阵M(R)是对称阵。是对称阵。n其关系图中，如果两个不同的结点间有边，一定有方其关系图中，如果两个不同的结点间有边，一定有方向相反的两条边。向相反的两条边。n实例：设A=1,2,3，A上的二元关系R=1,2,2,1,3,3 对称关系对称关系全域关系全域关系EA,恒等关系恒等关系IA空关系空关系关系的对称性定义：设RAA，对称关系关系的反对称性n定义：设RAA，(x)(y)(x A y A x,yR y,xR(x=y)则称则称R在在A上是反对称的上是反对称的。n反对称关系的特点n其关系矩阵其关系矩阵M(R)中以主对角线为轴的对称位置上不能同时为中以主对角线为轴的对称位置上不能同时为1(主主对角线除外对角线除外)。n其关系图中，每两个不同的结点间不能有方向相反的两条边。其关系图中，每两个不同的结点间不能有方向相反的两条边。n实例：设A=1,2,3，A上的二元关系R=1,2,2,3,3,3 反对称关系反对称关系恒等关系恒等关系IA空关系空关系关系的反对称性定义：设RAA，(实例例例2 设设A1,2,3,R1,R2,R3和和R4都是都是A上的关系上的关系,其中其中 R1,，R2,R3,，R4,R1 对称、反对称对称、反对称.R2 对称，不反对称对称，不反对称.R3 反对称，不对称反对称，不对称.R4 不对称、也不反对称不对称、也不反对称.实例例2 设A1,2,3,R1,R2,R3和关系的传递性 n定义：设R AA xyz(RR R)则称R是A上的传递关系.n传递关系的特点n其关系矩阵其关系矩阵M(R)中中1所在位置所在位置,M(R)中相中相应位置都是位置都是1n如果如果顶点点 xi 连通到通到xk,则从从 xi到到 xk 有有边n实例：实例：nA上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系n小于等于关系小于等于关系,小于关系，整除关系，包含关系，小于关系，整除关系，包含关系，n真包含关系真包含关系关系的传递性 定义：设R AA 实例例例3 设设A1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中 R1,R2,R3R1 和和 R3 是是A上的传递关系上的传递关系 R2不是不是A上的传递关系上的传递关系实例例3 设A1,2,3,R1,R2,R3是A判断下图中关系的性质 图1图2图3自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性判断下图中关系的性质 图1图2图3自反性反自反性10.4.2 运算与性质的关系 设设R,S是自反的是自反的,则则 IA R，IA S 所以所以 IA R S，IA RS，即即 R S和和RS也是自反的也是自反的自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 1 R1R2 R1 R2 R1 R2 R1 R2 原有性质原有性质运算运算 设设R=,S=则则 R和和S都是都是传递的、反对称的传递的、反对称的但但 R S=,不是传递的，不是反对称的不是传递的，不是反对称的10.4.2 运算与性质的关系 设R,S是自反的,自反性10.5 关系的闭包n设设R为为A上的关系上的关系,n为自然数为自然数,则则 R 的的 n次幂次幂定义为：定义为：(1)R0=|x A=IA（恒等关系）（恒等关系）(2)Rn+1=Rn R（n1）n注意：注意：n对于对于A上的任何关系上的任何关系R1和和R2都有都有 R10=R20=IA n 对于对于A上的任何关系上的任何关系 R 都有都有 R1=R0 R=R10.5 关系的闭包设R为A上的关系,n为自然数,则 R10.5.1 多个关系合成的运算nP174例3 设A=a,b,c,d,R=,求R0,R1,R2,R3,R4,R5。n解：R0=IA，其关系矩阵和关系图分别为10.5.1 多个关系合成的运算P174例3 设A=多个关系合成的运算n设A=a,b,c,d,R=,n求R0,R1,R2,R3,R4,R5。n解：R1=R，其关系矩阵和关系图为多个关系合成的运算设A=a,b,c,d,R=a,b多个关系合成的运算n设A=a,b,c,d,R=,n解：R2=R R，其关系矩阵为关系图关系图多个关系合成的运算设A=a,b,c,d,R=a,b多个关系合成的运算n设A=a,b,c,d,R=,n解：R3=R2 R，其关系矩阵为关系图关系图多个关系合成的运算设A=a,b,c,d,R=a,b同理，同理，R4=R3 R=R2，R5=R4 R=R3还可以得到还可以得到R2=R4=R6=,R3=R5=R7=多个关系合成的运算说明：对于有限集说明：对于有限集A和和A上的关系上的关系R，R的不同的幂只存的不同的幂只存在有限个在有限个同理，R4=R3R=R2，R5=R4 R0,R1,R2,R3,的关系图如下图所示的关系图如下图所示多个关系合成的运算R0,R1,R2,R3,的关系图如下图所示多个关系合n定理定理 设A是的限集,R是A上的关系,m,nN,则 (1)Rm Rn=Rm+n (2)(Rm)n=Rmn n证证(1)用归纳法用归纳法 对对 m N,施归纳于施归纳于n.若若n=0,则有则有 Rm R0=Rm IA=Rm=Rm+0 假设假设Rm Rn=Rm+n,则有则有 Rm Rn+1 =Rm(Rn R)=(Rm Rn)R =Rm+n+1,所以所以,对对 m,n N有有Rm Rn=Rm+n.多个关系合成的运算的性质定理 设A是的限集,R是A上的关系,m,nN,则10.5.2 关系闭包的定义n闭包的定义定义 设设R是非空集合是非空集合A上的关系上的关系,R的的自反自反（对称对称或或传递传递）闭包闭包是是A上的关系上的关系R,使得使得R 满足以下条件：满足以下条件：（1）R 是是自反的自反的（对称的对称的或或传递的传递的）（2）R R（3）对）对A上任何包含上任何包含R的的自反自反(对称对称或或传递传递)关系关系 R 有有 RR.n 一般地，将一般地，将 R 的的n自反闭包自反闭包记作记作 r(R),n对称闭包对称闭包记作记作 s(R),n传递闭包传递闭包记作记作 t(R).包含包含R的最小自反关系是的最小自反关系是R的的自反闭包自反闭包包含包含R的最小对称关系是的最小对称关系是R的的对称闭包对称闭包包含包含R的最小传递关系是的最小传递关系是R的的传递闭包传递闭包10.5.2 关系闭包的定义闭包的定义 包含R的最小自反关作业11nP189:15，16,nP190:18，22作业11P189:15，16,
展开阅读全文