chapter

Boolean Algebra, Canonical Forms and Logic Minimization Short Notes for GATE CS

Boolean Algebra, Canonical Forms and Logic Minimization short notes for GATE CS: 6 study cards covering concepts, formulas, shortcuts and exam traps, plus sol

boolean algebra canonical forms and logic minimization short notes

Final Checklist: Boolean Laws Cheat Sheet

Boolean Laws Cheat Sheet Core Identities A + 0 = A, A \cdot 1 = A A + 1 = 1, A \cdot 0 = 0 A + A = A, AA = A A + \overline{A} = 1, A \overline{A} = 0 Simplification Absorption: A + A B = A Redundancy: A + \overline{A} B = A + B Consensus: A B + \overline{A} C + B C = A B + \overline{A} C De Morgan's: \overline{A B} = \overline{A} + \overline{B} | \overline{A + B} = \overline{A} \cdot \overline{B}

Canonical Forms: Minterms and Maxterms

Canonical Minterm and Maxterm Forms Why this matters: Any Boolean function can be written in exactly one standard form using minterms (for SOP) or maxterms (for POS). This unique representation is essential before you minimize anything. What you'll learn here: What minterms and maxterms are How to identify them from a truth table How to write functions as \sum m (\dots) or \prod M (\dots) The relationship between minterm and maxterm indices Chapter context: Digital Logic \to Boolean Algebra \to Canonical Forms \to Minimization (K-maps)

What is a Minterm?

Minterm Definition A minterm is a product (AND) term that includes every variable of the function exactly once, either in its true form or complemented form. For n variables, there are 2^{n} possible minterms. Example: 3-variable function F (X, Y, Z) Row X Y Z Minterm Notation 0000 \overline{X} \overline{Y} \overline{Z} m_{0} 1001 \overline{X} \overline{Y} Z m_{1} 2010 \overline{X} Y \overline{Z} m_{2} 3011 \overline{X} Y Z m_{3} 4100 X \overline{Y} \overline{Z} m_{4} 5101 X \overline{Y} Z m_{5} 6110 X Y \overline{Z} m_{6} 7111 X Y Z m_{7} Key property: Each minterm m_{i} equals 1 for exactly one input combination (the binary representation of i) and 0 for all others.

3 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

Assertion (A): For a 3-variable function F (A, B, C), if the sum-of-minterms is \sum m (1, 3, 4, 6), then the product-of-maxterms is \prod M (0, 2, 5, 7) . Reason (R): The arithmetic sum of the minterm indices and the maxterm indices equals the total number of rows in the truth table, which is 2^{3} = 8 .

Question 2

Level 1: Warm-up

According to the definition of an Essential Prime Implicant, what is the minimum number of minterms it must uniquely cover (i.e., not covered by any other Prime Implicant) to be considered mandatory in the minimal expression?

Question 3

Level 1: Warm-up

For a Prime Implicant of a Boolean function, what is the maximum number of literals that can be removed from it such that the resulting term is still guaranteed to be an implicant of the function?

Question 4

Level 1: Warm-up

If a minimal Sum-of-Products expression excludes a specific Prime Implicant that uniquely covers at least one minterm, what is the direct consequence for the function's truth table?

Question 5

Level 1: Warm-up

For the Boolean function F (A, B, C, D) = \sum m (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 15), how many Essential Prime Implicants does it have?

Question 6

Level 1: Warm-up

A Boolean function has 3 Essential Prime Implicants. To cover the remaining minterms, exactly 2 additional Prime Implicants are needed. What is the total number of product terms in the minimal Sum-of-Products expression?

Question 7

Level 1: Warm-up

For a Boolean variable A, consider the four expressions E_{1} = A \oplus 0, E_{2} = A \oplus 1, E_{3} = A \oplus A, E_{4} = A \oplus \overset{ˉ}{A} . As A takes all values in {0, 1}, the maximum number of these expressions that can be equal to 1 at the same time is

Question 8

Level 1: Warm-up

When applying the adjacency theorem to combine the terms A \overline{B} C and A \overline{B} \overline{C} in a Sum-of-Products expression, which variable is eliminated and what is the resulting minimal term?

Question 9

Level 1: Warm-up

Consider the following three Boolean functions: F_{1} = \sum m (0, 1, 2, 3) F_{2} = \sum m (0, 1, 2, 3, 4, 5, 6, 7) F_{3} = \sum m (0, 1, 2, 4, 5, 6) Let N_{1}, N_{2}, N_{3} be the number of Prime Implicants for F_{1}, F_{2}, F_{3} respectively. Which of the following correctly ranks them?

