Discrete Structure and Theory of Logic
(BCS 303)
Poset & Lattices
By
Ms. Vibha Srivastava
Assistant Professor Department of CSE
1
Partial Ordering
A relation 𝑹 on a set 𝑨 is called a
partial ordering or partial order relation,
if 𝑹 is reflexive, anti symmetric and
transitive.
(i.e) 𝑹 is a partial order relation on 𝑨 if it has
the following three properties.
• 𝐚𝐑𝐚 for every 𝐚 ∈ 𝐀
• 𝐚𝐑𝐛 and 𝐛𝐑𝐚 ⟹ 𝐚 = 𝐛
• 𝐚𝐑𝐛 and 𝐛𝐑𝐜 ⟹ 𝐚𝐑𝐜
Poset
A set 𝑨 together with a partial
order relation 𝑹 is called a partially
ordered set or poset.
Example :
The greater than or equal to ≥ relation
is a partial ordering on the set of integers
𝒁,
Since
𝒂 𝒂 ≥ 𝒂 forevery integer
𝒂
(i.e) ≥ is reflexive.
𝒃 𝒂 ≥ 𝒃 and𝒃 ≥ 𝒂 ⟹ 𝒂
=𝒃
(i.e) ≥ is anti
symmetric
𝒄 𝒂 ≥ 𝒃 and𝒃 ≥ 𝒄 ⟹ 𝒂
≥𝒄
1. Show that 𝑵,≤ is a partially ordered
set where 𝑵 is set of all positive integers and
≤ is defined by 𝒎 ≤ 𝒏 iff 𝒏 − 𝒎 is a non-
negative integer.
Solution :
To prove 𝑵 , ≤ is a partially ordered
set, we have
relation ≤
to prove
symmetric andthe transitive. is reflexive,
(i) As 𝒂 − 𝒂 = 𝟎 which is a non-negative
anti
integer,
𝒂 ≤𝒂
Therefore, ≤ is a reflexive.
(ii)Assume 𝒂 ≤ 𝒃 and𝒃 ≤ 𝒂
𝒃 − 𝒂 ≥ 𝟎 and𝒂
− 𝒃≥ 𝟎
This is possible only if 𝒃 − 𝒂 = 𝟎 = 𝒂
−𝒃
Therefore, 𝒂 = 𝒃
(i.e) ≤ is anti symmetric.
(iii)Assume 𝒂 ≤ 𝒃 ,𝒃
≤𝒄
𝒄− 𝒂≥ 𝟎
𝒂 ≤𝒄
(i.e) 𝒂 ≤ 𝒃 ,𝒃 ≤ 𝒄
⟹ 𝒂 ≤𝒄
Therefore, ≤ is
transitive.
Hence, 𝑵 , ≤ is a
partially
ordered set.
2. If 𝑹 isthe relation on the set of integers such
that 𝒂 , 𝒃 ∈ 𝑹 if and only if 𝒃 = 𝒂𝒎
for some positive integer 𝒎 , show that 𝑹
is a partial ordering.
Solution :
(i) As 𝒂 = 𝒂𝟏
𝒂,𝒂 ∈𝑹
Therefore, 𝑹 is reflexive.
∈ 𝑹 and 𝒃 , 𝒂 ∈ 𝑹
𝒂,𝒃
(ii) Assume
and 𝒂 = 𝒃𝒏 , where 𝒎 and
𝒃 𝒏
= 𝒂𝒎
Then
are positive integers.
𝒂 𝒂𝒎
= 𝒏
𝒂 = 𝒂𝒎𝒏
𝒎𝒏=𝟏
𝒎 = 𝟏 and 𝒏=
𝟏
(i.e)
Therefore, 𝒂 = 𝒃
∈ 𝑹 and 𝒃 , 𝒄
𝒂,𝒃 ∈𝑹
(iii) Assume
𝒎 and 𝒏 are
𝒃 = and 𝒄 = 𝒃𝒏 where
𝒂𝒎
Then
𝒄
positive integers.
𝒄 = 𝒂 𝒃𝒏
𝒎
= 𝒏
𝒄= 𝒂𝒎𝒏
𝒄= 𝒂𝒌 where 𝒌 is a positive integer.
⟹ 𝒂,𝒄∈ 𝑹
Therefore, 𝑹 is transitive.
As 𝑹 is reflexive, anti symmetric and transitive,
𝑹
is a partial order relation.
3. Let 𝑹 be a relation on a set 𝑨. Then define
𝑹−𝟏 = 𝒂 , 𝒃 ∈ 𝑨 × 𝑨/ 𝒃 , 𝒂∈ 𝑹 .
Prove that if
𝑨 , 𝑹 is poset then 𝑨 , 𝑹−𝟏 is also a
poset.
Solution :
Given 𝑹 is a partial order relation.
(i) 𝑹 is reflexive ⟹ 𝒂 , 𝒂 ∈ 𝑹
⟹
its inverse 𝒂 , 𝒂 ∈ 𝑹−𝟏
is reflexive.
𝑹−𝟏 𝒂 , 𝒃 ∈ 𝑹−𝟏 and
Then
∈
𝒃,𝒂
(ii)
Their inverse 𝒃 , 𝒂∈ 𝑹 𝑹−𝟏and 𝒂 , 𝒃
∈𝑹
Since 𝑹 isanti symmetric, 𝒂
=𝒃
⟹ 𝑹−𝟏 is also−𝟏anti symmetric.
(iii) 𝒂 , 𝒃∈ 𝑹 ∈
𝒃 , 𝒄 ∈ 𝑹𝑹 ∈𝑹
−𝟏
and
𝒃,𝒂 𝒄,𝒃
Their inverses and
𝒃,𝒂 ∈
Since 𝑹 istransitive 𝒄,𝒃 ∈𝑹 𝑹
⟹ 𝒄 , 𝒂∈ 𝑹
and
∈
𝒂,𝒄
Therefore, its inverse
𝑹−𝟏
𝑹−𝟏
(i.e) is transitive.
𝑨 , 𝑹−𝟏 is also a poset.
Hence
Hasse Diagrams for Partial Orderings
The simplified form of the digraph of a partial
ordering on a finite set that contains
sufficient information about the partial
ordering is called a Hasse diagram.
The Hasse diagram representing a partial
ordering can be obtained from its digraph by
removing all the loops, by removing all edges
that are present due to transitivity and by
drawing each edge without arrow so that
its initial vertex is below its terminal
vertex.
1. Draw the Hasse diagram for 𝑷 = 𝟐 , 𝟑 , 𝟔 , 𝟏𝟐
, 𝟐𝟒
and ≤ is a relation such that 𝒙 ≤ 𝒚 if and only if
𝒙|𝒚 .
Solution : The Hasse diagram for 𝑷 = 𝟐 , 𝟑 , 𝟔 , 𝟏𝟐 ,
𝟐𝟒
is given by
24
12
2 3
2 . Draw the Hasse diagram for 𝑷 = 𝟏 , 𝟐 , 𝟑 ,
𝟒 , 𝟔 , 𝟏𝟐
and ≤ is a relation such that 𝒙 ≤ 𝒚 if and only
if
𝒙|𝒚 .
Solution :
The Hasse diagram for 𝑷 𝟏 , 𝟐 , 𝟑 , 𝟒 , 𝟔 , 𝟏𝟐
= 12 is given
by
4 6
2 3
1
3 . Draw the Hasse diagram of 𝑺𝟐𝟒 , | where
𝑺𝟐𝟒
denotes the set of positive divisors of 𝟐𝟒 and
| denotes the relation “division”.
Solution :
𝑺𝟐𝟒 = 𝟏 , 𝟐 , 𝟑 , 𝟒 , 𝟔 , 𝟖 , 𝟏𝟐 , 𝟐𝟒
The Hasse diagram for 𝑺𝟐𝟒 , | is given by
24
8 12
4 6
2 3
1
4. Obtain the Hasse diagram of 𝑷 , ⊆ where
𝑨𝟑
𝑨𝟑 = 𝟏,𝟐,𝟑 .
Solution :
Given 𝑨𝟑 𝟏,𝟐,
= 𝟑
𝑷 𝑨∅
= 𝟑 , 𝟏 , 𝟐 , 𝟑 , , 𝟏 , 𝟑, 𝟐 , 𝟑, 𝟏 , 𝟐
𝟏,𝟐 ,𝟑
The Hasse diagram of 𝑷 𝑨𝟑 , ⊆ is given by
{1,2,3}
{ 1 ,2 { 1, { 2,
} 3} 3}
{1 {2 {3
} } }
{φ
}
Greatest Member :
If there exists an element 𝒂 ∈ 𝑷
such that 𝒃 ≤ 𝒂 for all 𝒃 ∈ 𝑷, then 𝒂 is
called the greatest member of the poset
𝑷,≤ .
Least Member :
𝒂∈𝑷
If there exists an element
such that
𝐚 ≤ 𝒃 for all 𝒃 ∈ 𝑷, then 𝒂 is
called the least
Maximal Member :
When 𝑷,≤ is a poset, an element 𝒂
∈ 𝑷 is called a maximal member of 𝑷, if
there is no element 𝒃 ∈ 𝑷 such that 𝒂 < 𝒃.
Minimal Member :
When 𝑷 , ≤ is a poset, an element 𝒂
∈ 𝑷 is called a minimal member of 𝑷, if
there is no element 𝒃 ∈ 𝑷 such that 𝐛 < 𝒂.
Note :
1. The maximal, minimal, the
least greatest and member of
a
identified posetcan
using be
the Hasse easily
diagram of the
poset. They are the top and bottom
element in the diagram.
2. A poset can have more than one maximal
member and more than one minimal
member whereas the greatest and least
member, when they exist, are unique.
Upper Bound :
When 𝑨 isa subset of a poset 𝑷 , ≤ and if 𝒖 is
an element of 𝑷 such that 𝒂 ≤ 𝒖 for all
elements 𝒂∈𝑨, then called an upper
𝒖 is bound of 𝑨.
Lower Bound :
When 𝑨 is a subset of a 𝑷 , ≤ and if 𝐥
an element of 𝑷 such that
poset is
elements 𝒂 ∈ 𝑨, then 𝐥 is 𝐥 ≤ 𝒂 for all
called of 𝑨. a lower
bound
Least Upper Bound
The element 𝒙 is least
bound (LUB) called the or upper the
𝑷 , ≤,supremum 𝑨
𝒙
of a poset if is ansubset
that is less ofupper
of 𝑨.
than every
bound other
upper bound
Greatest Lower Bound
The element 𝐲 is called the greatest
lower bound (GLB) or infimum of the
subset 𝑨 of a poset 𝑷 , ≤ , if 𝐲 is a lower
bound that is greater than every other lower
bound of 𝑨.
Lattices
A partially ordered set 𝑳 , ≤ in
which every pair of elements has a least
upper bound and a greatest lower bound is
called a lattice.
The 𝑳𝑼𝑩 ofa 𝒂, 𝒃
⊆ 𝑳 is
subset
denoted by
𝒂∨𝒃 or 𝒂⊕𝒃 or 𝒂 + 𝒃 or 𝒂𝖴
𝒃 and is called the join or sum
of 𝒂 and 𝒃.
The 𝐆𝐋𝐁 ofa 𝒂, 𝒃
⊆ 𝑳 is
subset
denoted by
𝒂𝖠𝒃 or 𝒂 ∗ 𝒃 or 𝒂 ⋅ 𝒃 or 𝒂∩𝒃
and is called the meet or product
1. Draw the Hasse diagram representing the
;𝑨
𝑺 = 𝒂 , 𝒃⊆, 𝒄
𝑩 .
partial ordering on the power set
𝑨𝑺
𝑷 , 𝑩 where the
Find maximal,
minimal, greatest and least elements of the poset.
Solution :
Given 𝑺 𝒂,
= 𝒃,𝒄
𝑷𝑺
= ∅ , 𝒂 , 𝒃 , 𝒄, 𝒂,𝒃 , 𝒂,𝒄 , 𝒃,𝒄
, 𝒂,𝒃,𝒄
The Hasse diagram is given by
{a,b,c}
{a,b} {a,c} {b,c}
{a} {b} {c}
{φ}
1. The element 𝒂 , 𝒃 , 𝒄 does not
precede any element of the poset and
hence it is the only maximal element of
the poset.
2. The element ∅ does not succeed
any element of the poset and hence it is
the only minimal element.
3. All the elements of the poset
are related to 𝒂,𝒃,𝒄
and precede it. Hence
𝒂 , 𝒃 , 𝒄 is the greatest element
of the
4. All theelements
poset.
of the poset are related
to ∅ and succeed it. Hence ∅ is
the least element of the poset.
[Link] 𝑫𝟑𝟎 = 𝟏,𝟐,𝟑,𝟓,𝟔,
𝟏𝟎 , 𝟏𝟓 , 𝟑𝟎 and the relation 𝑹 be
divisor on 𝑫𝟑𝟎. Find
(i) all the lower bounds of 𝟏𝟎 and 𝟏𝟓.
(ii) the 𝒈𝒍𝒃 of 𝟏𝟎 and 𝟏𝟓.
(iii) all upper bounds of 𝟏𝟎 and 𝟏𝟓.
(iv) the 𝒍𝒖𝒃 of 𝟏𝟎 and 𝟏𝟓.
(v) Draw the Hasse diagram.
Solution :
Given 𝑫𝟑𝟎 = 𝟏 , 𝟐 , 𝟑 , 𝟓 , 𝟔 ,
𝟏𝟎 , 𝟏𝟓 , 𝟑𝟎
The Hasse diagram is given by
30
6 10 15
2 3 5
1
bounds of 𝟏𝟎 and 𝟏𝟓
are 𝟏
(i) All the lower
and 𝟓.
(ii) The 𝒈𝒍𝒃 of 𝟏𝟎 and 𝟏𝟓 is𝟓.
bounds of 𝟏𝟎 and 𝟏𝟓 is
𝟑𝟎.
(iii) All the upper
(iv) The 𝒍𝒖𝒃 of 𝟏𝟎 and 𝟏𝟓 is 𝟑𝟎.
3. Determine whether the poset
represented by the Hasse diagram given
below are lattices.
f
c d
a
Solution :
The poset represented by the Hasse
diagram is a lattice, since every pair of
elements of this poset have both least
upper bound and greatest lower bound.
Lattice as Algebraic System
𝑳 ,∨
with t wo binary operations ∨ and ,𝖠
A lattice is an algebraic system
𝖠 associative
𝑳
on
which satisfy the commutative,
and absorption law.
Commutative Law :
For any 𝒂 , 𝒃 ∈ 𝑳, we have
(i) 𝒂 ∨ 𝒃 = 𝒃 ∨ 𝒂
(ii)𝒂 𝖠 𝒃 = 𝒃 𝖠 𝒂
Associative Law :
For any 𝒂 , 𝒃 , 𝒄 ∈ 𝑳,
(i) 𝒂 𝒃 ∨ 𝒄 = 𝒂
we have
∨ ∨𝒃 ∨𝒄
(ii)
𝒂𝖠 𝒃𝖠𝒄 =
𝒂𝖠𝒃
Absorption Law 𝖠
: 𝒄
For any 𝒂 , 𝒃 ∈ 𝑳, we
(i) 𝒂 ∨ 𝒂 𝖠 𝒃
have
=𝒂
(ii)
𝒂𝖠 𝒂∨𝒃
If 𝒂 , 𝒃 are not related (non
comparable)
avb
a b
𝒂𝖠𝒃 𝒂 ≤𝒂∨
a^b
≤𝒂 𝒃
𝒂 𝖠𝒃 ≤𝒃 𝒃≤𝒂
∨𝒃
Also 𝒂 𝖠 𝒃 ≤𝒂
≤𝒂 ∨𝒃
𝒂 𝖠𝒃
≤𝒃 ≤ 𝒂∨ 𝒃
If 𝒂 , 𝒃 are related
(comparable)
b
Then, 𝒂 ∗ 𝒃 =
among𝒂 , 𝒃
smaller
𝒂 𝒃 = larger
among 𝒂,𝒃
4. Let 𝑳,≤ be a lattice. For any 𝒂, 𝒃 ∈ 𝑳,
prove that 𝒂 ≤ 𝒃 ⟺ 𝒂 ∗ 𝒃 = 𝒂 ⟺ 𝒂 𝒃 = 𝒃
where ∗ and denote the operations of
meet and join respectively.
Solution :
Given for any 𝒂, 𝒃 ∈ 𝑳,
𝒂 ≤ 𝒃⟺ 𝒂 ∗ 𝒃 = 𝒂 ⟺ 𝒂
𝒃=𝒃
In otherwords,
1. 𝐚 𝒃 = 𝒃 iff 𝒂 ≤ 𝒃
2. 𝐚 ∗ 𝐛 = 𝐚 iff 𝐚 ≤ 𝐛
3. 𝐚 ∗ 𝐛 = 𝒂 iff 𝒂 𝒃 = 𝒃
(1) Let 𝒂 ≤ 𝒃
𝒃 ≤ 𝒃 (By refexive)
𝒂 𝒃≤𝒃 ------ (1)
𝒃 ≤ 𝒂 𝒃 ------ (2) (By definition of
𝑳𝑼𝑩) From (1) and (2), by
antisymmetric, we have
𝒂 𝒃=𝒃
Conversely,
If 𝒂 𝒃 = 𝒃 -------
𝒂 ≤ 𝒂𝒃
(3)
𝒂 ≤𝒃 [By (3)]
(2) Let 𝒂 ≤ 𝒃
𝐚 ≤ 𝒂 (By refexive)
𝐚≤𝒂∗𝒃 ------ (4)
𝐚∗𝒃 ≤ 𝒂 ------ (5) (By definition of
𝐆𝐋𝐁)
From (4) and (5), by antisym metric, we
have
𝒂∗𝒃=
𝒂
Conversely,
If 𝒂 ∗ 𝒃
=𝒂
-------
𝒂∗𝒃
(6)
≤𝒃
𝒂
≤𝒃
[By (6)]
(3) Let 𝒂 ∗ 𝒃 = 𝒂
𝒃 𝒂 ∗ 𝒃=
𝒃 𝒂
𝒃 𝒃∗𝒂=
[By Commutative
𝒂 𝒃
law]
(i.e) 𝒂 𝒃
𝒃= 𝒂
[By Absorption law]
=𝒃
𝒃
𝒃
𝒂 =𝒃
Conversely, let
𝒂 ∗ 𝒂𝒃 =𝒂∗𝒃
𝒂=𝒂 ∗ 𝒃 [By
Absorption
(i. law]
5. State and prove the distributive
inequalities of a lattice.
Solution :
Statement :
Distributive Inequality :
𝑳 , ≤is a lattice, then for any 𝒂 , 𝒃 , 𝒄
∈𝑳
If
(i) 𝒂 𝖠 𝒃 ∨ 𝒄 ≥ 𝒂 𝖠 𝒃 ∨ 𝒂
𝖠𝒄
(ii) 𝒂
∨ 𝒃 𝖠𝒄≤ 𝒂∨𝒃
𝖠 𝒂 ∨𝒄
Proof :
(i) 𝒂 𝖠 𝒃 ∨ 𝒄 ≥ 𝒂 𝖠 𝒃 ∨ 𝒂
𝖠𝒄
By definition of 𝑮𝑳𝑩, we
𝒂𝖠 ≤𝒂
have
𝒃
𝒂 ≤ 𝒃 ≤ 𝒃∨ 𝒄
𝖠
𝒃
𝒂 𝖠 ≤ 𝒂 of𝖠 𝑮𝑳𝑩,
𝒃 ∨ 𝒄 we------------(1)
have 𝒃
By definition
𝒂𝖠 ≤𝒂
𝒄
𝒂 ≤ 𝒄 ≤ 𝒃∨ 𝒄
𝖠
𝒄
From (1) and (2), we have
𝒂 𝖠 𝒃 ∨ 𝒂 𝖠 𝒄 ≤ 𝒂𝖠 𝒃∨ 𝒄
𝒂 𝖠 𝒃∨𝒄 ≥ 𝒂𝖠𝒃∨ 𝒂𝖠𝒄
(ii) 𝒂 ∨ 𝒃 𝖠 𝒄 ≤ 𝒂 ∨ 𝒃 𝖠 𝒂 ∨ 𝒄
By definition of 𝑳𝑼𝑩, we have
𝒂 ≤ 𝒂∨ 𝒃
By definition of 𝑮𝑳𝑩, we have
𝒃 𝖠𝒄 ≤ 𝒃≤ 𝒂 ∨𝒃
𝒂 ∨ 𝒃𝖠 𝒄 ≤ 𝒂∨ 𝒃
------------ (3)
By definition of 𝑳𝑼𝑩, we have
𝒂 ≤ 𝒂∨ 𝒄
By definition of 𝑮𝑳𝑩, we have
𝒃 𝖠𝒄 ≤ 𝒄≤ 𝒂 ∨𝒄
𝒂 ∨ 𝒃𝖠 𝒄 ≤ 𝒂∨ 𝒄
------------ (4)
From (3) and (4), we have
𝒂 ∨ 𝒃𝖠𝒄 ≤ 𝒂∨𝒃 𝖠 𝒂∨𝒄
6. State and prove modular inequality of a
lattice.
Solution :
Statement :
Modular Inequality :
𝑳 , ≤is a lattice, then for any 𝒂 , 𝒃 , 𝒄
∈ 𝑳,
If
𝒂 ≤ :𝒄 iff 𝒂 ∨ 𝒃 𝖠𝒄 ≤ 𝒂 ∨𝒃
𝖠 𝒄.
Let 𝒂 ≤ 𝒄
Proof
𝒂∨𝒄
=𝒄
Then ----------- (1)
By distributive inequality, we have
𝒂 ∨ 𝒃𝖠𝒄 ≤ 𝒂 ∨𝒃 𝖠 𝒂∨𝒄
𝒂 ∨ 𝒃 𝖠 𝒄 ≤ 𝒂 ∨ 𝒃 𝖠 𝒄 [By (1)]
Conversely,
Assume 𝒂 ∨ 𝒃 𝖠 𝒄 𝒂 ∨ 𝒃
≤ 𝖠𝒄
𝖠𝒄
𝒂 ≤ 𝒂∨ 𝒃𝖠 𝒄 ≤ 𝒂 ≤𝒄
∨𝒃
(i. e) 𝒂 ≤𝒄
Hence, proved.
7. State and prove isotonic inequality of a
lattice.
Solution :
Statement :
Isotonic inequality :
If 𝑳 , ≤is a lattice, then for any 𝒂 , 𝒃 , 𝒄
∈ 𝑳,
𝒂 ≤ 𝒃 ⟹ 𝒂∗ 𝒄 ≤ 𝒃 ∗ 𝒄 and
𝒂 𝒄 ≤ 𝒃𝒄
Proof :
We know
that In a
lattice,
𝒂 ≤ 𝒃⇔ 𝒂 ∗ 𝒃 = 𝒂 ⇔𝒂 𝒃=𝒃
………..( A) Assume 𝒂 ≤𝒃
𝒂 ∗ 𝒃 = 𝒂 and 𝒂 𝒃
= 𝒃 ………
Then
(1)
𝒂 ∗ 𝒄 ∗ 𝒃 ∗ 𝒄= 𝒂 ∗ 𝒄 ∗ 𝒃
∗𝒄
Now,
𝐚∗𝐜∗ 𝐛 =𝐚 ∗ 𝐛∗𝐜
∗𝐜 ∗𝐜
[By Commutative law]
= 𝒂∗𝒃
∗ 𝒄∗𝒄
[By Associative law]
=𝒂 ∗𝒄
[By (1) and Idempotent
law] By (A), we have
𝒂 ∗𝒄 ≤𝒃 ∗𝒄
𝒂 𝒃 𝒄 =𝒂 𝒄 𝒃𝒄
𝒄
[By Associative
𝐚
𝐜
law]
𝐛 𝐜 = 𝐚 𝐛 𝐜𝐜
= 𝒂 𝒃 𝒄
𝒄
[By Commutative
law] [By Associative
law]
=𝒃 𝒄
[By (1) and
Idempotent
Distributive Lattice
A lattice 𝑳 ,∨ ,𝖠 is called a
distributive lattice, if for any
element 𝒂 , 𝒃 , 𝒄∈ 𝑳
𝒂 𝖠𝒃 ∨𝒄 = 𝒂 𝖠𝒃 ∨
𝒂 𝖠𝒄
and 𝒂 ∨ 𝒃 𝖠 𝒄 = 𝒂 ∨ 𝒃 𝖠 𝒂
∨𝒄
Modular Lattice
A lattice 𝑳 ,∨ ,𝖠 a modular
is called lattice, if
for𝒂 ≤any 𝒂,𝒃,𝒄
𝒄,then ∈ 𝑳,
𝒂 ∨ 𝒃𝖠𝒄 = 𝒂 ∨𝒃
𝖠 𝒄.
1. Examine whether the lattice given in the
following Hasse diagram is distributive or
not.
a b c
0
Solution :
To prove 𝒂 𝒃 𝖠 = 𝒂∨𝒃𝖠 𝒂
∨ 𝒄 ∨𝒄
𝒂 ∨
𝒃 = 𝒂∨𝟎
=𝒂
𝖠𝒄
………..…( 1 )
𝒂 ∨ 𝒃 𝖠 𝒂 ∨ 𝒄= 𝟏 𝖠 𝟏
=𝟏
… … … … … (2)
From (1) and (2), we have
𝒂 ∨ 𝒃 𝖠𝒄 ≠ 𝒂 ∨𝒃
2. Show that cancellation laws are valid in
distributive lattice.
Solution :
Cancellation Law :
If 𝑳 ,∗ , is a distributive lattice and if
𝒂∗𝒃=𝒂 ∗𝒄 and 𝒂 𝒄
𝒃=𝒂
for all
𝒂,𝒃,𝒄 ∈ 𝑳 ,then 𝒃
= 𝒄.
Proof :
Given 𝒂 ∗ 𝒃 = 𝒂
∗𝒄
………..
𝒂 𝒃 = 𝒂 𝒄 ……….( 2 )
( 1)
𝒄∗ 𝒂𝒃 =𝒄 𝒂𝒄
∗ (2)]
[By
= 𝒄∗ 𝒄 𝒂
[By Commutative law]
𝒄∗ 𝒂 = 𝒄 …………..( 3 )
𝒃
[By Absorption
law]
Also 𝒄 𝒂 𝒃 = 𝒄 𝒄
∗ ∗𝒂 ∗𝒃
= 𝒂∗𝒄 𝒃∗𝒄
[By Commutative
law]
= 𝒂∗𝒃⊕ 𝒃 ∗ 𝒄 [By
(1)]
= 𝒃∗𝒂 𝒃∗𝒄
[By Commutative
law]
= 𝒃∗ 𝒂 𝒄
[By Distributive
𝒄∗ 𝒂 𝒃 =𝒃 𝒂 𝒃 [By
∗
= 𝒃∗ 𝒃𝒂
(2)]
[By Commutative
𝒄 𝒂 =𝒃
law]
∗ 𝒃
…………
(4)
[By Absorption
law] From (3) and (4), we
have
3. Prove that every distributive
lattice is modular. Is the converse
true ? Justify your
claim.
Solution :
𝑳 ,∗ ,
Let be a distributive lattice.
We have to prove that 𝑳 ,∗ , is a modular
lattice.
(i.e) To prove that for any 𝒂 , 𝒃 , 𝒄 ∈ 𝑳
𝒂 ≤ 𝒄,𝒂 𝒃 ∗ 𝒄= 𝒂 𝒃 ∗𝒄
Since 𝑳 is a distributive lattice, for any
𝒂,𝒃,𝒄 ∈ 𝑳, we have
𝒂 𝒃 ∗ 𝒄= 𝒂 𝒃 ∗ 𝒂𝒄
If 𝒂 ≤ 𝒄 , then 𝒂 𝒄=𝒄
Therefore, 𝒂 𝒃 ∗ 𝒄= 𝒂 𝒃 ∗𝒄
Thus, the modularity condition is satisfied
Hence, 𝑳 isa modular lattice.
The converse is not true.
For example, the diamond lattice is
modular but not distributive.
Bounded Lattice
A lattice 𝑳 is said to have a lower
bound denoted by 𝟎, if 𝟎 ≤ 𝒂 for all 𝒂 ∈ 𝑳.
Similarly, 𝑳 is said to have an upper bound
denoted by 𝟏, if 𝒂 ≤ 𝟏 for all 𝒂 ∈ 𝑳.
The lattice 𝑳 is said to be bounded
lattice if it has both a lower bound 𝟎 and
an upper bound 𝟏.
The bounds 𝟎 and 𝟏 of a lattice
𝑳 ,∨ ,𝖠 , 𝟎 , 𝟏 satisfy the following identities,
which are seen to be true by the meanings of ∨
and 𝖠. ∈ 𝑳, 𝒂 ∨𝟏=𝟏 ;
𝒂 𝒂 𝖠 𝟏 = 𝒂 and
For any
𝒂∨𝟎=𝒂; 𝒂 𝖠𝟎=𝟎
Since, 𝒂 ∨ 𝟎 = 𝒂 and 𝒂 𝖠 𝟏 = 𝒂, 𝟎 is the
identity of the operation ∨ and 1 is the
identity element of the operation 𝖠.
Since, 𝒂 ∨ 𝟏 = 𝟏 and 𝒂 𝖠 𝟎 = 𝟎, 𝟏 and 𝟎
are the zeros of the operations ∨ and 𝖠
respectively.
Complement of an element
If 𝑳 ,∨ ,𝖠 , 𝟎 , 𝟏 is a bounded lattice and
𝒂 ∈ 𝑳, then an element 𝒃 ∈ 𝑳 is
called a complement of 𝒂 if
𝒂 ∨ 𝒃 = 𝟏 and 𝒂 𝖠 𝒃 = 𝟎.
Since 𝟎∨𝟏 =𝟏 and 𝟎 𝖠𝟏
= 𝟎 , 𝟎 and 𝟏 are complements to each
other.
When 𝒂 ∨ 𝒃 = 𝟏, 𝒃 ∨𝒂
=𝟏
we know that
and when
Complemented Lattice
𝑳 ,∨ ,𝖠 ,
𝟎,𝟏
A lattice is
a complemented lattice called if
element of 𝑳 has at
complement.
every
least one
1. If 𝑺𝟒𝟐 is the set of all divisors of 𝟒𝟐 and 𝑫 is
𝑺𝟒
the relation “divisor of ” on . Prove that
𝑺𝟒𝟐 , 𝑫 is a complemented 𝟐lattice.
𝑺𝟒𝟐 = 𝟏 , 𝟐 , 𝟑 , 𝟔 , 𝟕 , 𝟏𝟒 , 𝟐𝟏 , 𝟒𝟐
Solution :
The Hasse diagram of 𝑺𝟒𝟐 is given
by
42
6 14 21
2 3 7
1
The zero element of the lattice is 𝟏 and
unit element of the lattice is 𝟒𝟐.
𝟏 ∨ 𝟒𝟐 = 𝟏, = 𝟒𝟐
𝑳𝑪𝑴 𝟒𝟐 (≡ 𝟏)
𝟏 𝖠 𝟒𝟐 = 𝟏, = 𝟏 (≡
𝑮𝑪𝑫 𝟒𝟐 𝟎)
𝟐 ∨ 𝟐𝟏 = 𝟐, = 𝟒𝟐
𝑳𝑪𝑴 𝟐𝟏 (≡ 𝟏)
𝟐 𝖠 𝟐𝟏 = 𝟐, = 𝟏 (≡
𝑮𝑪𝑫 𝟐𝟏 𝟎)
𝟑 ∨ 𝟏𝟒 = 𝟑, = 𝟒𝟐
𝟔 𝖠 𝟕 = 𝑮𝑪𝑫
𝑳𝑪𝑴 𝟏𝟒 (≡ 𝟏)
𝟔,𝟕
𝟏′ =
𝟒𝟐
Now
𝟐′ = 𝟐𝟏
𝟑′ = 𝟏𝟒
𝟔′ = 𝟕
𝟕′ = 𝟔
𝟏𝟒′ = 𝟑
𝟐𝟏′ = 𝟐
𝟒𝟐′= 𝟏
Since every element of 𝑫𝟒𝟐 hasa complement,
𝑺𝟒𝟐 , 𝑫 is a complemented lattice.
2. If 𝑫𝟒𝟓 denotes the set of all divisors of 𝟒𝟓
under divisibility ordering, find which
elemenets have complements and which
do not have complements.
Solution :
𝑫𝟒𝟓 = 𝟏 , 𝟑 , 𝟓 , 𝟗 , 𝟏𝟓 , 𝟒𝟓
The Hasse diagram of 𝑫𝟒𝟓 is given
by
45
9 15
3 5
𝟏
The zero element of the lattice
is
𝟒𝟓.
and unit element of the lattice is
𝟏 ∨ 𝟒𝟓 = 𝟏, = 𝟒𝟓
𝑳𝑪𝑴 𝟒𝟓 (≡ 𝟏)
𝟏 𝖠 𝟒𝟓 = 𝟏, = 𝟏 (≡
𝑮𝑪𝑫 𝟒𝟓 𝟎)
𝟑 ∨ 𝟏𝟓 = 𝟑, = 𝟏𝟓
𝑳𝑪𝑴 𝟏𝟓𝟗 , 𝟓(≢
= 𝟏)
𝟒𝟓(≡
𝟏)
𝟑
𝟗 𝖠 𝟏𝟓
𝟓 ==𝑮𝑪𝑫
𝟑, = 𝟑 (≢
𝑮𝑪𝑫
𝟗,𝟓 𝟏𝟓 =𝟎) 𝟏 (≡ 𝟎)
𝟏′ =
𝟗∨𝟓=
𝟒𝟓
Now
𝑳𝑪𝑴
𝟓′ = 𝟗
𝟗′ = 𝟓
𝟒𝟓′
=𝟏
𝟑
𝟏𝟓
The elements and do not have
complements.
But the elements 𝟏 , 𝟓 , 𝟗 and 𝟒
𝟓
have
complements.
Totally Ordered Set OR Chain
A partial order relation ≤ on a set 𝑨
is called a total order or linear order, if
for every 𝒂 , 𝒃 ∈ 𝑨 either 𝒂 ≤ 𝒃 or 𝒃 ≤ 𝒂.
If ≤ is a total order on 𝑨, then the poset
𝑨,≤ is called a totally ordered set
or
chain.
1. Show that every totally ordered set is a
lattice.
Solution :
Let 𝑿 , ≤be a chain and 𝒂 , 𝒃
∈𝑿
Then we have either 𝒂 ≤ 𝒃 or 𝒃 ≤𝒂
Case (i) :
Assume that 𝒂 ≤ 𝒃
Clearly, 𝒃 is an upper bound of 𝒂 and
𝒃
If 𝒄 is an upper bound of 𝒂 and 𝒃, we have
𝒂 ≤ 𝒄 and 𝒃 ≤𝒄
Thus, 𝒃 ≤ 𝒄 for every upper bound 𝒄 of 𝒂 and
𝒃.
Hence, 𝒃 is the least upper bound of 𝒂 and 𝒃.
(i.e) 𝒂 ∨ 𝒃 = 𝒃
Similarly, 𝒂 𝖠 𝒃 = 𝒂.
Case (ii) :
Assume that 𝒃 ≤ 𝒂
Then we can prove that 𝒂 ∨𝒃 =𝒂 and
𝒂 𝖠 𝒃 = 𝒃.
Thus, 𝒂 ∨ 𝒃 and 𝒂 𝖠𝒃 exists
for all 𝒂 , 𝒃 ∈ 𝑿. Hence 𝑿,
≤ is a lattice.
2. Prove that every chain is a
distributive lattice.
Solution :
Let 𝑳 , ≤be a chain and 𝒂 , 𝒃 , 𝒄 ∈𝑳
Consider the following possible cases
𝒊 𝒂 ≤ 𝒃≤ 𝒄
𝒊𝒊 𝒂 ≤ 𝒄≤ 𝒃
𝒊𝒊𝒊 𝒃≤𝒄≤𝒂
𝒊𝒗 𝒃≤ 𝒂≤𝒄
𝒗 𝒄≤ 𝒂≤ 𝒃
𝒗𝒊 𝒄 ≤ 𝒃≤ 𝒂
𝒊 𝒂≤𝒃
≤𝒄
𝒂 𝖠 𝒃 ∨ 𝒄= 𝒂𝖠 𝒄 = 𝒂 …..(1)
𝒂 𝖠𝒃 ∨ 𝒂 𝖠𝒄 = c
𝒂 ∨𝒂=𝒂 … .. (2) From
(1) and (2), we have
b
𝒂 𝖠𝒃 ∨ 𝒄 = 𝒂 𝖠 𝒃 ∨
𝒂 𝖠𝒄
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒃 = 𝒃
a
…..(3)
𝒂 ∨ 𝒃 𝖠 𝒂 ∨ 𝒄 = 𝒃𝖠 𝒄
Also,
=𝒃
…..(4)
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒃 𝖠 𝒂
From (3) and (4), we have
∨𝒄
𝒊 𝒂 ≤𝒄
𝒊 ≤𝒃
𝒂 𝖠 𝒃 ∨ 𝒄= 𝒂𝖠 𝒃 = 𝒂 … ..
(5)
𝒂 𝖠𝒃 ∨ 𝒂 𝖠𝒄 =
b
𝒂 ∨𝒂=𝒂 … .. (6) From
c
(5) and (6), we have
𝒂 𝖠𝒃 ∨ 𝒄 = 𝒂 𝖠 𝒃 ∨
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒄 = 𝒄
𝒂 𝖠𝒄
…..(7) a
𝒂 ∨ 𝒃 𝖠 𝒂 ∨ 𝒄 = 𝒃𝖠 𝒄
=𝒄
…..(8)
Also,
From (7) and (8), we have
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒃 𝖠 𝒂
𝒊𝒊𝒊 𝒃 ≤ 𝒄 ≤ 𝒂
𝒂 𝖠 𝒃 ∨ 𝒄= 𝒂𝖠 𝒄 = 𝒄 …..(9)
𝒂 𝖠𝒃 ∨ 𝒂 𝖠𝒄 a
=𝒃 ∨𝒄=𝒄 … .. (10) From
(9) and (10), we have
c
𝒂 𝖠𝒃 ∨ 𝒄 = 𝒂 𝖠 𝒃 ∨
𝒂 𝖠𝒄
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒃 = 𝒂 …..(11)
𝒂 ∨ 𝒃 𝖠 𝒂 ∨ 𝒄= 𝒂𝖠 𝒂
Also, b
=𝒂
…..(12)
From (11) and (12), we have
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒃 𝖠 𝒂
𝒊 𝒃≤𝒂
𝒗 ≤𝒄
𝒂 𝖠 𝒃 ∨ 𝒄= 𝒂𝖠 𝒄 = 𝒃 …..(13)
𝒂 𝖠𝒃 ∨ 𝒂 𝖠𝒄
=𝒃 ∨𝒂=𝒂
c
… .. (14) From
(13) and (14), we have
𝒂 𝖠𝒃 ∨ 𝒄 = 𝒂 𝖠 𝒃 ∨
a
𝒂 𝖠𝒄
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒃 = 𝒂 … ..
𝒂 ∨ 𝒃 𝖠 𝒂 ∨ 𝒄= 𝒂𝖠 𝒄
Also, (15) b
=𝒂 …..(16)
From (15) and (16), we have
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒃 𝖠 𝒂
𝒗 𝒄≤ 𝒂≤𝒃
𝒂 𝖠 𝒃 ∨ 𝒄= 𝒂𝖠 𝒃 = 𝒂 …..(17)
𝒂 𝖠𝒃 ∨ 𝒂 𝖠𝒄
b
=𝒂 ∨𝒄=𝒂 … .. (18) From
(17) and (18), we have
𝒂 𝖠𝒃 ∨ 𝒄 = 𝒂 𝖠 𝒃 ∨
a
𝒂 𝖠𝒄
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒄 = 𝒂 …..(19)
𝒂 ∨ 𝒃 𝖠 𝒂 ∨ 𝒄 = 𝒃𝖠 𝒂
Also, c
=𝒂
…..(20)
From (19) and (20), we have
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒃 𝖠 𝒂
𝒗 𝒄≤𝒃
𝒊 ≤𝒂
𝒂 𝖠 𝒃 ∨ 𝒄= 𝒂𝖠 𝒃 = 𝒃 …..(21)
𝒂 𝖠𝒃 ∨ 𝒂 𝖠𝒄
=𝒃 ∨𝒄=𝒃
a
… .. (22) From
(21) and (22), we have
𝒂 𝖠𝒃 ∨ 𝒄 = 𝒂 𝖠 𝒃 ∨
b
𝒂 𝖠𝒄
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒄 = 𝒂 …..(23)
𝒂 ∨ 𝒃 𝖠 𝒂 ∨ 𝒄= 𝒂𝖠 𝒂
Also, c
=𝒂
…..(24)
From (23) and (24), we have
𝒂 ∨ 𝒃 𝖠 𝒄= 𝒂 ∨ 𝒃 𝖠 𝒂
3. Show that every chain is modular.
Solution :
Let 𝑳 , ≤be a chain.
Let 𝒂 , 𝒃 , 𝒄 ∈ 𝑳 and 𝒂
≤𝒄
As 𝑳 isa chain either 𝒃 ≤ 𝒄 or 𝒄
≤𝒃
Assume that 𝒃 ≤ 𝒄
Then 𝒄 is an upper bound of 𝒂 and
Thus in this case,
𝒂 ∨𝒃𝖠𝒄=𝒂 ∨𝒃 𝖠𝒄
Assume 𝒄 ≤ 𝒃
Then by transitive property of ≤, we
have
𝒂 ≤ 𝒃 and
𝒂 ∨𝒃𝖠𝒄=𝒃 𝖠𝒄=𝒄
while, 𝒂 ∨ 𝒃 𝖠 𝒄 = 𝒂 ∨ 𝒄 = 𝒄
In this case also, we have
𝒂 ∨𝒃𝖠𝒄=𝒂 ∨
𝒃 𝖠𝒄
≤ 𝒄,
Thus whenever, 𝒂 modular
the
equation
𝒂∨𝒃𝖠
Hence, 𝑳 𝒄, ≤is
= 𝒂a modular
∨ 𝒃 𝖠 𝒄lattice.
is
satisfied.
Sub Lattice
A non-empty subset 𝑴 of a lattice
𝑳 ,∨ ,𝖠 is called a sublattice of 𝑳, iff 𝑴 is
closed under both the operation ∨ and 𝖠.
(i. e) if 𝒂 , 𝒃 ∈ 𝑴,then 𝒂 ∨ 𝒃 ∈ 𝑴 and
𝒂 𝖠𝒃 ∈ 𝑴 From thedefinition, it is
obvious that the sub lattice itself is a
lattice with respect to ∨ and 𝖠.
If 𝑺𝒏 is the set of all divisors of the positive
integer 𝒏 and 𝑫 is the relation of
„division‟
, prove that 𝑺𝟑𝟎 , 𝑫 is a lattice.
Find also all the sub-lattices of
𝑺𝟑𝟎 , 𝑫 that contain
𝟔 or more elements.
Solution :
𝑺𝟑𝟎 = 𝟏 , 𝟐 , 𝟑 , 𝟓 , 𝟔 , 𝟏𝟎 , 𝟏𝟓 , 𝟑𝟎
3
0
6 1 1
0 5
2 3 5
1
𝟐∨𝟑= 𝟐,𝟑 =
𝑳𝑪𝑴 𝟔
𝟐𝖠𝟑= 𝟐,𝟑=𝟏
𝟏𝟎 𝑮𝑪𝑫
∨ 𝟏𝟓 = 𝟏𝟎 , =
𝑳𝑪𝑴 𝟏𝟓 𝟑𝟎
𝟏𝟎 𝖠 𝟏𝟓 = 𝟏𝟎 , =𝟓
𝟑, = 𝟑𝟎
𝑮𝑪𝑫 𝟏𝟓
𝟏𝟎
𝟑 𝖠 𝟏𝟎 = 𝟑, =𝟏
𝟑 ∨ 𝟏𝟎 =
𝑮𝑪𝑫 𝟏𝟎
𝑳𝑪𝑴 = 𝟑𝟎
𝟓 ∨ 𝟑𝟎 = 𝟓,
=
𝑳𝑪𝑴 𝟑𝟎
𝟓
𝟓 𝖠 𝟑𝟎 = 𝟓,
= 𝟑𝟎
𝑮𝑪𝑫 𝟑𝟎
=𝟐
𝟐 ∨ 𝟑𝟎 = 𝟐,
Similarly every pair of elements has LUB and
GLB.
Hence, 𝑺𝟑𝟎 , 𝑫 is a lattice.
The sub lattices of 𝑺𝟑𝟎 , 𝑫 containing
𝟔 elements are 𝟏 , 𝟐 , 𝟑 , 𝟔 , 𝟏𝟓 , 𝟑𝟎 ,
𝟏 , 𝟑 , 𝟓 , 𝟔 , 𝟏𝟓 , 𝟑𝟎 ,
𝟏 , 𝟐 , 𝟑 , 𝟔 , 𝟏𝟎 , 𝟑𝟎 𝟏,
𝟑 , 𝟓 , 𝟏𝟎 , 𝟏𝟓 , 𝟑𝟎 ,
,
𝟏 , 𝟐 , 𝟓 , 𝟔 , 𝟏𝟎 , 𝟑𝟎 𝟏,𝟐,𝟓,
𝟏𝟎 , 𝟏𝟓 , 𝟑𝟎
and
Lattice Homomorphism
If 𝑳𝟏 ,∨ , and 𝑳𝟐 , ,∗ are two lattices,
𝖠 𝒇∶ a called a
𝑳𝟏
mapping
homomorphism → 𝑳𝟐
from is lattice and 𝑳𝟐
if for any
𝒂 , 𝒃 ∈ 𝑳𝟏 , 𝑳𝟏
𝒇𝒂 ∨ 𝒃= 𝒇𝒂 𝒇
𝒃
𝒇 𝒂 𝖠 𝒃 = 𝒇𝒂 ∗ 𝒇
𝒃
If a homomorphism 𝒇 ∶ 𝑳𝟏 →
𝑳𝟐
of two
lattices 𝑳𝟏 ,∨ ,𝖠 ∗
onto 𝑳then, is𝒇 is
𝟐
,
bijective (i.e) one-one,and
called an isomorphism. If there
exists an isomorphism between two
lattices, then the lattices are said to be
isomorphic.
Complete Lattice
A lattice 𝑳 ,∨ ,𝖠 is said to be
complete lattice if every non empty
subset has a least upper bound and a
greatest lower bound.
1. Give an example of a lattice that is
not complemented.
Ans : 𝑺𝟒𝟓 , | and 𝑺𝟕𝟓 , 𝑫 .
2. Give an example of a distributive
lattice but not complemented.
𝟏,𝟐,𝟒
,≤ .
Ans :
example of lattice
3. which
Give an is bounded and
complemented. distributive
Ans : 𝑷 𝑺 ,𝖴,∩ , and
2. If 𝒂 , 𝒃 are elements in a
any two complemented lattice show
distributive that the 𝑳 , are
equivalent:
𝒂 ≤ 𝒃following
,𝒂 ∗ 𝒃′ = 𝟎 , 𝒂′ 𝒃 ≤ 𝒂
= 𝟏 , 𝒃′ ′.
Solution :
Let 𝑳 be a complemented distributive
lattice. For 𝒂,𝒃 ∈ 𝑳, the
following are equivalent.
(i) 𝒂 ≤ 𝒃 ,(ii) 𝒂 ∗ 𝒃′ = 𝟎 , (iii) 𝒂′ 𝒃
It is enough to prove that
𝒊 ⟹ ⟹ 𝒊𝒊𝒊 ⟹ 𝒊𝒗 ⟹
𝒊𝒊 (𝒊)
To 𝒊 ⟹ 𝒊𝒊
Then 𝒂 𝒃
prove
= 𝒃 : Let
𝒃 ∗𝒃
𝒂 𝒃𝒂 ′ ∗ 𝒃′ ′
𝒂
= ∗ 𝒃 𝒃 ∗ 𝒃 = 𝒃 ∗ 𝒃′
′ ≤𝒃
[By distributive
law]
𝒂 ∗ 𝒃′ =𝟎
𝟎
[By complement
𝐚 =𝟎
law]
[By Identity law]
∗
𝒃′
Let 𝐚 ∗ 𝒃′ 𝒊= 𝟎 𝒊𝒊
⟹
Therefore,
To prove : 𝒊𝒊 𝒊𝒊𝒊
Taking complement on both sides, we have
𝒂 ∗𝒃 ⟹′ = 𝟎′
′
𝒂′ 𝒃 ′ = 𝟏 [By demorgan‟s
𝒃
′
=𝟏
law]
𝒂
Therefore, 𝒊𝒊 ⟹ 𝒊𝒊𝒊 .
′
To prove : 𝒊𝒊𝒊 ⟹
𝒊𝒗
𝒂 ′ 𝒃 = 𝟏
𝒃 ∗ 𝒃′ = 𝟏∗ 𝒃
𝒂′
𝒂′ ∗ 𝒃 𝒃 ∗ 𝒃′ = 𝒃
′
′
′ [By Distributive law and Identity law]
𝒂′ ∗ 𝒃 𝟎 = 𝒃′ [By Complement law]
∗ 𝒃′ = 𝒃
′
[By Identity law]
𝒂′ ′
[By Commutative law]
𝒃′ ∗ 𝒂 = 𝒃
′
′
𝒊𝒊𝒊 ⟹
𝒃′
𝒊𝒗 ≤ 𝒂′
Therefore,
𝒊𝒗 ⟹
𝒊
To prove :
Let 𝒃′ ≤
𝒂′
Then 𝒃 ∗ 𝒂′ = 𝒃′
′
∗ 𝒃′ = 𝒃′ [By Commutative law]
Taking𝒂complement
′
on both sides, we have
𝒂′ ∗ 𝒃′ ′ = 𝒃′
′
′
=𝒃
[By Demorgan‟s law]
𝒂𝒂′ ′ 𝒃′
𝒃 =𝒃
𝒂 ≤𝒃
Therefore, 𝒊𝒗 ⟹ 𝒊
Hence, the following statements are equivalent.
3. Prove that 𝑫𝟏𝟏𝟎, the set of all positive divisors
of a positive integer 𝟏𝟏𝟎, is a Boolean algebra and
find all its sub-algebras. Also find the set of
atoms of 𝑫𝟏𝟏𝟎.
𝟏 , 𝟐, 𝟓 , 𝟏𝟎, 𝟏𝟏, 𝟐𝟐,
𝑫𝟏𝟏𝟎
𝟓𝟓, 𝟏𝟏𝟎
Solution :
=
The Hasse diagram of 𝑫𝟏𝟏𝟎 is given by
110
10 22 55
2 5 11
1
is 𝟏 and unit
𝑫𝟏𝟏
The zero element of
element of 𝑫𝟏𝟏𝟎 is 𝟎
𝟏𝟏𝟎.
𝟏 ∨ 𝟏𝟏𝟎 = 𝑳𝑪𝑴 𝟏 , 𝟏𝟏𝟎
= 𝟏𝟏𝟎 (≡ 𝟏)
𝟏 𝖠 𝟏𝟏𝟎 = 𝑮𝑪𝑫 𝟏 , 𝟏𝟏𝟎
=𝟏 (≡ 𝟎)
𝟐 ∨ 𝟓𝟓 = 𝑳𝑪𝑴 𝟐 , 𝟓𝟓 =
𝟏𝟏𝟎 (≡ 𝟏)
𝟐 𝖠 𝟓𝟓 = 𝑮𝑪𝑫 𝟐 , 𝟓𝟓 = 𝟏
(≡ 𝟎)
𝟓 ∨ 𝟐𝟐 = 𝑳𝑪𝑴 𝟓 , 𝟐𝟐 =
𝟏𝟎𝟏𝟏𝟎
∨ 𝟏𝟏
(≡=𝟏)𝑳𝑪𝑴 = 𝟏𝟏𝟎
𝟏𝟎 , 𝟏𝟏 (≡ 𝟏)
𝟓 𝖠 𝟐𝟐 = 𝑮𝑪𝑫 𝟓 , 𝟐𝟐 = 𝟏
10 (≡ 𝟎) = 𝑮𝑪𝑫
𝖠 𝟏𝟏 = 𝟏 (≡ 𝟎)
𝟏′ =
𝟏𝟏𝟎
Now
𝟐′ = 𝟓𝟓
𝟓′ = 𝟐𝟐
𝟏𝟎′ = 𝟏𝟏
𝟏𝟏′ = 𝟏𝟎
𝟐𝟐′ = 𝟓
𝟓𝟓′ = 𝟐
𝟏𝟏𝟎′= 𝟏
Since every element of 𝑫𝟏𝟏𝟎 has a complement,
𝑫𝟏𝟏
is a complemented lattice.
We know that 𝑷 𝑺 ,𝖴 ,∩ is a distributive
lattice where 𝑺 = 𝒂 , 𝒃 , 𝒄
𝑷 ,𝖴 ,∩
𝑺
From the Hasse diagram, is
same as 𝑫𝟏𝟏𝟎.
(i.e) 𝑫𝟏𝟏𝟎 is a distributive lattice.
𝑫𝟏𝟏
Since, is a complemented and
𝟎
𝑫𝟏𝟏
distributive lattice, is a Boolean
algebra. 𝟎
The sub algebras of 𝑫𝟏𝟏𝟎 are
𝟏 , 𝟏𝟏𝟎 , 𝟏 , 𝟐 , 𝟓𝟓 , 𝟏𝟏𝟎 𝟏,
𝟓 , 𝟐𝟐 , 𝟏𝟏𝟎
,
,
𝟏 , 𝟏𝟎 , 𝟏𝟏 , 𝟏𝟏𝟎
𝟏 , 𝟐, 𝟓 , 𝟏𝟎, 𝟏𝟏, 𝟐𝟐, 𝟓𝟓,
and
𝟏𝟏𝟎 .
The atoms of 𝑫𝟏𝟏𝟎 are 𝟐, 𝟓 and 𝟏𝟏.
4 . In a complemented and distributive lattice,
prove that complement of each element is
unique.
Solution :
Let 𝒂 ∈ 𝑩 be any element.
If possible let 𝒃 and 𝒄 are complements of
the element 𝒂 ∈ 𝑩.
Then 𝒂 + 𝒃 = 𝟏 and
𝒂. 𝒃 = 𝟎 (1)
… … ..
𝒂 + 𝒄 = 𝟏 and 𝒂 . 𝒄 = 𝟎 ……..(2)
Now 𝒃 = 𝒃 . 𝟏 [By Identity law]
𝐛 =
𝒃. 𝒂
[By (2)]
+𝒄 𝒃 . 𝒄 [By distributive law]
𝒃𝒃==𝒂 . 𝒃+ 𝒃 .
𝒄
[By commutative
𝒃 .
𝒃=𝟎+ 𝒂 + law]
𝒃.𝒄
𝒃.
[By (1)]
𝒃 = 𝒂 . 𝒄+ 𝒄 [By (2)]
𝒃= 𝒂+𝒃 . 𝒄 [By distributive
𝒃=
law]
𝟏.𝒄
[By (1)]
𝒃=𝒄 [By Identity law]
Hence, 𝒃 = 𝒄.
Therefore, in a complemented
distributive lattice,
anda complement of each
element is unique.
Sub Algebra
If 𝑪 is a non empty subset of a
Boolean algebra such that 𝑪 itself is a
Boolean algebra with respect to the
operations of 𝑩, then 𝑪 is called a sub
algebra of 𝑩.
It is obvious that 𝑪 is a subalgebra of 𝑩 iff
𝑪 is closed under the operations of 𝑩
,
namely + ,⋅ , ′ and contains
Boolean Homomorphism
If 𝑩 , + ,⋅ , ′ , 𝟎 , 𝟏 and 𝑪 ,𝖴 ,∩ , − , 𝑎 , 𝖰
are two Boolean algebras, then a
mapping 𝒇 ∶ 𝑩 → 𝑪 is called a Boolean
homomorphism, if all
the operations of Boolean algebra are
preserved (i.e) for any 𝒂 , 𝒃 ∈ 𝑩,
𝒇 𝒂+𝒃 = 𝒇 𝒂 𝖴 𝒇 𝒃 , 𝒇 𝒂.𝒃
=𝒇 𝒂 ∩𝒇 𝒃 ,
′
Isomorphic Boolean Algebras
Two Boolean algebras 𝑩 and 𝑩′ are said to
be isomorphic if there is a one-to-one
correspondence between 𝑩 and 𝑩
with (i.′ e)
respect to the three operations
there exists a mapping 𝒇 ∶ 𝑩 → 𝑩′
such that
𝒇 𝒂 + 𝒃 = 𝒇𝒂 + 𝒇 𝒃 ,
𝒇 𝒂 .𝒇𝒃=
𝒂′ 𝒇𝒂
= 𝒇. 𝒇 ′𝒃 ,
𝒂
and
Atom
Let 𝒂 and 𝒃 are t wo elements in a
lattice. The element 𝒃 is said to be a
c overof 𝒂 if
𝒂 < 𝒃 ((i. e) 𝒂 ≠ 𝒃 and 𝒂 < 𝒃) and there
is no element 𝒄 in the lattice such that 𝒂
< 𝒄 and
𝒄 < 𝒃.
If 𝒃 covers the element 𝒂, we write 𝒂 ≺ 𝒃.
An element which covers the element 𝟎
𝒙 𝒙
′ ′
+𝒚 𝒚 .
1. Simplify the Boolean expression
Solution :
𝒙 ′
𝒙 𝒚 ′ = 𝒙 ′ . 𝒚′ . 𝒙 ′ + 𝒚′
+𝒚
[By Demorgan ‟s
law]
= 𝒙 ′ . 𝒚′ . 𝒙 ′ + 𝒙 ′ . 𝒚′ . 𝒚′
[By Distributive law]
= 𝒙 ′ . 𝒚′ + 𝒙 ′ . 𝒚′
[By Idempotent law]
2. Simplify the Boolean expression
𝒂′ . 𝒃′. 𝒄 + 𝒂 . 𝒃′. 𝒄 + 𝒂′ . 𝒃′. 𝒄′ using
Boolean identities.
Solution :
𝒂′ . 𝒃′ . 𝒄 + 𝒂 . 𝒃′ . 𝒄 + 𝒂′ . 𝒃′ . 𝒄′
= 𝒂′ + 𝒂. 𝒃′ . 𝒄 + 𝒂′ . 𝒃′ . 𝒄′ [By
distributive law]
= 𝒂 + 𝒂′ . 𝒃′ . 𝒄′ + 𝒂′ . 𝒃′ . 𝒄′ [By
Commutative law]
= 𝟏. 𝒃′ . 𝒄 + 𝒂′ . 𝒃′ . 𝒄′ [By
= 𝒃′ . 𝒄 + 𝒃′ . 𝒂
′ . 𝒄′
[By Commutative law]
[By distributive
= 𝒃′′ . 𝒄 + 𝒂 ′
= 𝒃. 𝒄 + 𝒂 . 𝒄
′ . 𝒄′
law] [By distributive
+ 𝒄′ law]
= 𝒃′′ . 𝒄 + 𝒂′′ ′. 𝟏
= 𝒃 . 𝒄 +𝒃 . 𝒂
[By Complement
law]
[By Identity law and
Distributive law]
= 𝒂′ . 𝒃′ + 𝒃′ . 𝒄 [By Commutative law]
3. If 𝒂, 𝒃 ∈ 𝑺 = 𝟏, and 𝒂 + 𝒃 = 𝑳𝑪𝑴
𝟐, 𝟑, 𝟔 𝒂, 𝒃 ,
𝒂′ �
𝒂 ∗ 𝒃 = 𝑮𝑪𝑫 =𝟔 �
𝑺𝒃
𝒂, , + ,∗ ,′ , and
𝟏,𝟔
.
is a Show
Boolean algebra. that
Solution : The Hasse diagram is
6
2 3
𝟏 and 𝟔 are the zero and unit element of
1
𝑺 , + ,∗ ,′ , 𝟏 , 𝟔
If 𝒂 represents any of the elements 𝟏, 𝟐, 𝟑, 𝟔
of 𝑺
Clearly, 𝒂 + 𝟎 = 𝑳𝑪𝑴 𝒂, 𝟏 = 𝒂
and 𝒂. 𝟏 = 𝑮𝑪𝑫 𝒂, 𝟔 =𝒂
𝟏 + 𝟐 = 𝑳𝑪𝑴 = 𝟐 ; 𝟏. 𝟐 = 𝑮𝑪𝑫 = 𝟏
Hence, Identity laws hold hood.
𝟏, 𝟐 𝟏, 𝟐
𝟐 + 𝟏 = 𝑳𝑪𝑴 = 𝟐 ; 𝟐. 𝟏 = 𝑮𝑪𝑫 = 𝟏
𝟐, 𝟏
Therefore, 𝟐, 𝟏
Commutative laws is verified.
Let 𝟐, 𝟑, 𝟔
∈𝑺
𝟐 + 𝟑 + 𝟔 = 𝟐 + 𝑳𝑪𝑴 𝟑, 𝟔
= 𝟐 + 𝟔 = 𝑳𝑪𝑴 𝟐, 𝟔 =𝟔
𝟐 + 𝟑 + 𝟔 = 𝑳𝑪𝑴 + 𝟔 = 𝟔 + 𝟔 =
𝟐, 𝟑 𝑳𝑪𝑴 𝟔, 𝟔 =𝟔
𝟐. 𝟑. 𝟔 = 𝟐 + = 𝟐. 𝟑 = 𝑮𝑪𝑫 𝟐, 𝟑
𝟐. 𝟑 . 𝟔 = 𝑮𝑪𝑫 𝟐, 𝟑
𝑮𝑪𝑫 𝟑, 𝟔
+ 𝟔 = 𝟏. 𝟔 = 𝑮𝑪𝑫 𝟏, 𝟔
=𝟏
=𝟏
𝟐+ = 𝟐 + 𝑮𝑪𝑫 𝟑, 𝟔 =𝟐+𝟑
Therefore, Associative law is verified.
Let 𝟐, 𝟑, 𝟔 ∈ 𝑺
𝟑. 𝟔 = 𝑳𝑪𝑴 𝟐, 𝟑 = 𝟔
𝟐+ 𝟐 + 𝟔 = 𝑳𝑪𝑴 𝟐, 𝟑 . 𝑳𝑪𝑴 𝟐, 𝟔
= 𝟐. 𝑳𝑪𝑴 𝟑, 𝟔
𝟑 . = 𝟔. 𝟔 = 𝑮𝑪𝑫 𝟔, 𝟔 =𝟔
= 𝟐. 𝟔 = 𝑮𝑪𝑫 𝟐, 𝟔
𝟐. 𝟑 + 𝟐. 𝟔 = 𝑮𝑪𝑫 𝟐, 𝟑 + 𝑮𝑪𝑫 𝟐, 𝟔
𝟐. 𝟑 =𝟐
= 𝟏 + 𝟐 = 𝑳𝑪𝑴 𝟏, 𝟐 = 𝟐
+𝟔
Therefore, Distributive law is verified.
𝒂 + 𝒂′ = 𝑳𝑪𝑴 𝒂 = 𝑳𝑪𝑴 = 𝟔 (≡
,𝒂′ 𝒂 , 𝟔 𝟏)
�
= 𝟏 (≡
�
𝒂. 𝒂′ = 𝑮𝑪𝑫 𝒂 , 𝒂′
= 𝑮𝑪𝑫 𝒂, � 𝟎)
𝟔
�
Therefore, Complement laws hold good.
Thus all the five axioms of Boolean
algebra hold good.
Hence, 𝑺 , + ,∗ ,′ , 𝟏 , 𝟔 is a
Boolean algebra.