离散数学考前复习（（四）关系）

2021-11-25

离散数学考前复习：（四）关系 4.1 关系及其基本概念

二元关系：由两个元素 x 和 y，按照一定的顺序组成的二元组称为有序对，记作
特殊的关系
（1）空关系（反自反性，反对称性，传递性）
（2）恒等关系：｛|x∈A｝＝｛，，｝ΕA（恒等关系也满足自反性、对称性、反对称性、传递性。又称幺关系。）
（3）全域关系：A×A＝｛，，，，，，，，｝ΙA（自反性，对称性，传递性）
前域(domR)：所有元素x组成的集合
后域(ranR)：所有元素y组成的集合

4.2 关系的运算

关系的合成

文章图片
关系的逆运算：关系矩阵是原关系矩阵的转置

4.3 关系的性质

自反性与反自反性：A中每个元素都有的表示，为存在自反性，若无任何元素存在，则为反自反性，否则，被称为既无自反性也无反自反性
对称性与反对称性：对于任意的可以找到，则为对称性；对于任意的都找不到则成为反对称性；否则，被称为既无对称性也无反对称性
传递关系：存在，，则存在，被称为传递关系，否则，不存在传递性。

4.4 关系的闭包

自反闭包：r ( R )=RU; （自反闭包计算方式：原始二元关系加自反性关系）
对称闭包：s ( R )=RU;
传递闭包：t ( R )=RUUU……
矩阵求闭包
关系图求闭包

4.5 等价关系

定义：集合A上的二元关系R满足自反性，对称性和传递性，则R称为等价关系
商集：R是A上的等价关系，由关于R的所有不同的[等价类]作为元素组成的集合称为A关于R的[商集]，记作A/R

4.6 偏序关系

定义：集合A上的关系R满足自反性，反对称性和传递性，则称R是A上的一个偏序关系；
极值和最值
极小元：集合A中没有比它更小的元素(若存在可能不唯一)；
极大元：集合A中没有比它更大的元素(若存在可能不唯一)；
最小元：比集合A中任何其他元素都小(若存在就一定唯一)；
最大元：比集合A中任何其他元素都大(若存在就一定唯一)；
前提：B是A的子集
上界：A中的某个元素比B中任意元素都大，称这个元素是B的上界(若存在，可能不唯一)；
下界：A中的某个元素比B中任意元素都小，称这个元素是B的下界(若存在，可能不唯一)；
上确界：最小的上界(若存在就一定唯一)；
下确界：最大的下界(若存在就一定唯一)；

4.7 函数

若|X|=m,|Y|=n,则从X到Y有种不同的关系，有种不同的函数；
【离散数学考前复习（（四）关系）】在一个有n个元素的集合上，可以有种不同的关系，有种不同的函数，有n!种不同的双射；
若|X|=m,|Y|=n，且m<=n，则从X到Y有种不同的单射；
单射：f:X-Y，对任意x1,x2,属于X,且x1≠x2，若f(x1)≠f(x2)；（不同的x对应不同的y）
满射：f:X-Y，对值域中任意一个元素y在前域中都有一个或多个元素对应；（任何y都有x对应）
双射：f:X-Y，若f既是单射又是满射，则f是双射；
复合函数：fog=g(f(x));
设函数f:A-B，g:B-C，那么
①如果f,g都是单射，则fog也是单射；
②如果f,g都是满射，则fog也是满射；
③如果f,g都是双射，则fog也是双射；
④如果fog是双射，则f是单射，g是满射；

（符号太难打了趴……）

推荐阅读

上一篇：离散数学考前复习（（一）集合、整数、序列、矩阵）

下一篇：离散数学考前复习（（二）数理逻辑）