Discrete Mathematics Multiple Choice Questions on “Graphs – Lattices”.
1. A Poset in which every pair of elements has both a least upper bound and a greatest lower bound is termed as _______
a) sublattice
b) lattice
c) trail
d) walk
Answer: b
Clarification: A poset in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice. A lattice can contain sublattices which are subsets of that lattice.
2. In the poset (Z+, |) (where Z+ is the set of all positive integers and | is the divides relation) are the integers 9 and 351 comparable?
a) comparable
b) not comparable
c) comparable but not determined
d) determined but not comparable
Answer: a
Clarification: The two integers 9 and 351 are comparable since 9|351 i.e, 9 divides 351. But 5 and 127 are not comparable since 5 | 127 i.e 5 does not divide 127.
3. If every two elements of a poset are comparable then the poset is called ________
a) sub ordered poset
b) totally ordered poset
c) sub lattice
d) semigroup
Answer: b
Clarification: A poset (P, <=) is known as totally ordered if every two elements of the poset are comparable. “<=” is called a total order and a totally ordered set is also termed as a chain.
4. ______ and _______ are the two binary operations defined for lattices.
a) Join, meet
b) Addition, subtraction
c) Union, intersection
d) Multiplication, modulo division
Answer: a
Clarification: Join and meet are the binary operations reserved for lattices. The join of two elements is their least upper bound. It is denoted by V, not to be confused with disjunction. The meet of two elements is their greatest lower bound. It is denoted by ∧ and not to be confused with a conjunction.
5. A ________ has a greatest element and a least element which satisfy 0<=a<=1 for every a in the lattice(say, L).
a) semilattice
b) join semilattice
c) meet semilattice
d) bounded lattice
Answer: d
Clarification: A lattice that has additionally a supremum element and an infimum element which satisfy 0<=a<=1, for every an in the lattice is called a bounded lattice. A partially ordered set is a bounded lattice if and only if every finite set (including the empty set) of elements has a join and a meet.
6. A sublattice(say, S) of a lattice(say, L) is a convex sublattice of L if _________
a) x>=z, where x in S implies z in S, for every element x, y in L
b) x=y and y<=z, where x, y in S implies z in S, for every element x, y, z in L
c) x<=y<=z, where x, y in S implies z in S, for every element x, y, z in L
d) x=y and y>=z, where x, y in S implies z in S, for every element x, y, z in L
Answer: c
Clarification: A sublattice S of a lattice L is a convex sublattice of L, if x ≤ z ≤ y and x, y in S implies that z belongs to S, for all elements x, y, z in L.
7. Every poset that is a complete semilattice must always be a _______
a) sublattice
b) complete lattice
c) free lattice
d) partial lattice
Answer: b
Clarification: A poset is called a complete lattice if all its subsets have both a join and a meet. Every complete lattice is a bounded lattice. Every poset that is a complete semilattice must always be a complete lattice.
8. A free semilattice has the _______ property.
a) intersection
b) commutative and associative
c) identity
d) universal
Answer: d
Clarification: Any set X may be used to generate the free semilattice FX. The free semilattice is defined to consist of all of the finite subsets of X with the semilattice operation given by ordinary set union; the free semilattice has the universal property.