等价关系与等价类.doc_第1页
等价关系与等价类.doc_第2页
等价关系与等价类.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

定义10.6.1 对非空集合上的关系 ，如果是自反的、对称的和传递的，则称为上的等价关系。等价关系的例子很多，如平面上三角形集合中，三角形的相似关系是等价关系；上海市的居民的集合中，住在同一区的关系也是等价关系。等价关系的关系图具有以下特征：1每个结点都由自回路，即R是自反的；2两个结点a,b之间若有从a指向b的弧，就有从b指向a的弧，即R是对称的；3若有从a指向b的弧，且有从b指向c的弧，就有从a指向c的弧，即R是传递的。第9章给出了用平面坐标系中的矩形表示笛卡儿积的图形表示法。显然可以用正方形表示 ，如图10.6.2(a)所示。A上的关系是的子集，因此可以用正方形的子集表示。A上的等价关系可以用正方形的一条对角线和线上的若干正方形表示。如图10.6.2(b)所示。但图10.6.2(c)所表示的关系不是等价关系。它包括了对角线，所以有自反性。它以对角线为对称轴，所以有对称性。但它没有传递性。因为R中的a和b点对应的有序对，经传递得到c点对应的有序对应在R中，但c点不在R中。图10.6.2例1 在非空集合A上的恒等关系和全关系都是等价关系。在所有谓词公式的集合上的等值关系也是等价关系。例2 集合上的关系。其中表示可被3整除。对任意的可被3整除。若可被3整除，则也可被3整除。若和可被3整除，则可被3整除。所以，R具有自反性、对称性和传递性，R是A上的等价关系。R的关系图如图10.6.1所示。在图中，A的元素被分成三组，每组中任两个元素之间都有关系，而不同组的元素之间都没有关系。这样的组称为等价类。 图10.6.1 定义10.6.2 R是非空集合A上的等价关系，对任意的，令 则称集合为x关于R的等价类，简称x的等价类，也可简记作x或。例3 对例2的等价关系R,有三个不同的等价类:，。A的8个元素各有一个等价类。各等价类之间，或者相等，或者不相交。而且所有等价类的并集就是A。整数集合Z上的模n等价关系，即可以根据任何整数除以n（n为正整数）所得余数进行分类，构成n个等价类，记作即定理10.6.1 R是非空集合A上的等价关系，对任意的，成立（1） 且， （2）若，则，（3）若，则，（4）。证明（1） 对任意的，则，因此 。由等价类定义，显然。（2）对任意的，有。由对称性，有和传递性，有，所以。类似可证 。因此，。（3）假设 。则存在，使得且。即且，由对称性，由传递性。与已知矛盾。（4）对任意的 。则有。反之，对任意的，则有。所以，。因此 。由定理可知，对A上的等价关系R，所有等价类的集合具有很好的性质。定义10.6.3 对非空集合A上的
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论