Discrete Mathematics: Representation of Relations
Welcome to our guide on the representation of relations in discrete mathematics. In this article, we will explore the concept of relations and various methods of representing them. We will also provide examples to help you understand these concepts better.
Understanding Relations
In discrete mathematics, a relation is a connection or association between two sets of elements. These elements can be numbers, objects, or any other entities. Relations allow us to describe and analyze the relationships between these elements.
Relations can be represented in different ways, depending on the nature of the connection between the elements. Some common types of relations include:
- Binary Relations: These relations involve two sets of elements and describe the relationship between them. For example, the “less than” relation between two numbers.
- Equivalence Relations: These relations satisfy three properties: reflexivity, symmetry, and transitivity. An example of an equivalence relation is the “equality” relation between two objects.
- Partial Order Relations: These relations describe a partial ordering between elements. They satisfy the properties of reflexivity, antisymmetry, and transitivity. The “less than or equal to” relation is an example of a partial order relation.
Methods of Representing Relations
There are several methods of representing relations in discrete mathematics. Let’s explore some of the commonly used methods:
1. Tabular Representation
Tabular representation involves creating a table to represent the relation between elements. Each row and column in the table represents an element from the two sets being related. The intersection of a row and column indicates the relationship between the corresponding elements.
For example, consider the relation “less than” between the set {1, 2, 3} and {4, 5, 6}. The tabular representation would look like this:
| 4 | 5 | 6 | |
|---|---|---|---|
| 1 | true | true | true |
| 2 | true | true | true |
| 3 | true | true | true |
In this table, the value “true” indicates that the element in the corresponding row is less than the element in the corresponding column.
2. Matrix Representation
Matrix representation is similar to tabular representation, but it uses a matrix to represent the relation. Each row and column in the matrix corresponds to an element from the two sets being related. The value in the matrix indicates the relationship between the corresponding elements.
Continuing with the previous example, the matrix representation of the “less than” relation would look like this:
| 4 5 6--+------1 | T T T2 | T T T3 | T T T
In this matrix, “T” represents true, indicating that the element in the corresponding row is less than the element in the corresponding column.
3. Set Builder Notation
Set builder notation is a concise way of representing relations using set notation. It involves specifying the elements that are related using a condition or rule.
For example, consider the relation “divisible by” between the set of positive integers and the number 3. The set builder notation for this relation would be:
{x | x is a positive integer and x is divisible by 3}
This notation represents the set of all positive integers that are divisible by 3.
4. Digraph Representation
Digraph, short for directed graph, is a graphical representation of relations. It uses nodes to represent elements and directed edges to represent the relationship between them.
For example, consider the relation “parent of” between the set {A, B, C} and {D, E, F}. The digraph representation would look like this:
ABC/ / / DE FD EF
In this digraph, the arrows indicate the direction of the relationship. For example, the arrow from A to D represents the fact that A is the parent of D.
Examples of Relations
Let’s explore some more examples of relations to deepen our understanding:
1. “Greater than” Relation
Consider the relation “greater than” between the set {1, 2, 3} and {4, 5, 6}. The tabular representation of this relation would be:
| 4 | 5 | 6 | |
|---|---|---|---|
| 1 | false | false | false |
| 2 | false | false | false |
| 3 | true | true | false |
In this table, the value “false” indicates that the element in the corresponding row is not greater than the element in the corresponding column. The value “true” indicates that the element in the corresponding row is greater than the element in the corresponding column.
2. “Parallel to” Relation
Consider the relation “parallel to” between the set of lines in a plane. The set builder notation for this relation would be:
{(l1, l2) | l1 and l2 are lines in a plane and l1 is parallel to l2}
This notation represents the set of all pairs of lines that are parallel to each other.
3. “Friend of” Relation
Consider the relation “friend of” between a set of people. The digraph representation of this relation would look like this:
Alice/BobCarol/Dave
In this digraph, the arrows indicate the direction of the relationship. For example, the arrow from Bob to Alice represents the fact that Bob is a friend of Alice.
Conclusion
Relations are an important concept in discrete mathematics, allowing us to describe and analyze the connections between elements. In this article, we explored various methods of representing relations, including tabular representation, matrix representation, set builder notation, and digraph representation. We also provided examples to illustrate these concepts.
By understanding the representation of relations, you can gain insights into the relationships between elements and apply this knowledge to solve problems in various fields, such as computer science, mathematics, and social sciences.