离散数学-二元关系与函数

二元关系基本概念

二元关系定义

$$设存在集合A=\{a,b,c,d,e\}$$

$$若存在集合形如R=\{(a,b),(b,c),(b,d),(d,e)\}的仅由A中两个元素组成的集合，称为二元关系$$

笛卡尔积

笛卡尔积，又称直积

定义

设A、B是集合,A到B的笛卡尔积用$A\times B$表示，$A\times B$为所有以形如（a,b）的有序对为元素的集合，其中$a \in A,b\in B$

当B = A时，$A\times A$称为集合A上的笛卡尔乘积

例子

$A = \{a,b,c\},B = \{x,y\}$
$则A\times B = \{(a,x),(a,y),(b,x),(b,y),(c,x),(c,y)\}$

笛卡尔积元素个数

由笛卡尔积的性质可知，若确定了某个集合A和B，则$A\times B$中的元素个数时可确定的。

接下来讨论元素个数的特点

若$|A| = n,|B| = m$

A中任意一个元素a都能与B中的每一个元素组成一个元组，则可以组成m个

则$|A\times B| = n\times m$

笛卡尔积相关定义

二元关系

$设A、B是集合，R是笛卡尔乘积A\times B的子集，则称R是A到B的一个二元关系$

$若B = A，R是笛卡尔乘积A\times B的子集，称R是A上的一个二元关系$

前域与值域

$设R是二元关系，由(x,y)\in R的所有x组成的集合称为R的前域记作domR$

$所有y组成的集合称为R的值域，记作ranR$

平凡子集

对于集合A，空集和集合A本身一定是A的子集，则成这两个集合为A的平凡子集

笛卡尔积的平凡子集

对于A和B的笛卡尔乘积$A\times B$，$\emptyset和A\times B$分别称为空关系和全域关系

二元关系表示法

表格表示法

前域为行，值域为列

如：

$A = \{a_1,a_2,a_3,a_4,a_5\}$

$B = \{b_1,b_2,b_3,b_4\}$

$R = \{(a_1,b_1),(a_1,b_2),(a_3,b_3),(a_4,b_4),(a_5,b_3)\}$

则R可表示为

矩阵表示法

设$|A| = n,|B| = m$,则可以用一个$n\times m$的矩阵C来表示关系二元关系R

即将C中元素$C_{ij}$定义为：

$$\begin{cases} 1 & (a_i,b_j)\in R \\\\ 0 & (a_i,b_j) \notin R \end{cases}$$

则，矩阵

$$C = \begin{bmatrix} 1 & 0 & 0 \\\\ 0 & 1 & 1 \\\\ 0 & 0 & 1 \\\\ 0 & 1 & 0 \\\\ 0 & 0 & 1 \\\\ \end{bmatrix}$$

则C称为R的关系矩阵

图形表示法

对于R中的所有关系，分别用n个点表示A中的所有元素，m个点表示B中的所有元素，若$a\in A,b \in B,(a,b) \in R$,则从点a至b画一条有向边

若R是A上的二元关系，则可以只用n个点表示A中的所有元素，若$(a_i,a_j) \in R$,则从点$a_i$到点$a_j$画一条有向边

二元关系的基本类型

传递性的判断

判断关系R是否为传递的二元关系时，需要利用矩阵乘法，下面进行分析

$$设A = {a_1,a_2,...,a_3},R时A上的二元关系，R的关系矩阵A_R为$$

$$A_R = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\\\ a_{21} & a_{22} & \cdots & a_{2n} \\\\ \vdots & \vdots & \ddots & \vdots \\\\ a_{n1} & a_{n2} & \cdots & a_{nn} \\\\ \end{bmatrix}$$

其中

$$a_{ij} = \begin{cases} 1 & (a_i,b_j)\in R \\\\ 0 & (a_i,b_j) \notin R \end{cases}$$

令$B = A_R \times A_R, B$中的元素为$b_{ij}$,即有

$$B = \begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1n} \\\\ b_{21} & b_{22} & \cdots & b_{2n} \\\\ \vdots & \vdots & \ddots & \vdots \\\\ b_{n1} & b_{n2} & \cdots & b_{nn} \\\\ \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\\\ a_{21} & a_{22} & \cdots & a_{2n} \\\\ \vdots & \vdots & \ddots & \vdots \\\\ a_{n1} & a_{n2} & \cdots & a_{nn} \\\\ \end{bmatrix}\times \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\\\ a_{21} & a_{22} & \cdots & a_{2n} \\\\ \vdots & \vdots & \ddots & \vdots \\\\ a_{n1} & a_{n2} & \cdots & a_{nn} \\\\ \end{bmatrix}$$

由矩阵乘法运算规则可知

$$b_{ij} = a_{i1} \times a_{1j} + a_{i2}\times a_{2j} + \cdots +a_{in}\times a_{nj} = \sum\limits_{R = 1}^n a_{ik} \times a_{kj}$$

即，当$b_{ij} \neq 0$时，说明，存在一个$k\leq n$,其对应的一组$a_{ik}=a_{kj}=1$，即$(a_{ik},a{jk})\in R$，那么如果R为传递关系，则必须有$a_{ij} = 1$，故对于任意$b_{ij} \neq 0$都有$a_{ij} = 1$,则R为传递关系。