文章目录

一、关系矩阵
二、关系矩阵示例
三、关系矩阵性质
四、关系矩阵运算
五、关系图
六、关系图示例
七、关系表示相关性质

一、关系矩阵

{

⋯

}

⊆

A = \{ a_1, a_2 , \cdots , a_n \} , R \subseteq A \times A

$A = {a_{1}, a_{2}, \dots, a_{n}}, R \subseteq A \times A$

R

R

$R$ 使用关系矩阵表示 :

(

)

(

)

M(R) = (r_{ij})_{n\times n}

$M (R) = (r_{i j})_{n \times n}$

关系矩阵取值 :

(

)

(

)

{

无

关

系

M(R)(i, j) = r_{ij} =\begin{cases} 1, & a_i R a_j \\ 0, & 无关系 \end{cases}

$M (R) (i, j) = r_{i j} = {1, 0, a_{i} R a_{j} 无关系$

关系矩阵定义说明 :

$A$ 是个

$n$ 元集 ( 集合中有

$n$ 个元素 ) ,

$R$ 是

$A$ 上的二元关系 ,

$R$ 的关系矩阵是

n \times n

$n \times n$ 的方阵 , 第

$i$ 行第

$j$ 列位置的元素

r_{ij}

$r_{i j}$ 取值只能是

$0$ 或

$1$ ;

关系矩阵取值说明 :

如果

r_{ij} = 1

$r_{i j} = 1$ , 则说明

$A$ 集合中第

$i$ 个元素与第

$j$ 个元素具有关系

$R$ , 记作 :

a_i R a_j

$a_{i} R a_{j}$ ;

如果

r_{ij} = 0

$r_{i j} = 0$ , 则说明

$A$ 集合中第

$i$ 个元素与第

$j$ 个元素没有关系

$R$ ;

关系矩阵本质 : 关系矩阵中 , 每一行对应着

$A$ 集合中的元素 , 每一列也对应着

$A$ 集合中的元素 , 行列交叉的位置的值 (

$0$ 或

$1$ ) 表示

$A$ 集合中第

$i$ 个元素与第

$j$ 个元素构成的有序对是否有关系

$R$ ;

二、关系矩阵示例

{

}

A = \{ a, b, c \}

$A = {a, b, c}$

{

}

R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \}

$R_{1} = {< a, a >, < a, b >, < b, a >, < b, c >}$

{

}

R_2 = \{ <a,b> , <a,c> , <b,c> \}

$R_{2} = {< a, b >, < a, c >, < b, c >}$

使用关系矩阵表示上述

R_1 , R_2

$R_{1}, R_{2}$ 两个关系 :

{

}

R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \}

$R_{1} = {< a, a >, < a, b >, < b, a >, < b, c >}$ 其中 :

其余全是

(

)

[

]

M(R_1) = \begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix}

$M (R_{1}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 110100010 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$

{

}

R_2 = \{ <a,b> , <a,c> , <b,c> \}

$R_{2} = {< a, b >, < a, c >, < b, c >}$ 其中 :

其余全是

(

)

[

]

M(R_2) = \begin{bmatrix} 0 & 1 & 1 \\\\ 0 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix}

$M (R_{2}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 000100110 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$

三、关系矩阵性质

有序对集合表达式与关系矩阵可以唯一相互确定

性质一 : 逆运算相关性质

(

−

)

(

)

M(R^{-1}) = (M(R))^T

$M (R^{- 1}) = (M (R))^{T}$

(

−

)

M(R^{-1})

$M (R^{- 1})$ 关系的逆的关系矩阵
与

(

)

(M(R))^T

$(M (R))^{T}$ 关系矩阵的逆
这两个矩阵是相等的 ;

性质二 : 合成运算相关性质

(

∘

)

(

)

∙

(

)

M(R_1 \circ R_2) = M(R_2) \bullet M(R_1)

$M (R_{1} \circ R_{2}) = M (R_{2}) ∙ M (R_{1})$

∙

\bullet

$∙$ 是矩阵的逻辑乘法 , 计算矩阵

r_{ij}

$r_{i j}$ 的值第

$i$ 行乘以第

$j$ 列 , 逐位逻辑相乘 , 再将逻辑相乘结果再逻辑相加 ;

上述逻辑乘法使用

∧

\land

$\land$ 运算 , 逻辑加法使用

∨

\lor

$\lor$ 运算 ;

四、关系矩阵运算

{

}

A = \{ a, b, c \}

$A = {a, b, c}$

{

}

R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \}

$R_{1} = {< a, a >, < a, b >, < b, a >, < b, c >}$

{

}

