Study Material

DIGITAL SYSTEM DESIGN (PCC-ECR302)

MODULE II
BOOLEAN ALGEBRA AND MINIMIZATION TECHNIQUE

Table of Contents

Content Page No

2.1 Introduction 2.3

2.2 Boolean logic operations 2.3
2.3 Basic Laws of Boolean Algebra 2.4
2.3.1 Basic OR, AND, NOT laws of Boolean algebra 2.4
2.3.2 Commutative Law 2.6
2.3.3. Associative Law 2.6
2.3.4 Distributive Law 2.6
2.3.5 Absorption Law 2.6
2.3.6 Boolean Identity 2.7
2.4. De Morgans’s theorems 2.8
2.5 Simplification of Boolean Expression 2.9
2.6 Sum of Products (SOP) and Product of Sums (POS) 2.13
2.6.1 Minterm and Maxterm 2.14
2.6.2 Canonical Sum of Product or Sum-of-Minterms (SOM) 2.15
2.6.3 Canonical product of sum or Product-of-Maxterms (POM) 2.16
2.7 KARNAUGH MAP 2.17
2.7.1 Minimization using K-Maps 2.19
2.7.2 Don’t care condition: 2.28
2.8 Examples on K - Map 2.28
2.9 Exercise 2.34
2.1 Introduction:
Boolean algebra is a mathematical system that deals with binary variables and logical operations. It was
introduced by George Boole in the mid-19th century and has since become fundamental to digital
electronics, computer science, and various other fields related to logic and information processing.
In Boolean algebra, variables can take only two values: true (1) and false (0). These values are often
represented as 1 and 0, respectively, but they can also be represented by other symbols, such as "T" and
"F", "on" and "off", or "high" and "low."
2.2 Boolean logic operations
The basic logical operations in Boolean algebra are:
2.3 Basic Laws of Boolean Algebra
The rules, laws and theorems of Boolean algebra can be used to simplify many a complex Boolean
expression and also to transform the given expression into a more useful and meaningful equivalent
expression. Similar to real algebra, the Boolean algebra also possess certain well – defined rules and laws.
Let us now discuss the most important laws of Boolean algebra.
2.3.1 Basic OR, AND, NOT laws of Boolean algebra

Proof of A.1=A

A LHS= 1.A RHS=A

0 1.0 = 0 0
1 1.1 = 1 1

Proof of 0.A = 0

A LHS= 0.A RHS=0

0 0.0 = 0 0
1 0.1 = 1 0

Proof of A.A = A

A LHS= A.A RHS=A

0 0.0 = 0 0
1 1.1 = 1 1
Proof of 1+A=1

A LHS= 1+A RHS=1

0 1+0 = 1 1
1 1+1 = 1 1

Proof of 0+A=A

A LHS= 0+A RHS=A

0 0+0 = 0 0
1 0+1 = 1 1

Proof of A+A=A

A LHS= A+A RHS=A

0 0+0 = 0 0
1 1+1 = 1 1

Proof of A + 𝐀̅=1

A LHS= A + A RHS=1
0 0+1 = 1 1
1 1+0 = 1 1

Proof of A . 𝐀̅=0

A LHS= A . A RHS=0
0 0.1 = 0 0
1 1.0 = 0 0
2.3.2 Commutative Law

This law indicates that the order of application of two separate terms is not important.

A  B B A
A  B  B A
2.3.3. Associative Law

This law enables the removal of the brackets from the expression and regrouping of the variables.

A  B  C  A  B  C
A   B C  A  B  C

2.3.4 Distributive Law

This law allows the multiplying or factoring out an expression

A(B C)  A B  AC

2.3.5 Absorption Law

1. A  A B  A

Proof:

A  AB
 A 1  A  B
 A  (1  B)
 A 1  A
2. A  (A  B)  A
Proof:

A  (A  B)
 AA  AB
 A  AB
 A  (1  B)
 A 1  A
3. A  AB  A  B
Proof:

A  AB
 
 A  A   A  B
 A  BC  (A  B)  (A C)
 1  A  B
AB

 
4. A  A  B  A  B
Proof:



A A  B 
 AA  AB
 AB
2.3.6 Boolean Identity

A  BC  (A  B)  (A  C)

Proof:

