Please enable JavaScript.
Coggle requires JavaScript to display documents.
Relations (PROPERTIES OF RELATIONS (Symmetric Relation (Relation R is…
Relations
PROPERTIES OF RELATIONS
Symmetric Relation
Relation R is called a symmetric relation if for every (a, b) ∈ R implies that (b, a) also belong to R.
Asymmetric Relation
Relation R is called an asymmetric relation if for every (a, b) ∈ R implies that (b, a) does not belongs to R.
Irreflexive Relation
Relation R is called irreflexive relation if, for every a in set A, (a, a) ∉ R, i.e., (a, a) ∉ R, ∀ a ∈ A
Transitive Relation
Relation R is called transitive relation if whenever both (a, b) and (b, c) belong to R, implies that (a, c) also belongs to R i.e., (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R
Reflexive Relation
R on a set A. Relation R is called a reflexive relation if, for every a in set A, (a, a) ∈ R, i.e., (a, a) ∈ R, ∀ a ∈ A.
Antisymmetric Relations
Relation R is called antisymmetric relation if (a, b) ∈ R implies that (b, a) ∉ R unless a = b. In other words, we can say if (a, b) and (b, a) belong to R, then a = b.
REPRESENTATION OF RELATIONS
Relation as a Matrix
Let P = {a1, a2, …., am} and Q = {b1, b2, …., bn} are finite sets, containing m and n number of elements respectively. R is a relation from P to Q. The relation R can be represented by m × n matrix M = [Mij], defined as
Relation as a Directed Graph
If P is a finite set and R is a relation on P, R can be represented as a directed graph
Let P = {1, 2, 3, 4}
Relation as an Arrow Diagram
If P and Q are finite sets and R is a relation from P to Q. Relation R can be represented as an arrow diagram
Let P = {1, 2, 3, 4}, Q = {a, b, c, d}
Relation as a Table
CLOSURE PROPERTIES OF RELATIONS
Symmetric Closure
Relation Rs is called the symmetric closure of R if RS is the smallest relation containing R, having the symmetric property. The relation RS = R ∪ R −1 is the smallest symmetric relation containing R
Transitive Closure
The transitive closure R of a relation R is the smallest transitive relation containing R.
Reflexive Closure
Relation RF is called reflexive closure of R if RF is the smallest relation containing R, having the reflexive property i.e., RF = R ∪ Δ where Δ is a diagonal relation
BINARY RELATION
binary relation R is defined to be a subset of P × Q
If (a, b) ∈ R and R ⊆ P × Q then a is related to b by R
Domain of Relation
domain of relation R is the set of elements in P which are related to some element in Q
denoted by DOM (R)
Range of Relation
range of a relation R is the set of elements in Q which are related to some element in P
RAN (R).
COMPLEMENT OF A RELATION
The complement of relation R denoted by is a relation from A to B such that
INVERSE OF A RELATION
The inverse of a relation R, denoted by R−1, is a relation from B to A such that bR−1 a iff aRb
COMPOSITION OF RELATIONS
Consider a relation R1 from A to B and R2 be a relation from B to C. The composition of relation R1 and R2 denoted by R1 ∘ R2, is the relation from A to C and is defined by R1 ∘ R2 = {(a, c): (a, b) ∈ R1 and (b, c) ∈ R2 for some b ∈ B}.
PATH IN RELATIONS
Consider a relation R on set A. A path of length n in R from a to b, is a finite sequence a, Y1, Y2, Y3, ……, Yn − 1, b which begins with a and ends with b
represented by a directed graph
WARSHALL'S ALGORITHM TO FIND TRANSITIVE CLOSURE
Let n be the number of elements in a given set A i.e., n → | A |
Let w0, w1, w2, …., wn be Warshall sets.
To find transitive closure of relation R on A, maximum of n Warshall sets of which wn is the last need to be computed.
The procedure to compute wk from wk−1 is as follows:
Copy 1 to all entries in wk from wk−1, where there is 1 in wk−1.
Find the row numbers p1, p2, p3,………for which there is 1 in column k in wk−1 and the column numbers q1, q2, q3, ……. for which there is 1 in row k in wk−1.
Mark entries in wk as 1 for (pi, qi) of wk if there are not already 1.
Stop when wn is obtained and it is the needed result (transitive closure).
EQUIVALENCE RELATIONS
Relation R is reflexive i.e., aRa ∀ a ∈ A.
Relation R is symmetric i.e., aRb ⇒ bRa.
Relation R is transitive i.e., aRb and bRc ⇒ aRc.
PARTIAL ORDER RELATION
Relation R is reflexive i.e., aRa ∀ a ∈ A.
Relation R is antisymmetric aRb and bRa ⇒ a = b.
Relation R is transitive aRb and bRc ⇒ aR
Partial Order Set (Poset)
et A together with a partially order relation R on the set A and is denoted by (A, R) is called a partially ordered set or POSET.
TOTAL ORDER RELATION
Consider the relation R on the set A. If it is also the case that for all a, b ∈ A, we have either (a, b) ∈ R or (b, a) ∈ R or a = b, then the relation R is called total order relation on set A
PARTITION
A partition (A1, A2, …, Ai) of a non-empty set A is defined as a collection of non-empty subsets of A, such that
Every element of A belongs to one of Ai i.e., the union of Ai is equal to set A.
If Ai and Aj are distinct, then Ai ∩ Aj = φ i.e., the partitions divides the elements of the set A into disjoint subsets.
EQUIVALENCE CLASS
Consider, an equivalence relation R on a set A. The equivalence class of an element a ∈ A, is the set of elements of A to which element a is related. It is denoted by [a]
CIRCULAR RELATION
Consider a binary relation R on a set A. Relation R is called circular if (a, b) ∈ R and (b, c) ∈ R implies (c, a) ∈ R.
