Boolean Algebra, Canonical Forms and Logic Minimization Practice Questions for GATE CS

Solve 189+ Boolean Algebra, Canonical Forms and Logic Minimization practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Journey: Boolean Algebra and Logic Minimization

Chapter Journey

Master the foundation of digital circuit design, from basic axioms to advanced minimization techniques.

Boolean Laws & Identities High Weightage
The foundational axioms and theorems for manipulation.

Canonical Forms Moderate
Standardizing functions into Minterm and Maxterm representations.

Algebraic Minimization High Weightage
Reducing Sum-of-Products expressions using Boolean theorems.

Karnaugh Maps Moderate
Visual minimization for up to 4-6 variables using prime implicants.

Composite Functions Moderate
Analyzing Majority, XOR, and complex composite logic structures.

Boolean Laws, Identities and Expression Equivalence

Boolean Laws & Identities

The grammar of digital logic. Master these rules to simplify circuits, reduce gate count, and verify complex expressions.

Core axioms: Commutative, Associative, Distributive, Identity, Complement
Advanced theorems: Absorption, Redundancy, and Consensus
Transformation tools: De Morgan's Laws and the Principle of Duality

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

Try a question

Login to view the complete practice questions and solutions

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 Practice Questions for GATE CS

Chapter Journey: Boolean Algebra and Logic Minimization

Chapter Journey

Boolean Laws, Identities and Expression Equivalence

Boolean Laws & Identities

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 practice questions in this unit