软件数学基础学习辅导—— 二元关系.doc

软件数学基础学习辅导 二元关系一、主要内容1.序偶与迪卡尔积2.关系的概念和性质：二元关系、关系矩阵与关系图。3.复合关系与逆关系 4.关系的自反性、对称性与反对称性、传递性。5.等价关系与等价类。6.偏序关系、偏序集、哈斯图、序关系、序集。7.函数、复合函数、反函数、单射、满射、双射。二、学习要求1.理解序偶与迪卡尔积的概念。2.理解关系的概念,练掌握关系矩阵与关系图。3.理解复合关系与逆关系的概念，掌握其求法。4.熟练掌握等价关系的概念；会判断等价关系。5.了解偏序关系、偏序集的概念，会用哈斯图表示；6.了解函数、复合函数与反函数的概念；掌握单射、满射、双射的判断方法。 7.知道序关系与序集的概念。 三、学习重点1. 知道关系的三种不同的表示方式, 会求给定关系的关系矩阵和关系图.2. 会判断给定关系是否具有某种特殊性质.3. 能熟练判断给定集合A上的二元关系是否为等价关系.4. 会由等价关系确定划分, 也会由划分决定等价关系.5. 掌握偏序集合的概念, 会画偏序关系的Hasse图, 也会由Hasse图给出偏序关系. 四、重、难点解析(一) 集合的笛卡尔积设A, B是两个集合, 称集合(x, y) | xA, yB 为集合A与B的笛卡尔积, 记作AB, 集合AB中的元素叫做有序对. 笛卡尔积有如下简单性质:(1) 如果用|A|来表示集合A所含元素的个数, 那么| AB |=|A| |B|. (2) A=, A=.(3) AB= BAA=B或者A, B之中至少有一个为空集.(4) 笛卡尔积对并和交运算都满足分配律:A(BC) = (AB)(AC), (BC)A = (BA)(CA), A(BC) = (AB)(AC), (BC)A = (BA) (CA). (5) 如果AC, BD, 那么ABCD.请自己给出上述性质的证明. 尤其是应该给出最后一个命题的逆命题不成立的例子.(二) 集合上的二元关系我们主要研究给定集合A上的二元关系. 所谓集合A上的一个二元关系, 说通俗一点就是给定一个法则R, 对于A中任意两个元素a, b, 利用这个法则可以判定a与b是否具有关系R. 如果使用更数学化的语言来叙述, 就是: R就是AA的一个子集. 比较平凡的关系有: 空关系, 恒等关系, 全关系. 我们要研究关系所具备的一些常见性质. 这类似于我们研究函数的常见性质. 所有这些研究, 必须建立在对关系有一个比较方便的表示方式. 下面就是关系最常用的三种表示方式: 集合、关系矩阵和关系图, 其中关系矩阵和关系图只能用来表示有限集合A上的关系. 1. 集合表示法因为集合A上的关系R就是AA的一个子集, 这样作为集合的R当然也就可以用列举法和描述法来加以表示. 例如 A=2, 3, 4, 6, 对于A上的整除关系R, 我们可以用描述法也可以用列举法来表示这个关系:R=(a, b) | a, bA且a整除b 或R=(2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (6, 6).2. 矩阵表示法设R是从有限集合A=a1, a2, , am上的一个关系, 可以按照如下方式定义一个m阶矩阵:矩阵MR为R的关系矩阵. 用关系矩阵来表示二元关系, 非常方便. 上面例1中集合A=2, 3, 4, 6上的整除关系R的矩阵为:需要注意的是关系矩阵并不是绝对唯一的, 与集合A的元素次序有关系.矩阵表示法最大的优点是, 很容易判定关系是否满足自反性, 对称性, 反对称性. 对于传递性, 也可以通过计算关系矩阵的乘积来判定, 但是多少有点麻烦.3. 有向图表示法设R是从有限集合A=a1, a2, , am上的二元关系, 以A的元素为顶点, 用一个从a到b的箭头来表示aRb, 则可以得到一个有向图, 称为R的关系图.例如 设A=1, 2, 3, 4, R=(1, 1), (1, 2) , (1, 3), (2, 3), (2, 4), (3, 4), (4, 2), 则R的关系图为: (三) 关系的运算 既然关系可看作AA的子集, 因此可以说关系也是集合. 所以, 对于同一个集合A上的关系, 可以进行交、并、差、补等运算. 但是, 对于关系而言, 最重要的两种运算是逆运算和复合运算. 这两种运算可以帮助判断给定关系是否具有某种特殊的性质. 逆运算: 设RAA是集合A上的关系, 则R-1=(x, y) | (y, x)R称为R的逆关系. 复合运算: 设RAA, SAA是二元关系, 则T=(x, z)|$yB使得(x, y)R且(y, z)S称为R与S的复合关系, 记作T=RoS或T=RS. 逆关系十分容易确定. 考虑一下, 关系与其逆关系R-1关系矩阵和关系图有什么关系? 下面用一个简单例子来说明如何进行关系的复合运算. 例如 设A=a, b, c, d, 定义A上的关系R如下:R=(a, a) , (a, b), (b, d), (c, a), (d, c), 求复合关系R2=RoR.分析: 计算复合关系RoR一般有三种方法, 可以根据不同的情况选取不同的计算, 下面我们只采用其中一种, 其余见书中有关例题.解 根据关系R中所包含的有序对, 按照复合关系RoR的定义: (a,b), (b, c)R(a,c)R2. 由此可得R2=(a, a) , (a, b), (a, d), (b, c), (c, a), (c, b), (d, a). (四) 关系的常见性质对于集合A上的二元关系R, 我们最关系的性质有:自反性: 若对于任意的都有, 则称是A上的一个自反关系. 对称性: 若对于任意的都有“xRyyRx”, 则称R是A上的一个对称关系.传递性: 若对于任意的都有“xRy, yRzxRz”, 则称R是A上的一个传递关系.反对称性: 若对于任意的都有“xRy, yRxx=y”, 则称R为集合A上的一个反对称关系. 如何判断给定的二元关系是否具有上述某个性质? 可以根据关系的不同表示方式来加以考察. 1. 利用定义考察关系R的性质自反性: 对于任意aA, R必须包含(a, a). 即: IAR.对称性: 若R包含(a, b), 则R必须同时包含(b, a). 即: R-1=R.传递性: 若R包含(a, b), (b, c), 则R必须同时包含(a, c). 即: R2R.反对称性: 若R包含(a, b), 而且ab, 则R不能同时包含(b, a). 即: RR-1 IA.2. 利用关系矩阵MR考察关系R的性质自反性: MR主对角线元素必须都是1.对称性: MR必须是对称矩阵. 即: MRT=MR.传递性: MR-MR2不出现负数.反对称性: 若ij, (i, j)位置与(j, i)位置不能同时为1(但是可以同时为0).3. 利用关系图考察关系R的性质自反性: 每个顶点必须有环.对称性: 若从a到b有有向边, 则从b到a也必须有有向边.传递性: 若从a到b有有向边, 从b到c有有向边, 则必须有从a到c的有向边.反对称性: 若ab, 从a到b有有向边, 则不能有从b到a的有向边.以上方法可以说各有好处. 第一种容易理解, 第二种容易计算, 第三种比较直观. 如果所使用的计算机编程能力比较强, 不妨自己编写程序, 让计算机来判断关系是否具有某种性质. (五) 等价关系与集合的划分等价关系: 若集合A上的二元关系R具有自反性、对称性、传递性, 则称其为等价关系.等价关系是最常用也是最重要的二元关系. 我们熟悉的: 数的相等关系、直线的平行关系都是等价关系. 但是, 实数的小于等于关系、集合的包含关系都不是等价关系.划分: 若集合的一个非空子集族满足（1）; （2）, 则称是的一个划分. 设R是A上的等价关系, aA, 集合aR=xA | (x, a)R称为a所在的等价类. 设R是A上的等价关系, 则 集合上的一个等价关系可以唯一确定的一个划分：; 集合的一个划分也可以唯一确定上的一个等价关系：.认清等价关系与划分本质是一回事是理解这两个概念的关键.例如 考虑整数集合Z上模5同余关系R5. 这是一个等价关系, 即R5=(x, y) | x y (mod 5).这个等价关系刚好有下列5个等价类:(五) 偏序关系偏序关系: 若集合A上二元关系具有自反性、传递性、反对称性, 则称R为集合A上的一个偏序关系, 称A为带有偏序关系R的偏序集, 记作(A, ).偏序集合的偏序关系 “”, 也读作“小于等于”. 之所以采用这样的符号和名称, 是因为偏序关系和小于等于关系具有完全相似的性质. 集合的包含关系也是偏序关系. 设(A, )是偏序集, 则A中的任何两个元素a, b只可能出现如下四种情况之一:a = b, a b, b a, a与b不可比较.顺便提一下, 如果一个偏序集合当中任意两个元素都可以比较, 就称为全序集.偏序关系的重要性不亚于等价关系. 对于这种特殊的关系, 我们也采用特殊的方式来表示, 这种表示方式就是Hasse图表示法.设有偏序集(A, ), 则其Hasse图构造法如下：S1. 以“点”表示A中的元素; S2. 若y是x的直接后继, 则y在x的上方; S3. 在x和x的直接后继间连线.例如 设A是正整数12的全部正整数因子组成的集合, 并设偏序关系为整除关系“|”, 则这个偏序关系的Hasse图如下: 五、 典型例题例1 设A=2, 3, 6, 12, R是A上的整除关系.（1） 给出R的集合表示式.（2） 给出R的关系矩阵.（3） 画出R的有向图.（4） 考察关系R是否具有自反性、对称性、传递性、反对称性.（5） R是否为等价关系? R是否为偏序关系? 分析 首先根据整除关系的含义, 列出A中整除有序数对: 2|2, 2|6, 2|12, 3|3, 3|6, 3|12, 6|6, 6|12, 12|12. 此即R所包含的全部有序对. 至于其矩阵和有向图很容易根据R的集合表达式得到. 然后可以利用定义、关系矩阵或者关系图来判定R所具有的性质. 最后根据这些性质就能知道这个关系是一个什么样的关系. 解 （1）根据关系R的定义:R=(2, 2), (2, 6), (2, 12), (3, 3), (3, 6), (3, 12), (6, 6), (6, 12), (12, 12).（2）R的关系矩阵MR如下:（3）R的关系图略. (4) 可以从R的意义、集合表示、关系矩阵或者关系图得到R自反、传递、反对称. (5) 根据(4)我们知道R是偏序关系, 不是等价关系. 例2 设T=1, 2, 3, , 9, A=TT. 按照下列方式定义集合A上的关系R:(a, b)R(c, d) a + d= b + c(1) 证明R是A上的等价关系.(2) 求出元素(5, 2)所在的等价类(5, 2).分析 求解本题时要注意集合A的元素本身都是有序对. 这样R由形如(2, 1), (3, 2)的元素组成. 由于|A|=81, 因此并不一定非要列举出R所包含的全部元素. 可以直接按照R的定义直接验证R满足: (i)自反性: (a, b)R(a, b); (ii) 对称性: (a, b)R(c, d) (c, d)R(a, b) ; (iii) 传递性: (a, b)R(c, d), (c, d)R(u, v) (a, b)R(u, v). 由此证明R是A上的等价关系.根据R的定义, 可以看出(a, b)R(c, d) a + d= b + c a - b = c - d. 由此看见, (a, b)R(5, 2) a-b=5-2=3.根据这个特点很容易写出等价类(5, 2).解 (1) (i) R满足自反性: 设 (a, b)A, a+b=b+a(a, b)R(a, b);(ii) R满足对称性: (a, b)R(c, d)a+d=b+cc+b=d+a (c, d)R(a, b) ; (iii)R满足传递性: (a, b)R(c, d), (c, d)R(u, v)a+d=b+c, c+v=d+u a-b=c-d=u-v a + v= b + u (a, b)R(u, v) 所以R是等价关系.(2) (5, 2)=(4, 1), (5, 2), (6, 3), (7, 4), (8, 5), (9, 6).例3 设A=a, b, c, d, e, f, 有一个划分S=a, b, c, d, e, f, 试由划分S确定A上的一个等价关系R.分析 根据题设要求, 我们需要求一个等价关系R, 使得R 的等价关类恰好是上述划分S中的三个子集合. 要使得a, b, c成为R的一个等价类, 那么其中的任意两个元素都满足关系R, 从而R必须包含这个子集中元素构成的任意一个有序对, 必然有R1=a, b, ca, b, cR, R2=d, ed, e R, R3=ff R.只要令R= R1 R2 R3即可. 解 我们用如下办法产生一个等价关系R:R1=a, b, ca, b, c=(a, a), (b, b), (c, c), (a, b), (a, c), (c, a), (b, c), (c, b)R2=d, ed, e=(d, d), (e, e), (d, e), (e, d)R3=ff=(f, f) R.R=R1R2R3.容易证明R是等价关系, 而且等价类正是S中的三个子集.例4 设有集合A=a, b, c, d, e上的偏序关系:R=(a, b), (a, c), (a, d), (a, e), (b, d), (b, e), (c, d), (c, e), (d, e)IA.画出Hass