[go: up one dir, main page]
Scribd
Upload
48 views9 pages

Discrete Practical 1

The document describes various relations like divides relation, sum relation and equal relation over sets of integers. It defines functions to check properties of relations like reflexive, antisymmetric, transitive and partial order. It also describes functions to find covering relations, Hasse diagram and minimal/maximal elements for a given partial order.

Uploaded by

suhanasuthar01
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
48 views9 pages

Discrete Practical 1

The document describes various relations like divides relation, sum relation and equal relation over sets of integers. It defines functions to check properties of relations like reflexive, antisymmetric, transitive and partial order. It also describes functions to find covering relations, Hasse diagram and minimal/maximal elements for a given partial order.

Uploaded by

suhanasuthar01
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 9

PRACTICAL-1

H*Expressing relations as ordered pairs and creating relations*L

In[163]:= pairQ@8_, _<D := True;


pairQ@___D := False;

relationQ@8___ ? pairQ<D := True;


relationQ@___D := False;

dividesrelation @A : 8___Integer<D := Select@Tuples@A, 2D, Divisible@ð@@2DD, ð@@1DDD &D;


sumrelation@A : 8___Integer<D := Select@Tuples@A, 2D, ð@@2DD + ð@@1DD Š 6 &D;
sumrelation1 @n_IntegerD := Select@Tuples@Range@nD, 2D, ð@@2DD + ð@@1DD Š 10 &D;
dividesrelation1 @n_IntegerD := Select@Tuples@Range@nD, 2D, Divisible@ð@@2DD, ð@@1DDD &D;
inverseRelation @R_ ? relationQD := Reverse@R, 2D;
productRelation @n_IntegerD := Select@Tuples@Range@nD, 2D, ð@@2DD * ð@@1DD Š 10 &D;
equalRelation @n_IntegerD := Select@Tuples@Range@nD, 2D, ð@@1DD Š ð@@2DD &D;

In[174]:= pairQ@81, 2<D

Out[174]= True

In[175]:= pairQ@1D

Out[175]= False

In[179]:= relationQ@881, 2<, 83, 4<<D

Out[179]= True

relationQ@881, 2<, 84<<D


In[180]:=

Out[180]= False

In[181]:= div6 = dividesrelation1 @6D

881, 1<, 81, 2<, 81, 3<, 81, 4<, 81, 5<, 81, 6<,
82, 2<, 82, 4<, 82, 6<, 83, 3<, 83, 6<, 84, 4<, 85, 5<, 86, 6<<
Out[181]=

In[182]:= sum = sumrelation@81, 2, 3, 4<D

Out[182]= 882, 4<, 83, 3<, 84, 2<<

Practical-2

In[18]:= findDomain@R_ ? relationQD := Union@Flatten@R, 1DD

In[19]:= div6

881, 1<, 81, 2<, 81, 3<, 81, 4<, 81, 5<, 81, 6<,
82, 2<, 82, 4<, 82, 6<, 83, 3<, 83, 6<, 84, 4<, 85, 5<, 86, 6<<
Out[19]=
2 kusum discrete practical.nb

In[20]:= Flatten@div6, 1D
Flatten@div6D
Flatten@div6, 0D

Out[20]= 81, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 2, 2, 2, 4, 2, 6, 3, 3, 3, 6, 4, 4, 5, 5, 6, 6<

Out[21]= 81, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 2, 2, 2, 4, 2, 6, 3, 3, 3, 6, 4, 4, 5, 5, 6, 6<

881, 1<, 81, 2<, 81, 3<, 81, 4<, 81, 5<, 81, 6<,
82, 2<, 82, 4<, 82, 6<, 83, 3<, 83, 6<, 84, 4<, 85, 5<, 86, 6<<
Out[22]=

In[23]:= findDomain@div6D

Out[23]= 81, 2, 3, 4, 5, 6<

In[24]:= H*REFLEXIVE RELATION*L


reflexiveQ@R_ ? relationQD := Module@8a, domain<, domain = findDomain@RD;
Catch@Do@If@! MemberQ@R, 8a, a<D, Throw@FalseDD, 8a, domain<D;
Throw@TrueDDD

In[25]:= reflexiveQ@div6D

Out[25]= True

In[26]:= reflexiveQ@sumrelation1 @10DD

Out[26]= False

H*ANTISYMMETRIC RELATION*L
antisymmetricQ @R_ ? relationQD := Module@8u<,
In[27]:=

Catch@Do@If@MemberQ@R, Reverse@uDD && u@@1DD ¹ u@@2DD, Throw@FalseDD, 8u, R<D;


