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

软件数学基础学习辅导—— 二元关系 一、主要内容 1.序偶与迪卡尔积2.关系的概念和性质二元关系、关系矩阵与关系图。复合关系与逆关系 4关系的自反性、对称性与反对称性、传递性。 等价关系与等价类。偏序关系、偏序集、哈斯图、序关系、序集。函数、复合函数、反函数、单射、满射、双射。 1.理解序偶与迪卡尔积的概念理解关系的概念,练掌握关系矩阵与关系图 3.理解复合关系与逆关系的概念，掌握其求法。 等价关系；会判断等价关系。 了解偏序关系、偏序集的概念，会用哈斯图表示；了解函数、复合函数与反函数的概念；掌握单射、满射、双射的判断方法。 7.知道序关系与序集的概念。 三、学习重点 1. 知道关系的三种不同的表示方式, 会求给定关系的关系矩阵和关系图. 2. 会判断给定关系是否具有某种特殊性质. 3. 能熟练判断给定集合A上的二元关系是否为等价关系. 4. 会由等价关系确定划分, 也会由划分决定等价关系. 5. 掌握偏序集合的概念, 会画偏序关系的Hasse图, 也会由Hasse图给出偏序关系. 四、重、难点解析 (一) 设A, B是两个集合, 称集合{(x, y) | x(A, y(B }为集合A与B的笛卡尔积, 记作A(B 集合A(B中的元素叫做有序对笛卡尔积有如下简单性质: (1) 如果用|A|来表示集合A所含元素的个数, 那么| A(B |=|A| |B|. A((=(, ((A=(. A(B= B(A(A=B或者A, B之中至少有一个为空集(. 笛卡尔积对并和交运算都满足分配律: A((B(C) = (A(B)((A(C), (B(C)(A = (B(A)((C(A), A((B(C) = (A(B)((A(C), (B(C)(A = (B(A) ( (C(A). 如果A(C, B(D, 那么A(B(C(D. (二) 集合上的二元关系 我们主要研究给定集合A上的A上的一个二元关系, 说通俗一点就是给定一个法则R, 对于A中任意两个元素a, b, 利用这个法则可以判定a与b是否具有关系R. 如果使用更数学化的语言来叙述, 就是: R就是A(A的一个子集. 比较平凡的关系有: 空关系, 恒等关系, 全关系. 我们要研究关系所具备的一些常见性质. 这类似于我们研究函数的常见性质. 所有这些研究, 必须建立在对关系有一个比较方便的表示方式. 下面就是关系最常用的三种表示方式: 集合、关系矩阵和关系图, 其中关系矩阵和关系图只能表示有限集合A上的关系. 1. 集合表示法 因为集合A上的关系R就是A(A的一个子集, 这样作为集合的R当然也就可以用列举法和描述法来加以表示. 例 A={2, 3, 4, 6}, 对于A上的整除关系R, 我们可以用描述法也可以用列举法来表示这个关系: R={(a, b) | a, b(A且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的箭头来表示aRbR的关系图. 例设A={1, 2, 3, 4}, R={(1, 1), (1, 2) , (1, 3), (2, 3), (2, 4), (3, 4), (4, 2)}, 则R的关系图为: () 关系的运算 A(A的子集, 因此可以说关系也是集合. 所以, 对于同一个集合A上的关系, 可以进行交、并、差、补等运算. 但是, 对于关系而言, 最重要的两种运算是逆运算和复合运算. 设R(A(A是A上的关系, 则R(1={(x, y) | (y, x)(R}称为R的逆关系. 复合设R(A(A, S(A(A是二元关系, 则 T={(x, z)|(y(B使得(x, y)(R且(y, z)(S} 称为R与S的复合关系, 记作T=R(S或T=RS. R(1关系矩阵和关系图有什么关系? 下面用一个简单例子来说明如何进行关系的运算. 例 设A={a, b, c, d}, 定义A上的关系R如下: R={(a, a) , (a, b), (b, d), (c, a), (d, c)}, 求复合关系R