CSC 225 Discrete Structures for Computer Science Home Work 3 Due Date: March 31,
ID: 3808686 • Letter: C
Question
CSC 225 Discrete Structures for Computer Science Home Work 3
Due Date: March 31, 2017 Friday 2:00pm.
1. Write what is Reflective relation and give an example
2. What are the different types of relations discussed in class write with examples
3. Let A = {0, 1, 2, 3, 4} and B = {a, b, c, d}. Then {(0, a), (0, b), (1, a), (2, b), (3, c), (4, d)}} is a relation from A to B. Represent the above relation using a diagram.
4. Which of the following relations, defined on {1, 2, 3, 4} are symmetric and which are antisymmetric, and which are reflective? – R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)} – R2 = {(1, 1), (1, 2), (2, 1)} – R3 = {(1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)} – R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} – R5 = {(3, 4)} – R6 = {(1, 1), (2, 2), (3, 3), (4, 4)}
Explanation / Answer
Reflexive[edit]
A relation is reflexive if, we observe that for all values a:
a R a
In other words, all values are related to themselves.
The relation of equality, "=" is reflexive. Observe that for, say, all numbers a (the domain is R):
a = a
so "=" is reflexive.
In a reflexive relation, we have arrows for all values in the domain pointing back to themselves:
Note that is also reflexive (a a for any a in R). On the other hand, the relation < is not (a < a is false for any a in R).
Say we are asked to prove that "=" is an equivalence relation. We then proceed to prove each property above in turn (Often, the proof of transitivity is the hardest).
Thus = is an equivalence relation.