Relation
between 2 sets:
™
A relation between two sets A and B is a
subset of the Cartesian product AxB; A is called the source set and B is
called the target set.
™
Often, we use notation aRb to denote that (a.b)єR and a~Rb to
denote that (a,b)∉ ..
EXAMPLE:
Let
U={0,1,2,3,4,5,6} represent set with bit strings
a) A= {2,4,5,6}
bit string is 0010111
b) B is the set of all odd integer, B Í U.
B=
{1,3,5} the bit string is 0101010
c) C is a subset of U, containing all integers
greater than 4.
C={5,6}
the bit string is 0000011
COMPLEMENT, UNION, INTERSECTION AND DIFFERENCES OF SETS
} Using bit strings to represent sets, it is
easy to find complement of sets, unions, intersection and differences of sets.
EXAMPLE:
Let U=
{0,1,2,3,4,5,6,7} , A= {1,3,5,6,7} , B= {1,2,3,4,5}. Use bit strings to find
a) ¬A (complement
of A)
A : 01010111
¬A : 10101000
b) A ʌ B (Intersection @ bitwise AND)
A :
01010111
B :
01111100
A ʌ B : 01010100
Therefore A ʌ B={1,3,5}
c) A ᴠ B
(Union @ bitwise OR)
A :
01010111
B :
01111100
A ᴠ B :
01111111
Therefore A ᴠ B={1,2,3,4,5,6,7}
RELATIONS ON SET
A relation on
set A is a relation from A to A. A relation on set A is also a subset of AxA.
EXAMPLE
Let R1 relation
defined as R1 = { (a,b) | a-b is even}; R1 on set X = {1,
2, 3, 4} ordering of X=1, 2, 3, 4.
Solution: This
means that it is a relation on set X containing ordered pairs of elements a and
b such that a-b is an even number.
Hence, R1= { (1,1), (1,3),
(2,2), (2,4), (3,1), (3,3), (4,2), (4,4) }
WAYS OF REPRESENTING RELATIONS
1. Relations using Matrices
-List the elements of set A and B in the particular order
-Create a matrix MR = [mij]
EXAMPLE:
Suppose that
A={1,2,3} and B={1,2} then let R be the relation from A to B containing (a,b)
if a∊A,b∊B and a>b.
what is the matrix representing R if a1=1,a2=2,a3=3,b1=1,b2=2?
Solution
because
R={(2,1),(3,1),(3,2)} the matrix for R is:
2. Relations using Directed Graph (Digraph)
It is used to represent the
relationship between the each element in the relation.
A directed graph consist of:
-A set V of vertices (or nodes)
-A set of edges (or arcs)
-If there is an arrow from a to b, then
(a,b) is in the relation.
EXAMPLE:
Consider our relation R=
{(a,b) | a divides b} on set X = {1, 2, 3, 4} where the universal of discourse
is N.
Solution:
PROPERTIES OF RELATIONS
1. Reflexive
A relation R on a set A is
called reflexive if (a,a) ∈ R for every element a ∈ A
RELATION USING MATRICES
|
If the centre diagonal
is all 1’s, a relation is reflexive.
|
RELATION USING DIRECTED GRAPH
|
A relation is reflexive if every node has a loop.
|
2. Symmetric
The relation is symmetric if (b, a) ∈ R whenever (a, b) ∈ R,
for all a, b ∈ A.
RELATION USING MATRICES
|
Let A={1,2,3,4,5}
*The relation is symmetric, if for every
value, it is the equal to the value in its transposed position.
|
RELATION USING DIRECTED GRAPH
|
If for every edge, there is an edge in other direction, then the
relation is symmetric. (Red arrows)
|
3. ANTISymmetric
For all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b
RELATION USING MATRICES
|
The relation is antisymmetric, if for every
value and the value in
its transposed position
are not both 1.
|
RELATION USING DIRECTED GRAPH
If for every edge, there is not an edge in other direction, then the
relation is antisymmetric.
|
4. Transitive
If a is related to b and b
is related to c, then a is related to c for all (a,b), (b,c) and (a,c)
RELATION USING MATRICES
|
The relation is transitive, if for every spot
(a,b), (b,c) and (a,c)
each have 1.
|
RELATION USING DIRECTED GRAPH
|
If for(1,2)∊ R and
(2,3) ∊ R,
then (1,3) ∊ R is
true, then (1,3) ∊ R.
|
TRY THIS~~~~Describe whether each of the relation is
reflexive, transitive, symmetric or antisymmetric:
R1= {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)}
R2={(1,1),(1,2),(2,1)}
R3={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)}
R4={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)}
R5={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}
R6={(3,4)}
Answer:
R1 is antisymmetric only.
R2 is both symmetric and transitive.
R3 is reflexive, symmetric and transitive.
R4 is antisymmetric only.
R5 is reflexive, antisymmetric, and transitive.
R6 is antisymmetric only.
EQUIVALENCE RELATION VS PARTIAL ORDER RELATION
A relation on a set A is called an equivalence relation if it is reflexive, symmetric,
and transitive.
Two elements a and b that are related by an equivalence relation are called equivalent.
The notation a ∼ b is often used to
denote that a and b are equivalent elements with respect to a particular equivalence relation.
A relation R on a set S is called a partial
ordering or partial order if it is reflexive, antisymmetric, and
transitive. A set S together with a
partial ordering R is called a partially
ordered set, or poset, and is denoted by (S,R). Members of S are called elements
of the poset.
COMPOSITE OF TWO RELATIONS
Let R be a relation
from a set A to a set B and S a relation from B to
a set C. The composite of R and S is the relation
consisting of ordered pairs (a, c), where a ∈ A, c ∈ C, and for which there
exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S. We denote the
composite of R and S by S ◦R. (Shows transitive)
RECURSIVE RELATIONS
Let R be a relation
on the set A. The powers
, n = 1, 2, 3, . . . , are
defined recursively by
No comments:
Post a Comment