Throw@TrueDDD

In[28]:= antisymmetricQ @div6D

Out[28]= True

In[29]:= antisymmetricQ @sumD

Out[29]= False

In[30]:= H*TRANSITIVE RELATION*L


transitiveQ@R_ ? relationQD := Module@8a, b, c, domain<, domain = findDomain@RD;
Catch@
Do@If@MemberQ@R, 8a, b<D && MemberQ@R, 8b, c<D && ! MemberQ@R, 8a, c<D, Throw@FalseDD,
8a, domain<, 8b, domain<, 8c, domain<D; Throw@TrueDDD

In[31]:= transitiveQ@div6D

Out[31]= True

In[32]:= transitiveQ@sumD

Out[32]= False

H*PARTIAL ORDER*L
partialorderQ @R_ ? relationQD := reflexiveQ@RD && antisymmetricQ @RD && transitiveQ@RD
In[33]:=

In[34]:= partialorderQ @div6D

Out[34]= True

In[35]:= partialorderQ @equalRelation @5DD

Out[35]= True
kusum discrete practical.nb 3

In[36]:= Reverse@882, 83, 5<<, 82, 5<<, 1D

Out[36]= 882, 5<, 82, 83, 5<<<

In[37]:= Reverse@882, 83, 5<<, 82, 5<<, 2D

Out[37]= 8883, 5<, 2<, 85, 2<<

In[38]:= Reverse@882, 83, 5<<, 82, 5<<, 3D

Out[38]= 882, 85, 3<<, 82, 5<<

In[39]:= inverseRelation @R_ ? relationQD := Reverse@R, 2D

PRACTICAL-3

In[102]:= H*FINDING THE FOLLOWING FOR a given poset


1. Covering Relations
2. The corresponding Hasse Diagram
3. Minimal and Maximal Element*L

In[44]:= coverseQ@R_ ? partialorderQ , 8x_, y_<D :=


Module@8z, checkset<, Catch@If@x Š y, Throw@FalseDD;
If@! MemberQ@R, 8x, y<D, Throw@FalseDD;
checkset = Complement@findDomain@RD, 8x, y<D;
Do@If@MemberQ@R, 8x, z<D && MemberQ@R, 8z, y<D,
Throw@FalseDD, 8z, checkset<D; Throw@TrueDDD

In[45]:= coverseQ@div6, 81, 2<D

Out[45]= True

In[46]:= coveringRelation @R_ ? partialorderQ D := Select@R, coverseQ@R, ðD &D

In[47]:= coveringRelation @div6D

Out[47]= 881, 2<, 81, 3<, 81, 5<, 82, 4<, 82, 6<, 83, 6<<

In[48]:= ? Rule

lhs -> rhs or lhs ® rhs represents a rule that transforms lhs to rhs. ‡
4 kusum discrete practical.nb

In[49]:= ? LayeredGraphPlot

LayeredGraphPlotA9vi1 -> v j1 , vi2 -> v j2 , …=E


generates a layered plot of the graph in which vertex vik is connected to vertex v jk .
LayeredGraphPlotA99vi1 -> v j1 , lbl1 =, …=E associates labels lblk with edges in the graph.
LayeredGraphPlot@g, posD places the dominant vertices in the plot at position pos.
LayeredGraphPlot@mD generates a layered plot of the graph represented by the adjacency matrix m. ‡

hasseDiagram @R_ ? partialorderQ D :=


Module@8edges<, edges = coveringRelation @RD . 8a_, b_< ® Rule@b, aD;
In[50]:=

LayeredGraphPlot @edges, VertexLabeling ® TrueDD

In[51]:= hasseDiagram @div6D

4 6

Out[51]= 5 2 3

In[52]:= r2 = 881, 1<, 81, 2<, 81, 3<, 81, 4<, 82, 2<, 82, 3<, 82, 4<, 83, 3<, 83, 4<, 84, 4<<

Out[52]= 881, 1<, 81, 2<, 81, 3<, 81, 4<, 82, 2<, 82, 3<, 82, 4<, 83, 3<, 83, 4<, 84, 4<<
kusum discrete practical.nb 5

In[53]:= hasseDiagram @r2D

Out[53]=

divisorLattice @n_IntegerD := dividesrelation @Divisors@nDD


divisorLattice @30D
In[54]:=

881, 1<, 81, 2<, 81, 3<, 81, 5<, 81, 6<, 81, 10<, 81, 15<, 81, 30<, 82, 2<, 82, 6<,
82, 10<, 82, 30<, 83, 3<, 83, 6<, 83, 15<, 83, 30<, 85, 5<, 85, 10<, 85, 15<,
Out[55]=