A  B C
 A 11  B C
 A  (1  B)  (1  C)  B C
 A (1  B C B C)  B C
 A A B A C A B C B C
 A A B A C B C (1  A)
 A  A  A  B  A  C  B C
 A  (A B)  C  (A  B)
 (A B)  (A C)
2.4. De Morgans’s theorems

De Morgan, a mathematician and a logician, proposed two theorems to enrich the Boolean algebra.

Theorem-1: The complement of product is equal to the sum of complements. It also states that the
complement of two or more variables ANDed together is equivalent to ORing of complements of individual
two or more variables.

A  B  AB
Proof using truth table:

A B A+B 𝐀̅ 𝐁̅ 𝐀̅̅+̅̅𝐁̅̅ 𝐀̅. 𝐁̅

0 0 0 1 1 1 1

0 1 1 1 0 0 0

1 0 1 0 1 0 0

1 1 1 0 0 0 0

Theorem-2: The complement of sum is equal to the product of complements. It also states that the
complement of two or more variables ORed together is equivalent to the ANDing of the complements of
individual two or more variables.

AB  A  B

Proof using truth table:

A B AB 𝐀̅ 𝐁̅ 𝐀̅̅𝐁̅ 𝐀̅ + 𝐁̅

0 0 0 1 1 1 1

0 1 0 1 0 1 1

1 0 0 0 1 1 1

1 1 1 0 0 0 0

Theorem-3
 A  B  C  .....  A  BC
Theorem-4

A  BC  A  B  C  .......
2.5 Simplification of Boolean Expression

 
Example 2.1. Simplify: Y  A  B A  B

Y   A  B    A  B


 B AA
 B0 B
Example 2.2. Simplify: Y  A  BC  A  BC  A  BC  A  BC

Y  A  B C  A  B C  A  B C  A  B C


 
 AC B  B  AC B B  
 A C  A C



C A  A 
C
Example 2.3. Simplify: A  B  A  BC  A  (B  AB)

Solution:
A  B  A  B C  A  (B  AB)

 
 A  B  B C  A  (B  A)

 A   B  B C  A  (B  A)

 A   B  C  A  (B  A)

 AB AC AB AA

 AB AC AB A

 A  B  A  C  A  (B  1)

 AB AC A

  
 A B  A C  A

  A  B    A  C  A

  A  B   A  C  A

  A  B C  A

 A  B C  A
 1  B C
1 0

Example 2.4. Simplify: Y  A  A  B  A  BC  A  BC D

Y  A  A  B  A  B C  A  B C  D
 A  B  A  B C  A  B C  D
 A  B  B C  A  B C  D
 A  B  C  A  B C  D
 A  B  C  B C  D
 A  B C  CD
 ABCD
Example 2.5. If, A  B  A  B  C , then prove A  C  A  C  B

AC  AC

  
 A  A  B  A  B  A  AB  AB 
 A   A  B    A  B  A  A  B  A  A  B
  A  A  A  B    A  B  A  B
 A  B  A  B B  A  B
 
 A  B 1  B  A  B
AB AB

 B A  A  B 
Example 2.6. Simplify: Y  AB AB AB

Y  AB  AB  AB

 A  A B  AB 
 B  AB
 BA
Example 2.7. Simplify: Y  A  AB AB

Y  A  AB  AB
 A(1  B)  AB
 A  AB
AB
Example 2.8. Simplify: Y  A  BC  A  BC  A  BC
 Y  ABC  ABC  ABC
 
 AC B  B  ABC

 AC  ABC

 A C  BC 
 AB  C

Example 2.9. Prove: A  B  BC  BC  A  B  C

AB  BC  BC


 AB  C B  B 
 AB  C

Example 2.10. Simplify: Y  A CA  B D  A  BC D  A  BC

Y  ACABD  ABCD  ABC

 AC A  B  D  ABCD  ABC
 


 AAC  ACB  ACD  ABCD  ABC

 ABC  ACD  ABCD  ABC

 
 BC A  A  AD C  BC  
 BC  ADB  C

Example 2.11. Prove: A  BC  A  BC  A  BC  A  B C  A  B C  A  B  C
ABC  ABC  ABC  ABC  ABC

 
 AB C  C  AB C  C  ABC  
 AB  AB  ABC


 A B  B  ABC
 A  ABC
 A  BC
 ABC
