Lattices

P P Savani University

November 13, 2022

(P P Savani University) Lattices November 13, 2022 1 / 27

 Lattice

Definition of Lattice

(P P Savani University) Lattices November 13, 2022 2 / 27

 Lattice

Lattice
Definition of Lattices
A partially ordered set (poset) in which every pair of elements has both a least
upper bound and a greatest lower bound is called a lattice.
In this case we denote
x ∨ y = lub{x, y} (read as join of x and y) ⊕ or +
x ∧ y = glb{x, y} (read as meet of x and y) ∗ or ·

Lattices have many special properties. Furthermore, lattices are used in many
different applications such as models of information flow and play an important role
in Boolean algebra.
(P P Savani University) Lattices November 13, 2022 3 / 27
 Lattice

f f h

e d e e f g

c d

b b c b c d

a a a

(a) (b) (c)

Hasse Diagrams of Three Posets.
FIGURE 8 Hasse Diagrams of Three Posets.
▶ The posets represented by the Hasse diagrams in (a) and (c) are both lattices.
▶ Hasse diagram shown in (b) is not a lattice.
(P P Savani University) Lattices November 13, 2022 4 / 27
 Lattice

Example: Is the poset (Z+ , |) a lattice?

Solution: Let a and b be two positive integers. The least upper bound and greatest
lower bound of these two integers are the least common multiple and the greatest
common divisor of these integers, respectively. So, It follows that this poset is a
lattice. ◀
Example: Determine whether the posets ({1, 2, 3, 4, 5}, |) and ({1, 2, 4, 8, 16}, |) are
lattices.
Solution: Because 2 and 3 have no upper bounds in ({1, 2, 3, 4, 5}, |), they certainly
do not have a least upper bound. Hence, the first poset is not a lattice.
Every two elements of the second poset have both a least upper bound and a greatest
lower bound. The least upper bound of two elements in this poset is the larger of the
elements and the greatest lower bound of two elements is the smaller of the elements.
Hence, this second poset is a lattice. ◀
(P P Savani University) Lattices November 13, 2022 5 / 27
 Lattice

Example:

(a) (b) (c)

(a) and (b) are lattices while (c) is not lattice.

(P P Savani University) Lattices November 13, 2022 6 / 27

 Lattice

Properties of a Lattice
▶ Idempotency
a) a ∨ a = a b) a ∧ a = a
▶ Commutativity
a) a ∨ b = b ∨ a b) a ∧ b = b ∧ a
▶ Associativity
a) a∨(b∨c) = (a∨b)∨c b) a∧(b∧c) = (a∧b)∧c
▶ Absorption
a) a ∨ (a ∧ b) = a b) a ∧ (a ∨ b) = a
Note: ∨ = ⊕ and ∧ = ∗
(P P Savani University) Lattices November 13, 2022 7 / 27
 Lattice

Lattice as an Algebraic System

By an algebraic system, we mean a set together with a few rules for combining
elements of the set to form other elements of the set.
We had introduced lattices as partial ordered sets in which for each a, b ∈ A,

lub(a, b) = a ∨ b; glb(a, b) = a ∧ b

exists in the set.

Thus any lattice can be viewed as an algebraic system and hence one can apply many
concepts associated with algebraic system to lattices.

(P P Savani University) Lattices November 13, 2022 8 / 27

 Lattice Sublattice

Sublattices
Sublattices
A non empty subset L′ of a lattice L is called a sub lattice of L if

a, b ∈ L′ ⇒ a ∨ b, a ∧ b ∈ L′

i.e. the algebra (L′ , ∨, ∧) is a sub lattice of (L, ∧, ∨) iff L′ is closed under both
operation ∧ and ∨.

From the definition it follows that a sub lattice itself is a lattice and every singleton
of a lattice L is a sublattice of L. However, any subset of L, which is a lattice need
not be sublattice.
(P P Savani University) Lattices November 13, 2022 9 / 27
 Lattice Sublattice

Example: If S be a set and L = (P(S), ∩, ∪). Then only those sub collections of
P(S) are sublattices of L which are closed under ∩ and ∪. If S = {a, b, c, d}, then
{∅, {a}, {a, c}, {c}, {a, b, c}} would be sublatice but {∅, {a}, {b}, {c}, {b, c}} would not
form a sublattice as {a} ∪ {c} = {a, c} is not there. ◀

(P P Savani University) Lattices November 13, 2022 10 / 27

 Lattice Sublattice

Example: Show that with an example that the union of two sub lattice may not be
a sub lattice.
Solution: Consider the lattice L = {1, 2, 3, 4, 6, 12} of factors of 12 under divisibility.
Then S = {1, 2} and T = {1, 3} are sub lattices of L. But the union of S and T
i.e., S ∪ T = {1, 2, 3} is not a sub lattice since 2, 3 ∈ S ∪ T but 2 ∨ 3 = 6 ∈/ S ∪ T .◀

(P P Savani University) Lattices November 13, 2022 11 / 27

 Lattice Sublattice

Example: Let Dn denote the set of all positive divisors of n. Draw the Hasse
diagram and find at least 3 sub lattice for L if L = D30 = {1, 2, 3, 5, 6, 10, 15, 30}.
Solution: D6 = {1, 2, 3, 6}, D10 = {1, 2, 5, 10}, D15 = {1, 3, 5, 15}
30

10 15
6
5
2 3

1 ◀
In general if m|n then Dm is sub lattice of Dn . Also all the multiples of m in Dn
form sub lattice.
(P P Savani University) Lattices November 13, 2022 12 / 27
 Types of Lattices Bounded Lattice

Some Special Lattices

