离散数学常考题型梳理

1、PAGE PAGE 10离散数学常考题型梳理第2章 关系与函数一、题型分析本章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容。常涉及到的题型主要包括：2-1关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算2-2关系自反和反自反、对称和反对称等性质的概念理解与判定；自反、对称和传递闭包运算。2-3 HYPERLINK /mod/resource/view.php?inpopup=true&id=428 t _blank 等价关系 2-4偏序关系和哈斯图2-5 函数的概念和性质因此，在本章学习过程中希望大家要清楚地知

2、道：1有序对和笛卡尔积（1）有序对：所谓有序对就是指一个有顺序的数组，如 ，x , y 的位置是确定的，且。（2）笛卡尔积：把集合A，B合成集合AB，规定：由于有序对中 x，y 的位置是确定的，因此 AB 的记法也是确定的，不能写成 BA 。笛卡儿积的运算一般不满足交换律。2二元关系的概念和表示、几种特殊的关系和关系的运算（1）二元关系的概念：二元关系是一个有序对集合，设集合 A，B ，从集合 A 到 B 的二元关系记作xRy。二元关系的定义域：；二元关系的值域：。二元关系 R 是一个有序对组成的集合因此，一个二元关系是一个集合，可以用集合形式表示；反过来说，一个集合未必是一个二元关系，仅当集

3、合是由有序对元素组成的，才能当做二元关系。常用关系的表示法包括了集合表示法、列举法、描述法、关系矩阵法和关系图法。关系矩阵和关系图是有限集合上的二元关系的表示方法。（2）特殊的关系：空关系、全关系和恒等关系空关系（记作）：是任何关系的子集全关系（记作EA）： 恒等全系（记作IA）：（3）关系的集合运算、复合运算和逆运算：关系的集合运算与普通集合运算基本相同，主要为并运算、交运算、补运算、差运算和对称差运算。关系复合运算，描述为复合关系满足结合律：关系的逆运算，描述为逆关系满足： 二元关系 R 的逆关系可以用关系矩阵和关系图表示并且逆关系的关系矩阵就是关系R的关系矩阵的转置，而逆关系的关系图就是

4、把关系 R 的关系图中的有向弧的方向改变。3关系的性质：自反性、反自反性、对称性、反对称性、传递性（1）自反性：对任意，则关系R 是自反的。自反关系的矩阵主对角线元素全为1；自反关系图的每个结点都有自回路。（2）反自反性：对，则关系R 是反自反的。反自反关系矩阵主对角线元素全为0；关系图的每个结点都没有自回路。（3）对称性：对，则关系R 是对称的。对称关系的矩阵是对称矩阵，即；关系图中有向弧成对出现，方向相反（4）反对称性：对，必有，则关系R 是反对称的；或者，则关系R 是反对称的反对称关系的矩阵不出现对称元素，关系图中任意两个顶点之间或者没有有向弧，或者仅有一条有向弧（5）传递性：对，则关系

5、R 是传递的 在传递关系的关系图中，若有从a 到b 的弧，且有从b 到c 的弧，则必有从a 到c 的弧。4关系的自反闭包、传递闭包和对称闭包求解方法（1）求解关系的自反闭包集合法：把所有的构成的有序对 添加到A 上的关系R 中，就能够获得R 的自反闭包r (R)。即：，其中，IA是A上的恒等关系。矩阵法：若R 的关系矩阵MR ，通过公式，就能够求出R 的自反闭包r (R) 的关系矩阵Mr ，其中E 是单位矩阵。图像法：在R 的关系图上没有自回路的结点处都添上自回路，就得到了R 的自反闭包r (R) 的关系图。（2）求解关系的对称闭包集合法：若R上的任意关系a , b，若，则把b , a添加到关

6、系R 中，就能够获得R 的对称闭包s (R)。即：。矩阵法：若R 的关系矩阵为MR ，利用公式，就能够得出R 的对称闭包s (R)的关系矩阵Ms ，其中的转置矩阵. 图像法：把R 的关系图图上所有单向弧都画为双向弧，就能得到R 的对称闭包s (R)的关系图（3）求解关系的传递闭包集合法：先求出R2，Rn ，再求它们的并，就能够获得R 的传递闭包t (R)。即：。矩阵法：若已知R 的关系矩阵MR ，通过公式，便能求出R 的传递闭包t (R)的关系矩阵Mt 。图像法：若已知R 的关系图，从关系图的每个结点ai（i =1，2，n）出发，找出所有2步，3步，n步长的路径，设路径的终点为，从aI依次用有

