离散数学复习辅导之一

《离散数学复习辅导之一》由会员分享，可在线阅读，更多相关《离散数学复习辅导之一（8页珍藏版）》请在金锄头文库上搜索。

1、1离散数学复习辅导之一第 1 章 关系与函数一、主要内容1有序对与笛卡儿积 有序对，就是有顺序的数组，如，x, y 的位置是确定的，不能随意放置.注意：有序对 ，以 a, b 为元素的集合a, b=b, a；有序对( a, a)有意义，而集合 a, a是单元素集合，应记作a . 笛卡儿积，把集合 A，B 合成集合 AB，规定ABxAy B由于有序对中 x, y 的位置是确定的，因此 AB 的记法也是确定的，不能写成BA. 笛卡儿积也可以多个集合合成，A 1A2An. 笛卡儿积的运算性质. 一般不能交换.2关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示. 二元关系，是一个有序对

2、集合，设集合 A，B，从集合 A 到 B 的二元关系，,yxyR记作 xRy二元关系的定义域：Dom(R) ； 二元关系的值域：Ran( R) 关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法. 列举法，如 R,；描述法：如 ,ByAxy关系矩阵： RAB，R 的矩阵 njmibRarMiijnmijR ,.2101)(关系图：R 是集合上的二元关系，若R，由结点 aI 画有向弧到 bj 构成的图形.3几个特殊的关系空关系；唯一是任何关系的子集的关系. 全关系 AbEA,恒等关系 ，M I 是单位矩阵. aI4关系的运算 关系的集合运算，有并、交、补、差和对称差. 复合关系 ，有

3、, 2121 RcbabcR使复合关系矩阵： (布尔运算)，有结合律：(RS)TR (ST)21 逆关系 ， ，(RS) 1 =S1 R1 . ,yx T15关系的性质 自反性 ；矩阵 的主对角线元素全为 1；关系图的每个结Ax,RM点都有自回路. 反自反性 ；矩阵 的主对角线元素全为 0；关系图的每个x,结点都没有自回路. 对称性 若 ，则 ；矩阵 是对称矩阵，即 ；关Ry,y,Rjiijr2系图中有向弧成对出现,方向相反. 反对称性 若 且 ，则 x=y 或若 ，则Ryx,xy, yxR,；矩阵 不出现对称元素.Rxy,RM 传递性 若 且 ，则 ；在关系图中，有从 a 到 bba,c,c

4、a,的弧，有从 b 到 c 的弧，则有从 a 到 c 的弧. 判断传递性较为困难.可以证明：R 是集合 A 上的二元关系，(1) R 是自反的I AR; (2) R 是反自反的 IAR ;(3) R 是对称的 RR 1 ； (4) R 是反对称的 RR1 IA；(5) R 是传递的RR R. 关系的性质所具有的运算见表 41. 表 41 二元运算的并、交、补、差、逆、复合具有的性质表运算 关系性质 自反性 反自反性 对称性 反对称性 传递性R1 R1R2 R1R2 R1R 2 R1R2 IA 由表可见，I A 具有自反性，对称性、反对称性和传递性.E A 具有自反性，对称性和传递性.故 IA，

5、E A 是等价关系. 具有反自反性、对称性、反对称性和传递性是偏序关系.关系性质的判定，可以用定义、关系矩阵或关系图. 6. 关系的闭包设 R 是非空集合 A 上的二元关系，在关系 R 中，添加最少的有序对，新关系用 R表示，使得 R具有关系的自反 (对称、传递)性质，R就是 R 的自反( 对称、传递)闭包，记作 r(R) ，s(R)和 t(R)闭包的求法：定理 12：自反闭包 ；AIr)(定理 13：对称闭包 ；1s定理 14 的推论：传递闭包 niRt1)(7. 等价关系、相容关系和偏序关系等价关系、相容关系和偏序关系是具有不同性质的两个关系. ？ A价价 价等价关系图的特点：每一个结点都

6、有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从 a 到 b，从 b 到 c 各有一条有向弧线，则从 a 到 c 一定有有向弧线等价类，若 R 是等价关系，与 R 中的某个元素等价的元素组成的集合，就是 R 的一个等价类，a R=bbAaRb. 相容类，设 B 是 A 的子集，如果在 B 中的任意两个元素都是相关的，则称为由相容关系 R 产生的相容类3偏序集的哈斯图 偏序集概念和偏序集的哈斯图哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若 ab，则结点 b 画在上边，a 画在下边，并画 a 到 b 的无向弧；(3) 若,则R，此时，a 到 c 的有向弧不画出.确定任一子

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

8、二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同. 函数的类型单射 若 )(2121ff满射 f(A)=B. 即 )(,xfyAxy使 得双射 单射且满射. 复合函数 若 即 .,:,:,: CgfBgf 则 )()(xfgf复合成立的条件是： )(Dom)(Ranf一般 ，但fgfhf复合函数的性质： 如果 f,g 都是单射的，则 fg 是单射的； 如果 f,g 都是满射的，则 fg 是满射的；如果 f,g 都是双射的，则 fg 是双射的； 如果 f,g 是单射的，则 f 是单射的；如果 f,g 是满射的，则 g 是满射的；如果 f,g 是双射的，则 f 是单射的，g

9、是满射的. 反函数 若 f：AB 是双射，则有反函数 f1 ：BA，,)(,1 abba fffg11)(,)(二、实例例 1 设给定集合 Aa,b，写出 P(A)和 P(A)上的包含关系的集合表达式解 ,)(P, bababa例 2 设 A1,2,3,用列举法给出 A 上的恒等关系 IA，全关系 EA，A 上的小于关系 ,yxyxL及其逆关系和关系矩阵. 解 3,2,1,AIAIE ,23,1,1, LA 的逆关系, 2,31,1. 有 0ALM011ALMTLAM14例 3 设集合 A=a, b, c，A 上的二元关系R,，S=,求 RS，并用关系矩阵验证解R S,10,01SRM，SR从

10、矩阵也可得 RS,例 4 设 R 和 S 是集合 A1,2,3上的二元关系，R,S=,求 RS 和 S2 以及 M 2S解 RS= ,= 3,2,3,1,3,1 S2=SS=,= 10S例 5 设 R 是实数集，R 上的二元关系 S 为Sx,yRx=y试问二元关系 S 具有哪些性质？简单说明理由解 12. S 具有自反性，显然S； S 具有对称性，S，有 x=y，则S； S 具有反对称性，,S，有 x=y； S 具有传递性，,S,因为 x=y=z，故S例 6设集合 A1,2,3,4,A 上的二元关系 R1,2,3,2,2,3,3,4 （1）求出 R2，R 3 的集合表达式；（2）画出 R2 的

11、关系图解(1)R 2=, R3=,(2) R2 的关系图如例 6 图例 7 设集合 Aa,b,c,d,e，定义 A 上的二元关系AIde,1,2 edcb判断 R1，R 2 是否为等价关系？分析 判断等价关系，就是验证是否具有自反性、对称性和传递性. 解 写出 R1 的关系矩阵，1 24 3例 6 图 R2 的关系图51010RM由关系矩阵可知，R 1 具有自反性和对称性. 由关系图(例 7 图) 可知它具有传递性，故R1 是等价关系. R2 不是等价关系，因为 ，故 R 不具有自反性. ),(),(22eRa或注意：自反性，对称性和传递性之一不具备，就是破坏了等价关系的定义. 事实上 ，故

12、R2 不具有对称性； ，2,deed但 2,Rab，R 2 也不具有传递性. ,a但对例 7 的 R1 进行分类：元素 a，因为 均属于 R1，所以ba,a 生成的等价类 或记作 .,b1R元素 c，因为 ，所以 c 生成的等价类 ;1c1cR类似地， d 生成的等价类 .,ed1例 8 设集合 A0，1，2，3 ，4，5，6 上的偏序关系 R 如下：R,，I A做偏序集的哈斯图，并求 B=0,2,3的极大元、极小元、最大元和最小元，B 的上界和最小上界，下界和最大下界 解 A0,1,2,3,4,5,6, B =0，2，3，哈斯图如例 8 图所示 B 的极大元：2，3, B 的极小元：0B 的最大元：无 B 的最小元：0 B 的上界为 5，最小上界也是 5；B 的下界和最大下界均为 0若 C0,3，那么 C 的上界为 5，3，最小上界为 3若 D4,6，那么 D 的上界和最小上界为 6，下界为 0，4，最大下界为 4再强碉一下，子集 B 的极大(小) 、最大(小)元，一定是 B 的元素；而 B 的界可以不是B 的元素，只要是所讨论的集合 A 的元素即可例 9 已知如图，集合 A 上的关系，请回答下列问题： 1 1 1 1 1 12 2 2 2 2 23 3 3 3 3 34 4 4 4 4 4f