二元关系基本概念
二元关系定义
$$
设存在集合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可表示为
| b1 | b2 | b3 | b4 | |
|---|---|---|---|---|
| a1 | √ | √ | ||
| a2 | ||||
| a3 | √ | |||
| a4 | √ | |||
| a5 | √ |
矩阵表示法
设$|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中每一个元素a，都有$(a,a) \in R$，则称R为自反的二元关系 | R的关系矩阵中的主对角线元素均为1 |
| 反自反 | 设R是A上的二元关系，如果对于A中每一个元素a，都有$(a,a) \notin R$，则称R为反自反的二元关系 | R的关系矩阵中主对角线元素均为0 |
| 对称 | 设R是A上的二元关系，且每当$(a,b)\in R$时，就一定有$(b,a)\in R$，则称R为对称的二元关系 | R的关系矩阵是一个对称的方阵 |
| 反对称 | 设R是A上的二元关系，每当$(a,b)\in R$，且$(b,a) \in R$时，必有a = b，则称R为反对称的二元关系 | R的关系矩阵中以主对角线对称的两个元素不能同时为1 |
| 传递 | 设R是A上的二元关系，每当有$(a,b)\in R$且$(b,c) \in R$时，必有$(a,c) \in R$，则称R为传递的二元关系 | 可以通过矩阵乘法判断是否传递 |
传递性的判断
判断关系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为传递关系。
