DMS_PROJECT_PPT.pptxkajdfkaseufoabfajefhoaieifh

DMS

1. DEFINE THE PROPERTIES OF A RELATION ON A SET USING THE MATRIX REPRESENTATION OF THAT RELATION WITH EXAMPLES PRESENTED BY: DIBYANSU SEKHAR DAS(230101120147) SANJAYA KUMAR PANDA(230101120155) RUDRA LENKA(230101120156) YAJNADATTA PATTANAYAK(230101120157) ASHU KUMAR(230101120161) SUBMITTED TO: Prof. ASHOK MISHRA

2. CONTENTS

3. Definition and Matrix Representation

4. MATRIX REPRESENTATION OF A RELATION Representing Relations Using Matrices A relation between finite sets can be represented using a zero & one matrix. Suppose R is a relation from A = { , ,…, } to B = { , ,…, }. The relation R is represented by the matrix MR = [ ], where The matrix representing R has a 1 as its ( i , j) entry when is related to and a 0 if is not related to .  

5. Properties of Relations

6. Reflexive Relation:- R is reflexive relation if and only if ( x,x ) € R; ∀X € A. In other word:- IA ⊆ R. Irreflexive relation :- R is Irreflexive relation Iff ( x,x ) does not € R ; ∀X € A. In other word:- IA ∩ R = Φ . Symmetric relation:- R is symmetric Iff ( x,y )€ R ( y,x )€ R; ∀X, Y€ A. In other word:- R= R   –1

7. Asymmetric relation:- R is Asymmetric Iff ( x,y )€ R ( y,x ) doesn ’t € R ; ∀ x,y € A In other word:- R ∩ R   –1= Φ . Antisymmetric relation R is Antisymmetric Iff ( x,y ) € R ^ ( y ,x ) € R x = y , ∀ x,y € A. In other word:- R ∩ R   –1 ⊆ IA. Transitive relation :- R is transitive Iff ( x,y ) € R ^ ( y,z ) € R ( x,z ) € A ; ∀ x,y,z € A. In other words:- R is transitive Iff R 2 ⊆ R.

8. REPRESENTATION OF A RELATION DIGRAPH : A directed graph G = (V , E), or digraph, consists of a set V of vertices (or nodes) together with a set E of edges (or arcs). The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge. An edge of the form ( a,a ) is called a loop. ADJACENCY MATRIX : Matrix representation of a relation. MATRIX REPRESENTATION OF A RELATION (MR) : Let A={ , ,……. ,…….. ,……. } R ⊆ A² = A*A. MR= ( mij ) = {1, if ( , ) € R} {0, if ( , ) ∉ R} {also called Bit matrix}.  

9. PROPERTIES OF A RELATION USING ITS MATRIX REPRESENTATION:- Reflexive : A relation is reflexive if every element in the set is related to itself. In other words, for every element 𝑎 in the set, the pair (𝑎,𝑎)is in the relation. Irreflexive : A relation is irreflexive if no element in the set is related to itself. In other words, for every element 𝑎 in the set, the pair (𝑎,𝑎) is not in the relation Symmetric : A relation is symmetric if whenever a is related to 𝑏, then 𝑏 is also related to 𝑎. In other words, if (𝑎,𝑏) is in the relation, then (𝑏,𝑎) is also in the relation. Asymmetric : A relation is asymmetric if whenever 𝑎 is related to 𝑏, 𝑏 is not related to 𝑎. In other words, if (𝑎,𝑏)is in the relation, then (𝑏,𝑎) is not in the relation. Antisymmetric : A relation is antisymmetric if whenever a is related to 𝑏 and 𝑏 is related to 𝑎, then 𝑎 equals 𝑏. In other words, if (𝑎,𝑏) and (𝑏,𝑎) are in the relation, then 𝑎=𝑏. Transitive : A relation is transitive if whenever a is related to 𝑏 and 𝑏 is related to 𝑐, then 𝑎 is related to 𝑐. In other words, if (𝑎,𝑏) and (𝑏,𝑐) are in the relation, then (𝑎,𝑐) is also in the relation.

10. Reflexive relation “ R ” is reflexive iff = 1 , ∀ i   Examples of reflexive relations: Let A={ 1,2,3,4} R={(1,1) , (2,2), (3,3), (4,4), (1,2),(2,1),(2,3),(3,1),(3,2)} MR=

11. 2. Irreflexive relation :- “ R ” is irreflexive iff = 0 , ∀ i   Examples of irreflexive relations: Let A={1,2,3}. R={(1,2),(2,1), (1,3),(2,3),(3,1)}  MR =  

12. Symmetric relation:- R is symmetric iff MR=   Examples of Symmetric relations: Let set A =  {1 , 2 ,3 } R={(1,1),(1,2), (2,1),(1,3),(3,1)}  MR=  

13. 4. Asymmetric relation: - “R ” is asymmetric iff =1⇒ = 0 ; ∀ i ,j   Examples of asymmetric relations : Let A= {1,2,3,4} R={(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(3,4),(4,3} MR=

14. 5. Antisymmetric relation:- “ R” is Anti-Symmetric iff =1 ⇒ = 0 ;∀ i,j [Except form I = J]   Examples of antisymmetric relations:- Let A={1,2,3,4} R={(1,1),(1,2),(1,3),(2,2),(2,3),(2,4)} MR=

15. 6. Transitive relation :- “ R ” is transitive iff 1 & = 1 ⇒ = 1 ; ∀ i ,j,k   Examples of transitive relations: MR = Let A = {1,2,3 }  R={(1,2),(1,3), (2,2),(2,3),(3,3)}   

16. CONCLUSION

17. THANK YOU !!