Answer to Question #191586 in Discrete Mathematics for Leia

Question

1 Let a relation R be represented by the following matrix MR =

1000001 1111000  1 0 1 1 0 1 0 

MR=1 0 0 1 0 0 0

 1 1 0 1 0 0 0  0 1 0 1 1 0 1 0111100

 

Determine whether R is

(a) reflexive

(b) irreflexive

(c) symmetric

(d) asymmetric

(e) antisymmetric

(f) transitive

GIVE REASONS for your answer.

2 Consider the following relation R on A where A = {1, 2, 3, 4,5}

aRb ⇔ ab < min(a, b)

For example, 2R4 since 24 = 12 and min(2,4) = 2 and 12 < 2.

(a) Draw the digraph of R

(b) Give a path of length 2 from 3, if any

(c) Give the domain and range of R.

(d) Determine R

Answer 1

1.The matrix can be written in relation form,

a) To be reflexive relation should satisfy

(a,a) for all elements i.e all diagonal elemtents must be 1

hence the relation is Not Reflexive.

b)It is Not Irreflexive .

To be irreflexive all diagonal elements must be 0

But (1,1) is present.

c) To be symmetric it should satisfy

if(a, b) is present then (b,a) must me present

It does not satisfy for (1,7) because (7,1) is not present hence the relation is not symmetric.

d) To be asymmetric

if(a, b) is present then (b, a) should not be present.

but (1,1) is present therefore Not Asymmetric.

e) To be antisymmetric

if(a,b) and (b,a) is present then a must be equal to b

hence the relation satisfy and it is Antisymmetric.

f)To be in transitive it should satisfy

if (a,b ) and ( b,c) is present then (a,c) must be present.

But here for no element this property is satisfied hence it is Not Transitive.

2.For A={1,2,3,4,5}

The Relation R is given as-

R={(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,%),(3,2),(3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)}

(a) Diagraph is-

(b)These are paths of length 2 from vertex 3.

$P_1:3\to 2 \to 5 \\ P_2:3\to 2 \to 4 \\ P_3:3\to 2 \to 3\\ P_4:3\to 4 \to 5\\ \\$

(c) Domain (R)={1,2,3,4,5}

  Range (R)={2,3,4,5}

By definition 

   Domain (R)={$x\in A:(x,y)\in R$ }

   Range (R)={$y\in A:(x,y)\in R$ }

(d) R={$(a,b)\in A\times A:\dfrac{a}{b}<min(a,b)$ }

{(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,%),(3,2),(3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)}