【理论】离散数学中的二元关系

这篇文章将了解到以下方面的知识

01 二元关系的定义

02 笛卡尔积定义

03 二元关系的表示方式

   0301 二元关系是笛卡尔积的子集(二元关系的个数)

   0302 等价关系与集合上的划分一一对应 （等价关系的个数）

---

二元关系定义

由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作<x,y>.

序列：是某些元素或成员按照某种顺序排成的一个列表。在集合中可以不考虑元素的顺序，在序列中需要考虑元素的顺序。

序列分为有穷序列和无穷序列。有穷序列称为多元组，二元组也称为有序对。（ordered pair）

定义：如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系

二元关系即集合，定义域为有序对集合的关系。

什么是定义域：函数所有可能的输入构成的集合

笛卡尔积

假设集合A={a, b}，集合B={0, 1, 2}，则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。

设A,B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对，所有这样的有序对组成的集合叫做A与B的笛卡尔积，记作AxB.

笛卡尔积的符号化为：

A×B={(x,y)|x∈A∧y∈B}

例如，A={a,b}, B={0,1,2}，则

A×B={(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}

B×A={(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}

二元关系是笛卡尔积的子集

设X={1,2,3},则X 上不同的关系有多少种?

X={1,2,3}

X的元素个数为3,

则X与X笛卡尔积X*X的元素个数为3*3=9,

故笛卡尔积的子集个数为2^9=512,每个笛卡尔积的子集确定了一个X 上的关系,所以X 上不同的关系有512种.

等价关系与X上的划分一一对应

找出集合A的所有划分，每一个划分对应一个等价关系。

集合的划分就是对集合的元素分块，看到底是分成几块。

关系矩阵

rij表示矩阵的第i行第j列元素在计算机中，矩阵可以用数组表示，多维数组。

对于一个无向图G，pxq, p为顶点的个数，q为边数。bij 表示在关联矩阵中点i和边j之间的关系。若点i和边j之间是连着的，则bij = 1. 反之，则bij = 0.

矩阵图如下

参考资料 https://zhidao.baidu.com/question/2139816262011178748.html