Discrete Mathematics and Graph Theory
Module 4 - Lattices and Boolean Algebra
Aarthy B
Department of Mathematics
School of Advanced Sciences
Vellore Institute of Technology
Chennai campus.
September 30, 2024
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 1 / 73
Contents
1 Introduction
2 Basic Ideas
3 Posets
4 Lattices
5 Properties of Lattices
6 Boolean Algebra
7 Problems on Boolean Algebra
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 2 / 73
Introduction
Introduction
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 3 / 73
Introduction
Introduction
In this chapter, two algebraic systems known as Lattices and
Boolean Algebra are discussed.
These structures are useful in sorting and searching and in the
construction of logical representations for computer circuits.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 4 / 73
Basic Ideas
Basic Ideas
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 5 / 73
Basic Ideas
Cartesian Product of sets
Let A and B be non-empty sets. The set of all ordered pairs (a, b), a ∈
A, b ∈ B, defined as the cartesian product of A and B and is defined
by A × B.
A × B = {(a, b) | a ∈ A, b ∈ B}
Example:
Let A = {1, 2}, B = {a, b, c}. Then
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 6 / 73
Basic Ideas
Note
A × B ̸= B × A. So, the product is not commutative.
If A has 2 elements and B has 3 elements, then A × B has
2 × 3 = 6 elements.
In general, if A has m elements and B has n elements, then
A × B has mn elements.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 7 / 73
Basic Ideas
Relation from A to B
Let A and B be non-empty sets. A relation from R from A to B is a
subset of A × B i.e. R ⊆ A × B.
If (a, b) ∈ R, we say that a is related to b by R and we denote it as
aRb.
Example:
Let A = {0, 1, 2, 3, 4}, B = {0, 1, 2, 3} and aRb if and only if a + b = 4.
Then, R = {(1, 3), (2, 2), (3, 1), (4, 0)}.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 8 / 73
Basic Ideas
Relation on A
A relation R from A to A is said to a relation on A.
Example:
1. Let R be the relation on A = {1, 2, 3, 4}, defined by aRb if a ≤
b; a, b ∈ A. Then
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
2. Let A = {cities in India} and B = {states in India}. Then R is a
relation from A to B if a city ′ a′ is in state ′ b′ .
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 9 / 73
Basic Ideas
Properties on Relations
Types Condition Using quantifiers
Reflexive ∀a ∈ A, (a, a) ∈ R ∀a [(a, a) ∈ R]
Symmetric whenever (a, b) ∈ R, ∀a ∀b [(a, b) ∈
then (b, a) ∈ R R] → [(b, a) ∈ R]
Antisymmetric whenever (a, b) ∈ R ∀a ∀b [(a, b) ∈
and (b, a) ∈ R, then R ∧ (b, a) ∈ R] →
a=b (a = b)
Transitive whenever (a, b) ∈ R ∀a ∀b ∀c [(a, b) ∈
and (b, c) ∈ R, then R ∧ (b, c) ∈ R] →
(a, c) ∈ R (a, c) ∈ R
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 10 / 73
Basic Ideas
Example 1
Let T = {set of triangles} and R = {(Ti , Tj ) | Ti is similar to Tj }.
(Ti , Ti ) ∈ R since Ti ||| Ti and this is true for all Ti ∈ R.
=⇒ R is reflexive.
Whenever (Ti , Tj ) ∈ R, then (Tj , Ti ) ∈ R.
i.e. whenever Ti ||| Tj , Tj ||| Ti .
=⇒ R is symmetric.
Whenever (Ti , Tj ) ∈ R and (Tj , Tk ) ∈ R, then (Ti , Tk ) ∈ R.
i.e. whenever Ti ||| Tj and Tj ||| Tk , then Ti ||| Tk .
=⇒ R is transitive.
Hence, R is an equivalence relation.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 11 / 73
Basic Ideas
Example 2
Let A = {1, 2, 3, 4} and
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}.
Since (3, 3) ∈
/ R1 , R1 is not reflexive.
Since (3, 4) ∈ R1 but (4, 3) ∈ / R1 , R1 is not symmetric.
Since (3, 4) ∈ R1 and (4, 1) ∈ R1 , but (3, 1) ∈ / R1 , R1 is not
transitive.
Since (1, 2) ∈ R1 and (2, 1) ∈ R1 , but 1 ̸= 2, R1 is not
antisymmetric.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 12 / 73
Basic Ideas
Example 2 Contd.
Let R2 = {(1, 1), (2, 2), (3, 3), (1, 3), (3, 1), (4, 4)}.
Since (a, a) ∈ R2 ∀a ∈ A, R2 is reflexive.
Since (1, 3) ∈ R2 and (3, 1) ∈ R2 , R2 is symmetric.
Since whenever (a, b) ∈ R2 and (b, c) ∈ R2 , then
(a, c) ∈ R2 ∀a, b, c ∈ A.
Not antisymmetric.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 13 / 73
Basic Ideas
Try!!
1 List the ordered pairs in the relation R from A = {0, 1, 2, 3, 4}
and B = {0, 1, 2, 3} where (a, b) ∈ R if and only if (i) a = b; (ii)
a + b = 4; (iii) a > b; (iv) a | b; (v) gcd(a, b) = 1 and (vi)
lcm(a, b) = 2.
2 Let R = {(a, b) |a ≤ b} where a and b belong to the set of
integers.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 14 / 73
Basic Ideas
Note
If |A| = n and R is a relation on the set A, then the [Link] relations on
2
the set A is 2n .
i.e. R ⊆ A×A and |A×A| = n2 . Then, [Link] subsets of |A×A| = 2n .
2
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 15 / 73
Posets
Posets
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 16 / 73
Posets
Partial order Relation
A relation R on a set A is called a partial order relation if R is reflexive,
antisymmetric and transitive.
Example:
In the set of integers Z, the relation R ”is less than or equal to” (≤) is
a partial order.
a ≤ a ∀a ∈ Z.
If a ≤ b and b ≤ a, then a = b.
If a ≤ b and b ≤ c, then a ≤ c.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 17 / 73
Posets
Partially Ordered set (Poset)
Let R be a partial order relation on A. Then the set A together with
R is called a partially ordered set or simply Poset and is denoted as a
pair (A, R).
Example:
(N, a ≤ b)
(N, a divides b)
(power({a, b, c}), ⊆)
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 18 / 73
Posets
Immediate Predecessor
An element x is an immediate predecessor of y or y is an immediate
successor of x if {z | x < z < y} = ∅.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 19 / 73
Posets
Poset Diagram or Hasse Diagram
A graph representing a poset but with only immediate predecessor edges
and the edges are oriented up from x to y when x < y.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 20 / 73
Posets
Procedure to draw Hasse Diagram
Start with the directed graph of finite poset (S, ≤).
Remove the loops at each vertex (Reflexive).
Remove all the directed edges which is present due to the
transitive relation.
Arrange each edge such that all the edges point upwards.
Finally, remove all the arrow heads.
The resulting diagram is called the Hasse diagram of (S, ≤).
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 21 / 73
Posets
Problem 1
Draw the Hasse diagram representing the partial ordering
R = {(a, b) | a divides b} on the set S = {1, 2, 3, 4, 6, 8, 12}.
Solution:
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 22 / 73
Posets
Problem 2
A = {1, 2, 3, 4} and the usual ≤ is the usual order relation. Then
(A, ≤) is a poset. Draw the Hasse diagram.
Solution:
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4).
Immediate Successors:
(1, 2), (2, 3), (3, 4).
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 23 / 73
Posets
Problem 3
Let S = {a, b, c}, then the power set P (S) = {∅, {a}, {b}, {c}, {a, b},
{a, c}, {b, c}, {a, b, c}} is a poset with respect to the relation inclusion
⊆. Draw the Hasse diagram.
Solution:
The immediate successors are:
∅ ⊆ {a}, ∅ ⊆ {b}, ∅ ⊆ {c}, {a} ⊆ {a, b}, {a} ⊆ {a, c}, {b} ⊆ {a, b},
{b} ⊆ {b, c}, {c} ⊆ {a, c}, {c} ⊆ {b, c}, {a, b} ⊆ {a, b, c},
{b, c} ⊆ {a, b, c}, {a, c} ⊆ {a, b, c}
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 24 / 73
Posets
Problem 3 Contd.
The Hasse diagram is:
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 25 / 73
Posets
Problem 4
Let A = {2, 3, 6, 12, 24, 36} and the relation ≤ is defined as a ≤ b if
a | b. Draw the Hasse diagram of (A, ≤).
Solution:
The immediate successors are:
(2, 6), (3, 6), (6, 12), (12, 24), (12, 36)
The Hasse diagram is:
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 26 / 73
Posets
Problem 5
Let D36 denote the set of divisors of 36 and the relation ≤ is defined
as a ≤ b if a | b. Draw the Hasse diagram of the poset (D36 , |).
Solution:
Given D36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}.
The immediate successors are:
(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (3, 9),
(4, 12), (6, 12), (6, 18), (9, 18), (12, 36), (18, 36)
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 27 / 73
Posets
Problem 5 Contd.
The Hasse diagram is:
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 28 / 73
Posets
Problem 6
Let D24 denote the set of divisors of 24 and the relation ≤ is defined
as a ≤ b if a | b. Draw the Hasse diagram of the poset (D24 , |).
Solution:
Given D24 = {1, 2, 3, 4, 6, 8, 12, 24}.
The immediate successors are:
(1, 2), (1, 3), (2, 4), (2, 6), (3, 6),
(4, 8), (4, 12), (6, 12), (8, 24), (12, 24)
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 29 / 73
Posets
Problem 6 Contd.
The Hasse diagram is:
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 30 / 73
Posets
Try!!
1. Let A = {1, 2, 3, 4} and let R be the relation ≤ on A. Draw the
Hasse diagram of R.
2. Let B = {2, 3, 4, 6, 12, 36, 48} and let S be the relation ”divides”
on B. Draw the Hasse diagram of S.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 31 / 73
Posets
Maximal and Minimal Element
Maximal Element:
An element of a poset is called maximal if it is not less than any element
of the poset. That is, a is maximal in the poset (S, ≤) if there is no
b ∈ S such that a < b.
Minimal Element:
An element of a poset is called minimal if it is not greater than any
element of the poset. That is, a is minimal if there is no element b ∈ S
such that b < a.
Note:
Maximal and minimal elements are easy to spot using a Hasse
diagram. They are the top and bottom elements in the
diagram.
The symbols < and ≤ are used as a general symbols for partial
orders.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 32 / 73
Posets
Greatest and Least Element
Greatest Element:
An element is called the greatest element if it is greater than all the
other elements in the poset. That is, a is the greatest element of the
poset (S, ≤) if b ≤ a for all b ∈ S. The greatest element is unique
when it exists.
Least Element:
An element is called the least element if it is less than all the other
elements in the poset. That is, a is the least element of the poset
(S, ≤) if b ≤ a for all b ∈ S. The least element is unique when it exists.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 33 / 73
Posets
Examples
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 34 / 73
Posets
Upper bound and Lower bound
Upper bound:
If u is an element of S such that a ≤ u for all elements a ∈ A, then u
is called an upper bound of A.
Lower bound:
If l is an element of S such that l ≤ a for all elements a ∈ A, then l is
called a lower bound of A.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 35 / 73
Posets
Least upper bound and Greatest lower bound
Least upper bound (Supremum):
The element x is called the least upper bound of the subset A if x is
an upper bound that is less than every other upper bound of A. The
least upper bound of A is unique if it exists.
Greatest lower bound (Infimum):
The element y is called the greatest lower bound of A if y is a lower
bound of A and z ≤ y whenever z is a lower bound of A. The greatest
lower bound of A is unique if it exists.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 36 / 73
Posets
Problem 1
Draw the Hasse diagram for D110 with respect to ”divisibility” relation.
Solution:
D110 = {1, 2, 5, 10, 11, 22, 55, 110}
The Hasse diagram is:
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 37 / 73
Posets
Problem 1 Contd.
Maximal Element 110
Minimal Element 1
Greatest 110
Least 1
Upper bound of {2, 11} 22 and 110
Least upper bound of {2, 11} 22
Lower bound of {10, 55} 5 and 1
Greatest lower bound of {10, 55} 5
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 38 / 73
Posets
Problem 2
Draw the Hasse diagram for D30 with a relation x ≤ y if and only if x
divides y.
Solution:
D30 = {1, 2, 3, 5, 6, 10, 15, 30}.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 39 / 73
Posets
Problem 2 Contd.
Maximal Element 30
Minimal Element 1
Greatest 30
Least 1
Upper bound of {2, 5} 10 and 30
Least upper bound of {2, 5} 10
Lower bound of {6, 15} 3 and 1
Greatest lower bound of {6, 15} 3
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 40 / 73
Posets
Problem 3
Let D30 = {1, 2, 3, 5, 6, 10, 15, 30} and let the relation D be divisor on
D30 (i.e. xRy if x divides y). Find i) all lower bounds of 10 & 15, ii)
the GLB of 10 & 15, iii) all upper bounds of 10 & 15, iv) the LUB of
10 & 15, v) Draw the Hasse diagram for D30 with D.
Solution:
The Hasse diagram is:
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 41 / 73
Posets
Problem 3 Contd.
i) All lower bounds of 10 & 15 are 1 & 5.
ii) The GLB of 10 & 15 is 5.
iii) Upper bound of 10 & 15 is 30.
iv) The LUB of 10 & 15 is 30.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 42 / 73
Lattices
Lattices
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 43 / 73
Lattices
Definition
Definition:
A lattice is a poset (L, ≤) in which every pair of elements has a LUB
and GLB in L.
Note:
1. Since a Lattice L is an algebraic system with binary operations ∨
and ∧, it is denoted by
[L, ∨, ∧] or [L, ⊕, ∗]
2. To check for a lattice, it is enough to consider pairwise unrelated
elements.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 44 / 73
Lattices
Remark
LUB of a subset {a, b} is denoted by a ∨ b = a ⊕ b (also termed
as Join)
GLB of a subset {a, b} is denoted by a ∧ b = a ∗ b (also termed as
Meet)
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 45 / 73
Lattices
Example 1
Consider the Poset ({1, 2, 4, 8, 16}, |). Then, the Hasse diagram is
Clearly, for every pair of elements, there is a GLB and LUB. Hence, it
is a lattice.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 46 / 73
Lattices
Example 2
Let n be a positive integer and Sn be the set of all divisors of n.
For instance, S6 = {1, 2, 3, 6} and D denote the divisibility relation.
Clearly, this is a lattice.
Not a Lattice:
This is not a lattice, as there is no LUB of {2, 3}. Similarly, LUB of
{2, 5} does not exist.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 47 / 73
Lattices
Problem 1
Check whether the following Hasse diagrams are Lattices or not.
Solution:
LU B(a, b) = b; LU B(c, d) = e
GLB(a, b) = a; GLB(c, d) = b
Since every pair of this poset has LUB and GLB, the given poset is a
Lattice.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 48 / 73
Lattices
Problem 1 Contd.
Solution:
LU B(a, b) = c
GLB(a, b) = Doesn’t exist
Since the pair a and b does not have a greatest lower bound in this
poset, the given poset is not a Lattice.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 49 / 73
Lattices
Problem 1 Contd.
Solution:
U B(b, c) = {d, e, f }
LU B(b, c) = Does not exist because it is not unique.
Since LUB of b and c is not unique, we conclude that the given poset
is not a Lattice.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 50 / 73
Lattices
Problem 2
Draw the Hasse diagram for S110 with respect to ”divisibility relation”
and check whether it is a Lattice.
Solution:
S110 = {1, 2, 5, 10, 11, 22, 55, 110}
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 51 / 73
Lattices
Problem 3
If P (S) is the power set of a set S and ∪ and ∩ are taken as the join
and intersection, then prove that (P (S), ⊆) is a Lattice.
Solution:
W.K.T (P (S), ⊆) is a Poset.
For Lattice, a + b and a.b must exist ∀ a, b ∈ L.
Here, let A and B be the two elements of P (S). i.e. A and B are the
subsets of S.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 52 / 73
Lattices
Problem 3 Contd.
Least Upper Bound:
W.K.T, A ⊆ A ∪ B and B ⊆ A ∪ B. Then, A ∪ B is an upper bound
for (A, B).
Let C ∈ P (S) such that A ⊆ C and B ⊆ C, then A ∪ B ⊆ C.
Therefore, LU B(A, B) = A ∪ B.
Greatest Lower Bound:
W.K.T, A ∩ B ⊆ A and A ∩ B ⊆ B, then A ∩ B is a lower bound for
(A, B).
Let C ∈ P (S) such that C ⊆ A and C ⊆ B, then C ⊆ A ∩ B.
Therefore, GLB(A, B) = A ∩ B.
Since every pair of elements of P (S) has both LUB and GLB, (P (S), ⊆)
is a Lattice.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 53 / 73
Lattices
Problem 4
Let L = {1, 3, 5, 7, 15, 21, 35, 105} and let ≤ be the relation ”divides”
on L. Find i) Upper bounds of 3 & 7, ii) LUB of 3 & 7, iii) Lower
bounds of 15 & 21, iv) GLB of 15 & 21, v) Upper bound and Lower
bound of 15 & 35, vi) LUB and GLB of 15 & 35.
Solution:
Since 1 divides every element in L, 1 is the least element and since
every element in L divides 105, 105 is the greatest element.
∴ (L, |) is a Lattice.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 54 / 73
Lattices
Problem 4 Contd.
i)Upper bounds of 3 & 7 are 21 & 105.
ii)LUB of 3 & 7 is 21.
iii)Lower bounds of 15 & 21 are 1 & 3.
iv) GLB of 15 & 21 is 3.
v) Upper bound of 15 & 35 is 105. Lower bound of 15 & 35 are 1 &
5.
vi) LUB of 15 & 35 is 105. GLB of 15 & 35 is 5.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 55 / 73
Properties of Lattices
Properties of Lattices
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 56 / 73
Properties of Lattices
Properties of Lattices
Let (L, ≤) be a Lattice. Then for a, b, c ∈ L.
Idempotent Law: a ∨ a = a and a ∧ a = a
Commutative Law: a ∨ b = b ∨ a and a ∧ b = b ∧ a
Associative Law: a ∨ (b ∨ c) = (a ∨ b) ∨ c and
a ∧ (b ∧ c) = (a ∧ b) ∧ c
Absorption Law: a ∨ (a ∧ b) = a and a ∧ (a ∨ b) = a
a ≤ b ⇔ (a.b = a) ⇔ (a + b = b)
Isotonic Property: b ≤ c ⇒ (a.b) ≤ (a.c), (a + b) ≤ (a + c)
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 57 / 73
Properties of Lattices
Properties of Lattices Contd.
A lattice is complete if each of its nonempty subsets has a LUB
and a GLB. Every finite lattice is complete. (A lattice is finite if
its underlying set is finite).
The least and greatest elements of a lattice are called the bounds
of the lattice. They are denoted by 0 and 1 respectively. A lattice
which has both elements 0 and 1 is called Bounded lattice. A
bounded lattice s denoted by (L, +, ., 0, 1) or (L, ∨, ∧, 0, 1).
A lattice L is distributive if for any a, b, c ∈ L,
a.(b + c) = (a.b) + (a.c) and a + (b.c) = (a + b).(a + c).
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 58 / 73
Boolean Algebra
Boolean Algebra
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 59 / 73
Boolean Algebra
Definition
A lattice which is complemented and distributive is called a
Boolean Algebra.
If B is a non empty set with two binary operations + and . and
unary operation ′ with two distinct elements 0 and 1, then B is
called a Boolean algebra if it satisfies the following conditions
∀a, b, c ∈ B
a + 0 = a, a.1 = a (Identity laws)
a + b = b + a, a.b = b.a (Commutative laws)
a + (b + c) = (a + b) + c, a.(b.c) = (a.b).c (Associative laws)
a + (b.c) = (a + b).(a + c), a.(b + c) = (a.b) + (a.c) (Distributive laws)
a + a′ = 1, a.a′ = 0 (Negation laws)
Boolean Algebra is denoted as (B, ., +, 0, 1).
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 60 / 73
Boolean Algebra
Laws
Identity: a + 0 = a, a.1 = a
Commutative: a + b = b + a, a.b = b.a
Associative: a + (b + c) = (a + b) + c, a.(b.c) = (a.b).c
Distributive: a + (b.c) = (a + b).(a + c), a.(b + c) = (a.b) + (a.c)
Negation: a + a′ = 1, a.a′ = 0
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 61 / 73
Boolean Algebra
Laws
Idempotent: a + a = a, a.a = a
Dominance: a + 1 = 1, a.0 = 0
Absorption: a + (a.b) = a, a.(a + b) = a
De Morgan’s laws: (a + b)′ = a′ .b′ , (a.b)′ = a′ + b′
Involution or Double complement law: (a′ )′ = a
Zero law and One law: 0′ = 1, 1′ = 0
Duality: a + a.(b + 1) = a whose dual is a.(a + b.0) = a
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 62 / 73
Problems on Boolean Algebra
Problems on Boolean Algebra
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 63 / 73
Problems on Boolean Algebra
Problem 1
Simplify the Boolean expression a′ .b′ .c + a.b′ .c + a.b′ .c′ , using Boolean
algebra identities.
Solution:
a′ .b′ .c + a.b′ .c + a.b′ .c′
= a′ .b′ .c + a.b′ .(c + c′ ) (Distributive)
= a′ .b′ .c + a.b′ .1 (Negation)
= b′ .(a + a′ .c) (Distributive)
= b′ .(a + a′ ).(a + c) (Distributive)
= b′ .1.(a + c) (Negation)
= a.b′ + b′ .c (Distributive)
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 64 / 73
Problems on Boolean Algebra
Problem 2
In any Boolean algebra, show that ab′ + a′ b = 0 if and only if a = b.
Solution:
(i) Let a = b. Then,
ab′ + a′ b = aa′ + a′ a
= 0 + 0 (Negation)
=0
(ii) Let ab′ + a′ b = 0. Then (1)
a + ab′ + a′ b = 0 + a
a + a′ b = a (Absorption)
(a + a′ ).(a + b) = a (Distributive)
a + b = a (Negation) (2)
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 65 / 73
Problems on Boolean Algebra
Problem 2 Contd.
Similarly, from (1),
ab′ + a′ b + b = 0 + b
ab′ + b = b (Absorption)
(a + b).(b + b′ ) = b (Distributive)
(a + b).1 = 1 (Negation) (3)
From (2) and (3),
a=b
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 66 / 73
Problems on Boolean Algebra
Problem 3
In any Boolean algebra, show that (a + b′ )(b + c′ )(c + a′ ) = (a′ + b)(b′ +
c)(c′ + a).
Solution:
LHS = (a + b′ + 0)(b + c′ + 0)(c + a′ + 0)
= (a + b′ + cc′ )(b + c′ + aa′ )(c + a′ + bb′ ) (Negation)
= (a + b′ + c)(a + b′ + c′ )(b + c′ + a)(b + c′ + a′ )
(c + a′ + b)(c + a′ + b′ ) (Distributive)
= [(b + c′ + a′ )(c + a′ + b)][(c + a′ + b′ )(a + b′ + c)]
[(a + b′ + c′ )(b + c′ + a)] (Associative)
= (a′ + b + cc′ )(b′ + c + aa′ )(c′ + a + bb′ ) (Distributive)
= (a′ + b + 0)(b′ + c + 0)(c′ + a + 0) (Negation)
= (a′ + b)(b′ + c)(c′ + a) (Identity)
= RHS
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 67 / 73
Problems on Boolean Algebra
Problem 4
Simplify the following Boolean expression using Boolean algebra:
i) xy ′ + z + (x′ + y)z ′
ii) (x + y + xy)(x + z)
iii) x[y + z(xy + xz)′
Solution:
i) xy ′ + z + (x′ + y)z ′ = (xy ′ + z) + (xy ′ + z)′ (De Morgan’s law)
=1 (a + a′ = 1)
ii) (x + y + xy)(x + z) = (x + y)(x + z) (Absorption)
= xx + xz + xy + yz
= x + xy + yz (Absorption)
= x + yz (Absorption)
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 68 / 73
Problems on Boolean Algebra
Problem 4 Contd.
iii) x[y + z(xy + xz)′ = x[y + z(xy)′ (xz)′ ] (De Morgan’s law)
= x[y + z(x′ + y ′ )(x′ + z ′ )] (De Morgan’s law)
= x[y + z(x′ + x′ z ′ + y ′ x′ + y ′ z ′ )]
= x[y + z(x′ + y ′ x′ + y ′ z ′ )] (Absorption)
= x[y + z(x′ + y ′ z ′ )] (Absorption)
= x[y + zx′ + y ′ zz ′ ]
= x(y + zx′ )
= xy + zxx′
= xy
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 69 / 73
Problems on Boolean Algebra
Problem 5
Find the Disjunctive normal formals of the following Boolean expressions
by (i) Truth table method (ii) Algebraic method.
a) f (x, y, z) = xy + yz ′
b) f (x, y, z) = y ′ + [z ′ + x + (yz)′ ](z + x′ y)
Solution: a)i)
x y z xy yz ′ f
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 1 1
0 1 1 0 0 0
1 0 0 0 0 0
1 0 1 0 0 0
1 1 0 1 1 1
1 1 1 1 0 1
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 70 / 73
Problems on Boolean Algebra
Problem 5 Contd.
The minterms corresponding to the 3 rows for which 1 occurs in the f
column are x′ yz ′ , xyz ′ and xyz.
∴ DNF of f (x, y, z) = x′ yz ′ + xyz ′ + xyz.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 71 / 73
Problems on Boolean Algebra
Problem 5 Contd.
b) i) g = z ′ + x′ + (yz)′ , h = z + x′ y
x y z yz (yz)′ g x′ y h gh f = y ′ + gh
0 0 0 0 1 1 0 0 0 1
0 0 1 0 1 1 0 1 1 1
0 1 0 0 1 1 1 1 1 1
0 1 1 1 0 0 1 1 0 0
1 0 0 0 1 1 0 0 0 1
1 0 1 0 1 1 0 1 1 1
1 1 0 0 1 1 0 0 0 0
1 1 1 1 0 1 0 1 1 1
DNF = x′ y ′ z ′ + x′ y ′ z + x′ yz ′ + xy ′ z ′ + xy ′ z + xyz.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 72 / 73
Problems on Boolean Algebra
Problem 5 Contd.
Aarthy B (VIT Chennai) Boolean Algebra September 30, 2024 73 / 73