Scribd
Upload
28 views5 pages

Relations in Discrete Math Tutorial

The document is a tutorial on relations in discrete mathematics and linear programming, covering matrix representations of relations, properties such as reflexivity and symmetry, and operations like union and intersection. It includes exercises on representing relations with matrices, determining their properties, and finding closures. Additionally, it discusses directed graphs and equivalence relations, providing examples and solutions throughout.

Uploaded by

ibrahemashhab
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views5 pages

Relations in Discrete Math Tutorial

The document is a tutorial on relations in discrete mathematics and linear programming, covering matrix representations of relations, properties such as reflexivity and symmetry, and operations like union and intersection. It includes exercises on representing relations with matrices, determining their properties, and finding closures. Additionally, it discusses directed graphs and equivalence relations, providing examples and solutions throughout.

Uploaded by

ibrahemashhab
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Discrete Math.

& Linear Programming BES 114


Tutorial #5
”Relations”

1. Represent each of these relations on {1, 2, 3} with a matrix (with the elements of this set listed in
increasing order).

(a) {(1, 1), (1, 2), (1, 3)} (c) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
   
1 1 1 1 1 1
0 0 0 0 1 1
0 0 0 0 0 1

(b) {(1, 2), (2, 1), (2, 2), (3, 3)} (d) {(1, 3), (3, 1)}
   
0 1 0 0 0 1
1 1 0 0 0 0
0 0 1 1 0 0

2. List the ordered pairs in the relations on {1, 2, 3} corresponding to these matrices (where the rows
and columns correspond to the integers listed in increasing order).

(a)  
1 0 1
0 1 0
1 0 1
The ordered pairs are:
{(1, 1), (1, 3), (2, 2), (3, 1), (3, 3)}
(b)  
0 1 0
0 1 0
0 1 0
The ordered pairs are:
{(1, 2), (2, 2), (3, 2)}
(c)  
1 1 1
1 0 1
1 1 1
The ordered pairs are:

{(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)}

3. How can the matrix representing a relation R on a set A be used to determine whether the relation is
irreflexive? Give an example.
Solution:
A relation R on a set A is irreflexive if no element is related to itself, i.e., (a, a) →
/ R for all a → A.
Using the matrix representation of R:
• Check the main diagonal (entries where the row index equals the column index).
• If all diagonal entries are 0, the relation is irreflexive.
• If any diagonal entry is 1, the relation is not irreflexive.
Example:  
0 1 1
0 0 1
0 0 0
This relation is irreflexive because all diagonal entries ((1, 1), (2, 2), (3, 3)) are 0.
4. Determine whether the relations represented by the matrices in Exercise 2 are reflexive, irreflexive,
symmetric, antisymmetric, and/or transitive.
Solution: Relations on {1, 2, 3}

(a)  
1 0 1
0 1 0
1 0 1
Properties:
• Reflexive: Yes (all diagonal elements are 1).
• Irreflexive: No (since it is reflexive).
• Symmetric: Yes ((1, 3) is present and (3, 1) is also present).
• Antisymmetric: No ((1, 3) and (3, 1) both exist, but 1 ↑= 3).
• Transitive: Yes (check all possible pairs).
(b)  
0 1 0
0 1 0
0 1 0
Properties:
• Reflexive: No (missing (1, 1) and (3, 3)).
• Irreflexive: No ((2, 2) exists).
• Symmetric: No ((1, 2) exists but (2, 1) does not).
• Antisymmetric: Yes (Because there are no distinct pairs (a, b) and (b, a) in R).
• Transitive: Yes (all possible pairs satisfy transitivity).
(c)  
1 1 1
1 0 1
1 1 1
Properties:
• Reflexive: No (missing (2, 2)).
• Irreflexive: No ((1, 1), (3, 3) exist).
• Symmetric: Yes (for every (a, b), (b, a) exists).
• Antisymmetric: No (since it is symmetric and not diagonal).
• Transitive: No (Because (2, 1) → R and (1, 2) → R, but (2, 2) →
/ R).

5. Let R be the relation represented by the matrix


 
0 1 1
MR =  1 1 0 .
1 0 1

Find the matrix representing:


(a) R→1 The inverse relation R→1 is represented by the transpose of MR :
 T  
0 1 1 0 1 1
MR→1 = MRT = 1 1 0 =  1 1 0 .
1 0 1 1 0 1

(b) R The complement relation R is represented by the matrix of all 1’s minus MR :
   
