离散数学复习

1.关系的介绍和性质

（1）序偶和笛卡尔积

两个元素按照一定的顺序组成的二元组就是序偶，使用尖括号进行表示，尖括号里面的元素一般都是有顺序的；

笛卡尔积就是有两个集合，从第一个集合里面选择一个元素，第二个集合选择一个元素，这个集合之间的笛卡尔积就是这两个集合元素的随机组合，因此这个笛卡尔积就类似于这个向量之间的叉乘，不满足这个交换律和结合律；

如果想让两个集合的笛卡尔积的结果是空的，当且仅当这两个集合都是空的才会出现这个情况；

概括来讲，这个序偶表示的就是一个二元组，笛卡尔积的结果里面的每一个元素都是序偶，笛卡尔积反映的也是两个集合之间的一种关系；

（2）二元关系

首先指出：关系就是笛卡尔积的子集（高度概括）！！！！！！！

二元关系就是两个元素之间的关系，这个和前面的笛卡尔积是有联系的，因为这个假设有12两个集合，第一个集合里面有12345这五个元素，第二个集合里面有678910这五个元素，他们这两个集合之间相互匹配，就会形成多种关系，如果某个集合在这个关系里面，我们就说这个是这个集合上面的关系；

通过下面的这个例子我们也可以明白两个集合进行这个笛卡尔积的运算，一共就有4个序偶，但是却可以产生16种关系；实际上，这个分为了一元子集，二元子集，三元子集，四元子集等等，就是这上面的4个序偶之间不断地相互匹配就组成了这16种关系；

（3）特殊的关系

需要留意的就是下面的这三种：

空关系：这个关系里面没有任何的序偶；

全关系：这个关系就是两个集合的笛卡尔积；

恒等关系：组成这个集合的序偶的两个元素是一样的；

（4）布尔矩阵的交并运算

这个和我们的矩阵运算是不一样的，因为这个要求这两个布尔矩阵的行数列数是完全一样的，而且是这两个矩阵的指定位置上面的元素进行运算，交就是进行对应位置元素的合取运算，并就是进行对应位置元素的析取运算；

（5）布尔矩阵的积运算

这个就是和我们的线性代数里面的矩阵运算是一样的，但是这个时候全部都是01之间的运算，而且这个结果矩阵的元素要想是1，要求这个两个对应位置进行运算的元素都是1才可以；

 （6）关系的运算

关系里面涉及到复合运算，就是两个关系之间使用小圆圈进行连接的运算，这个时候只需要注意的就是从后向前进行这个传递就可以了；这个满足结合律，

关系的逆运算就是让这个序偶里面的两个元素的位置颠倒即可；

关系的幂运算就是自己向自己进行这个关系的合成；

（7）关系的性质

&&自反性，反自反性

首先要知道这个性质是对于这个关系而言的，我们首先要知道建立在这个集合上面的关系，然后再进行判断这个关系是否符合这些性质；

自反性就是对于这个集合里面的每一个元素，这个关系里面都有自己和自己的序偶，就是这个序偶的两个元素是一样的；

反自反就是不存在自己和自己的关联，都是不同的元素之间的关系；

在矩阵上面就会体现出来这个自反性的矩阵就是对角线上面的元素都是1，反自反性就是对角线上面的元素都是0，两个都不是的话就是主对角线上面的元素有的是0，有的是1；

&&对称性，反对称性

对称性就是如果有<x,y>这个序偶，那么就需要有<y,x>这个序偶；

反对称性就是不能同时存在<x,y>和<y,x>，可以这样进行判断；

下面的这个例子，第一个就是对称的，13,31同时存在，第二个就是反对称的，13存在反过来就没有存在，注意的就是这个xx这种两个元素相同的序偶是对于我们判断这个对称性和反对称性是没有影响的，因此我们判断某个关系是不是满足对称性和反对称性的时候不需要关注这个两个元素相同的序偶；

第三个的话，就是因为这个12存在，但是21不存在，因此这个就不满足对称性的条件，13存在，但是31也同样存在，这个就不满足反对称性的条件；

第四个就是纯一色的恒等关系你，对于我们判断这个对称性，反对称性没有影响，因此两个关系都是满足的；

&&传递性

这个是很容易理解的，<xy>存在，<y,z>存在，那么这个<x,z>就一定存在，这个关系就是传递性的关系；

同理，在进行这个传递性的判断的时候，这个相同的元素组成的序偶也不会影响我们对于这个传递性的判断，我们可以直接忽略；

这个第二个例子为什么是传递的，这个需要使用这个定义和蕴含式的真假判断，通过判断这个只有一个序偶的关系，这个传递性定义的前件是不成立的，因此这个肯定是符合传递性的；

（8）等价关系

等价关系的定义就是同时满足这个自反关系，对称关系，传递关系的关系，这三个需要同时满足，缺一不可；

以4为模的同余关系就是一个等价的关系，这个需要我们自己进行这个列举出来，就是x-4可以被4整除，列举之后可以字面进行判断，也可以画出来这个有向图进行判断；

等价类就是具有相同关系的数据的集合，这个里面的048的等价类是一样的，都是{0,4,8}这个集合

1 5 9这三个元素的等价类也是一样的，都是{11,5,9}这个集合，我们自己可以画出有向图出来，这个159之间具有这个相同的关系，同理048之间也是具有相同的关系的，我们把这些具有相同关系的数据称之为等价类；

通过下面的这个数据我们可以观察到，这个任何数的等价类都是非空的，有的元素的等价类是一样的，有的元素的等价类是不一样的；