GATE 2017 CS (CS2) – Question 31

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 1 mark · Numerical answer

X={a,b,c,d,e} has partial order R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}, with Hasse diagram shown. How many ordered pairs must minimally be added to make it a lattice?

Diagram for GATE 2017 CS (CS2) question 31

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: -0.01 to 0.01

Explanation

The diagram is the pentagon lattice N₅. The chain a<b<c<e coexists with a<d<e. Comparable pairs already have meet/join. For incomparable d,b and d,c, the meet is a and join is e. Thus every pair already has both, and zero added pairs are required.

More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions

GATE 2010 CS (CS1) Q13 – How many reflexive relations exist on a five-element set?
GATE 2015 CS (CS2) Q12 – Find the cardinality of the power set of 0,1,2,…,10.
GATE 2015 CS (CS2) Q13 – On positive integers, aRb iff a≠b and a,b have a common divisor greater than one. Which…
GATE 2015 CS (CS3) Q12 – U is the power set of S=1,2,3,4,5,6. T is cardinality, T′ complement in S, and T∖R set…
GATE 2015 CS (CS3) Q60 – On ordered pairs of positive integers, ((p,q),(r,s))∈R iff p−s=q−r. Which describes R?
GATE 2021 CS (CS2) Q21 – For n≥2, S1 contains all n×n matrices over a,b,c, and S2 contains all functions from…

All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →