七、关系表示相关性质

文章目录一、关系矩阵二、关系矩阵示例三、关系矩阵性质四、关系矩阵运算五、关系图六、关系图示例七、关系表示相关性质一、关系矩阵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 = \{ , , , \}R_2 = \{ , , \}使用关系矩阵表示上述

R_1 , R_2 两个关系 :

R_1 = \{ , , , \} 其中 :

:

a 是第

1 个元素 ,

a 是第

1 个元素 , 第

1 行第

1 列元素是

1 :

a 是第

1 个元素 ,

b 是第

2 个元素 , 第

1 行第

2 列元素是

1 :

b 是第

2 个元素 ,

a 是第

1 个元素 , 第

2 行第

1 列元素是

1 :

b 是第

2 个元素 ,

c 是第

3 个元素 , 第

2 行第

3 列元素是

1其余全是 0M(R_1) = \begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix}R_2 = \{ , , \} 其中 :

:

a 是第

1 个元素 ,

b 是第

2 个元素 , 第

1 行第

2 列元素是

1 :

a 是第

1 个元素 ,

c 是第

3 个元素 , 第

1 行第

3 列元素是

1 :

b 是第

2 个元素 ,

c 是第

3 个元素 , 第

2 行第

3 列元素是

1其余全是 0M(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 = \{ , , , \}R_2 = \{ , , \}在上面的示例中 , 已经求出两个关系矩阵 ;

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} = \{ , , , \}R_2^{-1} = \{ , , \}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 = \{ , , , , \}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_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 = \{ a, b, c \}R_1 = \{ , , , \} 关系图表示方式 :

R_2 = \{ , , \} 使用关系图表示 :

R_1^{-1} = \{ , , , \}R_2^{-1} = \{ , , \}七、关系表示相关性质A 集合中的元素 , 标定次序后 , 即生成了

A 上的关系 ,

R \subseteq A \times A , 有如下性质 :

关系图 G(R) 与 关系的

R 的集合表达式 ( 有序对集合 ) , 可以 唯一确定 ;

关系 R 的集合表达式 , 关系矩阵

M(R) , 关系图

G(R) , 都是一一对应的 ;

R \subseteq A \times B集合 A 中有

n 个元素 ,

|A| = n集合 B 中有

m 个元素 ,

|B| = m关系矩阵 M(R) 是

n \times m 阶矩阵 ;

关系图 G(R) 有向边都是从

A 集合中的元素 指向

B 集合中的元素