二元关系 (3)

电子科技大学离散数学课程组——国家精品课程离散数学任课教师：杨春2020年1月22日星期三数学科学学院电子科技大学离散数学课程组——国家精品课程150-22020/1/226.4.1关系性质的定义1、自反性和反自反性定义6.4.1设R是集合A上的关系1.如果对任意x∈A，都有x,x∈R，那么称R在A上是自反的(Reflexive)，或称R具有自反性(Reflexivity)；例如：朋友关系。2.如果对任意x∈A，都有x,xR，那么称R在A上是反自反的(Antireflexive)，或称R具有反自反性(Antireflexivity)。例如：父子关系。电子科技大学离散数学课程组——国家精品课程150-32020/1/22例6.4.1设A={1,2,3}，定义A上的关系R,S和T如下：（1）R={1,1,1,2,2,2,3,3}；（2）S={1,2,2,3,3,1}；（3）T={1,1,1,2,1,3,3,1,3,3}。分析A上的关系R,S和T是否满足自反与反自反。电子科技大学离散数学课程组——国家精品课程150-42020/1/22例6.4.2设A={a,b}，试计算A上所有具有自反性的关系R的个数。解因为A2={a,a,b,b,a,b,b,a}，所以A上具有自反性的关系R的个数为：C(2,0)+C(2,1)+C(2,2)=4。电子科技大学离散数学课程组——国家精品课程150-52020/1/222、对称性和反对称性定义6.4.2设R是集合A上的关系。1.对任意x,y∈A，如果x,y∈R，那么y,x∈R，则称关系R是对称的(Symmetric)，或称R具有对称性(Symmetry)；2.对任意x,y∈A，如果x,y∈R且y,x∈R，那么x＝y（或者如果x≠y且x,y∈R，那么y,x∈R），则称关系R是反对称的(Antisymmetric)，或称R具有反对称性(Antisymmetry)。电子科技大学离散数学课程组——国家精品课程150-62020/1/22例6.4.2设A={1,2,3,4}，定义A上的关系R,S,T和V如下：（1）R={1,1,1,3,3,1,4,4}；（2）S={1,1,1,3,1,4,2,4}；（3）T={1,1,1,2,1,3,3,1,1,4}；（4）V={1,1,2,2,3,3,4,4}。试判定它们是否具有对称性和反对称性电子科技大学离散数学课程组——国家精品课程150-72020/1/22解:a)关系R是对称的；b)关系S是反对称的；c)在关系T中，有1,2，但没有2,1，即S不是对称的；另外有1,3，且有3,1，但是1≠3，即S不是反对称的。因此T既不是对称的，也不是反对称的；d)在关系V中，对任意x,y∈A，x≠y时都有x,yR，V既是对称的，也是反对称的。电子科技大学离散数学课程组——国家精品课程150-82020/1/223、传递性定义6.4.3设R是集合A上的关系。对任意x,y,z∈A，如果x,y∈R且y,z∈R，那么x,z∈R，则称关系R是传递的(Transitive)，或称R具有传递性(Transitivity)。电子科技大学离散数学课程组——国家精品课程150-92020/1/22例6.4.3设A={1,2,3}，定义A上的关系R,S,T和V如下：（1）R={1,1,1,2,2,3,1,3}；（2）S={1,2}；（3）T={1,1,1,2,2,3}；（4）V={1,2,2,3,1,3,2,1}。试判定它们是否具有传递性电子科技大学离散数学课程组——国家精品课程150-102020/1/22a)关系R是传递的；b)关系S是传递的；c)在关系T中，存在x=1，y=2，z=3∈A且1,2,2,3∈T，但1,3T，因此T不是传递的；d)在关系V中，存在x=1，y=2和z=1∈A，使得1,2∈V且2,1∈V，但是1,1V，因此关系V不是传递的。解:电子科技大学离散数学课程组——国家精品课程150-112020/1/22说明：对任意给定的A上的关系R，可以采用下面的三种方法判定它所具有的性质：（1）定义判定法；（2）关系矩阵判定法；（3）关系图判定法.课外作业：指出用关系矩阵和关系图判定关系性质的方法。电子科技大学离散数学课程组——国家精品课程150-122020/1/22例6.4.6判定下列关系所具有的特殊性质。（1）集合A上的全关系；（2）集合A上的空关系；（3）集合A上的恒等关系。解(1)集合A上的全关系具有自反性，对称性和传递性；(2)集合A上的空关系具有反自反性、对称性、反对称性和传递性；(3)集合A上的恒等关系具有自反性、对称性、反对称性和传递性。电子科技大学离散数学课程组——国家精品课程150-132020/1/22例6.4.7判定下列关系所具有的特殊性质。（1）在实数集R上定义的“等于”关系；（2）幂集上的“真包含”关系。解（1）R上的“等于”关系具有自反性、对称性、反对称性和传递性；（2）幂集上的“真包含”关系具有反自反性，反对称性和传递性。电子科技大学离散数学课程组——国家精品课程150-142020/1/22例6.4.8假设A={a,b,c,d}，R={a,a,a,b,b,a,c,d}是定义在A上的关系。试判定R所具有的特殊性质。解由前面的分析可知，R既不是自反的，也不是反自反的；既不是对称的，也不是反对称的；而且也不是传递的。即R不具备关系的任何性质。电子科技大学离散数学课程组——国家精品课程150-152020/1/22设A＝{a,b,c},试判断如下图所示A上关系的性质：例abc(a)abc(b)abc(c)abc(d)abc(e)abc(f)abc(g)abc(h)图(a)的关系是自反的、对称的、反对称的、传递的关系图(b)的关系是具备反自反的、对称的、反对称的、传递的关系图(c)的关系是具备对称的、反对称的、传递的关系图(d)的关系是不具备任何的性质关系图(e)的关系是具备自反的、对称的、传递的关系图(f)的关系是具备反自反的、反对称的、传递的关系图(g)的关系是具备反自反的、反对称的关系图(h)的关系是具备反自反的、反对称的、传递的关系电子科技大学离散数学课程组——国家精品课程150-162020/1/22例6.4.9设R={1,1,2,2}，试判断R在集合A和B上具备的特殊性质，其中A={1,2}，B={1,2,3}。解当R是定义在集合A上的关系时，R是自反、对称、反对称和传递的；当R是定义在集合B上的关系时，R是对称、反对称和传递的。注意：绝对不能脱离基集（即定义关系的集合）来谈论关系的性质。电子科技大学离散数学课程组——国家精品课程150-172020/1/22在二元关系中，由于关系的性质的定义全部都是按“如……则……”来描述的，因此，在证明关系的性质时，一般都都采用按定义证明方法，即：将“如……”部分作为附加的已知条件，证得“则……”部分，就证明了关系具有该性质。关系性质的证明电子科技大学离散数学课程组——国家精品课程150-182020/1/222.反自反关系性质的证明方法1.自反任取xA，中间过程任取xA，中间过程3.对称任取x,yA，假设x,yR，中间过程y,xR。x,xR。x,xR。电子科技大学离散数学课程组——国家精品课程150-192020/1/22关系性质的证明方法(续)4.反对称任取x,yA，假设x,yR，y,xR，中间过程x＝y。或者任取x,yA，x≠y，假设x,yR，中间过程y,xR。5.传递任取x,y,zA，假设x,yR，y,zR，中间过程x,zR。电子科技大学离散数学课程组——国家精品课程150-202020/1/22定理6.4.1设R是集合A上的二元关系，则：（1）RIAR；（2）RR∩IA＝Φ；（3）RR＝R-1；（4）RR∩R-1IA；（5）RRRR。6.4.2关系性质的判断定理电子科技大学离散数学课程组——国家精品课程150-212020/1/22证明（4）“”设R是反对称的。对任意a,b∈R∩R-1，则a,b∈R且a,b∈R-1，即：a,b∈R且b,a∈R，由于R是反对称的，则a＝b。所以，a,b＝a,a∈IA，即R∩R-1IA。“”设R∩R-1IA。对任意a,b∈A，若a,b∈R且b,a∈R，则有：a,b∈R且a,b∈R-1，即：a,b∈R∩R-1。又因R∩R-1IA，所以，a,b∈IA，即a＝b。即R是反对称的。电子科技大学离散数学课程组——国家精品课程150-222020/1/22定理6.4.2设R,S是定义在A上的二元关系，则：(1)若R,S是自反的，则R-1,R∪S,R∩S,RS也是自反的；(2)若R,S是反自反的，则R-1,R∪S,R∩S也是反自反的。(3)若R,S是对称的，则R-1,R∪S,R∩S也是对称的。(4)若R,S是反对称的，则R-1,R∩S也是反对称的。(5)若R,S是传递的，则R-1,R∩S也是传递的。6.4.3关系性质的保守性注意：（1）逆运算与交运算具有较好的保守性；（2）并运算、差运算和复合运算的保守性较差。电子科技大学离散数学课程组——国家精品课程150-232020/1/226.5关系的闭包运算对于一个给定的关系，可能不具有某一个特殊性质。但是，如果我们希望它具有该特定的性质，那么应该怎么做呢？例如，对给定集合A={1,2,3}上的关系R={1,1,1,2,2,1}，它不具有自反性。根据自反性的定义，在关系R中添加2,2，3,3这两个元素后，所得到的新关系就具有自反性。另外，还可以添加2,2，3,3，1,3，得到的新关系仍然具有自反性。电子科技大学离散数学课程组——国家精品课程150-242020/1/226.5.1关系的闭包定义6.5.1设R是定义在A上的关系，若存在A上的另一个关系R′，满足：（1）R′是自反的(对称的、或传递的)；（2）对任何自反的(对称的、或传递的)关系R〞，如果RR〞，就有R′R〞，则称为R的自反闭包(ReflexiveClosure)(对称闭包(SymmetricClosure)、或传递闭包(TransitiveClosure))，分别记为r(R)(s(R)或t(R))。从定义6.5.1可以看出，关系的闭包是增加最少元素，使其具备所需性质的扩充。电子科技大学离散数学课程组——国家精品课程150-252020/1/22例6.5.1设A={1,2,3}，R={1,1,1,2,2,1,1,3}是A上的关系。试求R的自反闭包、对称闭包和传递闭包。解由关系的自反性定义知，R是自反的当且仅当对a∈A，都有a,a∈R，因此，在R中添上2,2和3,3后得到的新关系就具有自反性，且满足自反闭包的定义，即r(R)={1,1,2,2,3,3,1,2,2,1,1,3}；电子科技大学离散数学课程组——国家精品课程150-262020/1/22例6.5.1(续)由关系的对称性定义知，R是对称的当且仅当对a,b∈A，若a,b∈R，则必有b,a∈R，因此，在R中添上3,1后得到的新关系就具有对称性，且满足对称闭包的定义，即s(R)={1,1,1,2,2,1,1,3,3,1}；由关系的传递性定义知，R是传递的当且仅当对a,b,c∈A，若a,b∈R，且b,c∈R，则必有a,c∈R，因此，在R中添上2,2和2,3后得到的新关系就具有传递性，且满足传递闭包的定义。即t(R)={1,1,