【离散数学】第三章笔记（完）

大家好，我是讯享网，很高兴认识大家。

1. 集合的相关概念

平凡子集：空集和集合自身叫做平凡子集。（就是自身及空集这两种特殊情形）
在这里插入图片描述
讯享网

一堆定义

1、集合A与B相等，就是里面的元素完全相同。
在这里插入图片描述
2、幂集：全体子集的集合。若有n个元素，则幂集中元素的个数为2^n.
幂集的元素可以对子集合的脚标用二进制编码来唯一地确定。从头到尾按顺序，有就是1，无就是0。

2.集合运算

A-B中，若A中无B，则结果为A（就直接不管B了）。
~A是全集除去A。
对称差画图即可知对称。

（两张运算公式）

在这里插入图片描述

3.包含排斥原理

在这里插入图片描述

元素奇数是加，偶数是减。

4.序偶与笛卡尔积

在这里插入图片描述
举例：
A={1，2}；B={3，4}；
A X B={<1,3>,<1,4>,<2,3>,<2,4>};

序偶的运算符合分配律。

集合之间的属于关系：

5. 关系及其表示

在这里插入图片描述

一个暂时没讲的概念：

相关运算：

关系矩阵：
A是行，B是列。存在是1，不存在是0.

6.关系的性质

自反与反自反

A={1,2};
自反：有<1,1>,<2,2>;
反自反：<1,1>,<2,2>一个都没有。
在这里插入图片描述
S上的关系可以是自反的, 是反自反的，也可以两者都不是。——有，但不完全有。

对称与反对称

对称：除了<1,1>,<2,2>之外，有<1,2>就有<2,1>，即对称。
反对称：除了<1,1>,<2,2>之外，有<1,2>就没有<2,1>，即反对称。
在这里插入图片描述
关系可以是对称的，或反对称的，或既是对称又是反对称（？），或既不对称也不反对称{<1,2>,<2,1>,<1,3>}。

传递性

如：{<1,1>,<1,2>,<2,2>,<2,3>,<1,3>}
在这里插入图片描述

一些性质

自反
在这里插入图片描述

对称与反对称

7.复合关系和逆关系

在这里插入图片描述

三个定理

在这里插入图片描述

布尔加法/乘法

在这里插入图片描述

逆关系

在这里插入图片描述

一些计算的定理和关系

在这里插入图片描述

闭包

在这里插入图片描述
自反闭包：使之有所有{<x,x>};
对称闭包：使之所有对称。
传递闭包：见下面的算法。

一个废话：

Warshall算法

其实没啥好看的，做一次题就会了。
在这里插入图片描述

9.集合的划分与覆盖

m就是有几个划分。
在这里插入图片描述

10.等价关系与等价类

在这里插入图片描述

商集是集合的集合。
商集的每个元素是等价关系的一个等价类。
等价类中的每个元素都是集合A上的元素。
同一等价类中的任意两个元素都具有关系R。

一个例子
在这里插入图片描述

一些定理

集合A上的等价关系R决定了A的一个划分，即为商集A/R。
由这条定理可以说明，我们可以根据等价关系对集合进行划分。
集合A的任一划分S确定了A的一个等价关系R。

11.相容关系

定义：设R是集合A上的二元关系，若R是自反的和对称的，称R是相容关系。

因为相容关系是自反和对称的,其关系矩阵是对称的且主对角线元素全为1,因此我们可仅用下三角矩阵T来表示和存储就够了,即关系矩阵可以简化为〞阶梯形〞。

在这里插入图片描述

在这里插入图片描述
1.利用相容关系的关系图来确定相容类和最大相容类是方便的。
2.极大完全子图的顶点集合就是最大相容类。
3.所谓极大完全子图是指每对顶点都有边相连的多边形,而最大相容类外的任何顶点不可能与类内的所有顶点相连。
4.极大完全子图也可以这样理解:如果一个极大完全子图在添加任何新的顶点后就不再成为极大完全子图。例:三角形是极大完全子图;一个四边形加上两条对角线也是极大完全子图。
5.另外孤立顶点,以及不在极大完全子图两个顶点及其连线,也是最大相容类。