资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,P85: 3(4),指出下列推演中的错误，并改正之,(,x,),P,(,x,) = F,(,x,),P,(,x,),(,x,),P,(,x,),改为：,(,x,),P,(,x,) = F,(,x,),P,(,x,),(,x,),P,(,x,),或,(,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),列出下列各集合所有的元素：,A=z|z=x, yxZyZ,0x2,-2y1,A=,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,) ,x,1,x,2,z,3,z,2,z,1,y,1,y,2,F,G,F,G,关系的合成运算 FG = | z (x,关系基本运算的性质,定理,10.3.1,设,X, Y, Z,是集合,R,X,Y, S,Y,Z,dom,(,R,1,)=,ran,(R),ran,(R,1,)=,dom,(R),(,R,1,),1,=R,(,S,R,),1,=,R,1,S,1,证,(4),对任取,x,z,(,S,R,),-1,z,x,(,R,S,),(,y,)(,z,y,S,y,x,R,),(,y,)(,y,z,S,-1,x,y,R,-1,),x,z,S,-1,R,-1,R,1,= | ,R,F,G,= |,z,(,G,F,) ,关系基本运算的性质 定理10.3.1设X, Y, Z是集合,关系基本运算的性质,定理10.3.2,设,X,，,Y,，,Z,，,W,是集合，,Q,X,Y,，,S,Y,Z,，,R,Z,W,，则,(,R,S,),Q,=,R,(,S,Q,),证明：,对任取,(,R,S,),Q,(,y,)(,x,y,Q,y,w,R,S,),(,y,)(,x,y,Q,),(,z,)(,y,z,S,z,w,R,),(,y,)(,z,)(,x,y,Q,),z,w,R,y,z,S,),(,z,)(,y,)(,z,w,R,x,y,Q,y,z,S,),(,z,)(,z,w,R,)(,y,)(,x,y,Q,y,z,S,),(,z,)(,z,w,R,x,z,S,Q,),x,w,R,(,S,Q,),所以 (,R,S,),Q,=,R,(,S,Q,),F,G,= |,z,(,G,F,) ,关系基本运算的性质定理10.3.2 设X，Y，Z，W是集合,关系基本运算的性质,定理10.3.3,设,X, Y, Z,是集合,S、T,X,Y,R,Y,Z,则,R,(,S,T,)=,R,S,R,T,(,R,S,),T,=,R,T,S,T,R,(,S,T,),R,S,R,T,(,R,S,),T,R,T,S,T,证明：,仅证明，类似地可证明、和。,x,z,R,(,S,T,),(,y,)(,y,z,R,x,y,S,T,),(,y,)(,y,z,R,(,x,y,S,x,y,T,),(,y,)(,y,z,R,x,y,S,)(,y,z,R,x,y,T,),(,y,)(,y,z,R,x,y,S,)(,y,)(,y,z,R,x,y,T,),x,y,R,S,x,y,R,T,x,y,R,S,R,T,故,R,(,S,T,),R,S,R,T,关系基本运算的性质 定理10.3.3 设X, Y, Z是,10.4 关系的性质,关系的,自反性,定义:,设,R,A,A，,(,x,)(,x,A,x,x,R,),，则称,R,在A,上是自反的,。,自反关系的特点,其关系矩阵,M,(,R,)的主对角线全为1,；,其关系图中每一个结点上都有自回路。,实例,：设,A=1,2,3，A上的二元关系R,R,=,1,1,2,2,3,3,1,2,自反关系,全域关系,E,A,恒等关系,I,A,小于等于关系,L,A,整除关系,D,A,10.4 关系的性质关系的自反性定义: 设RAA，自反关,关系的,反自反性,定义：,设,R,A,A,，,(,x,)(,x,A,x,x,R,),，则称,R,在,X,上是,反自反的,。,反自反关系的特点,其关系矩阵,M,(,R,) 的主对角线全为0,；,其关系图中每一个结点上都没有自回路。,实例：,设,A,=1,2,3,，,X,上的二元关系,R,=,1,2,2,3,3,1,，,反自反关系,实数集上的小于关系,幂集上的真包含关,关系的反自反性定义： 设RAA，反自反关系,实例,例1,A,=1,2,3,R,1,R,2,R,3,是,A,上的关系, 其中,R,1,R,2,R,3,R,1,自反,R,2,反自反,R,3,既不是自反也不是反自反的,实例例1 A=1,2,3, R1, R2, R3是,关系的,对称性,定义：,设,R,A,A，,(,x,)(,y,)(,x,A,y,A,x,y,R,y,x,R,),则称,R,在,A,上是对称的,。,对称关系的特点,其关系矩阵,M,(,R,),是对称阵。,其关系图中，如果两个不同的结点间有边，一定有方向相反的两条边。,实例：,设,A,=1,2,3，,A,上的二元关系,R,=,1,2,2,1,3,3,对称关系,全域关系,E,A,恒等关系,I,A,空关系,关系的对称性定义： 设RAA， 对称关系,关系的,反对称性,定义：,设,R,A,A，,(,x,)(,y,)(,x,A,y,A,x,y,R,y,x,R,(,x,=,y,),则称,R,在,A,上是反对称的,。,反对称关系的特点,其关系矩阵,M,(,R,) 中以主对角线为轴的对称位置上不能同时为1(主对角线除外),。,其关系图中，每两个不同的结点间不能有方向相反的两条边。,实例：,设,A,=1,2,3，,A,上的二元关系,R,=,1,2,2,3,3,3,反对称关系,恒等关系,I,A,空关系,关系的反对称性定义： 设RAA， (,实例,例2 设,A,1,2,3,R,1,R,2,R,3,和,R,4,都是,A,上的关系,其中,R,1,，,R,2,R,3,，,R,4,R,1,对称、反对称,.,R,2,对称，不反对称,.,R,3,反对称，不对称,.,R,4,不对称、也不反对称,.,实例例2 设A1,2,3, R1, R2, R3和,关系的,传递性,定义：,设,R,A,A,x,y,z,(,R,R,R,),则称,R,是,A,上的,传递,关系.,传递关系的特点,其关系矩阵,M,(,R,),中1所在位置,M,(,R,),中相应位置都是1,如果顶点,x,i,连通到,x,k, 则从,x,i,到,x,k,有边,实例：,A,上的全域关系,E,A,恒等关系,I,A,和空关系,小于等于关系, 小于关系，整除关系，包含关系，,真包含关系,关系的传递性 定义：设R AA,实例,例3 设,A,1,2,3,R,1,R,2,R,3,是,A,上的关系, 其中,R,1,R,2,R,3,R,1,和,R,3,是,A,上的传递关系,R,2,不是,A,上的传递关系,实例例3 设A1,2,3, R1, R2, R3是A,判断下图中关系的性质,图1,图2,图3,自反性,反自反性,对称性,反对称性,传递性,判断下图中关系的性质 图1图2图3自反性反自反性,10.4.2 运算与性质的关系,设,R, S,是自反的,则,I,A,R,，,I,A,S,所以,I,A,R,S,，,I,A,R,S,，,即,R,S,和,R,S,也是自反的,自反性,反自反性,对称性,反对称性,传递性,R,1,1,R,1,R,2,R,1,R,2,R,1,R,2,R,1,R,2,原有性质,运算,设,R,=,S,=,则,R,和,S,都是,传递的、反对称的,但,R,S,=,不是传递的，不是反对称的,10.4.2 运算与性质的关系 设R, S是自反的, 自反性,10.5 关系的闭包,设,R,为,A,上的关系,n,为自然数,则,R,的,n,次幂,定义为：,(1),R,0,= |,x,A,=,I,A,（恒等关系）,(2),R,n,+1,=,R,n,R,（,n,1,）,注意：,对于,A,上的任何关系,R,1,和,R,2,都有,R,1,0,=,R,2,0,=,I,A,对于,A,上的任何关系,R,都有,R,1,=,R,0,R,=R,10.5 关系的闭包设R为A上的关系, n为自然数, 则 R,10.5.1 多个关系合成的运算,P174例3 设,A,=,a,b,c,d,R,=,求,R,0,R,1,R,2,R,3,R,4,R,5,。,解：,R,0,=,I,A,，其关系矩阵和关系图分别为,10.5.1 多个关系合成的运算P174例3 设A=,多个关系合成的运算,设,A,=,a,b,c,d, R=,求,R,0,R,1,R,2,R,3,R,4,R,5,。,解：,R,1,=,R,，其关系矩阵和关系图为,多个关系合成的运算设A=a,b,c,d, R=a,b,多个关系合成的运算,设,A,=,a,b,c,d,R,=,解：,R,2,=,R,R,，其关系矩阵为,关系图,多个关系合成的运算设A=a,b,c,d, R=a,b,多个关系合成的运算,设,A,=,a,b,c,d,R,=,解：,R,3,=,R,2,R,，其关系矩阵为,关系图,多个关系合成的运算设A=a,b,c,d, R=a,b,同理，,R,4,=,R,3,R =R,2,，,R,5,=,R,4,R=R,3,还可以得到,R,2,=,R,4,=,R,6,=,R,3,=,R,5,=,R,7,=,多个关系合成的运算,说明：对于有限集,A,和,A,上的关系,R,，,R,的不同的幂只存在有限个,同理， R4 = R3R =R2， R5=R4 ,R,0,R,1,R,2,R,3,的关系图如下图所示,多个关系合成的运算,R0, R1, R2, R3,的关系图如下图所示多个关系合,定理,设,A,是的限集,R,是,A,上的关系,m,n,N,则,(1),R,m,R,n,=,R,m,+,n,(2) (,R,m,),n,=,R,mn,证,(1),用归纳法 对,m,N,施归纳于,n,.,若,n,=0,则有,R,m,R,0,=,R,m,I,A,=,R,m,=,R,m,+0,假设,R,m,R,n,=,R,m,+,n,则有,R,m,R,n,+1,=,R,m,(,R,n,R,),=(,R,m,R,n,),R,=,R,m,+,n,+1,所以,对,m,n,N,有,R,m,R,n,=,R,m,+,n,.,多个关系合成的运算的性质,定理 设A是的限集, R是A上的关系, m, nN, 则,10.5.2 关系闭包的定义,闭包的,定义,设,R,是非空集合,A,上的关系,R,的,自反,（,对称,或,传递,）,闭包,是,A,上的关系,R, 使得,R,满足以下条件：,（1）,R,是,自反的,（,对称的,或,传递的,）,（2）,R,R,（3）对,A,上任何包含,R,的,自反,(,对称,或,传递,)关系,R,有,R,R,.,一般地，将,R,的,自反闭包,记作,r,(,R,),对称闭包,记作,s,(,R,),传递闭包,记作,t,(,R,).,包含,R,的最小自反关系是,R,的,自反闭包,包含,R,的最小对称关系是,R,的,对称闭包,包含,R,的最小传递关系是,R,的,传递闭包,10.5.2 关系闭包的定义闭包的定义 包含R的最小自反关,作业11,P189: 15，16,P190: 18，22,作业11P189: 15，16,
展开阅读全文