2.6 Sum of Products (SOP) and Product of Sums (POS)

Sum of Products (SOP) and Product of Sums (POS) are two common forms of Boolean expressions used
in digital logic and Boolean algebra. They are used to represent logic functions that depend on multiple
binary variables

The logical sum of two or more logical product terms, is called sum of products expression. In SOP form,
a logic function is represented as the sum (OR) of multiple product terms (AND). Each product term
consists of one or more variables (either in their true or complemented form). The SOP form is also known
as the Canonical Sum of Products or the Disjunctive Normal Form (DNF).
Y  A  B  B C  C  A

A product of sums expression is a logical product of two or more logical sum terms. In POS form, a logic
function is represented as the product (AND) of multiple sum terms (OR). Each sum term consists of one
or more variables (either in their true or complemented form). The POS form is also known as the Canonical
Product of Sums or the Conjunctive Normal Form (CNF).

Y  A  B  B  C  C  A
Each individual term in canonical SOP form is known as Minterm (e.g. ABC) and each individual term in
canonical POS form is known as Maxterm (e.g. A’B’C’).

SOP from can be converted to canonical SOP by ANDing the term with the ORing term of missing variable
and its complement.
2.6.1 Minterm and Maxterm
A minterm is a product term (ANDed combination) that includes all the input variables of a logic function,
where each variable appears either in its true form (positive) or complemented form (negative). A minterm
is true (1) only for a specific combination of inputs for which the output of the logic function is 1.

A B Minterms

0 0 m AB
0

0 1 m AB
1

1 0 m AB
2

1 1 m AB
3

A B C Minterms

0 0 0 m0 ABC

0 0 1 m1 AB𝐶

0 1 0 m2 A𝐵C

0 1 1 m3 A𝐵𝐶

1 0 0 m4 ABC

1 0 1 m5 ABC

1 1 0 m6 ABC

1 1 1 m7 ABC
A maxterm is a sum term (ORed combination) that includes all the input variables of a logic function, where
each variable appears either in its true form (positive) or complemented form (negative). A maxterm is false
(0) only for a specific combination of inputs for which the output of the logic function is 0.

A B Maxterms

0 0 M0 A+B

0 1 M1 A+B

1 0 M2 A+B

1 1 M3 A+B

A B C Maxterms
0 0 0 m0 A+B+C
0 0 1 m1 A+B+C
0 1 0 m2 A+B+C
0 1 1 m3 A+B+C
1 0 0 m4 A+𝐵+𝐶
1 0 1 m5 A+𝐵+C
1 1 0 m6 A+B+𝐶

1 1 1 m7 A+B+C

2.6.2 Canonical Sum of Product or Sum-of-Minterms (SOM)

The Canonical Sum of Products (SOP) form, also known as the Sum of Minterms (SOM) or Disjunctive
Normal Form (DNF), is a unique representation of a logic function using minterms. In this form, each
minterm that produces a true output (1) is written as a product (AND) of the input variables, where each
variable is either in its true form (positive) or complemented form (negative). To represent a logic function
using the Canonical SOP form, all the minterms for which the output of the function is true (1), and then
write each minterm as a product term.
2.6.3 Canonical product of sum or Product-of-Maxterms (POM)

The Canonical Product of Sums (POS) form, also known as the Product of Maxterms (POM) or Conjunctive Normal
Form (CNF), is a unique representation of a logic function using maxterms. In this form, each maxterm that produces
a false output (0) is written as a sum (OR) of the input variables, where each variable is either in its true form (positive)
or complemented form (negative). To represent a logic function using the Canonical POS form, list all the maxterms
for which the output of the function is false (0), and then write each maxterm as a sum term.
Example 2.12. Obtain the canonical sum of product form of the function
Y(A, B)  A  B

Solution:

Y(A, B)  A  B
 A 1  B1


 
 A  B  B  B A  A  
 A  B  A  B  B A  B A
 AB AB AB
Example 2.13: Obtain the canonical sum of product form of the function
Y(A, B,C)  A  BC

Solution:

Y(A, B,C)  A  BC
  
 A  B  B  C  C  B C  A  A  
  
 A  B  A  B  C  C  B C A  B C A
 A  B C  A  B C  A  B C  A  B C  B C A  B C A
 A  B C  A  B C  A  B C  A  B C  A  B C
