Representing Relations : Representing Relations What do we know about the matrices representing symmetric relations?
These matrices are symmetric, that is, MR = (MR)t. symmetric matrix, symmetric relation. non-symmetric matrix, non-symmetric relation.
Representing Relations : Representing Relations The Boolean operations join and meet (you remember?) can be used to determine the matrices representing the union and the intersection of two relations, respectively.
To obtain the join of two zero-one matrices, we apply the Boolean “or” function to all corresponding elements in the matrices.
To obtain the meet of two zero-one matrices, we apply the Boolean “and” function to all corresponding elements in the matrices.
Representing Relations : Representing Relations Example: Let the relations R and S be represented by the matrices What are the matrices representing RS and RS?
Solution: These matrices are given by
Representing Relations Using Matrices : Representing Relations Using Matrices Do you remember the Boolean product of two zero-one matrices?
Let A = [aij] be an mk zero-one matrix and B = [bij] be a kn zero-one matrix.
Then the Boolean product of A and B, denoted by AB, is the mn matrix with (i, j)th entry [cij], where
cij = (ai1 b1j) (ai2 b2j) … (aik bkj).
cij = 1 if and only if at least one of the terms (ain bnj) = 1 for some n; otherwise cij = 0.
Representing Relations Using Matrices : Representing Relations Using Matrices Let us now assume that the zero-one matrices MA = [aij], MB = [bij] and MC = [cij] represent relations A, B, and C, respectively.
Remember: For MC = MAMB we have:
cij = 1 if and only if at least one of the terms (ain bnj) = 1 for some n; otherwise cij = 0.
In terms of the relations, this means that C contains a pair (xi, zj) if and only if there is an element yn such that (xi, yn) is in relation A and (yn, zj) is in relation B.
Therefore, C = BA (composite of A and B).
Representing Relations Using Matrices : Representing Relations Using Matrices This gives us the following rule:
MBA = MAMB
In other words, the matrix representing the composite of relations A and B is the Boolean product of the matrices representing A and B.
Analogously, we can find matrices representing the powers of relations:
MRn = MR[n] (n-th Boolean power).
Representing Relations Using Matrices : Representing Relations Using Matrices Example: Find the matrix representing R2, where the matrix representing R is given by Solution: The matrix for R2 is given by
Representing Relations Using Digraphs : Representing Relations Using Digraphs Definition: A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs).
The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge.
We can use arrows to display graphs.
Representing Relations Using Digraphs : Representing Relations Using Digraphs Example: Display the digraph with V = {a, b, c, d}, E = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}. An edge of the form (b, b) is called a loop.
Representing Relations Using Digraphs : Representing Relations Using Digraphs Obviously, we can represent any relation R on a set A by the digraph with A as its vertices and all pairs (a, b)R as its edges.
Vice versa, any digraph with vertices V and edges E can be represented by a relation on V containing all the pairs in E.
This one-to-one correspondence between relations and digraphs means that any statement about relations also applies to digraphs, and vice versa.
Closures of Relations : Closures of Relations What is the closure of a relation?
Definition: Let R be a relation on a set A. R may or may not have some property P, such as reflexivity, symmetry, or transitivity.
If there is a relation S that contains R and has property P, and S is a subset of every relation that contains R and has property P, then S is called the closure of R with respect to P.
Note that the closure of a relation with respect to a property may not exist.
Closures of Relations : Closures of Relations Example I: Find the reflexive closure of relation R = {(1, 1), (1, 2), (2, 1), (3, 2)} on the set A = {1, 2, 3}.
Solution: We know that any reflexive relation on A must contain the elements (1, 1), (2, 2), and (3, 3).
By adding (2, 2) and (3, 3) to R, we obtain the reflexive relation S, which is given by S = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 2), (3, 3)}.
S is reflexive, contains R, and is contained within every reflexive relation that contains R.
Therefore, S is the reflexive closure of R.
Closures of Relations : Closures of Relations Example II: Find the symmetric closure of the relation R = {(a, b) | a > b} on the set of positive integers.
Solution: The symmetric closure of R is given by
RR-1 = {(a, b) | a > b} {(b, a) | a > b}
= {(a, b) | a b}
Closures of Relations : Closures of Relations Example III: Find the transitive closure of the relation R = {(1, 3), (1, 4), (2, 1), (3, 2)} on the set A = {1, 2, 3, 4}.
Solution: R would be transitive, if for all pairs (a, b) and (b, c) in R there were also a pair (a, c) in R.
If we add the missing pairs (1, 2), (2, 3), (2, 4), and (3, 1), will R be transitive?
No, because the extended relation R contains (3, 1) and (1, 4), but does not contain (3, 4).
By adding new elements to R, we also add new requirements for its transitivity. We need to look at paths in digraphs to solve this problem.