Question

离散数学第五版：第四章知识点概要

Answer 1

第一节为集合的笛卡尔积与二元关系：前半部分主要讲了有序对，第一元素，第二元素，笛卡尔积等的概念；后半部分讲了一些二元关系，比如空关系，全域关系，恒等关系，小于等于关系，整除关系，关系矩阵和关系图等。

第一元素和第二元素就像是坐标的x值和y值，像是一个死规定。

笛卡尔积是一个听过很多次也经常忘的概念，就像括号乘法一样，作各项的有序组合。另外其有四个性质：第一个是关于空集，集合与空集的笛卡尔积仍然为空；笛卡尔积不满足结合律；笛卡尔积满足分配率。

二元关系指的是一个集合，一般称为R，要求是该集合为空集或者其元素都为有序对。

另外，A*B的子集称为从A到B的二元关系，若AB相等，则称为A上的二元关系。

空关系指空集。

全域关系指集合A的全部关系组成。

恒等关系指x，y相等的关系；同理可以理解小于等于关系以及整除关系。

关系矩阵和关系图指的是关系具体描述形式，见例分析。

第二节为关系的运算：重新说明了定义域domR，值域ranR，以及域fldR；同时定义了三种关系，逆，合成，限制，像。并且夹带了一些定理，最后说明了概念R的n次幂。

逆有点像逆运算，从y推x。

合成可以类比为复合函数。

限制如名所示，就是在给定限制条件下的关系。

像指的是给定限定条件下的关系的值域。

R的n次幂运算，样式和乘方很像，其实就是不断的合成关系。R的0次方为单位矩阵。

第三节为关系的性质：主要是指五种，自反性，非自反性，对称性，反对称性以及传递性。首先必须要说的是，对于一个关系而言，其可以不含有以上任何一种性质。下面以关系矩阵特点展开介绍。

自反性指主对角线元素全部为1。

非自反性指主对角线元素全部为0。

对称性指矩阵为对称矩阵。

非对称性指矩阵中对称位置的两个元素必定一者为1另一者为0。

传递性指如果顶点a到b有关系，b到c有关系，则a到c也有关系。

第四节为关系的闭包：所谓闭包什么的都是一些比较扯的概念，其实说白了就是往关系中少添加一点元素，使得原本不具备某些属性的关系具有想要的属性。其中有三个概念，自反闭包r(R)，对称闭包s(R)，传递闭包t(R)，同时说了一些构造方法。

第五节为等价关系和偏序关系：顾名思义，主要就介绍了等价关系和偏序关系，其中定义了等价类、商集、划分、偏序集、全序集、哈斯图、元、界等。

等价关系指在非空集合A上同时满足自反、对称和传递性的关系，可以记作x～y。

等价类指等价关系中具有完整传递关系的一个类，指的是y，记作[x]。

A在R下的商集，指的是等价关系R下哥哥等价类的整体集合，记作A/R。

划分就像切大饼一样，讲集合分为互斥的几个部分。一个有意思的点是，划分和商集可以互相对应起来。

偏序关系指在非空集合A上满足自反性、反对称性和传递性的关系，简称偏序，记作≤。

一个集合A和A上的偏序关系R一齐称之为偏序集，记作<A,R>。

全序集是偏序集的特例，全序集中对于任意的x,y∈A，x与y都可比，且这种关系叫全序关系。

哈斯图指偏序集的描述方式，其描述关系是下部指向上部，从定义可以看出，全序集的图像是一条直线，所以全序集也可以叫线序集。

最大（小）元指的是所有元都指向（指向所有元）的元，并不是所有偏序集都有最大（小）元。

极大（小）元指的是不指向其他元（不被其他元指）的元。

上界与下界引入了新的集合B，对于属于A的集合B，若存在元y，使得B中所有元都指向y，则y算是B的一个上界。下界则反之。

最小上界（上确界）、最大下界（下确界）可以顾名思义了，在已知的上下界中做选择。

第六节为函数的定义和性质：定义了函数、函数值、满射、单射、双射、函数的像、常函数、恒等函数、单调函数、特征函数、自然映射。

函数和函数值，实在是不想讲。

函数的集合：若A、B为集合，所有从A到B的函数构成集合B↑A，读作“B上A”。

集合在函数下的像，这种叫法对应的其实是该集合（定义域）下函数的值域。

满射指值域刚好等于集合B，单射指x与y一一对应，双射指同时满足单射和满射。

常函数指常数函数，恒等函数指y=x，单调函数略，特征函数指0或1的函数。

自然映射可以单独提出来， 相对于之前的概念比较陌生，指的是某一元素直接映射到等价类的情况，如 1 —> {1,3,5}。

第七节为复合函数和反函数：如题所示，跟初高中学的知识完全划等，无需多言。