1 1 1 1 0 0
MR = 1 1 1 ↓ MR = 0 0 1 .
1 1 1 0 1 0

(c) R2 The composition R2 = R ↔ R is represented by the Boolean product of MR with itself:


 
(0 ↘ 0) ≃ (1 ↘ 1) ≃ (1 ↘ 1) (0 ↘ 1) ≃ (1 ↘ 1) ≃ (1 ↘ 0) (0 ↘ 1) ≃ (1 ↘ 0) ≃ (1 ↘ 1)
MR2 = MR ↗MR = (1 ↘ 0) ≃ (1 ↘ 1) ≃ (0 ↘ 1) (1 ↘ 1) ≃ (1 ↘ 1) ≃ (0 ↘ 0) (1 ↘ 1) ≃ (1 ↘ 0) ≃ (0 ↘ 1)
(1 ↘ 0) ≃ (0 ↘ 1) ≃ (1 ↘ 1) (1 ↘ 1) ≃ (0 ↘ 1) ≃ (1 ↘ 0) (1 ↘ 1) ≃ (0 ↘ 0) ≃ (1 ↘ 1)
 
1 1 1
=  1 1 1 .
1 1 1

6. Let R1 and R2 be relations on a set A represented by the matrices

   
0 1 0 0 1 0
MR 1 = 1 1 1 MR 2 = 0 1 1 .
1 0 0 1 1 1

Find the matrices that represent:

(a) R1 ⇐ R2 The union is represented by the element-wise logical OR:


   
0≃0 1≃1 0≃0 0 1 0
MR1 ↑R2 = MR1 ≃ MR2 = 1 ≃ 0 1 ≃ 1 1 ≃ 1 = 1 1 1 .
1≃1 0≃1 0≃1 1 1 1

(b) R1 ⇒ R2 The intersection is represented by the element-wise logical AND:


   
0↘0 1↘1 0↘0 0 1 0
MR1 ↓R2 = MR1 ↘ MR2 = 1 ↘ 0 1 ↘ 1 1 ↘ 1 = 0 1 1 .
1↘1 0↘1 0↘1 1 0 0

7. Draw the directed graphs representing each of the relations from Exercise 1 and Exercise 2.
8. Draw the directed graph that represents the relation (a, a), (a, b), (b, c), (c, b), (c, d), (d, a), (d, b).
9. List the ordered pairs in the relations rep- resented by the directed graphs. Then, Determine whether
the relations represented by the directed graphs shown are reflexive, irreflexive, symmetric, antisym-
metric, asymmetric, and/or transitive.
10. Let R be the relation on the set {0, 1, 2, 3} containing the ordered pairs (0, 1), (1, 1), (1, 2), (2, 0), (2, 2),
and (3, 0). Find the:

(a) Reflexive closure of R


The reflexive closure is obtained by adding all missing pairs of the form (a, a):

R ⇐ {(0, 0), (3, 3)} = {(0, 0), (0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0), (3, 3)}
Figure 1: Example 9.

(b) Symmetric closure of R


The symmetric closure is obtained by adding the inverse of each existing pair:

R ⇐ {(1, 0), (2, 1), (0, 2), (0, 3)} = {(0, 1), (1, 0), (1, 1), (1, 2), (2, 1), (2, 0), (0, 2), (2, 2), (3, 0), (0, 3)}

11. Let R be the relation {(a, b) | a ↑= b} on the set of integers. What is the reflexive closure of R?
Solution:
The reflexive closure is obtained by adding all pairs (a, a):

R ⇐ {(a, a) | a → Z} = {(a, b) | a, b → Z} = Z ⇑ Z

The reflexive closure is the complete relation containing all possible ordered pairs of integers.

12. Let R be the relation {(a, b) | a divides b} on the set of integers. What is the symmetric closure of R?
Solution:
The symmetric closure is obtained by adding all pairs (b, a) where (a, b) → R:

R ⇐ {(b, a) | a divides b} = {(a, b) | a divides b or b divides a}

This gives us all pairs where either a divides b or b divides a.

13. Draw the directed graph of the reflexive closure, symmetric closure, transitive closure of the relations
with the directed graph shown.

Figure 2: Example 13. Figure 3: Example 14. Figure 4: Example 15.

14. Determine whether the relation with the directed graph shown is an equivalence relation and find the
equivalence classes for the equivalence relations.

15. Determine whether the relations represented by these zero–one matrices are equivalence relations and
find the equivalence classes for the equivalence relations.