85, 30<, 86, 6<, 86, 30<, 810, 10<, 810, 30<, 815, 15<, 815, 30<, 830, 30<<
6 kusum discrete practical.nb

In[56]:= hasseDiagram @divisorLattice @30DD

30

6 10 15

Out[56]=

2 3 5

In[57]:= a = Subsets@81, 2, 3<D

Out[57]= 88<, 81<, 82<, 83<, 81, 2<, 81, 3<, 82, 3<, 81, 2, 3<<

In[58]:= b = Tuples@a, 2D

888<, 8<<, 88<, 81<<, 88<, 82<<, 88<, 83<<, 88<, 81, 2<<, 88<, 81, 3<<, 88<, 82, 3<<,
88<, 81, 2, 3<<, 881<, 8<<, 881<, 81<<, 881<, 82<<, 881<, 83<<, 881<, 81, 2<<,
Out[58]=

881<, 81, 3<<, 881<, 82, 3<<, 881<, 81, 2, 3<<, 882<, 8<<, 882<, 81<<, 882<, 82<<,
882<, 83<<, 882<, 81, 2<<, 882<, 81, 3<<, 882<, 82, 3<<, 882<, 81, 2, 3<<, 883<, 8<<,
883<, 81<<, 883<, 82<<, 883<, 83<<, 883<, 81, 2<<, 883<, 81, 3<<, 883<, 82, 3<<,
883<, 81, 2, 3<<, 881, 2<, 8<<, 881, 2<, 81<<, 881, 2<, 82<<, 881, 2<, 83<<,
881, 2<, 81, 2<<, 881, 2<, 81, 3<<, 881, 2<, 82, 3<<, 881, 2<, 81, 2, 3<<,
881, 3<, 8<<, 881, 3<, 81<<, 881, 3<, 82<<, 881, 3<, 83<<, 881, 3<, 81, 2<<,
881, 3<, 81, 3<<, 881, 3<, 82, 3<<, 881, 3<, 81, 2, 3<<, 882, 3<, 8<<, 882, 3<, 81<<,
882, 3<, 82<<, 882, 3<, 83<<, 882, 3<, 81, 2<<, 882, 3<, 81, 3<<, 882, 3<, 82, 3<<,
882, 3<, 81, 2, 3<<, 881, 2, 3<, 8<<, 881, 2, 3<, 81<<, 881, 2, 3<, 82<<, 881, 2, 3<, 83<<,
881, 2, 3<, 81, 2<<, 881, 2, 3<, 81, 3<<, 881, 2, 3<, 82, 3<<, 881, 2, 3<, 81, 2, 3<<<

In[59]:= minimalElements @R_ ? partialorderQ , S_ListD := Module@8M, s, t<, M = S;


Do@
Do@If@MemberQ@R, 8t, s<D, M = Complement@M, 8s<DD, 8t, Complement@S, 8s<D<D, 8s, S<D; MD
kusum discrete practical.nb 7

minimalElements @div6, 81, 2, 3, 4, 5, 6<D


minimalElements @div6, 82, 3, 4<D
In[60]:=

Out[60]= 81<

Out[61]= 82, 3<

In[62]:= maximalElements @R_ ? partialorderQ , S_ListD := Module@8M, s, t<, M = S;


Do@
Do@If@MemberQ@R, 8s, t<D, M = Complement@M, 8s<DD, 8t, Complement@S, 8s<D<D, 8s, S<D; MD

In[63]:= maximalElements @div6, 81, 2, 3, 4, 5, 6<D

Out[63]= 84, 5, 6<

In[64]:=

PRACTICAL-4

UpperBoundsQ @R_ ? partialorderQ , S_List, u_D := Module@8s<,


Catch@Do@If@! MemberQ@R, 8s, u<D, Throw@FalseDD, 8s, S<D; Throw@TrueDDD

In[66]:= UpperBoundsQ @div6, 81, 2, 3<, 6D

Out[66]= True

In[67]:= UpperBoundsQ @div6, 81, 2, 3, 4<, 6D

Out[67]= False

In[68]:= ? AppendTo

AppendTo@s, elemD appends elem to the value of s, and resets s to the result. ‡

In[69]:= upperbounds@R_ ? partialorderQ , S_ListD := Module@8domR, d, U = 8<<,


domR = findDomain@RD;
Do@If@UpperBoundsQ @R, S, dD, AppendTo@U, dDD, 8d, domR<D; UD

In[70]:= upperbounds@div6, 81, 2<D

Out[70]= 82, 4, 6<

In[71]:= upperbounds@div6, 81, 2, 3<D

