《计算机数学基础(1)》离散数学辅导(4)-关系与函数

《《计算机数学基础(1)》离散数学辅导(4)-关系与函数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、9《计算机数学基础》离散数学辅导(4)¾¾第4章二元关系与函数(2002级用)中央电大冯泰本章重点：关系概念与其性质，等价关系和偏序关系，函数.一、重点内容1.关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.h二元关系，是一个有序对集合，设集合A,B，，记作xRy二元关系的定义域：Dom(R)；二元关系的值域：Ran(R)h关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法.列举法，如R＝{<1,1>,<1,2>}；描述法：如关系矩阵：RÍA×B，R的矩阵关系图：R是集合上的二元关系，若ÎR，由结点aI画有向弧到bj构成的图形.2.几

2、个特殊的关系空关系Æ；唯一是任何关系的子集的关系.全关系恒等关系，MI是单位矩阵.3.关系的运算h关系的集合运算，有并、交、补、差和对称差.h复合关系，有复合关系矩阵：(布尔运算)，有结合律：(R·S)·T＝R·(S·T)h逆关系，，(R·S)－1=S－1·R－1.4.关系的性质h自反性；矩阵的主对角线元素全为1；关系图的每个结点都有自回路.h反自反性；矩阵的主对角线元素全为0；关系图的每个结点都没有自回路.h对称性若，则；矩阵是对称矩阵，即；关系图中有向弧成对出现,方向相反.h反对称性若且，则x=y或若，则；矩阵不出现对称元素.h传递性若且，则；在关系图中，有从a到b的弧，有

3、从b到c的弧，则有从a到c的弧.判断传递性较为困难.可以证明：R是集合A上的二元关系，(1)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.9表4－1二元运算的并、交、补、差、逆、复合具有的性质表运算关系性质自反性反自反性对称性反对称性传递性R－1ÖÖÖÖÖR1ÈR2ÖÖÖ´´R1ÇR2ÖÖÖÖÖR1－R2´ÖÖÖ´R1·R2Ö´´´´IAÖÖÖÖÆÖÖÖÖ由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.

4、故IA，EA是等价关系.Æ具有反自反性、对称性、反对称性和传递性。Æ是偏序关系.关系性质的判定，可以用定义、关系矩阵或关系图.传递性的判定，难度稍大.也常如下判定：不破坏传递性的定义，可认为具有传递性.例如Æ可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性；5.关系的闭包设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R¢表示，使得R¢具有关系的自反(对称、传递)性质，R¢就是R的自反(对称、传递)闭包，记作r(R)，s(R)和t(R)。闭包的求法：定理12：；定理13：；定理14的推论：6.等价关系和偏序关系极大(小)元、最大(小)元问题h等价

5、关系和偏序关系是具有不同性质的两个关系.h等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线。h等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={b½bÎAÙaRb}.h偏序集的哈斯图偏序集概念和偏序集的哈斯图。哈斯图的画法：(1)用空心点表示结点，自环不画；(2)若a£b，则结点b画在上边，a画在下边，并画a到b的无向弧；(3)若,Î,则ÎR，此时，a到c的有向弧不画出.确定任一子集的最大(小)元，极大(小)

6、元.极大(小)元、最大(小)元、界一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一.且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样.7.函数h函数,设f是集合A到B的二元关系，"aÎA,$bÎB,且Îf，且Dom(f)=A，f是一个函数(映射).函数是一种特殊的关系.集合A×B的任何子集都是关系，但不一定是函数.函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制.二函数相等是指：定义域相同，对应关系相同，而且

7、定义域内每个对应值都相同.h函数的类型单射若9满射f(A)=B.即双射单射且满射.h复合函数即.复合成立的条件是：一般，但复合函数的性质：如果f,g都是单射的，则f·g是单射的；如果f,g都是满射的，则f·g是满射的；如果f,g都是双射的，则f·g是双射的；如果f,g是单射的，则f是单射的；如果f,g是满射的，则g是满射的；如果f·,g是双射的，则f是单射的，g是满射的.h反函数若f：A®B是双射，则有反函数f－1：B®A，二、实例例4.1设集合A＝{a,b},R是P(A)上的包含关系，写出