离散数学复习辅导之一

《离散数学复习辅导之一》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、8离散数学复习辅导之一第1章关系与函数一、主要内容1．有序对与笛卡儿积h有序对，就是有顺序的数组，如，x,y的位置是确定的，不能随意放置.注意：有序对¹，以a,b为元素的集合{a,b}={b,a}；有序对(a,a)有意义，而集合{a,a}是单元素集合，应记作{a}.h笛卡儿积，把集合A，B合成集合A×B，规定A×B＝{½xÎAÙyÎB}由于有序对中x,y的位置是确定的，因此A×B的记法也是确定的，不能写成B×A.笛卡儿积也可以多个集合合成，A1×A2×…×An.笛

2、卡儿积的运算性质.一般不能交换.2．关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.h二元关系，是一个有序对集合，设集合A，B，从集合A到B的二元关系，记作xRy．二元关系的定义域：Dom(R)；二元关系的值域：Ran(R)h关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法.列举法，如R＝{<1,1>,<1,2>}；描述法：如关系矩阵：RÍA×B，R的矩阵关系图：R是集合上的二元关系，若ÎR，由结点aI画有向弧到bj构成的图形.3．几个特殊的关系空关系Æ；唯一是任何关

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

4、则；在关系图中，有从a到b的弧，有从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.表4－1二元运算的并、交、补、差、逆、复合具有的性质表运算关系性质自反性反自反性对称性反对称性传递性R－1ÖÖÖÖÖR1ÈR2ÖÖÖ´´R1ÇR2ÖÖÖÖÖR1－R2´ÖÖÖ´R1·R2Ö´´´´IAÖÖ

5、ÖÖÆÖÖÖÖ由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系.Æ具有反自反性、对称性、反对称性和传递性．Æ是偏序关系.关系性质的判定，可以用定义、关系矩阵或关系图.6.关系的闭包设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R¢表示，使得R¢具有关系的自反(对称、传递)性质，R¢就是R的自反(对称、传递)闭包，记作r(R)，s(R)和t(R)．闭包的求法：定理12：自反闭包；定理13：对称闭包；定理14的推论：传递闭包7.等价关系、

6、相容关系和偏序关系h等价关系、相容关系和偏序关系是具有不同性质的两个关系.？h等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线．h等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={b½bÎAÙaRb}.h相容类，设B是A的子集，如果在B中的任意两个元素都是相关的，则称为由相容关系R产生的相容类．8h偏序集的哈斯图偏序集概念和偏序集的哈斯图．哈斯图的画法：(1)用空心点表示结

7、点，自环不画；(2)若a£b，则结点b画在上边，a画在下边，并画a到b的无向弧；(3)若,Î,则ÎR，此时，a到c的有向弧不画出.确定任一子集的最大(小)元，极大(小)元.极大(小)元、最大(小)元、界一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一.且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样.8.函数h函数,设f是集合A到B的二元关系，"aÎA,$bÎ

8、B,且Îf，且Dom(f)=A，f是一个函数(映射).函数是一种特殊的关系.集合A×B的任何子集都是关系，但不一定是函数.函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制.二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同.h函数的类型单射若满射f(A)=B.即双射单射且满射.h复合函数若即.复合成立的条件