16. Which of these collections of subsets are partitions of {1, 2, 3, 4, 5, 6}?


(a) {1, 2}, {2, 3, 4}, {4, 5, 6}
(b) {1}, {2, 3, 6}, {4}, {5}
(c) {2, 4, 6}, {1, 3, 5}
(d) {1, 4, 5}, {2, 6}

Common questions

Powered by AI

A relation is an equivalence relation if it is reflexive, symmetric, and transitive. For the given matrix 0 1 1 1 1 0 1 0 1, this relation lacks reflexivity as not all diagonal entries are 1, proven by the absence of (0, 0) and (3, 3). Symmetry may hold, but without reflexivity, this criterion is irrelevant for equivalence, and the relation's composition fails to satisfy necessary comprehensive transitive checks, excluding it from equivalence classification .

The union of two relations R1 and R2 is computed using the element-wise logical OR operation on their matrices. For example, if MR1 = 0 1 0 1 1 1 1 0 0 and MR2 = 0 1 0 0 1 1 1 1 1, then the union MR1 ∪ MR2 = 0 1 0 1 1 1 1 1 1 . The intersection is computed using element-wise logical AND: MR1 ∩ MR2 = 0 1 0 0 1 1 1 0 0 .

A relation is transitive if whenever (a, b) and (b, c) are in the relation, (a, c) must also be in the relation. To check transitivity using a matrix, for any pair of entries (i, j) and (j, k) that are 1, the entry (i, k) should also be 1. The matrix's Boolean product with itself should maintain ones where transitivity exists. This is illustrated in matrix R2 where the composition R2 = R * R results in additional ones indicating transitive pairs .

A symmetric relation is one where for every (a, b) in the relation, (b, a) is also present, as seen in matrix 1 1 1 1 0 1 1 1 1 where if (1, 2) is present, (2, 1) is too . An antisymmetric relation, however, allows (a, b) and (b, a) only if a equals b, meaning no distinct (a, b) can have its symmetric pair also present; for instance, in matrix 0 1 0 0 1 0 0 1 0, distinct (a, b) and (b, a) pairs are missing .

A relation on a set is irreflexive if no element is related to itself, meaning for matrix entries where the row index equals the column index (main diagonal), all entries are 0. If all diagonal entries are 0, the relation is irreflexive; if any diagonal entry is 1, the relation is not irreflexive .

Reflexive closure of a relation involves adding pairs so that every element is related to itself, ensuring reflexivity. Given a set of ordered pairs, like {(0, 1), (1, 1), (1, 2), (2, 0), (3, 0)}, the reflexive closure is achieved by including missing self-pairs, resulting in new pairs such as (0, 0) and (3, 3) being added to make it reflexive, leading to the relation: {(0, 0), (0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0), (3, 3)} .

Examining the main diagonal of a relation matrix checks for reflexivity because the diagonal contains entries (a, a) for each element in the set. If all diagonal entries are 1, it confirms that every element has a self-loop, and thus the relation is reflexive . If any diagonal entry is 0, the relation is not reflexive because at least one element does not relate to itself .

Antisymmetric relations require that if (a, b) is present and a is not equal to b, then (b, a) cannot be present. In a matrix, this is seen where both (i, j) and (j, i) having 1s only coincide with i = j. For example, matrix 0 1 0 0 1 0 0 1 0 has no such pairs—it's antisymmetric . Asymmetric relations demand that if (a, b) is present, (b, a) is not, and vice-versa, and (a, a) pair is impossible. This distinction is evident if a matrix has no symmetric entries and no diagonal 1s, again shown in matrix form .

The Boolean product is significant in determining the composition of relations because it effectively combines two matrices to check which pairs continue through a middle element. For example, when using MR2 = MR * MR, the Boolean product involves computing each entry as 1 if any logical AND across a row and column sums to a non-zero value, creating new pairs that satisfy transitivity in a relation's context. This is a cornerstone for applications needing transitive closure of a relation .

The symmetric closure of a relation is formed by adding pairs such that if (a, b) is in the relation, then (b, a) must also be included. For example, given the relation on the set {(0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0)}, its symmetric closure would include additional pairs {(1, 0), (2, 1), (0, 2), (0, 3)}, resulting in a symmetric set {(0, 1), (1, 0), (1, 1), (1, 2), (2, 1), (2, 0), (0, 2), (2, 2), (3, 0), (0, 3)} .

You might also like