Example 2.14: Obtain the canonical product of sum form of the function
Y(A,B,C)  A  BC
Solution:
Y(A, B,C)  A  BC
 
 A  B   A  C

  A  B  C  C    A  C  B B
  A  B  C    A  B  C    A  B  C   A  B  C
 A  B C  (A  B)  (A  C)
  
 A  B  C  A  B  C   A  B  C

2.7 KARNAUGH MAP

A Karnaugh map, also known as a K-map, is a graphical tool used in digital logic to simplify Boolean
expressions and minimize logic functions. It is an efficient method to visually identify patterns and common
terms in truth tables, which helps in reducing the number of logic gates required to implement a given logic
function. Karnaugh maps are used for logic functions with multiple input variables, typically ranging from
2 to 6 variables (although they can be used for more variables as well). The K-map arranges all possible
combinations of input values in a two-dimensional grid, with each cell representing a specific combination
of inputs.
A Karnaugh map (K-map) is a graphical method used to minimize Boolean expressions without using
Boolean algebra rules, laws and theorems.

The K-map consists of a number of squares called cells. Each square cell represents a minterm (or
maxterm). Figures indicate graphical representation of k-maps for 2, 3 and 4 variables.
In K-map, rows and columns are assigned the binary code (particularly Gray code) such that two adjacent
rows or columns differ only in one bit. In addition, the column on extreme left is adjacent to column on the
extreme right. Similarly, the top row is adjacent to the bottom row.
Two cells are said to be adjacent if they are physically adjacent to each other or made adjacent by wrapping
left to right column or to and bottom rows.

The K-map indicates representation of 2n cells for n=2,3 and 4. Each cell represents the minterm and the
minterm number is written in each cell. Any Boolean function can be represented by placing ‘1’ in the cell
corresponding to presence of minterm.
2.7.1 Minimization using K-Maps

Karnaugh maps contain exactly the same information as truth tables. The difference is that the Karnaugh
map uses a 'matrix' format to hold the output values. The Karnaugh map is arranged so that, as far as
possible, logically adjacent product terms are also adjacent in the 'matrix' and so can be logically combined
hence minimized. Essentially the minimization process, described using Boolean algebra is performed
visually.

The procedure for minimization using K-map is

 Write a minterm Boolean expression from a truth table. Each 1 in Output column of truth table
produces ANDed term. These ANDed terms are ORed to form sum-of-products (minterms).
 Draw the K-map with the desired number of cells.
 Fill the cells by 1 where the product term (minterm) is present. Each ANDed set of variables from
the minterm is placed in appropriate square of the map. The map is just a very special output column
of the truth table.
 Group/ Draw loops around neighboring cells in pairs (2) or quads (4) or octets (8) 1s together on
the map.
 Eliminate the variable. When a variable and its complement are within a loop, that variable is
eliminated.
 OR the terms that remain to generate simplified minterm Boolean expressions.
3- variables K-Map

A Karnaugh map (K-map) for a 3-variable function has 8 cells arranged in a 2x4 grid. Each cell in the grid
represents a specific combination of input variables. The three variables (A, B, and C) are organized in a
systematic way to form the K-map.
4- variables Kmap

A Karnaugh map (K-map) for a 4-variable function has 16 cells arranged in a 4x4 grid. Each cell in the grid
represents a specific combination of input variables. The four variables (A, B, C, and D) are organized in a
systematic way to form the K-map.
2.7.2 Don’t care condition:

In certain digital systems, some input combinations never occur during the process of a normal operation
because those input conditions are guaranteed never to occur. Such inputs combinations are don’t care
conditions. The don’t care combinations are represented by d or x. The values of this combinations are not
specified i.e. either 1 or 0.

2.8 Examples on K - Map

Example 2.15. Simplify the following expression using K-map: F(A,B,C)= Ʃm (0,1,2,5,6)
Example 2.16. Simplify the following expression using K-map method:
F= Ʃm (7,9,10,11,12,13,14,15)

F  A  B  A  C  A  D  B C  D

Example 2.17. Simplify the following expression using K-map method:

F= Ʃ m (1,5,10,11,12,13,15)
Alternative Method:

