U ni t IV Re la tio ns and Functions
w the Ha ssi diagra m rep resentin g the partia l ord ering
1):- Dra ar
2,3 ,4, 6,8,l2 }. Name :- Dhanashri Gampaw
{(a,b) Ia div ide b}o n {1,
s
for thi s pa rtia l ord er, as sh ow in fig . [Link] ov e all loop,a
Ans:-Begin w it h diagraph pe rty .These
. b.T he n de let e all the ed ge s implied by the trans it ive pro
sh ow n in fig
)(2, 12)a nd (3, 12).
are(1,2),( 1, 6), (1,8 ) (1, 12)(2,8
po int up wo rd, an d de let e all arr ow to obta in th e Hasse
Ar range all edges to
diagram is sh ow n in fig .c.
~ ~ ~~ ~ -+fr -- t----,--, ·_J_
~ ~ ~~ - f i - - t - - ~\--
V/ I
e s -. ;~+ *~- t'- f----i-r -- -- \-
i ~ /,- · I _..1~1- --,
~--_
--- l 3
\~ 1[ /Z
'-,_\/,I/
- - -- 1.
------- --------------------------------------------
--
--------------------------------------------- ----- -----
Que2):- Let R & S be two relation on A=
{l,2,3,4}
R={ (1, 1),( 1,2), (2,3 ), (2,4 ),(3,4 ), (4, 1), (4,2)}
S={(3, 1), (4,4 ), (2,3 ), (2,4 ), (3,4 ), (1, 1), (1,4)}
Compute Ros.
Ans:- Let We have, A={l,2,3,4}
R={( 1, 1), (1,2 ), (2,3 ), (2,4 ),(3 ,4 ), (4, 1), (4,2)}
5={(3, 1), (4,4 )(2,3 )(2,4 ),(3,4 ), (1, 1)( 1,4)}
Since (3, 1) c Sand (1, 1) c R
We must have (3, 1) c Ros.
Simil arly, (4,4) c S & (4,1) € R
(4,1) c Ros
{2,3) € S & (3,4) <:: R
(2,4) <:: Ros
(2,4) € S & (4,1) € R
(2,1) ( Ros
(3,4) c &(1,2) €R
(3, 1) c Ros
(1, 1) € S &(1,2) € R
(1,2) c RoS
(1,4) c S & (4,1) E: R
(1,1) c Ros
RoS={(3, l),(4, 1),(2,4 ), (2, 1),(3, 1),( 1,2)(1, 1)}
Que3):-L et A={2,3,4,6} and Let aRb if a divide b. Show that Risa partial order and
draw it's Hasse diagram.
Ans:-We have the given,
A={2,3,4 ,6}
R={ (2,2 ), (2,4 ), (2,6 ), (3 ,3 ), (3, 6 ), (4,4 ), (6, 6)}
R is reflexive since
(2,2),(3,3),(4,4),(6,6) € R
R is anti symmetric Sin ce
If a I b b Ia unless a=b.
R is t ransitive since
a l band blcimpliesalc.
Hence, R is partial order.
Hasse diagram for R,
Que4):-Function f,g,h are define on a·set x={l,2,3} as
f={( 1,2),(2,3 ), (3 1)}
I
g={ (1,2), (2, 1), (3,3 )}
h={( 1, 1), (2,2), (3, 1)}
Find fog,gof,fogoh,fohog.
Ans:-We have,x={l,2,3}
f={ (1,2), (2,3 ), (3, 1)}
g={ (1,2 ), (2, 1),(3 ,3)}
h={ (1, 1), (2, 2), (3, 1)}
We may depic t f,g,h
Graphically as-
l }fog is depicted as
Hence,
fog={( 1,3 ),(3,1),(2,2)}
2}gof is depticted as
gof={( 1,3 ), (2,2), (3,3)}
vs
3)fogoh=(fog)o h, which ca n be depti cted can be depi cted
r : 1·
fogo h={( 1,3 ), (2,2 ), (3 ,3)}
4)foh og=f o(hog) whic h can be depi cted as
Fo(hog) is
fo hog={( 1,3 ),(2,2), (3,2)}
QueS ) :- Let f(x) = x+2, g(x) = x-2,h(x) = 3x
For x belon gs ti R(x E: R),wh ere Risa set of all real numb er. And find gof & fog.
Ans:- w e have the given
f (x) = x+2, g(x) = x-2
h(x) = 3x
gof(x) = g(f(x)) = g(x+2)
= (x+2}- 2
=x
fog(x) = f(g( x)) = f(x-2)
= (x-2)+2
=x
Que6): Let R= {(l,4), (2,4),(2,5),(2,4),(4, 3),( 5,3),(3,2)} use w arshall' s algo rit hm to
find matrix of t ran sitive closure.
Ans: w e have t he given is R={( 1,4 ),( 2, 1),( 2,5 ),(2,4 ),(4, 3 ),(5,3 ),(3, 2)}
0 0 0 1 0
1 0 0 1 1
0 1 0 0 0
e 0
I
0 1 0 0
I I
\ . I (
0 0 1 0 0
. ) I ( ·'.\., , ;
For k=l,place 1 is already in the position (2,4).
Hence, . l,
Fo r K=2,place 1 in the position (3,1),(3,4),and (3,5).
'· I
0 0 0I 1 Q
"
0 1 0 0 1 1 I
/
= 1 1 0 1 1
0 "' o ,1 0 .o
0 0 1 0 0
Similarly, . r ~
\
1 1 1 1 1
1 0 0 1 1
= 1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
Finaly,
1 . 1 ~ 1 1 . 1
1 1 1 1 l
= 1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
------------------------------------------------------------------- ------------------------------------------
1
R
Que 7) :- Use_Warshall's algori thm to find transi tive closure of the realation
whose dig is shown below .
Ans: - We have to find a relation Ron above graph
• 0
R={ (a, b ),(b ,a), (b,c),( c,cf):(c,a ),{ d,c)}
0 0 1
- - 1 0 1 0
1 0 0 1
0 0 1 0
Now,
K=l,
Column 1 has the 1' sat lo~ati~rn (?,3).
Row 1 has the l's at location 4.
We have to add the order pair (2,4),(3,4)
0 0 0 1
= 1 0 1 0
1 0 0 1
0 0 1 0
• I
For K=2,
Column 2 has the 1· s at location nothing.
Row 2 has the l 's at location (1,3).
We have nothing to add the order pair
0 0 0 1
= 0 1 0
1 0 ·. _o,. .. _1
'
0 0 i1
1, 0
I
For K=3, Column 3 has the 1' sat location (2,4}.
Row 3 has the l's at location (1,4).
We have to add the order pair (2,1),(2,4),(4,1),(4,4)
0 0 I o. 1
= 0 1 .1
1 0 0 1
1 0 . ,. 1 1
For K=4 j( -
Column 4 has the i's at locatjon 1,2,3,4.
Row 4 ha s the l's at location 1,3,4.
C
We have to add the order pair
(1, 1),( 1,3 ),( 1,4 ),(2, 1 ), (2,3 ), (2,4 ),(3, 1 ), (3 ,3 ), {3 ,4 ), (4, 1), (4,3 ),( 4,4)
1 0 1 1
= 0 1 1 =
1 0 1 1
1 0 1 1
1 0 1·, 1I , . 1 - I
= 1 0 1 1 =
1 0 1 I
1 -'
1 0 1 1
= transitiv e closure of R.
Therefo re,
l = {(1, 1),( 1,3 ),( 1,4 ),(2, 1),(2,3 ),(2,4 ), (3, 1), {3,3 ),(3 ,4 ),(4, 1), (4,3 ), (4,4)}
------------------------------------------------------------------------------------------------------------
Que 8):- Given a relation_R= {(2,3),(2,1),(3,2),(4,3)} on A={l,2,3 ,4}.
Find a transitiv e closure of R by ~[Link]'s algorith m.
,, .
I I
Ans:- We have,
A={l,2,3,4}
R={(2,3 )(2, 1), (3 ,2),(4,3 )}
0 0 0 0
= 1 0 1 0
0 1 0 0
0 0 1 0
Now,
K=l
Column 1 has the 1· s at location 2.
Row 1 has the 1 ' s at location nothing.
We have nothing to add the order pair.
0 0 0 0
= 0 1 0
0 1 0 0
0 0 1 0
For K=2
Colu mn 2 has t he 1· sat location 3.
Row 2 ha s the 1 'sat location (1,3). ·
We have t o add the order pa ir (3,1),( 3,3).
I
I =
0
0
0
1
0
0
0
1 1 1 0
0 0 1 0
For K=3
Colu mn 3 has the 1· s at locat ion 2,3,4.
Row 3 has the l's at locat ion 1,2,3. ~
,2)(3,3),(4,1),(4,2),(4,3).
We have to add the orde r :pair(2,1) (2,2),(2,3},(3,1),(3
0 0 0 0
= 1 1 0
1 1 1 0
1 1 , r -- .1 _ ~ 0
For K=4
Column 4 has the 1' sat locat ion nothing.I, -.
I) I- I ', ,
Row 4 has the l's at location 1,2,3 .
We have nothing to add the order pair.
0 0 - 0 0
= 1 1 0 =
1 1 1 0,
1 1 1 0
0 0 0 0
= 1 1 0 =
1 1 1 0
1 1 1 0
=trans itive closure of R.
t)
There fore,
={ (2, 1),(2,2), (2,3 )(3, 1),(3 ,2),(3 ,3 ), (4, 1 ), (4,2 ),(4,3)}
--- ----------------------------------------------------------------------------- --------------
itself is one-
Que9) :- Deter mine wheth er ·each of these functi on from {a,b,c,d} to
to- one .
to only one
Ans:- A functi on f(x) =y is one-to -one if ea ch value in doma in(x)m aps
L
value in the range(y).
A functi on f is one-to -one if f(x)i:f(y)
When ever xjy
f(a)i:f(b)
f(a)t:f(c)
f( a ):if( d)
f(b)i:f(c)
f(b)=#(d)
f(c)i:f(d) Thus, functi on is one-to -one .