Question

Discrete Mathematical Structures for Computer Science. Please show your step and explain !

7. Set A = {0, 1,2,3}, relation R: A x A is defined as: R= {(0, 1), (0, 2), (1, 1), (1,3), (2, 2), (3,0)}. For relation R find the (c) Transitive cclosure.

Answer 1

Transitive > A relation R is transitive on s whenever aRb, brc then are i.e. if (a,b)ER, (b, Cher then (a, c) ER & a, b, c EAS. Composition of Relations 7 het A, B and C be sets. het R in the relation from A to B, i.e. RC AXB. s in the relation from Bito 6, ie se Bye The composition of R and S, denoted by Ros, where Ros= {(2, c) E AXC for some be B, (a,b) ER and (6, C) ES?

Transitive Closure:-

The Transitive Closure, R⁺ is the smallest transitive relation that contains R as a subset.

Let a relation R is defined on a Set A and A contains n elements, then

R⁺ = R U R² U R³ U .......... U Rⁿ.

Here to find the transitive closure for the given relation, we need to find the n.

n is the total number of elements(also called cardinality) in set A.

Given, Set A = { 0,1, 2, 3 }

so, n = 4.

So, Transitive closure of R is,

R⁺ = R U R² U R³ U R^4.

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

R² = R o R

= { (0,1) , (0,2) , (1,1) , (1,3) , (2,2) , (3,0) } o { (0,1) , (0,2) , (1,1) , (1,3) , (2,2) , (3,0) }

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

R³= R² o R

= { (0,1) , (0,3) , (0,2) , (1,1) , (1,3) , (1,0) , (2,2) , (3,1) , (3,2) } o { (0,1) , (0,2) , (1,1) , (1,3) , (2,2) , (3,0) }

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

R⁴= R³ o R

= { (0,1) , (0,3) , (0,0) , (0,2) , (1,1) , (1,3) , (1,0) , (1,2) , (2,2) , (3,1) , (3,3) , (3,2) } o { (0,1) , (0,2) , (1,1) , (1,3) , (2,2) , (3,0) }

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

R⁺ = R U R² U R³ U R⁴

= { (0,1) , (0,2) , (1,1) , (1,3) , (2,2) , (3,0) } o { (0,1) , (0,3) , (0,2) , (1,1) , (1,3) , (1,0) , (2,2) , (3,1) , (3,2) } o { (0,1) , (0,3) , (0,0) , (0,2) , (1,1) , (1,3) , (1,0) , (1,2) , (2,2) , (3,1) , (3,3) , (3,2) } o { (0,1) , (0.3) , (0,0) , (0,2) , (1,1) , (1,3) , (1,0) , (1,2) , (2,2) , (3,1) , (3,3) , (3,0) , (3,2) }  

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

So, the Transitive closure for the given relation R is

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