R_2 = \{ <a,b> , <a,c> , <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_{1}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 110100010 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$ ,

(

)

[

]

M(R_2) = \begin{bmatrix} 0 & 1 & 1 \\\\ 0 & 0 & 1 \\\\ 0 & 0 & 0 \end{bmatrix}

$M (R_{2}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 000100110 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$

1. 求

M

(

R

−

1

)

,

M

(

R

2

−

1

)

M(R^{-1}) , M(R_2^{-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_{1}^{- 1}) = (M (R_{1}))^{T} = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 110101000 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$

(

−

)

(

)

[

]

M(R_2^{-1}) = (M(R_2))^T = \begin{bmatrix} 0 & 0 & 0 \\\\ 1 & 0 & 0 \\\\ 1 & 1 & 0 \end{bmatrix}

$M (R_{2}^{- 1}) = (M (R_{2}))^{T} = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 011001000 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$

−

{

}

R_1^{-1} = \{ <a, a> , <a, b> , <b,a> , <c,b> \}

$R_{1}^{- 1} = {< a, a >, < a, b >, < b, a >, < c, b >}$

−

{

}

R_2^{-1} = \{ <b, a> , <c,a> , <c,b> \}

$R_{2}^{- 1} = {< b, a >, < c, a >, < c, b >}$

2. 求

M

(

R

1

∘

R

1

)

M( R_1 \circ R_1 )

$M (R_{1} \circ R_{1})$

(

∘

)

(

)

∙

(

)

M( R_1 \circ R_1 ) = M(R_1) \bullet M(R_1)

$M (R_{1} \circ R_{1}) = M (R_{1}) ∙ M (R_{1})$

其中的

∙

\bullet

$∙$ 是两个矩阵的逻辑乘法 , 加法使用

∨

\lor

$\lor$ , 乘法使用

∧

\land

$\land$

(

)

∙

(

)

[

]

∙

[

]

[

]

M(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}

$M (R_{1}) ∙ M (R_{1}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 110100010 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ ∙ ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 110100010 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 110110100 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$

矩阵的逻辑乘法 : 结果矩阵的第

$i$ 行 , 第

$j$ 列元素的值为 , 第

$i$ 行的三个元素分别与上第

$j$ 列的三个元素 , 然后三个结果进行或运算 , 最终结果就是矩阵的第

$i$ 行 , 第

$j$ 列元素的值 ;

∘

{

}

R_1 \circ R_1 = \{ <a,a> , <a,b> , <a,c> , <b,a>, <b,b> \}

$R_{1} \circ R_{1} = {< a, a >, < a, b >, < a, c >, < b, a >, < b, b >}$

3. 求

M

(

R

1

∘

R

2

)

M( R_1 \circ R_2 )

$M (R_{1} \circ R_{2})$

(

∘

)

(

)

∙

(

)

M( R_1 \circ R_2 ) = M(R_2) \bullet M(R_1)

$M (R_{1} \circ R_{2}) = M (R_{2}) ∙ M (R_{1})$

其中的

∙

\bullet

$∙$ 是两个矩阵的逻辑乘法 , 加法使用

∨

\lor

$\lor$ , 乘法使用

∧

\land

$\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}

$M (R_{1}) ∙ M (R_{2}) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 000100110 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ ∙ ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 110100010 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 100000100 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$

矩阵的逻辑乘法 : 结果矩阵的第

$i$ 行 , 第

$j$ 列元素的值为 , 第

$i$ 行的三个元素分别与上第

$j$ 列的三个元素 , 然后三个结果进行或运算 , 最终结果就是矩阵的第

$i$ 行 , 第

$j$ 列元素的值 ;

∘

{

}

R_1 \circ R_2 = \{ <a,a>, <a,c> \}

$R_{1} \circ R_{2} = {< a, a >, < a, c >}$

五、关系图

{

⋯

}

⊆

A = \{ a_1, a_2 , \cdots , a_n \} , R \subseteq A \times A

$A = {a_{1}, a_{2}, \dots, a_{n}}, R \subseteq A \times A$

R

R

$R$ 的关系图 :

顶点 : $\circ ∘ 表示 A A$
$A$ 集合中的元素 ;
有向边 : $\rightarrow → 表示 R R$
$R$ 中的元素 ;
$a_i R a_j aiRaj 就是从顶点 a i a_i ai 到顶点 a j a_j aj 的有向边 < a i , a j > <a_i , a_j>$
$< a_{i}, a_{j} >$ ;

六、关系图示例

{

}

A = \{ a, b, c \}

$A = {a, b, c}$

{

}

R_1 = \{ <a, a> , <a,b> , <b,a> , <b,c> \}

$R_{1} = {< a, a >, < a, b >, < b, a >, < b, c >}$ 关系图表示方式 :

在这里插入图片描述

{

}

R_2 = \{ <a,b>, <a,c>, <b,c> \}

$R_{2} = {< a, b >, < a, c >, < b, c >}$ 使用关系图表示 :

在这里插入图片描述

−

{

}

R_1^{-1} = \{ <a,a>, <a,b>, <b,a> , <c,b> \}

$R_{1}^{- 1} = {< a, a >, < a, b >, < b, a >, < c, b >}$

在这里插入图片描述

−

{

}

R_2^{-1} = \{ <b,a> , <c,a> , <c,b> \}

$R_{2}^{- 1} = {< b, a >, < c, a >, < c, b >}$

在这里插入图片描述

七、关系表示相关性质

$A$ 集合中的元素 , 标定次序后 , 即生成了

$A$ 上的关系 ,

⊆

R \subseteq A \times A

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

关系图
$G (R)$ 与关系的

R

R

$R$ 的集合表达式 ( 有序对集合 ) , 可以唯一确定 ;
关系
$G (R)$ , 都是一一对应的 ;

⊆

R \subseteq A \times B

$R \subseteq A \times B$

集合
集合
关系矩阵 $\times m$
$n \times m$ 阶矩阵 ;
关系图
$B$ 集合中的元素

【集合论】关系表示 ( 关系矩阵 | 关系矩阵示例 | 关系矩阵性质 | 关系矩阵运算 | 关系图 | 关系图示例 | 关系表示相关性质 )

文章目录

一、关系矩阵

二、关系矩阵示例

三、关系矩阵性质

四、关系矩阵运算

五、关系图

六、关系图示例

七、关系表示相关性质

相关推荐

一个分享Java & Python知识的社区