Out[71]= 86<

In[72]:= ? If

If@condition, t, f D gives t if condition evaluates to True, and f if it evaluates to False.


If@condition, t, f , uD gives u if condition evaluates to neither True nor False. ‡

In[73]:= leastupperbound @R_ ? partialorderQ , S_ListD := Module@8U, M<,


U = upperbounds@R, SD;
M = minimalElements @R, UD;
If@Length@MD ¹ 1, "LUB does not exist", MDD

In[74]:= leastupperbound @div6, 81, 2<D

Out[74]= 82<
8 kusum discrete practical.nb

In[75]:= leastupperbound @div6, 81, 2, 3<D

Out[75]= 86<

LowerBoundsQ @R_ ? partialorderQ , S_List, l_D := Module@8s<,


Catch@Do@If@! MemberQ@R, 8l, s<D, Throw@FalseDD, 8s, S<D; Throw@TrueDDD
In[76]:=

In[77]:= LowerBoundsQ @div6, 81, 2<, 1D

Out[77]= True

In[78]:= lowerbounds@R_ ? partialorderQ , S_ListD := Module@8domR, s, L = 8<<,


domR = findDomain@RD;
Do@If@LowerBoundsQ @R, S, sD, AppendTo@L, sDD, 8s, domR<D; LD

In[79]:= lowerbounds@div6, 81, 2<D

Out[79]= 81<

In[80]:= lowerbounds@div6, 81, 2, 4<D

Out[80]= 81<

In[81]:= lowerbounds@div6, 83, 6<D

Out[81]= 81, 3<

In[82]:= greatestlowerbound @R_ ? partialorderQ , S_ListD := Module@8L, M<,


L = lowerbounds@R, SD;
M = maximalElements @R, LD;
If@Length@MD ¹ 1, "GUB not exist"D; MD

In[83]:= greatestlowerbound @div6, 81, 2<D

Out[83]= 81<

In[84]:= greatestlowerbound @div6, 83, 6<D

Out[84]= 83<

In[85]:= greatestlowerbound @div6, 83, 4<D

Out[85]= 81<

PRACTICAL-5

In[86]:= hasGlbQ@R_ ? partialorderQ D := Module@8DomR, a, b<,


DomR = findDomain@RD;
Catch@Do@If@greatestlowerbound @R, 8a, b<D === "GUB not exist", Throw@FalseDD,
8a, DomR<, 8b, DomR<D; Throw@TrueDDD

In[87]:= div4 = dividesrelation1 @4D

Out[87]= 881, 1<, 81, 2<, 81, 3<, 81, 4<, 82, 2<, 82, 4<, 83, 3<, 84, 4<<

In[88]:= hasGlbQ@div4D

Out[88]= True
kusum discrete practical.nb 9

In[89]:= hasLubQ@R_ ? partialorderQ D := Module@8DomR, a, b<,


DomR = findDomain@RD;
Catch@Do@If@leastupperbound @R, 8a, b<D === "LUB does not exist", Throw@FalseDD,
8a, DomR<, 8b, DomR<D; Throw@TrueDDD

In[90]:= hasLubQ@div4D

Out[90]= False

In[91]:= latticeQ@R_ ? partialorderQ D := hasGlbQ@RD && hasLubQ@RD

In[92]:= latticeQ@div4D

Out[92]= False

In[93]:= a = Complement@Divisors@60D, 810<D

Out[93]= 81, 2, 3, 4, 5, 6, 12, 15, 20, 30, 60<

In[94]:= dividesrelation @aD

881, 1<, 81, 2<, 81, 3<, 81, 4<, 81, 5<, 81, 6<, 81, 12<, 81, 15<, 81, 20<, 81, 30<,
81, 60<, 82, 2<, 82, 4<, 82, 6<, 82, 12<, 82, 20<, 82, 30<, 82, 60<, 83, 3<, 83, 6<,
Out[94]=

83, 12<, 83, 15<, 83, 30<, 83, 60<, 84, 4<, 84, 12<, 84, 20<, 84, 60<, 85, 5<, 85, 15<,
85, 20<, 85, 30<, 85, 60<, 86, 6<, 86, 12<, 86, 30<, 86, 60<, 812, 12<, 812, 60<,
815, 15<, 815, 30<, 815, 60<, 820, 20<, 820, 60<, 830, 30<, 830, 60<, 860, 60<<

In[95]:= latticeQ@dividesrelation @aDD

Out[95]= False

In[96]:= latticeQ@r2D

Out[96]= True

In[97]:=

In[98]:=

In[99]:=

In[100]:=

You might also like