集合论

2023-11-19 17:29| 来源: 网络整理| 查看: 265

关系的自反、对称和传递闭包定义

设 R \text{R} R是非空集合 A A A上的关系， R \text{R} R的自反(对称、传递)闭包是 A A A上的关系 R ′ \text{R}' R′，且 R ′ \text{R}' R′满足以下条件：

R ′ \text{R}' R′是自反(对称、传递)的 R ⊆ R ′ \text{R}\subseteq\text{R}' R⊆R′对 A A A上的任何包含 R \text{R} R的自反(对称、传递)关系 R ′ ′ \text{R}'' R′′都有 R ′ ⊆ R ′ ′ \text{R}'\subseteq\text{R}'' R′⊆R′′

一般将 R \text{R} R的自反闭包(reflexive)记作 r ( R ) r(\text{R}) r(R)，对称闭包(symmetry)记作 s ( R ) s(\text{R}) s(R)，传递闭包(transfer)记作 t ( R ) t(\text{R}) t(R)

构造 A A A上关系的 R R R包

设 R R R为非空集合 A A A上的关系，则有定理：

r ( R ) = R ∪ R 0 r(R) = R\cup R^0 r(R)=R∪R0 s ( R ) = R ∪ R − 1 s(R) = R\cup R^{-1} s(R)=R∪R−1 t ( R ) = R ∪ R 2 ∪ R 3 ∪ . . . t(R) = R\cup R^2 \cup R^3 \cup ... t(R)=R∪R2∪R3∪...

例：设 A = { a , b , c , d } A=\{a,b,c,d\} A={a,b,c,d}， R = { ; a , b ; , ; b , a ; , ; b , c ; , ; c , d ; } R=\{;a,b;,;b,a;,;b,c;,;c,d;\} R={,,,}，则 R R R和 r ( R ) 、 s ( R ) 、 t ( R ) r(R)、s(R)、t(R) r(R)、s(R)、t(R)如图所示： R : R: R:

a b c d

r ( R ) : r(R): r(R):节点作圈

自反自反自反自反 a b c d

s ( R ) : s(R): s(R):节点互逆

对称对称 a b c d

t ( R ) : t(R): t(R):首尾连接

传递传递传递传递传递 a b c d

设 R R R的关系矩阵为 M M M，相应的自反、对称、传递闭包的矩阵为 M r M_r Mr、 M s M_s Ms、 M t M_t Mt，将以上三条定理公式转化为矩阵表示。即得：

M r = M + E M_r = M+E Mr=M+E M s = M + M ′ M_s = M+M' Ms=M+M′ M t = M + M 2 + M 3 + . . . M_t = M + M^2 + M^3+... Mt=M+M2+M3+...

其中 E E E为同阶单位矩阵， M ′ M' M′为 M M M的转置

例：设 A = { a , b , c , d } A=\{a,b,c,d\} A={a,b,c,d}， R = { ; a , b ; , ; b , a ; , ; b , c ; , ; c , d ; } R=\{;a,b;,;b,a;,;b,c;,;c,d;\} R={,,,}，则 M r 、 M s 、 M t M_r、M_s、M_t Mr、Ms、Mt如下所示：

M r = [ 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 ] + [ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ] = [ 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 ] M_r=\begin{bmatrix} 0 ; 1 ; 0 ; 0 \\ 1 ; 0 ; 1 ; 0 \\ 0 ; 0 ; 0 ; 1 \\ 0 ; 0 ; 0 ; 0 \\ \end{bmatrix} + \begin{bmatrix} 1 ; 0 ; 0 ; 0 \\ 0 ; 1 ; 0 ; 0 \\ 0 ; 0 ; 1 ; 0 \\ 0 ; 0 ; 0 ; 1 \\ \end{bmatrix} = \begin{bmatrix} 1 ; 1 ; 0 ; 0 \\ 1 ; 1 ; 1 ; 0 \\ 0 ; 0 ; 1 ; 1 \\ 0 ; 0 ; 0 ; 1 \\ \end{bmatrix} Mr=⎣⎢⎢⎡0100100001000010⎦⎥⎥⎤+⎣⎢⎢⎡1000010000100001⎦⎥⎥⎤=⎣⎢⎢⎡1100110001100011⎦⎥⎥⎤ M s = [ 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 ] + [ 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 ] = [ 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 ] M_s=\begin{bmatrix} 0 ; 1 ; 0 ; 0 \\ 1 ; 0 ; 1 ; 0 \\ 0 ; 0 ; 0 ; 1 \\ 0 ; 0 ; 0 ; 0 \\ \end{bmatrix} + \begin{bmatrix} 0 ; 1 ; 0 ; 0 \\ 1 ; 0 ; 0 ; 0 \\ 0 ; 1 ; 0 ; 0 \\ 0 ; 0 ; 1 ; 0 \\ \end{bmatrix} = \begin{bmatrix} 0 ; 1 ; 0 ; 0 \\ 1 ; 0 ; 1 ; 0 \\ 0 ; 1 ; 0 ; 1 \\ 0 ; 0 ; 1 ; 0 \\ \end{bmatrix} Ms=⎣⎢⎢⎡0100100001000010⎦⎥⎥⎤+⎣⎢⎢⎡0100101000010000⎦⎥⎥⎤=⎣⎢⎢⎡0100101001010010⎦⎥⎥⎤ M t = [ 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 ] + [ 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 ] + [ 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 ] = [ 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 ] M_t=\begin{bmatrix} 0 ; 1 ; 0 ; 0 \\ 1 ; 0 ; 1 ; 0 \\ 0 ; 0 ; 0 ; 1 \\ 0 ; 0 ; 0 ; 0 \\ \end{bmatrix} + \begin{bmatrix} 1 ; 0 ; 1 ; 0 \\ 0 ; 1 ; 0 ; 1 \\ 0 ; 0 ; 0 ; 0 \\ 0 ; 0 ; 0 ; 0 \\ \end{bmatrix} + \begin{bmatrix} 0 ; 1 ; 0 ; 1 \\ 1 ; 0 ; 1 ; 0 \\ 0 ; 0 ; 0 ; 0 \\ 0 ; 0 ; 0 ; 0 \\ \end{bmatrix} = \begin{bmatrix} 1 ; 1 ; 1 ; 1 \\ 1 ; 1 ; 1 ; 1 \\ 0 ; 0 ; 0 ; 1 \\ 0 ; 0 ; 0 ; 0 \\ \end{bmatrix} Mt=⎣⎢⎢⎡0100100001000010⎦⎥⎥⎤+⎣⎢⎢⎡1000010010000100⎦⎥⎥⎤+⎣⎢⎢⎡0100100001001000⎦⎥⎥⎤=⎣⎢⎢⎡1100110011001110⎦⎥⎥⎤

【本文地址】

集合论

集合论

今日新闻

推荐新闻