Question 10

Level 1: Warm-up

A minimal Sum-of-Products expression derived from a 4-variable Karnaugh map has exactly 3 product terms, containing 2, 3, and 4 literals respectively. Assuming no overlap between the groups and no redundant groups, what is the total number of cells (1s) covered by these groups in the K-map?

Free preview ends here

Login to view the complete short notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Boolean Algebra, Canonical Forms and Logic Minimization Short Notes for GATE CS

Boolean Algebra, Canonical Forms and Logic Minimization short notes for GATE CS: 6 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Final Checklist: Boolean Laws Cheat Sheet

Boolean Laws Cheat Sheet

Core Identities

$A + 0 = A, A \cdot 1 = A$
$A + 1 = 1, A \cdot 0 = 0$
$A + A = A, AA = A$
$A + \overline{A} = 1, A \overline{A} = 0$

Simplification

Absorption: $A + A B = A$
Redundancy: $A + \overline{A} B = A + B$
Consensus: $A B + \overline{A} C + B C = A B + \overline{A} C$

De Morgan's:

\overline{A B} = \overline{A} + \overline{B}

\overline{A + B} = \overline{A} \cdot \overline{B}

Canonical Forms: Minterms and Maxterms

Canonical Minterm and Maxterm Forms

Why this matters: Any Boolean function can be written in exactly one standard form using minterms (for SOP) or maxterms (for POS). This unique representation is essential before you minimize anything.

What you'll learn here:

What minterms and maxterms are
How to identify them from a truth table
How to write functions as $\sum m (\dots)$ or $\prod M (\dots)$
The relationship between minterm and maxterm indices

Chapter context: Digital Logic → Boolean Algebra → Canonical Forms → Minimization (K-maps)

What is a Minterm?

Minterm Definition

A minterm is a product (AND) term that includes every variable of the function exactly once, either in its true form or complemented form.

For $n$ variables, there are $2^{n}$ possible minterms.

Example: 3-variable function $F (X, Y, Z)$

Row	$X$	$Y$	$Z$	Minterm	Notation
0	0	0	0	$\overline{X} \overline{Y} \overline{Z}$	$m_{0}$
1	0	0	1	$\overline{X} \overline{Y} Z$	$m_{1}$
2	0	1	0	$\overline{X} Y \overline{Z}$	$m_{2}$
3	0	1	1	$\overline{X} Y Z$	$m_{3}$
4	1	0	0	$X \overline{Y} \overline{Z}$	$m_{4}$
5	1	0	1	$X \overline{Y} Z$	$m_{5}$
6	1	1	0	$X Y \overline{Z}$	$m_{6}$
7	1	1	1	$X Y Z$	$m_{7}$

Key property: Each minterm $m_{i}$ equals 1 for exactly one input combination (the binary representation of $i$ ) and 0 for all others.

SOP Minimization Cheat Sheet

Core Definitions

Implicant: Any product term that evaluates to 1 only when $F = 1$ .
Prime Implicant (PI): A maximal implicant; cannot be combined further to eliminate a variable.
Essential Prime Implicant (EPI): A PI that covers at least one minterm not covered by any other PI. Must be included.

Key Theorems

Adjacency: $X Y + X \overline{Y} = X$
Consensus: $X Y + \overline{X} Z + Y Z = X Y + \overline{X} Z$
Idempotent (for grouping): $X + X = X$

Minimal SOP Formula

Minimal SOP = \sum (All EPIs) + \sum (Minimum subset of remaining PIs to cover all 1s)

Boolean Algebra, Canonical Forms and Logic Minimization: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Digital Logic MCQ

Assertion (A): For a 3-variable function $F (A, B, C)$ , if the sum-of-minterms is $\sum m (1, 3, 4, 6)$ , then the product-of-maxterms is $\prod M (0, 2, 5, 7)$ .

Reason (R): The arithmetic sum of the minterm indices and the maxterm indices equals the total number of rows in the truth table, which is $2^{3} = 8$ .

A.
Both A and R are true and R is the correct explanation of A.
B.
A is true but R is false.
C.
Both A and R are true but R is not the correct explanation of A.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: Verify the mathematical truth of the Assertion, then check the Reason for conceptual and arithmetic accuracy.

