Intro to Discrete Structures

Enumerate the elements of the following relations from the set A of positive integers less than or equal to 10 to the set B of positive integers less than or equal to 30.

1. An element a of A is related to the element b of B if b = 3 × a

2. An element a of A is related to the element b of B if b = 2 × a – 1

Determine the inverse of the following relations:

1. The > relation defined on the integers
2. The = relation defined on the integers

Let A = {0, 1, 2, 3}. Define a relation R on Aas follows:

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

Draw a directed graph for this relation and identify which of the following properties hold for this relation:

• Reflexive
• Symmetric
• Transitive
• Antisymmetric

Explain why it has a property or give a counterexample.

Given the set A = {1, 2, 3} and the set S = {(x, y) | x and y in A}. Consider the relation ≤ defined on S as follows: ((x₁, y₁) ≤ (x₂, y₂) if x₁ ≤ x₂ and y₁ ≤ y₂. Draw the directed graph of this relation. Show that it is a partial order. Explain why it is not a total order.

Consider the set S defined in problem 4 and the following relation = defined on S as follows: (x₁, y₁) = (x₂, y₂) if x₁ + y₁ = x₂ + y₂. Draw the directed graph of this relation. Show that it is an equivalence relation. List its equivalence classes.