文章目录
一、关系矩阵
A = \{ a_1, a_2 , \cdots , a_n \} , R \subseteq A \times AR 使用 关系矩阵 表示 :
M(R) = (r_{ij})_{n\times n}关系矩阵取值 :
M(R)(i, j) = r_{ij} =\begin{cases} 1, & a_i R a_j \\ 0, & 无关系 \end{cases}关系矩阵定义说明 :
A 是个
n 元集 ( 集合中有
n 个元素 ) ,
R 是
A 上的二元关系 ,
R 的关系矩阵是
n \times n 的方阵 , 第
i 行第
j 列位置的元素
r_{ij} 取值只能是
0 或
1 ;
关系矩阵取值说明 :
如果
r_{ij} = 1 , 则说明
A 集合中 第
i 个元素与第
j 个元素具有关系
R , 记作 :
a_i R a_j ;
如果
r_{ij} = 0 , 则说明
A 集合中 第
i 个元素与第
j 个元素没有关系
R ;
关系矩阵本质 : 关系矩阵中 , 每一行对应着
A 集合中的元素 , 每一列也对应着
A 集合中的元素 , 行列交叉的位置的值 (
0 或
1 ) 表示
A 集合中第
i 个元素与第
j 个元素构成的有序对是否有关系
R ;
二、关系矩阵示例
A = \{ a, b, c \}R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \}R_2 = \{ <a,b> , <a,c> , <b,c> \}使用关系矩阵表示上述
R_1 , R_2 两个关系 :
R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \} 其中 :
<a, a> :
a 是第
1 个元素 ,
a 是第
1 个元素 , 第
1 行第
1 列元素是
1<a, b> :
a 是第
1 个元素 ,
b 是第
2 个元素 , 第
1 行第
2 列元素是
1<b, a> :
b 是第
2 个元素 ,
a 是第
1 个元素 , 第
2 行第
1 列元素是
1<b, c> :
b 是第
2 个元素 ,
c 是第
3 个元素 , 第
2 行第
3 列元素是
10M(R_1) = \begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix}R_2 = \{ <a,b> , <a,c> , <b,c> \} 其中 :
<a, b> :
a 是第
1 个元素 ,
b 是第
2 个元素 , 第
1 行第
2 列元素是
1<a, c> :
a 是第
1 个元素 ,
c 是第
3 个元素 , 第
1 行第
3 列元素是
1<b, c> :
b 是第
2 个元素 ,
c 是第
3 个元素 , 第
2 行第
3 列元素是
10M(R_2) = \begin{bmatrix} 0 & 1 & 1 \\\\ 0 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix}三、关系矩阵性质
有序对集合表达式 与 关系矩阵 可以唯一相互确定
性质一 : 逆运算相关性质
M(R^{-1}) = (M(R))^TM(R^{-1}) 关系的逆 的 关系矩阵
与
(M(R))^T 关系矩阵 的 逆
这两个矩阵是相等的 ;
性质二 : 合成运算相关性质
M(R_1 \circ R_2) = M(R_2) \bullet M(R_1)\bullet 是矩阵的 逻辑乘法 , 计算 矩阵
r_{ij} 的值 第
i 行 乘以 第
j 列 , 逐位 逻辑相乘 , 再将逻辑相乘结果再 逻辑相加 ;
上述 逻辑乘法使用
\land 运算 , 逻辑加法使用
\lor 运算 ;
四、关系矩阵运算
A = \{ a, b, c \}R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \}R_2 = \{ <a,b> , <a,c> , <b,c> \}在上面的示例中 , 已经求出两个关系矩阵 ;
M(R_1) = \begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix} ,
M(R_2) = \begin{bmatrix} 0 & 1 & 1 \\\\ 0 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix}1. 求
M(R^{-1}) , M(R_2^{-1})直接将矩阵转置 , 即可获取 关系的逆的关系矩阵 ;
M(R_1^{-1}) = (M(R_1))^T = \begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 0 & 0 \\\\ 0 & 1 & 0 \end{bmatrix}M(R_2^{-1}) = (M(R_2))^T = \begin{bmatrix} 0 & 0 & 0 \\\\ 1 & 0 & 0 \\\\ 1 & 1 & 0 \end{bmatrix}R_1^{-1} = \{ <a, a> , <a, b> , <b,a> , <c,b> \}R_2^{-1} = \{ <b, a> , <c,a> , <c,b> \}2. 求
M( R_1 \circ R_1 )M( R_1 \circ R_1 ) = M(R_1) \bullet M(R_1)其中的
\bullet 是两个矩阵的逻辑乘法 , 加法使用
\lor , 乘法使用
\landM(R_1) \bullet M(R_1) = \begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix} \bullet \begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\\\ 1 & 1 & 0 \\\\ 0 & 0 & 0 \end{bmatrix}矩阵的逻辑乘法 : 结果矩阵的第
i 行 , 第
j 列元素的值为 , 第
i 行的三个元素 分别与上第
j 列的三个元素 , 然后三个结果进行或运算 , 最终结果就是 矩阵的第
i 行 , 第
j 列元素的值 ;
R_1 \circ R_1 = \{ <a,a> , <a,b> , <a,c> , <b,a>, <b,b> \}3. 求
M( R_1 \circ R_2 )M( R_1 \circ R_2 ) = M(R_2) \bullet M(R_1)其中的
\bullet 是两个矩阵的逻辑乘法 , 加法使用
\lor , 乘法使用
\land特别注意 , 合成的顺序是逆序合成 , 后者关系矩阵在前 , 前者关系矩阵在后
M(R_1) \bullet M(R_2) =\begin{bmatrix} 0 & 1 & 1 \\\\ 0 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix} \bullet \begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 \\\\ 0 & 0 & 0 \\\\ 0 & 0 & 0 \end{bmatrix}矩阵的逻辑乘法 : 结果矩阵的第
i 行 , 第
j 列元素的值为 , 第
i 行的三个元素 分别与上第
j 列的三个元素 , 然后三个结果进行或运算 , 最终结果就是 矩阵的第
i 行 , 第
j 列元素的值 ;
R_1 \circ R_2 = \{ <a,a>, <a,c> \}五、关系图
A = \{ a_1, a_2 , \cdots , a_n \} , R \subseteq A \times AR 的关系图 :
\circ 表示
A 集合中的元素 ;
\rightarrow 表示
R 中的元素 ;
a_i R a_j 就是从顶点
a_i 到 顶点
a_j 的有向边
<a_i , a_j> ;
六、关系图示例
A = \{ a, b, c \}R_1 = \{ <a, a> , <a,b> , <b,a> , <b,c> \} 关系图表示方式 :
R_2 = \{ <a,b>, <a,c>, <b,c> \} 使用关系图表示 :
R_1^{-1} = \{ <a,a>, <a,b>, <b,a> , <c,b> \}R_2^{-1} = \{ <b,a> , <c,a> , <c,b> \}七、关系表示相关性质
A 集合中的元素 , 标定次序后 , 即生成了
A 上的关系 ,
R \subseteq A \times A , 有如下性质 :
G(R) 与 关系的
R 的集合表达式 ( 有序对集合 ) , 可以 唯一确定 ;
R 的集合表达式 , 关系矩阵
M(R) , 关系图
G(R) , 都是一一对应的 ;
R \subseteq A \times BA 中有
n 个元素 ,
|A| = nB 中有
m 个元素 ,
|B| = mM(R) 是
n \times m 阶矩阵 ;
G(R) 有向边都是从
A 集合中的元素 指向
B 集合中的元素