Step 1: Evaluate Assertion (A). For a 3-variable function, there are $2^{3} = 8$ total rows (0 to 7). The minterm indices are ${1, 3, 4, 6}$ . The maxterm indices must be the complement set: ${0, 1, 2, 3, 4, 5, 6, 7} ∖ {1, 3, 4, 6} = {0, 2, 5, 7}$ . Assertion (A) is TRUE.

Step 2: Evaluate Reason (R). The reason claims the "arithmetic sum" of the indices equals 8. Let's calculate the arithmetic sum: $(1 + 3 + 4 + 6) + (0 + 2 + 5 + 7) = 14 + 14 = 28$ .

Step 3: The arithmetic sum is 28, not 8. The correct concept is that the <i>union of the sets</i> of indices contains exactly 8 elements. Reason (R) is FALSE due to a unit mismatch (confusing set union size with arithmetic sum).

Answer: B

Question 2 · Digital Logic MCQ

According to the definition of an Essential Prime Implicant, what is the minimum number of minterms it must uniquely cover (i.e., not covered by any other Prime Implicant) to be considered mandatory in the minimal expression?

A.
0
B.
1
C.
2
D.
All minterms

Correct Answer:

Step-by-Step Solution

Key idea: An Essential Prime Implicant is defined by its coverage of at least one unique minterm.

Step 1: Recall the definition of an Essential Prime Implicant (EPI). It is a Prime Implicant that covers at least one minterm that is not covered by any other Prime Implicant.

Step 2: Identify the threshold for "at least one". The minimum number of uniquely covered minterms required to make a PI essential is exactly 1.

Step 3: Because this specific minterm must be 1, and the EPI is the only PI that can cover it, the EPI becomes mandatory.

Answer: B

Question 3 · Digital Logic MCQ

For a Prime Implicant of a Boolean function, what is the maximum number of literals that can be removed from it such that the resulting term is still guaranteed to be an implicant of the function?

A.
0
B.
1
C.
2
D.
It depends on the total number of variables

Correct Answer:

Step-by-Step Solution

Key idea: This is a definition-boundary question, recognizable because it tests the strict limits of what makes an implicant "Prime".

Step 1: Recall the definition of a Prime Implicant (PI). It is a maximal grouping of 1s. It cannot be expanded further without including a 0.

Step 2: Understand what "removing a literal" means in Boolean algebra. Removing a literal from a product term expands the term to cover more minterms (e.g., $A B$ covers fewer minterms than $A$ ).

Step 3: If you remove even 1 literal from a PI, the resulting term will expand to cover at least one minterm where the function is 0.

Step 4: Therefore, it will no longer be an implicant. The maximum number of literals you can remove while guaranteeing it remains an implicant is 0.

Answer: A

Question 4 · Digital Logic MCQ

If a minimal Sum-of-Products expression excludes a specific Prime Implicant that uniquely covers at least one minterm, what is the direct consequence for the function's truth table?

A.
The function will evaluate to 0 for that specific minterm, making the expression incorrect.
B.
The function will evaluate to 1 for that minterm, but the expression will contain redundant terms.
C.
The function will remain logically equivalent but will require more OR gates.
D.
The function will automatically convert to a Product-of-Sums form.

Correct Answer:

Step-by-Step Solution

Key idea: This is a consequence-analysis question, recognizable because it tests the mandatory nature of Essential Prime Implicants.

Step 1: Identify the definition of the excluded term. It is a Prime Implicant that "uniquely covers at least one minterm". This is the exact definition of an Essential Prime Implicant (EPI).

Step 2: Understand the role of an EPI. Because it is the <i>only</i> Prime Implicant that covers that specific minterm, no other term in the expression can cover it.

Step 3: If the EPI is excluded from the final Sum-of-Products expression, that unique minterm is left uncovered.

Step 4: An uncovered minterm in an SOP expression means the function will evaluate to 0 for that input combination, which contradicts the original truth table (where it should be 1). The expression becomes incorrect.

Answer: A

Question 5 · Digital Logic MCQ

For the Boolean function $F (A, B, C, D) = \sum m (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 15)$ , how many Essential Prime Implicants does it have?

A.
2
B.
3
C.
4
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: An Essential Prime Implicant (EPI) is a Prime Implicant (PI) that covers at least one minterm not covered by any other PI.

Step 1: Identify the PIs by grouping the minterms. The minterms 0-11 form a large block, and 14,15 form another.