Example 2.18. Simplify the following expression using K-map method:

Y (A, B, C, D) = Σ m (1, 3, 4, 6, 9, 11, 12, 14)

Example 2.19. Simplify the following expression using K-map method:

Y (A, B, C, D) = Σ m (1, 3, 4, 5,6,7,9,11,12,13,14,15)

Example 2.20. Simplify the following expression using K-map method:

Y (A, B, C, D) = ∏M (0,1,4,5,6,8,9,12,13,14)

Example 2.21. Simplify the following expression using K-map method:

F(A,B,C,D)=ΠM(0,1,2,3,7,8,9,10,11,14)
Example 2.22. Simplify the following expression using K-map method:

F(A,B,C,D) = Σ m (1,3,7,11,15) + Σ d (0,2,5)

Example 2.23. Simplify the following expression using K-map method:

F(A,B,C,D) = Σ m (0,2,3,6,7) + Σ d (8,10,11,15)

2.9 Exercise

A. Choose the correct alternative from the following

1. What is the outcome of a Boolean expression "A AND NOT A"?
a) 0
b) 1
c) A
d) NOT A

2. What is the relationship between Boolean algebra and logic gates?

a) Boolean algebra represents complex numbers
b) Logic gates represent Boolean operations
c) Boolean algebra focuses on calculus
d) Logic gates represent arithmetic operations

3. The NOT operation in Boolean algebra is also known as:

a) Inversion
b) Negation
c) Complement
d) All of the above

4. Which law of Boolean algebra states that "A AND 1 = A"?

a) Complement law
b) Identity law
c) Involution law
d) Null law

5. The Boolean expression "A + A'B" is simplified to:

a) A
b) B
c) A' + B
d) AB

6. Which of the following represents a Boolean expression for the XOR gate?
a) A + B
b) A · B
c) A ⊕ B
d) A B

7. The duality principle in Boolean algebra states that:

a) OR can be transformed into AND
b) NOT can be transformed into AND
c) AND can be transformed into OR
d) XOR can be transformed into AND
8. The Boolean expression "A + A'B + A'C" can be simplified to:
a) A
b) B
c) C
d) AB + AC

9. The Boolean expression "A(B + C)" can be expanded using which law?
a) Absorption
b) Complement
c) Distributive
d) Inversion

10. How can a Boolean equation be converted into its complement form?
a) By swapping AND and OR operators
b) By replacing AND with OR and vice versa
c) By replacing all variables with their complements
d) By using De Morgan's theorem

B. Short Answer Type Question

11. Simplify the Boolean expression A'B + AB + A' using Boolean algebra.
12. Use Boolean algebra to simplify the expression AB + A'B' + AB'.
13. Simplify the Boolean Equation A + AB using algebraic manipulation.
14. Apply Boolean algebra to simplify the expression A'B + AB'.
15. Simplify the Boolean equation AB + BC + AC using algebraic methods.
16. Use Boolean algebra to simplify the expression A + AB' + A'B.
17. Simplify the Boolean function AB + A'BC + AC using algebraic manipulation.
18. Apply Boolean algebra to simplify the expression A + AB' + AB.
19. Simplify the Boolean equation (A + B')(B + C) using Boolean algebra.
20. Use algebraic manipulation to simplify the expression A(B' + C) + B(A' + C).

C. Long Answer Type Question: Simplify the following expressions using K-map method:

21. Y(A,B,C,D)= Ʃm(0,2,5,7,8,10,13,15)

22. F= Ʃm(0,1,3,5,6,11,15)
23. Y(A,B,C)=A’B’C’+AB’C+A’B’C+ABC’+AB’C’+ABC
24. F(A,B,C,D) = ΠM (0,1,3,8,10,15) + Πd (11,13,14)
25. F(A,B,C,D) = Σ m (0,4,7,9,13,15) + Σ d (10,14)
26. F(A,B,C,D) = Σ m (1,3,4,5,9,11,14,15) + Σ d (2,6,7,8)
27. F(A,B,C,D) = Σ m (0,2,3,6,7) + Σ d (8,10,11,15)
28. F(A,B,C)= Ʃm (0,1,2,3,6,7)
29. Y(A,B,C)= Ʃm (0,1,3,4,5)