Relations - Exercise

RELATIONS - Exercise Problems

 

Exercise 1.

Let A = {0, 1, 2, 3} and R is a relation over A:

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

Draw the Digraph and matrix of R.

 

Exercise 2.

If   A = {2,3,4,6} and R is defined by   (a, b) ∈ R if a divides b.

To draw diagraph and also represented by using matrix of R.

 

Exercise 3.

List the ordered pairs in the relation R from A = {0,1,2,3,4} to B = {0,1,2,3} where (a, b) ∈ R if and only if

i.                     a = b

ii.                   a + b = 4

iii.                 a> b

iv.                 a / b (a divides b)

v.                   a ≠ b

vi.                 ab> 0

vii.               a = b 2

Find the domain and range of R.

 

Exercise 4.

Which of the ordered pairs given by {1,2,3} x {1,2,3} belong to the following relations?

i.                     a≤b

ii.                   a = b + 1

iii.                 ab≤4

 

Exercise 5.

 Draw the Digraph and also represented matrix of R.

Let A={1,2,3,4} and let R={(1,1),(1,2),(2,2),(3,4),(4,3),(3,3),(4,4)}

Show that R is an equivalence relation.

 

Exercise 6.

 Let A={1,2,3,4,5}, R={(a,b)|(a+b) is even}, R is a relation on set A.  

Show that R is an Equivalence relation.

 

Exercise 7.

Let A={1,2,3,4} and let R={(1,1),(1,2),(2,2),(3,4),(4,3),(3,3),(4,4)}

Let A=Z and let R={(a,b) ∈AxA:a=b mod 2}

Show that R is an equivalence relation.


Exercise 8.

List the ordered pairs in the relation R from A={0,1,2,3,4} to B={0,1,2,3} where (a,b)€R

if and only if  (i) a=b  (ii) a+b=4  (iii)a>b (iv) a/b

 

Exercise 9.

The Relation R on the set A={1,2,3,4,5} is defined by the rule (a,b) €R, if (a+b=even)

            (i)List the elements of R and and R-1

(ii) Find the domain and Range of R.

(iii) Find the domain and Range of R-1.

(iv) The Cartesian product A X A

(v) List the element of the complement of R

 

Exercise 10.

If R={(1,2),(2,4),(3,3)} and S={(1,3),(2,4),(4,2)}  find

            (i)R V S (ii) R ∧ S (iii) R-S  (iv)S-R  (v) verify that dom(R V S)= dom(R) V dom(S)

 

Exercise 11.

Which of the following relations on {0,1,2,3} are equivalence relations?

            (a) R1={(0,0)(1,1)(2,2)(3,3)}  

            (b) R2={(0,0)(0,2)(2,0)(2,2)(2,3)(3,2)(3,3)}

            (c) R3={(0,0)(1,1)(1,2)(2,1)(2,2)(3,3)

            (d) R4={(0,0)(1,1)((1,3)(2,2)(2,3)(3,1)(3,2)(3,3)}

(e) R5={(0,0)(0,1)(0,2)(1,0)((1,1)(1,1)(1,2)(2,0)(2,2)(3,3)

 

Exercise 12.

If A={1,2,3,4} and the relation R is defined on A by (a,b) R (c,d) if a+b=c+d. Verify that A is an equivalence relation on A and also find the quotient set of A by R.

 

Exercise 13.

If R is the relation on A = {1,2,3} such that (a, b) € R if and only if a + b = even. Find the relational matrix M R . Find also the relational matrices R -1 , Complement of R and R 2

 

Exercise 14.

If R is the relation from A = {1,2,3,4} to B = {2,3,4,5} list the elements in R, defined by aRb if a and b are both odd. Write also the domain and range of R.

 

Exercise 15.

If R is a Relation from A = {1,2,3 to B = {4,5} given by R = {(1,4) (2,4) (1,5) (3,5). Find R -1 and complement of R.

 

Exercise 16.

If R is a relation from A = 1, 2, 3} to B = {1,2} such that a R b if a> b, Write down the matrix representation of R.

 

Exercise 17. 

Draw the directed graph representing the relation {1,2,3,4} given by the ordered pairs {(1,2) (1,3) (1,4) (2,3) (2,4) (3, 4)


Comments

Post a Comment

Popular posts from this blog

Backtracking - N-Queens Problem, Sum of Subsets, Graph Colouring, Hamiltonian Cycle

Image
UNIT - V : BACKTRACKING General Method – 8-Queens Problem – Sum Of Subsets – Graph Coloring –  Hamiltonian Cycles General Method Backtracking is a problem-solving technique used in algorithms to find solutions by exploring all possible options. In backtracking, a state-space tree is a tree-like structure that represents all possible states (solutions or non-solutions) of a problem. Backtracking algorithms explore this tree using a depth-first search approach, systematically checking each path until a solution is found or all possibilities have been exhausted.  Here’s how it works, step-by-step: Start with a choice : Make a decision and move forward. Check feasibility : If this choice leads to a solution or partial solution, continue. If not, stop exploring this path. Go back and try a different path : If you reach a dead end, go back to the last point where you made a choice. Try a different path from there. Repeat until you find a solution ...
Read more

Divide and Conquer Technique - Binary Search, Quick Sort, Merge Sort

Image
  UNIT II - DIVIDE AND CONQUER TECHNIQUE General Method – Binary Search – Merge Sort – Quick Sort.  GENERAL METHOD The divide and conquer technique is a problem-solving approach that works in three main steps: 1.       Divide : Break down a large problem into smaller, simpler sub-problems. 2.       Conquer : Solve each of the sub-problems individually. This can often be done recursively if the sub-problems are still large. 3.     Combine : Combine the solutions of the sub-problems to get the solution to the original, larger problem. This approach is commonly used in algorithms like binary search, merge sort and quick sort, where breaking down a problem makes it easier and faster to solve.   BINARY SEARCH Binary search is an efficient algorithm for finding a target value within a sorted list. Here’s how it works: Start in the Middle : Look at the middle element of the list. Compare : ...
Read more

GRAPH THEORY

Image
  GRAPH THEORY DEFINITION A graph G = (V, E) consists of a non-empty set V, called the set of vertices (points, nodes) and a set  of ordered or unordered pairs of elements of V, called the edges E set (links), such that there is a mapping from the set E to the set of ordered or unordered pairs of elements of V. Example In the first graph, V = { A , B , C , D } E = {(A,B) , (A,C) , (A,D), (B,C), (B,D) , (C,D)} In the second graph, V = { E, F, G } E = {(F,E) , (E,G) , (G,F)} If an edge e ∈ E is associated with an ordered pair (u,v) or an unordered pair (u,v), where u,v ∈ V, then e is said to connect or join the nodes u and v.  The edge e that connects the nodes u and v is said to be incident on each of the nodes.  The pair of each node that is connected by an edge is called adjacent nodes . Isolated Nodes If any node has no edges connected with any other node then its degree will be zero(0) and it will be called as isolated node. Adjacent Nodes Her...
Read more