7、向弧连接到，当检查完所有结点后，就画出了R 的传递闭包t (R)的关系图。5.等价关系等价关系概念：设R是非空集合A上的二元关系，如果R是自反的、对称的和传递的，则称R是A上的等价关系。设R是一个等价关系，若R，则称a等价于b，记作ab。6.偏序关系和哈斯图（1）偏序关系设R是非空集合A上的二元关系，如果R是自反的、反对称的和传递的，则称R是A上的偏序关系或者简称序关系。偏序关系记作。，则称a小于等于b，记作a b。（2）哈斯图作图规则： = 1 * roman i去掉每个结点的自回路，用空心点表示集合的元素； = 2 * roman ii对于集合任意元素a和b，若ab，则将a画在b的下方；

8、= 3 * roman iii对于集合任意元素a和b，若ab，且不存在c使acb，则在a和b之间划一条弧。（3）最小元、极小元、最大元和极大元，上界和下界一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一；且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样。7函数的概念与性质（1）函数的概念设 f 是集合 A 到 B 的二元关系，若任意 aA，存在 bB，且 f ，Dom ( f ) = A，则 f 是一个函数（映射）函数是一种特殊的关系。注意：集合 AB 的任何子集都是关

9、系，但不一定是函数。函数要求对于定义域 A 中每一个元素 a ，B 中有且仅有一个元素与 a 对应，而一般的关系没有这个限制。（2）单射、满射和双射的判断单射：若； 满射：f (A) = B ，即对任意 y B，存在 x A，使得 y = f (x) ； 双射：单射且满射。（3）函数的复合若，则，即。复合成立的条件是：二、常考知识点分析常考知识点1：关系的概念与性质（历年考核次数：4次，本课程共考过6次；重要程度：）（2010年1月试卷第7题）如果R是非空集合A上的等价关系，a A，bA，则可推知R中至少包含 等元素解题过程： 由等价关系的概念，知道R具备了自反性、对称性和传递性。根据已知A上

10、的元素a和b，根据自反的概念，知道R中必须包含和，由对称和传递概念，得知，也具备对称性和传递性，因此对应A上的关系R至少应该包含元素，正确答案：，易错点：同学们对本题目中要求的最小等价关系没有理解清楚，容易将答案写为，仔细观察可以看出，该关系去掉和之后，仍然为等价关系。提示：先加入自反关系，然后再根据等价关系加入必要的对称和传递所需的元素。（2009年7月试卷第2题）集合A=1, 2, 3, 4, 5, 6, 7, 8上的关系R=|x+y=10且x, yA，则R的性质为（ ） A自反的 B对称的 C传递且对称的 D反自反且传递的解题过程：首先，可以写出关系R的有限集合表示，即,容易看出， R，

11、因此R不是自反的。R因此，R不是反自反的。又因为R，且R，而 R，因此，R不具备传递性。因此，答案选择B。易错点：同学们对关系的自反性、对称性、传递性和反自反性没有理解清楚，往往是能够写出R的有限集合表示却不能用相关概念进行判别。提示：熟练理解关系以及关系性质概念。（2009年7月试卷第6题）若A=1,2，R=|xA, yA, x+y=10，则R的自反闭包为 。解题过程：正确答案：，。本题考核的是关系闭包的计算。计算关系闭包有集合法、矩阵法和关系图法。本题目可以直接使用集合法计算公式。首先容易计算出R=，IA=，。= IA=，。易错点：有的同学对闭包的概念理解不够清楚。简单说，闭包是在原有关系

12、的基础上，添加最少的有序对，使得到的新关系具备某些特定性质。如，R自反闭包就是包含R的、并且具备自反性的最小关系。提示：同学们可以在理解相关概念的基础上，牢记并熟练应用闭包的计算公式。常考知识点2： HYPERLINK /mod/resource/view.php?inpopup=true&id=425 t _blank 函数的概念与性质（历年考核次数：4次，本课程共考过6次；重要程度：）（2009年7月试卷第7题）设A=a，b，c，B=1，2，作f：AB，则不同的函数个数为 。解题过程：本题目考核的是学生对函数概念的理解。函数可以有下面映射规则：（1）a,b,c全映射到2；（2）a映射到1，

13、b和c映射到2；（3）b映射到1，a和c映射到2；（4）c映射到1，a和b映射到2；（5）a映射到2，b和c映射到1；（6）b映射到2，a和c映射到1；（7）c映射到2，a和b映射到1；（8）a,b,c全映射到1；因此，函数个数为8。另外，此类题目也可以作以下分析。A到B映射个数可以描述为：=8 正确答案：8易错点：同学们对函数的单值性理解不够清楚，可能会认为A中必须有元素与B中元素唯一对应。提示：函数概念中，有两点尤其要注意。第一，是函数的单值性，即对于A中任何元素，必须有B中元素映射f唯一对应；第二，是函数的定义域，即A是函数f定义域。（2009年1月试卷第14题）判断说明：设N、R分别为