Step 2: The PIs are $\overline{A}$ (covers 0-7), $\overline{B}$ (covers 0,1,4,5,8,9,10,11), $\overline{C}$ (covers 0,1,2,3,8,9,10,11), and $A B$ (covers 14,15).

Step 3: Check for unique minterms. $\overline{A}$ uniquely covers 2,3,6,7. $\overline{C}$ uniquely covers 8,9,10,11. $A B$ uniquely covers 14,15.

Step 4: $\overline{B}$ covers 4,5 (also in $\overline{A}$ ) and 8,9,10,11 (also in $\overline{C}$ ). It has no unique minterms, so it is NOT an EPI.

Total EPIs = 3.

Answer: B

Question 6 · Digital Logic MCQ

A Boolean function has 3 Essential Prime Implicants. To cover the remaining minterms, exactly 2 additional Prime Implicants are needed. What is the total number of product terms in the minimal Sum-of-Products expression?

A.
2
B.
3
C.
5
D.
6

Correct Answer:

Step-by-Step Solution

Key idea: The minimal SOP expression is the sum of ALL Essential Prime Implicants plus the MINIMUM number of additional Prime Implicants needed to cover the rest.

Step 1: The problem states there are 3 EPIs. These are mandatory, so they contribute 3 product terms.

Step 2: It states exactly 2 additional PIs are needed to cover the remaining minterms. These contribute 2 product terms.

Step 3: Total product terms = (Number of EPIs) + (Number of additional PIs) = 3 + 2 = 5.

Answer: C

Question 7 · Digital Logic MCQ

For a Boolean variable $A$ , consider the four expressions

$E_{1} = A \oplus 0, E_{2} = A \oplus 1, E_{3} = A \oplus A, E_{4} = A \oplus \overset{ˉ}{A} .$

As $A$ takes all values in ${0, 1}$ , the maximum number of these expressions that can be equal to $1$ at the same time is

A.
1
B.
2
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Insight: The four expressions test the standard XOR identities. $E_{4} = A \oplus \overset{ˉ}{A}$ is always 1, while $E_{1}$ and $E_{2}$ are complementary as $A$ changes.

Exam route: Check the two possible values of $A$ . Whichever case gives more 1s gives the maximum.

Learning route:

Case 1: $A = 0$ .

$E_{1} = 0 \oplus 0 = 0$ .

$E_{2} = 0 \oplus 1 = 1$ .

$E_{3} = 0 \oplus 0 = 0$ .

$E_{4} = 0 \oplus 1 = 1$ .

Count of 1s is 2.

Case 2: $A = 1$ .

$E_{1} = 1 \oplus 0 = 1$ .

$E_{2} = 1 \oplus 1 = 0$ .

$E_{3} = 1 \oplus 1 = 0$ .

$E_{4} = 1 \oplus 0 = 1$ .

Count of 1s is 2.

Therefore the maximum count is 2.

Answer: Option B.

Wrong path: If one makes the sign error $A \oplus 1 = A$ instead of $A \oplus 1 = \overset{ˉ}{A}$ , then for $A = 1$ the count becomes $E_{1} = 1$ , $E_{2} = 1$ , $E_{4} = 1$ , giving 3, which matches option C. The identity $A \oplus 1 = \overset{ˉ}{A}$ is the correct one.

Generalization: $A \oplus 0 = A$ , $A \oplus 1 = \overset{ˉ}{A}$ , $A \oplus A = 0$ , and $A \oplus \overset{ˉ}{A} = 1$ .

Verification: In both cases exactly one of $E_{1}, E_{2}$ is 1, $E_{3}$ is always 0, and $E_{4}$ is always 1, so the total is always 2.

Question 8 · Digital Logic MCQ

When applying the adjacency theorem to combine the terms $A \overline{B} C$ and $A \overline{B} \overline{C}$ in a Sum-of-Products expression, which variable is eliminated and what is the resulting minimal term?

A.
Variable $C$ is eliminated, resulting in $A \overline{B}$
B.
Variable $B$ is eliminated, resulting in $A C$
C.
Variable $A$ is eliminated, resulting in $\overline{B} C$
D.
Variable $C$ is eliminated, resulting in $A B$

Correct Answer:

Step-by-Step Solution

Key idea: This is an adjacency theorem application, recognizable because two terms are identical except for one variable appearing in true and complemented forms.

Step 1: Compare the two terms: $A \overline{B} C$ and $A \overline{B} \overline{C}$ .

