计算机数学基础离散数学辅导-眉山广播电视大学.DOC

PAGE 1 PAGE 1 《计算机数学基础》离散数学辅导 －关系与函数 教学辅导 四川广播电视大学 计算机教研室 责任教师 孙继荣 028 本章重点：关系概念与其性质，等价关系和偏序关系，函数. 一、重点内容 1. 关系的概念 包括定义、关系的表示方法：集合表示、矩阵表示、图形表示. ?二元关系，是一个有序对集合，设集合A,B，，记作xRy 二元关系的定义域：Dom(R)； 二元关系的值域：Ran(R) ?关系的表示方法： 集合表示法：关系是集合，有类似于集合的表示方法. 列举法，如R＝{1,1,1,2}；描述法：如 关系矩阵： R?A×B，R的矩阵 关系图： R是集合上的二元关系，若aI,bj?R，由结点aI画有向弧到bj构成的图形. 2. 几个特殊的关系 空关系?；唯一是任何关系的子集的关系. 全关系 恒等关系，MI是单位矩阵. 3. 关系的运算 ?关系的集合运算，有并、交、补、差和对称差. ?复合关系 ，有 复合关系矩阵：(布尔运算)，有结合律：(R?S)?T＝R?(S?T) ?逆关系，，(R?S)－1=S－1?R－1. 4. 关系的性质 ?自反性 ；矩阵的主对角线元素全为1；关系图的每个结点都有自回路. ?反自反性 ；矩阵的主对角线元素全为0；关系图的每个结点都没有自回路. ?对称性 若，则；矩阵是对称矩阵，即；关系图中有向弧成对出现,方向相反. ?反对称性 若且，则x=y或若，则；矩阵不出现对称元素. ?传递性 若且，则；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧. 判断传递性较为困难. 可以证明：R是集合A上的二元关系， R是自反的?IA?R; (2)R是反自反的?IA?R＝?; (3)R是对称的 ?R＝R－1； (4)R是反对称的?R?R－1?IA； (5)R是传递的?R?R?R. 关系的性质所具有的运算见表4－1. 表4－1 二元运算的并、交、补、差、逆、复合具有的性质表 运算 关系性质 自反性 反自反性 对称性 反对称性 传递性 R－1 ? ? ? ? ? R1?R2 ? ? ? ? ? R1?R2 ? ? ? ? ? R1－R2 ? ? ? ? ? R1?R2 ? ? ? ? ? IA ? ? ? ? ? ? ? ? ? 由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系.?具有反自反性、对称性、反对称性和传递性。?是偏序关系. 关系性质的判定，可以用定义、关系矩阵或关系图. 传递性的判定，难度稍大. 也常如下判定：不破坏传递性的定义，可认为具有传递性. 例如?可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性； 5. 关系的闭包 设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R?表示，使得R?具有关系的自反(对称、传递)性质，R?就是R的自反(对称、传递)闭包，记作r(R) ，s(R)和t(R)。闭包的求法： 定理12：；定理13：；定理14的推论： 6. 等价关系和偏序关系 极大(小)元、最大(小)元问题 ?等价关系和偏序关系是具有不同性质的两个关系. ?等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线。 ?等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={b?b?A?aRb}. ?偏序集的哈斯图 偏序集概念和偏序集的哈斯图。哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若a?b，则结点b画在上边，a画在下边，并画a到b的无向弧；(3) 若a,b,b,c?,则a,c?R，此时，a到c的有向弧不画出. 确定任一子集的最大(小)元，极大(小)元. 极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样. 7. 函数 ?函数, 设f是集合A到B的二元关系，?a?A,?b?B,且a,b?f，且Dom(f)=A，f是一个函数(映射). 函数是一种特殊的关系. 集合A×B的任何子集都是关系，