14、自然数集与实数集，f：NR，f (x)=x+6，则f是单射。解题过程：正确。 设x1，x2为自然数且x1x2，则有f(x1)= x1+6 x2+6= f(x2)，故f为单射。 易错点：同学们对函数单射概念理解不够清楚，可能会认为对于R中的小数，自然数集中无法用函数f对应，因此给出“错误”判定结论。提示：“单射”概念中，强调的是对于不同定义域中的值，通过函数映射得到的对应值不同，这种“一对一”是从前到后的一对一，并不要求从后到前一对一。（2009年1月试卷第14题）设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=, ，R2=, , ，R3=, ，则（ ）不是从A到B的函

15、数。 AR1和R2 BR2 CR3 DR1和R3解题过程：选择A错误正确答案：B函数的概念中，强调两点：第一，函数的单值性，即对于每一个定义域中的值，只能有一个对应函数值；第二，函数的定义域必须为集合A。本题中的R2不符合函数概念强调的第一点。易错点：有的同学可能认为R1也不是函数，理由是a和b的对应的是相同值。这是对函数概念理解常见的错误。函数概念并不要求值域中的值必须与定义域唯一对应。提示：判断一个二元关系是否为函数，要按照函数概念所规定的两个条件逐一比较，只要完全符合便可得到正确判断。常考知识点3： HYPERLINK /mod/resource/view.php?inpopup=tru

16、e&id=425 t _blank 序关系（历年考核次数：4次，本课程共考过6次；重要程度：）（2009年7月试卷第14题）若偏序集的哈斯图如图二所示，则集合A的最大元为a，最小元不存在。 图二解题过程：判断结论：错误。集合A的最大元不存在，a是极大元。若a为最大元，则对于任意xA，必有R，但从图中可以得知，R，因此a不是最大元。同时，不存在xA，满足R，因此，a为极大元。易错点：同学们对序关系的相关概念理解不够透彻。哈斯图不是简单的层次关系图，不要用层次关系判断最大元、最小元、极大元、极小元等。提示：最小元应小于等于其它各元素；最大元应该大于等于其它个元素；极小元应该小于等于一些元素，而与剩

17、下的元素没有关系；极大元应该大于等于一些元素，而与剩下的元素没有关系。最大元和最小元不一定存在，如果存在则必定唯一。（2009年10月试卷第3题）设集合A=1，2，3，4，5，偏序关系是A上的整除关系，则偏序集上的元素5是集合A的（ ）A最大元 B极大元 C最小元 D极小元解题过程：选择A错了。正确答案：B。由于元素4和5没有整除关系，显然5不是最大元。同理，5和2没有整除关系，5也不是最小元。易错点：同学们对序关系的相关概念理解不够透彻。哈斯图不是简单的层次关系图，不要用层次关系判断最大元、最小元、极大元、极小元等。提示：整除关系是常考的一类偏序关系。两个元素是否具备整除关系可以不直接表达，

18、所以题型描述简单，但是同学们需要将序关系的概念应用到此类题目中才能正确辨别。三、模拟练习练习1 ：（2010年1月试卷第6题）设集合A=2, 3, 4，B=1, 2, 3, 4，R是A到B的二元关系， 则R的有序对集合为 解析：答案为，对于A中元素2，满足条件在集合B中的元素为2、3和4，因此，有序对应该包括，和。对于A中元素3，满足条件在集合B中的元素为3和4，因此，有序对应该包括，。对于A中元素4，满足条件在集合B中的元素为4，因此，有序对应该包括。汇总上面结论，R的有序对集合为：，练习2 ：（2009年7月试卷第2题）集合A=1, 2, 3, 4上的关系R=|x=y且x, yA，则R的性

19、质为（ ） A不是自反的 B不是对称的 C传递的 D反自反解析：答案为C 本题目考的知识点是关系的集合表示以及关系的性质。根据关系R的描述，可以将有限集合A上关系R表示为，由关系自反、反自反以及对称和传递的概念，可知关系R满足自反性、对称性和传递性。 因此答案选择为C。练习3 ：（2009年10月试卷第7题）设集合A=1，2，3上的函数分别为：f=, , ,，g=, , ,，则复合函数gf = 解析：, , 本题考核的是复合函数的概念。对于f中元素，g中存在元素， 使f(1)=2，g (2)=2，因此 gf。同理，对于f中的元素，g中存在元素以及f中的元素，g中存在元素使和满足复合函数的概念。因此，答案为, , 。练习4 ：（2008年7月试卷第3题）如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有（ ）个 A0 B2 C1 D3解析：答案B本题目考核的是集合的运算以及关系自反性的概念。因为R1和R2是A上的自反关系，对于A中任意元素a，均同时满足 R1