资源描述：
《离散数学等价偏序函数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六节等价关系与划分主要内容等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应一、等价关系的定义与实例定义7.15设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若∈R,称x等价于y,记做x～y.在我们日常生活和学习中，就有一些等价关系的例子，如：（1）在一群人的集合上年龄相等的关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递的。（2）命题公式间的逻辑等值关系是等价关系。（3）集合上的恒等关系是等价关系。（4）在同一平面上直线之间
2、的平行关系，三角形之间的相似关系都是等价关系。实例设A={1,2,…,8},如下定义A上的关系R：R={
3、x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.不难验证R为A上的等价关系,因为x∈A,有x≡x(mod3)x,y∈A,若x≡y(mod3),则有y≡x(mod3)x,y,z∈A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3)图6模3等价关系的关系图图6二、等价类及其性质1．等价类定义7.16设R为非空集合A上的等价关系,x∈
4、A，令[x]R={y
5、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}即A中所有和x有R关系的元素的集合。2．等价类的性质定理7.14设R是非空集合A上的等价关系,则（1）xA,[x]是A的非空子集.（2）x,yA,如果xRy,则[x]=[y].（3）x,yA,如果xy,则[x]与[y]不交.（4）∪{[x]
6、xA}=A三
7、、商集与集合的划分1.定义7.17设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,A/R={[x]R
8、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}}2．集合的划分定义7.18设A为非空集合,若A的子集族π(πP(A))满足下面条件：（1）π（2）xy(x,yπ∧x≠y→x∩y=)（3）∪π=A则
9、称π是A的一个划分,称π中的元素为A的划分块例设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的划分.四、商集与划分的对应关系商集A/R就是A的一个划分,不同的商集对应于不同的划分.任给A的一个划分π,如下定义A上的
10、关系R：R={
11、x,yA∧x与y在π的同一划分块中}则R为A上的等价关系,且该等价关系所确定的商集就是π.A上的等价关系与A的划分是一一对应的.例给出A＝{1,2,3}上所有的等价关系 解如下图,先做出A的所有划分,从左到右分别记作π1,π2,π3,π4,π5.123图7这些划分与A上的等价关系之间的一一对应是：π4对应于全域关系EA,π5对应于恒等关系IA,π1,π2和π3分别对应于等价关系R1,R2和R3.其中R1={<2,3>,<3,2>}∪IAR2={<1,3>,<3,1>}∪IAR3={<1,2>,
12、<2,1>}∪IA附录：等价关系在计算机科学中的应用关系概念对计算机科学的理论和应用都非常重要，复合的数据结构、如陈列表、树等，用来表示数据的集合，这些数据是由元素间的关系联系的。关系是数学模型的一部分，它常常在数据结构内隐含地体现出来，数值应用、信息检索、网络问题等就是关系的应用领域，因而关系的运算和处理是重要的。关系在包括程序结构和算法分析的理论方面也有重要的作用。例：在信息检索系统中，所有生物的集合X可分割成{P，A}，P表示所有植物集合，A表示所有动物集合；也可构成{E，F}，E表示史前生物，F表示史后生物，其交叉划分Q
13、={P∩E,P∩F,A∩E,A∩F}第七节偏序关系一、偏序关系1．定义7.19偏序关系：非空集合A上的自反、反对称和传递的关系，记作≼.设≼为偏序关系,如果∈≼,则记作x≼y,读作x“小于或等于”y.2.实例集合A上的恒等关系IA是A上的偏序关系.小于
