Question

In: Computer Science

CSC 225 Discrete Structures for Computer Science Home Work 3 Due Date: March 31, 2017 Friday...

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

Solutions

Expert Solution

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

  • Reflexive: Clearly, it is true that a = a for all values a. Therefore, = is reflexive.
  • Symmetric: If a = b, it is also true that b = a. Therefore, = is symmetric
  • Transitive: If a = b and b = c, this says that a is the same as b which in turn is the same as c. So a is then the same as c, so a = c, and thus = is transitive.

Thus = is an equivalence relation.


Related Solutions

CSC 101 Assignment 3 Barista Assistant Due Date: Friday, October 30 at 11:59 PM Learning Objectives:...
CSC 101 Assignment 3 Barista Assistant Due Date: Friday, October 30 at 11:59 PM Learning Objectives: Practice combining your knowledge of conditionals, loops, functions, strings, and lists. What to Submit: Write your program in a Python script named barista.py. Submit this file to the Assignment 3 page on Canvas. Description The purpose of this assignment is to write a Python program for a cafe to help baristas create coffee for a customer. Your program will take the customer's order and...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT