内容发布更新时间 : 2024/11/18 12:41:30星期一 下面是文章的全部内容请认真阅读。
离散数学常考题型梳理 第2章 关系与函数
一、题型分析
本章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容。常涉及到的题型主要包括：
2-1关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算 2-2关系自反和反自反、对称和反对称等性质的概念理解与判定；自反、对称和传递闭包运算。
2-3等价关系 2-4偏序关系和哈斯图 2-5 函数的概念和性质
因此，在本章学习过程中希望大家要清楚地知道： 1．有序对和笛卡尔积
（1）有序对：所谓有序对就是指一个有顺序的数组，如 < x , y >，x , y 的位置是确定的，且< a , b >< b , a >。
（2）笛卡尔积：把集合A，B合成集合A×B，规定：
A?B?{?x,y?|x?A且y?B}
由于有序对< x , y >中 x，y 的位置是确定的，因此 A×B 的记法也是确定的，不能写成 B×A 。
笛卡儿积的运算一般不满足交换律。
2．二元关系的概念和表示、几种特殊的关系和关系的运算
（1）二元关系的概念：二元关系是一个有序对集合，设集合 A，B ，从集合 A 到 B 的二元关系
R?{?x,y?|x?A且y?B}
记作xRy。
二元关系的定义域：Dom(R)?A；二元关系的值域：Ram(R)?B。 二元关系 R 是一个有序对组成的集合．因此，一个二元关系是一个集合，可以用集合形式表示；反过来说，一个集合未必是一个二元关系，仅当集合是由有序对元素组成的，才能当做二元关系。
常用关系的表示法包括了集合表示法、列举法、描述法、关系矩阵法和关系图法。关系矩阵和关系图是有限集合上的二元关系的表示方法。
1
（2）特殊的关系：空关系、全关系和恒等关系 空关系（记作）：是任何关系的子集 全关系（记作EA）：EA?{?a,b?|a,b?A}?A?A 恒等全系（记作IA）：IA?{?a,a?|a?A} （3）关系的集合运算、复合运算和逆运算：
关系的集合运算与普通集合运算基本相同，主要为并运算、交运算、补运算、差运算和对称差运算。
关系复合运算，描述为
R?R1?R2?{?a,c?|存在b使?a,b??R1且?b,c??R2}
复合关系满足结合律：(R?S)?T?R?(S?T) 关系的逆运算，描述为
R?1?{?x,y?|?y,x??R}
逆关系满足：(R?S)?1?S?1?R?1
二元关系 R 的逆关系可以用关系矩阵和关系图表示．并且逆关系的关系矩阵就是关系R的关系矩阵的转置，而逆关系的关系图就是把关系 R 的关系图中的有向弧的方向改变。
3．关系的性质：自反性、反自反性、对称性、反对称性、传递性 （1）自反性：对任意?x?A，有?x,x??R，则关系R 是自反的。 自反关系的矩阵MR主对角线元素全为1；自反关系图的每个结点都有自回路。
（2）反自反性：
对?x?A，有?x.x??R，则关系R 是反自反的。
反自反关系矩阵MR主对角线元素全为0；关系图的每个结点都没有自回路。 （3）对称性：
对??x,y??R，有?y,x??R，则关系R 是对称的。
对称关系的矩阵MR是对称矩阵，即rij?rji；关系图中有向弧成对出现，方向相反．
（4）反对称性：
对??x,y??R，若?y,x??R，必有x?y，则关系R 是反对称的；或者
??x,y??R，必有?y,x??R，则关系R 是反对称的．
反对称关系的矩阵MR不出现对称元素，关系图中任意两个顶点之间或者没有有向弧，或者仅有一条有向弧．
（5）传递性：
对??a,b??R，若??b,c??R，使得?a,c??R，则关系R 是传递的．
2
在传递关系的关系图中，若有从a 到b 的弧，且有从b 到c 的弧，则必有从a 到c 的弧。
4．关系的自反闭包、传递闭包和对称闭包求解方法 （1）求解关系的自反闭包
集合法：把所有的a?A构成的有序对< a , a > 添加到A 上的关系R 中，就能够获得R 的自反闭包r (R)。即：r(R)?R?IA，其中，IA是A上的恒等关系。
矩阵法：若R 的关系矩阵MR ，通过公式Mr?MR?E，就能够求出R 的自反闭包r (R) 的关系矩阵Mr ，其中E 是单位矩阵。
图像法：在R 的关系图上没有自回路的结点处都添上自回路，就得到了R 的自反闭包r (R) 的关系图。
（2）求解关系的对称闭包
集合法：若R上的任意关系a , b，若?b,a??R，则把b , a添加到关系R 中，就能够获得R 的对称闭包s (R)。即：s(R)?R?R?1。
T矩阵法：若R 的关系矩阵为MR ，利用公式Ms?MR?MR，就能够得出R 的T对称闭包s (R)的关系矩阵Ms ，其中MR是MR的转置矩阵.
图像法：把R 的关系图图上所有单向弧都画为双向弧，就能得到R 的对称闭包s (R)的关系图．
（3）求解关系的传递闭包
集合法：先求出R2，…，Rn ，再求它们的并R?R1?R2?...?Rn，就能够
n获得R 的传递闭包t (R)。即：t(R)?i?1R?R2?R3????。
2n矩阵法：若已知R 的关系矩阵MR ，通过公式Mt?MR?MR，便?...?MR能求出R 的传递闭包t (R)的关系矩阵Mt 。
图像法：若已知R 的关系图，从关系图的每个结点ai（i =1，2，…，n）出发，找出所有2步，3步，…，n步长的路径，设路径的终点为aj1,aj2,...,ajk，从aI依次用有向弧连接到aj1,aj2,...,ajk，当检查完所有结点后，就画出了R 的传递闭包t (R)的关系图。
5.等价关系
等价关系概念：设R是非空集合A上的二元关系，如果R是自反的、对称
3