Step 2: Identify the variable that differs. $A$ and $\overline{B}$ are identical in both terms. The variable $C$ appears in true form in the first term and complemented form ( $\overline{C}$ ) in the second.

Step 3: Apply the adjacency theorem ( $X Y + X \overline{Y} = X$ ). The differing variable ( $C$ ) is eliminated.

Step 4: The resulting term is the common part: $A \overline{B}$ .

Answer: A

Question 9 · Digital Logic MCQ

Consider the following three Boolean functions:

$F_{1} = \sum m (0, 1, 2, 3)$

$F_{2} = \sum m (0, 1, 2, 3, 4, 5, 6, 7)$

$F_{3} = \sum m (0, 1, 2, 4, 5, 6)$

Let $N_{1}, N_{2}, N_{3}$ be the number of Prime Implicants for $F_{1}, F_{2}, F_{3}$ respectively. Which of the following correctly ranks them?

A.
$N_{1} = N_{2} < N_{3}$
B.
$N_{1} < N_{2} < N_{3}$
C.
$N_{3} < N_{1} = N_{2}$
D.
$N_{1} = N_{3} < N_{2}$

Correct Answer:

Step-by-Step Solution

Key idea: A Prime Implicant is a maximal group of minterms. We need to count the maximal groups for each function.

Step 1: $F_{1}$ has minterms 0,1,2,3. This is a single block of 4, so it has 1 PI ( $\overline{A} \overline{B}$ ). Thus, $N_{1} = 1$ .

Step 2: $F_{2}$ has minterms 0 through 7. This is a single block of 8, so it has 1 PI ( $\overline{A}$ ). Thus, $N_{2} = 1$ .

Step 3: $F_{3}$ has minterms 0,1,2,4,5,6. We can group (0,1,4,5) as $\overline{B}$ and (0,2,4,6) as $\overline{C}$ . These are two maximal groups. Thus, $N_{3} = 2$ .

Step 4: Comparing the counts: $N_{1} = 1$ , $N_{2} = 1$ , $N_{3} = 2$ . Therefore, $N_{1} = N_{2} < N_{3}$ .

Answer: A

Question 10 · Digital Logic MCQ

A minimal Sum-of-Products expression derived from a 4-variable Karnaugh map has exactly 3 product terms, containing 2, 3, and 4 literals respectively. Assuming no overlap between the groups and no redundant groups, what is the total number of cells (1s) covered by these groups in the K-map?

A.
7
B.
9
C.
12
D.
16

Correct Answer:

Step-by-Step Solution

Key idea: This is a reverse-engineering question that links the algebraic property of a product term (number of literals) to its spatial representation in a K-map (number of cells covered).

Step 1: Recall the relationship between literals and cells in an $n$ -variable K-map. A product term with $k$ literals covers $2^{n - k}$ cells.

Step 2: For a 4-variable map ( $n = 4$ ), calculate the cells covered by each term:

Term with 2 literals: $2^{4 - 2} = 2^{2} = 4$ cells.
Term with 3 literals: $2^{4 - 3} = 2^{1} = 2$ cells.
Term with 4 literals: $2^{4 - 4} = 2^{0} = 1$ cell.

Step 3: Sum the cells covered by all three terms: $4 + 2 + 1 = 7$ cells.

Answer: A

boolean algebra canonical forms and logic minimization short notes

Final Checklist: Boolean Laws Cheat Sheet

Boolean Laws Cheat Sheet

Canonical Forms: Minterms and Maxterms

Canonical Minterm and Maxterm Forms

What is a Minterm?

Minterm Definition

Example: 3-variable function F(X,Y,Z)

Try a question

Login to view the complete short notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Boolean Algebra, Canonical Forms and Logic Minimization Short Notes for GATE CS

Final Checklist: Boolean Laws Cheat Sheet

Boolean Laws Cheat Sheet

Canonical Forms: Minterms and Maxterms

Canonical Minterm and Maxterm Forms

What is a Minterm?

Minterm Definition

Example: 3-variable function F(X,Y,Z)

SOP Minimization Cheat Sheet

SOP Minimization Cheat Sheet

Core Definitions

Key Theorems

Minimal SOP Formula

Boolean Algebra, Canonical Forms and Logic Minimization: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More short notes in this unit

Example: 3-variable function $F (X, Y, Z)$

Example: 3-variable function $F (X, Y, Z)$