Complete Lattice
A lattice is called complete if each of its non empty subset has a least upper
bound and a greatest lower bound.

Clearly, every finite lattice is complete because every subset here is finite. Also every
complete lattice must have a least element and a greatest element. The least and
greatest elements of a lattice are called bounds (units, universal bounds) of the
lattice and denoted by 0 and 1 respectively.
Bounded Lattice
A lattice which has both elements 0 and 1 is called a bounded lattice.
(P P Savani University) Lattices November 13, 2022 13 / 27
 Types of Lattices Bounded Lattice

1 Every finite lattice (L, ∨, ∧) with Ln = {a1 , a2 , · · · , an } is bounded. Here

∧ni=0 ai = 0 and ∨ni=0 ai = 1.
2 (P(S), ∪, ∩) is bounded with ∅ = 0 and S = 1.
3 The lattice Z + under partial order of divisibility is not bounded since it has a
least element 1 but no greatest elements.
4 The lattice Z (set of all integers) under the partial order ≤ is not bounded
since it has neither greatest nor a least element.
In a bounded lattice, the bounds 0 and 1 clearly satisfy:
0 ∧ a = 0 for all a∈ L
0 ∨ a = a for all a∈ L
1 ∧ a = a for all a∈ L
1 ∨ a = 1 for all a∈ L
(P P Savani University) Lattices November 13, 2022 14 / 27
 Types of Lattices Bounded Lattice

In bounded lattice, a complement of an element can be defined in

the following manner.

In a bounded lattice (L, ∨, ∧, 0, 1), an element b ∈ L, is called a complement

of an element a ∈ L
a ∧ b = 0 and a ∨ b = 1
where 0 and 1 are lower and upper bound of L.

1 The definition of a complement is symmetric in a and b, so that b is

complement of a if a is a complement in b.
2 Any element a ∈ L may or may not have a complement.
3 An element a ∈ L may have more than one complement in L, so complements
are not unique.
(P P Savani University) Lattices November 13, 2022 15 / 27
 Types of Lattices Bounded Lattice

In any bounded lattice, the bounds 0 and 1 are unique complements of each other
because
0 ∨ 1 = 1 and 0 ∧ 1 = 0

a1 a2

In figure complement of a1 is a2 since a1 ∧ a2 = 0 and a1 ∨ a2 = 1.

(P P Savani University) Lattices November 13, 2022 16 / 27

 Types of Lattices Bounded Lattice

a1

a3

a2

In figure both a1 and a2 are complements of a3 since a1 ∧ a3 = 0, a2 ∧ a3 = 0 and

a1 ∨ a3 = 1, a2 ∨ a3 = 1 and so here complements are not unique.

(P P Savani University) Lattices November 13, 2022 17 / 27

 Types of Lattices Complemented Lattice

Complemented Lattice
A lattice L is called complemented lattice if it is bounded and if every
element in L has a complement.

(P P Savani University) Lattices November 13, 2022 18 / 27

 Types of Lattices Complemented Lattice

Example: Show that the lattice (L3 , ⪯3 ) of 3 tuples of 0 and 1 is complemented.

Solution: The hasse-diagram of the lattice (L3 , ⪯3 ) is show in fig
111

110 011
101
010
100 001

000

The bounds of the lattice are (0, 0, 0) and (1, 1, 1). This is a complemented lattice in
which every element has unique complement. The complement of (1, 0, 1) is (0, 1, 0).
This lattice is also denoted by B3 .
(P P Savani University) Lattices November 13, 2022 19 / 27
 Types of Lattices Complemented Lattice

In general, the lattice (Ln , ⪯n ) is a complemented lattice. The complement of an

element of Ln can be obtained by interchanging 1 by 0 and 0 by 1.

(P P Savani University) Lattices November 13, 2022 20 / 27

 Types of Lattices Distributive Lattice

Distributive Lattice
A lattice (L, ∨, ∧) is called a distributive lattice if for any a, b, c ∈ L

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

▶ L = (P(S), ∪, ∩) is distributive lattice, since the distributive laws for ∪ over ∩

and ∩ over ∪ are well known facts of set theory.

(P P Savani University) Lattices November 13, 2022 21 / 27

 Types of Lattices Distributive Lattice

Example: Show that the lattices given in the following diagrams are not distributive.

1 a1

a3
b1 b2 b3
a2

0 0

(a) (b)

(P P Savani University) Lattices November 13, 2022 22 / 27

 Types of Lattices Modular Lattice

Modular Lattice
A lattice (L, ⪯) is said to be modular if a ∨ (b ∧ c) = (a ∨ b) ∧ c when ever a ⪯ c
for all a, b, c ∈ L.

▶ Every distributive lattice is modular. However, the converse is not true.

(P P Savani University) Lattices November 13, 2022 23 / 27

 Types of Lattices Modular Lattice

Example: Prove that the lattice given by the following diagram is modular.

b1 b2 b3

(P P Savani University) Lattices November 13, 2022 24 / 27

 Types of Lattices Modular Lattice

Finite Boolean Algebra

A complemented, distributive lattice is called a Boolean lattice. An algebraic
system defined on Boolean lattices is known as Boolean algebra. A Boolean
algebra will generally be denoted by (B, ⊕, ∗,′ , 0, 1).
A bounded, complemented and distributive lattice is known as Finite Boolean
algebra.

(P P Savani University) Lattices November 13, 2022 25 / 27

 Types of Lattices Modular Lattice

Example: Show that D30 is finite Boolean algebra under partial order of divisibility.

(P P Savani University) Lattices November 13, 2022 26 / 27

 Types of Lattices Modular Lattice

τ ℏαnk Ψϕu !!

(P P Savani University) Lattices November 13, 2022 27 / 27