当前位置：网站首页>[set theory] relational representation (relational matrix | examples of relational matrix | properties of relational matrix | operations of relational matrix | relational graph | examples of relationa

[set theory] relational representation (relational matrix | examples of relational matrix | properties of relational matrix | operations of relational matrix | relational graph | examples of relationa

2022-07-03 04:37:00 【Programmer community】

List of articles

One 、 The relational matrix
Two 、 Example of relational matrix
3、 ... and 、 Properties of relation matrix
Four 、 Relational matrix operation
5、 ... and 、 The diagram
6、 ... and 、 Diagram example
7、 ... and 、 Relationships represent related properties

One 、 The relational matrix

{

⋯

}

⊆

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$ Use The relational matrix Express :

(

)

(

)

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

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

Relation matrix value :

(

)

(

)

{

nothing

Turn off

system

M(R)(i, j) = r_{ij} =\begin{cases} 1, & a_i R a_j \\ 0, & It doesn't matter \end{cases}

$M (R) (i, j) = r_{i j} = {1, 0, a_{i} R a_{j} nothing Turn off system$

Description of relation matrix definition :

$A$ It's a

$n$ Meta set ( There are

$n$ Elements ) ,

$R$ yes

$A$ The binary relationship on ,

$R$ The relation matrix of is

n \times n

$n \times n$ Matrix of , The first

$i$ Xing di

$j$ Element at column position

r_{ij}

$r_{i j}$ The value can only be

$0$ or

$1$ ;

Description of relation matrix value :

r_{ij} = 1

$r_{i j} = 1$ , shows

$A$ Collection The first

$i$ Elements and

$j$ Elements have relationships

$R$ , Write it down as :

a_i R a_j

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

r_{ij} = 0

$r_{i j} = 0$ , shows

$A$ Collection The first

$i$ Elements and

$j$ Elements don't matter

$R$ ;

The essence of relational matrix : In the relation matrix , Each line corresponds to

$A$ The elements in the collection , Each column also corresponds to

$A$ The elements in the collection , The value of the position where the rows intersect (

$0$ or

$1$ ) Express

$A$ In the set

$i$ Elements and

$j$ Whether there is a relationship between the ordered pairs of elements

$R$ ;

Two 、 Example of relational matrix

{

}

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

Use the relation matrix to express the above

R_1 , R_2

$R_{1}, R_{2}$ Two relationships :

{

}

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

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

The rest are all

(

)

[

]

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 >}$ among :

The rest are all

(

)

[

]

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

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

3、 ... and 、 Properties of relation matrix

Ordered pair set expression And The relational matrix Can only be mutually determined

Property one : Inverse operation related properties

(

−

)

(

)

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

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

(

−

)

M(R^{-1})

$M (R^{- 1})$ The inverse of the relationship Of The relational matrix
And

(

)

(M(R))^T

$(M (R))^{T}$ The relational matrix Of The inverse
These two matrices are equal ;

Property two : Properties related to composition operation

(

∘

)

(

)

∙

(

)

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

$∙$ It's matrix Logical multiplication , Calculation matrix

r_{ij}

$r_{i j}$ Value The first

$i$ That's ok multiply The first

$j$ Column , Bit by bit Logical multiplication , Then multiply the logic and the result is Logical addition ;

Above Logical multiplication uses

∧

\land

$\land$ operation , Logical addition uses

∨

\lor

$\lor$ operation ;

Four 、 Relational matrix operation

{

}

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

In the example above , Two relational matrices have been found ;

(

)

[

]

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. seek

(

−

)

(

−

)

M(R^{-1}) , M(R_2^{-1})

$M (R^{- 1}), M (R_{2}^{- 1})$

Directly transpose the matrix , Can get Inverse relation matrix of relation ;

(

−

)

(

)

[

]

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. seek

(

∘

)

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

Among them

∙

\bullet

$∙$ Is the logical multiplication of two matrices , Addition uses

∨

\lor

$\lor$ , Multiplication uses

∧

\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 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$

Logical multiplication of matrices : The second of the result matrix

$i$ That's ok , The first

$j$ The value of the column element is , The first

$i$ The three elements of a row Respectively with the previous

$j$ The three elements of the column , Then the three results are or calculated , The end result is The order of the matrix

$i$ That's ok , The first

$j$ Value of column element ;

∘

{

}

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. seek

(

∘

)

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

Among them

∙

\bullet

$∙$ Is the logical multiplication of two matrices , Addition uses

∨

\lor

$\lor$ , Multiplication uses

∧

\land

$\land$

Particular attention , The order of synthesis is reverse synthesis , The latter relation matrix comes first , The former relation matrix is later

(

)

∙

(

)

[

]

∙

[

]

[

]

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 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤$

Logical multiplication of matrices : The second of the result matrix

$i$ That's ok , The first

$j$ The value of the column element is , The first

$i$ The three elements of a row Respectively with the previous

$j$ The three elements of the column , Then the three results are or calculated , The end result is The order of the matrix

$i$ That's ok , The first

$j$ Value of column element ;

∘

{

}

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

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

5、 ... and 、 The diagram

{

⋯

}

⊆

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$ Diagram for :

The vertices : $\circ∘ Express A A$
$A$ The elements in the collection ;
There is a directional side : $\rightarrow→ Express R R$
$R$ The elements in ;
$a_i R a_jaiRaj It's from the apex a i a_iai To The vertices a j a_jaj The directed side of < a i , a j > <a_i , a_j>$
$< a_{i}, a_{j} >$ ;

6、 ... and 、 Diagram example

{

}

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 >}$ Diagram representation :

Insert picture description here

{

}

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

$R_{2} = {< a, b >, < a, c >, < b, c >}$ Use diagrams to represent :

Insert picture description here

−

{

}

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

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

Insert picture description here

−

{

}

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

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

Insert picture description here

7、 ... and 、 Relationships represent related properties

$A$ The elements in the collection , After calibration sequence , That is, the

$A$ Relationship on ,

⊆

R \subseteq A \times A

$R \subseteq A \times A$ , It has the following properties :

The diagram $R R R Set expression of ( Ordered pair set ) , Sure Sole determination ;$
$G (R)$ And Relational
Relationship
$G (R)$ , They all correspond to each other ;