Boolean Algebra, Canonical Forms and Logic Minimization PYQs for GATE CS

Solve 12+ Boolean Algebra, Canonical Forms and Logic Minimization previous year 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 · 2026_Set2 MCQ

Which one of the following options is not a property of Boolean Algebra?

Note:

+

is OR operation,

.

is AND operation, and

^{'}

is NOT operation

A.
$a + b = b + a$
B.
$a . a^{'} = 1$
C.
$a + a^{'} = 1$
D.
$a . b = b . a$

Correct Answer:

Step-by-Step Solution

Insight: Recall the fundamental axioms of Boolean algebra, specifically the complement laws.

Exam route: $a \cdot a^{'} = 0$ , not $1$ . The other options are standard commutative and complement laws.

Learning route:

Let's evaluate each option against the standard axioms of Boolean algebra:

Option A: $a + b = b + a$ . This is the Commutative Law for OR. (Property)

Option B: $a \cdot a^{'} = 1$ . The Complement Law states that a variable ANDed with its complement is always 0, not 1. ( $a \cdot a^{'} = 0$ ). (NOT a property)

Option C: $a + a^{'} = 1$ . This is the correct Complement Law for OR. (Property)

Option D: $a \cdot b = b \cdot a$ . This is the Commutative Law for AND. (Property)

Therefore, Option B is the only one that is not a valid property.

Question 2 · Digital Logic · 2026_Set2 MCQ

Consider the following 4-variable Boolean function

F (A, B, C, D) = Σ m (0, 1, 2, 3, 8, 9, 10, 11)

Consider

A

as MSB,

D

as LSB. Which one of the following options represents the minimal sum of products form for the above function?

Note:

+

is OR operation,

.

is AND operation,

^{'}

is NOT operation

A.
$A^{'} + B^{'} + C^{'} + D^{'}$
B.
$B^{'}$
C.
$A^{'} . B^{'} + A . B$
D.
$A^{'}$

Correct Answer:

Step-by-Step Solution

Insight: The 8 minterms all share $B = 0$ , and the other variables run through all combinations, collapsing the function to a single literal.

Exam route: Scan the binary representations; the constant column gives the minimal SOP.

Learning route:

Minterms: 0(0000), 1(0001), 2(0010), 3(0011), 8(1000), 9(1001), 10(1010), 11(1011).

Column scan:

$A$ : 0 and 1
$B$ : always 0
$C$ : 0 and 1
$D$ : 0 and 1

Since $B$ is always 0 and the other three variables take all $2^{3} = 8$ possible combinations, the function is exactly $\overset{ˉ}{B}$ .

Matches Option B.

Question 3 · Digital Logic · 2026_Set1 MSQ

Consider the following Boolean expression of a function

F

F (P, Q) = (\overline{P} + Q) \oplus (\overline{P} Q)

Which of the following expressions is/are equivalent to

F

A.
$\overline{P \oplus Q}$
B.
$P \oplus Q$
C.
$\overline{P} \oplus Q$
D.
$\overline{P} \oplus \overline{Q}$

Correct Answer:

["A","C"]

Step-by-Step Solution

Insight: This is a composite XOR simplification. The expression has the standard form

$(A + B) \oplus (A B),$

which simplifies to $A \oplus B$ . Here $A = \overset{ˉ}{P}$ and $B = Q$ .

Exam route: Let $X = \overset{ˉ}{P}$ . Then

$F = (X + Q) \oplus (X Q) .$

Using $(X + Q) \oplus (X Q) = X \oplus Q$ , we get

$F = \overset{ˉ}{P} \oplus Q .$

For two variables, $\overset{ˉ}{P} \oplus Q$ is the XNOR of $P$ and $Q$ , i.e.

$\overset{ˉ}{P} \oplus Q = \overline{P \oplus Q} .$

Therefore the equivalent expressions are $\overline{P \oplus Q}$ and $\overset{ˉ}{P} \oplus Q$ .

Learning route:

Substitute $X = \overset{ˉ}{P}$ to expose the standard pattern:

$F = (X + Q) \oplus (X Q) .$

Prove or recall the identity

$(A + B) \oplus (A B) = A \oplus B .$

Proof sketch:

$(A + B) \oplus (A B) = (A + B) \overline{A B} + \overline{(A + B)} (A B) .$

The second term is zero because $\overline{(A + B)} = \overset{ˉ}{A} \overset{ˉ}{B}$ , and $\overset{ˉ}{A} \overset{ˉ}{B} A B = 0$ .

The first term becomes

$(A + B) (\overset{ˉ}{A} + \overset{ˉ}{B}) = A \overset{ˉ}{B} + \overset{ˉ}{A} B = A \oplus B .$

Apply the identity with $A = X$ and $B = Q$ :

$F = X \oplus Q .$

Substitute back $X = \overset{ˉ}{P}$ :

$F = \overset{ˉ}{P} \oplus Q .$

This matches option C.

Convert to option A if needed. Expand $\overset{ˉ}{P} \oplus Q$ :

$\overset{ˉ}{P} \oplus Q = \overline{\overset{ˉ}{P}} Q + \overset{ˉ}{P} \overset{ˉ}{Q} = P Q + \overset{ˉ}{P} \overset{ˉ}{Q} .$

But

$\overline{P \oplus Q} = \overline{P \overset{ˉ}{Q} + \overset{ˉ}{P} Q} = P Q + \overset{ˉ}{P} \overset{ˉ}{Q} .$

Hence

$\overset{ˉ}{P} \oplus Q = \overline{P \oplus Q} .$

So option A is also equivalent.

Tempting wrong path: a candidate may apply the identity correctly but forget that the first input was $\overset{ˉ}{P}$ , not $P$ . That produces $P \oplus Q$ , which is option B. It breaks at the substitution step: the standard form uses $A = \overset{ˉ}{P}$ , so the result is $\overset{ˉ}{P} \oplus Q$ , not $P \oplus Q$ . Another wrong path is complementing both variables and choosing $\overset{ˉ}{P} \oplus \overset{ˉ}{Q}$ , option D. But

$\overset{ˉ}{P} \oplus \overset{ˉ}{Q} = P \oplus Q,$

which is the complement of the correct two-variable XNOR form.

Generalization: When an XOR has one input as a sum and the other as the corresponding product, check whether it matches $(A + B) \oplus A B$ . Then replace $A$ and $B$ exactly as they appear, including any bars.

Verification: Use the truth table. For $(P, Q) = (0, 0), (0, 1), (1, 0), (1, 1)$ , the original expression gives $1, 0, 0, 1$ . Option A gives $1, 0, 0, 1$ . Option C gives $1, 0, 0, 1$ . Options B and D give $0, 1, 1, 0$ , so they are not equivalent.

Question 4 · Digital Logic · 2026_Set1 MSQ

Consider a Boolean function F with the following minterm expression:

F (P, Q, R, S) = \sum m (1, 2, 3, 4, 5, 7, 10, 12, 13, 14)

Which of the following options is/are the minimal sum-of-products expression(s) of F?

A.
$\overline{P} S + Q \overline{R} + \overline{P} \overline{Q} R + \overline{Q} R \overline{S}$
B.
$\overline{P} S + Q \overline{R} + \overline{P} \overline{Q} R + P R \overline{S}$
C.
$\overline{P} S + Q \overline{R} + P Q \overline{S} + P R \overline{S}$
D.
$\overline{P} S + Q \overline{R} + P Q \overline{S} + \overline{Q} R \overline{S}$

Correct Answer:

["B","D"]

Step-by-Step Solution

Insight: Map the 10 minterms on a 4-variable K-map and identify all Prime Implicants (PIs) and Essential Prime Implicants (EPIs).

Exam route: EPIs are $P^{'} S$ and $Q R^{'}$ . The remaining minterms ${2, 10, 14}$ can be covered by either ${P^{'} Q^{'} R, P R S^{'}}$ or ${P Q S^{'}, Q^{'} R S^{'}}$ , yielding two minimal forms.

Learning route:

Minterms: 1, 2, 3, 4, 5, 7, 10, 12, 13, 14.

K-map groups (Prime Implicants):

PI1: $m_{1}, m_{3}, m_{5}, m_{7} ⟹ P^{'} S$
PI2: $m_{4}, m_{5}, m_{12}, m_{13} ⟹ Q R^{'}$
PI3: $m_{2}, m_{3} ⟹ P^{'} Q^{'} R$
PI4: $m_{2}, m_{10} ⟹ Q^{'} R S^{'}$
PI5: $m_{10}, m_{14} ⟹ P R S^{'}$
PI6: $m_{12}, m_{14} ⟹ P Q S^{'}$

Essential check:

$m_{1}$ is only covered by PI1 $⟹ P^{'} S$ is EPI.
$m_{4}$ is only covered by PI2 $⟹ Q R^{'}$ is EPI.

EPIs $P^{'} S$ and $Q R^{'}$ cover ${1, 3, 4, 5, 7, 12, 13}$ .

Remaining uncovered minterms: ${2, 10, 14}$ .

To cover ${2, 10, 14}$ , we have two minimal choices:

Choice 1: Use PI3 ( $P^{'} Q^{'} R$ , covers 2) and PI5 ( $P R S^{'}$ , covers 10, 14).

Expression: $P^{'} S + Q R^{'} + P^{'} Q^{'} R + P R S^{'}$ . (Matches Option B)

Choice 2: Use PI4 ( $Q^{'} R S^{'}$ , covers 2, 10) and PI6 ( $P Q S^{'}$ , covers 14).

Expression: $P^{'} S + Q R^{'} + Q^{'} R S^{'} + P Q S^{'}$ . (Matches Option D)

Both are valid minimal SOP forms with 4 terms and 10 literals.

Question 5 · Digital Logic · 2025_Set2 MSQ

Given the following Karnaugh Map for a Boolean function

F (w, x, y, z)

y z

w x

1001011001101001
Which one or more of the following Boolean expression(s) represent(s)

F

A.
$\overset{w}{ˉ} \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + w \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} y \overset{z}{ˉ} + w \overset{x}{ˉ} y \overset{z}{ˉ} + x z$
B.
$\overset{w}{ˉ} \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} y \overset{z}{ˉ} + w \overset{x}{ˉ} y z + x z$
C.
$\overset{w}{ˉ} \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + w \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + w \overset{x}{ˉ} \overset{y}{ˉ} z + x z$
D.
$\overset{x}{ˉ} \overset{z}{ˉ} + x z$

Correct Answer:

["A","D"]

Step-by-Step Solution

Insight: Read the K-map values directly and form the largest valid power-of-2 groups.

Exam route: The four corners form $x^{'} z^{'}$ . The central $2 \times 2$ square forms $x z$ . The function is $x^{'} z^{'} + x z$ .

Learning route:

Step 1: Extract the 1s from the K-map (rows $w x$ , cols $y z$ ):

Row 00: $m_{0} = 1, m_{1} = 0, m_{3} = 0, m_{2} = 1$
Row 01: $m_{4} = 0, m_{5} = 1, m_{7} = 1, m_{6} = 0$
Row 11: $m_{12} = 0, m_{13} = 1, m_{15} = 1, m_{14} = 0$
Row 10: $m_{8} = 1, m_{9} = 0, m_{11} = 0, m_{10} = 1$

Step 2: Form groups of 1s.

Group 1: The four corners ( $m_{0}, m_{2}, m_{8}, m_{10}$ ).

Rows: $w x = 00, 10 ⟹ x = 0$ .

Cols: $y z = 00, 10 ⟹ z = 0$ .

Term: $x^{'} z^{'}$ .

Group 2: The central $2 \times 2$ square ( $m_{5}, m_{7}, m_{13}, m_{15}$ ).

Rows: $w x = 01, 11 ⟹ x = 1$ .

Cols: $y z = 01, 11 ⟹ z = 1$ .

Term: $x z$ .

Step 3: Combine terms.

$F = x^{'} z^{'} + x z$ .

Step 4: Verify options.

Option D is exactly $x^{'} z^{'} + x z$ . (Correct)

Option A expands $x^{'} z^{'}$ into its four minterms ( $m_{0}, m_{8}, m_{2}, m_{10}$ ) and adds $x z$ . This is logically identical. (Correct)

Options B and C include minterms like $m_{9}$ ( $w x^{'} y z$ ) or $m_{9}$ ( $w x^{'} y^{'} z$ ), which are 0 in the map. (Incorrect)

Question 6 · Digital Logic · 2025_Set2 MSQ

Which of the following Boolean algebraic equation(s) is/are CORRECT?

A.
$\overset{ˉ}{A} B C + A \overset{ˉ}{B} \overset{ˉ}{C} + \overset{ˉ}{A} \overset{ˉ}{B} \overset{ˉ}{C} + A \overset{ˉ}{B} C + A B C = B C + \overset{ˉ}{B} \overset{ˉ}{C} + \overset{ˉ}{A} \overset{ˉ}{B}$
B.
$A B + \overset{ˉ}{A} C + B C = A B + \overset{ˉ}{A} C$
C.
$(A + C) (\overset{ˉ}{A} + B) = A B + \overset{ˉ}{A} C$
D.
$\overline{(A + \overset{ˉ}{B} + \overset{ˉ}{D}) (C + D) (\overset{ˉ}{A} + C + D) (A + B + \overset{ˉ}{D})} = \overset{ˉ}{A} D + \overset{ˉ}{C} \overset{ˉ}{D}$

Correct Answer:

["B","C","D"]

Step-by-Step Solution

Insight: Options B and C are direct applications of the Consensus Theorem; Option D requires collapsing the product before applying De Morgan's and Consensus.

Exam route: Recognize $A B + \overset{ˉ}{A} C + B C = A B + \overset{ˉ}{A} C$ instantly. For D, use $(X + Y) (X + \overset{ˉ}{Y}) = X$ to simplify the inner expression before complementing.

Learning route:

Option A: Group terms: $(\overset{ˉ}{A} B C + A B C) + (A \overset{ˉ}{B} \overset{ˉ}{C} + \overset{ˉ}{A} \overset{ˉ}{B} \overset{ˉ}{C}) + A \overset{ˉ}{B} C = B C + \overset{ˉ}{B} \overset{ˉ}{C} + A \overset{ˉ}{B} C$ .

Test $A = 1, B = 0, C = 1$ : LHS $= 0 + 0 + 1 = 1$ . RHS $= 0 + 0 + 0 = 0$ . FALSE.

Option B: $A B + \overset{ˉ}{A} C + B C$ . The term $B C$ is the consensus of $A B$ and $\overset{ˉ}{A} C$ , so it is redundant. TRUE.

Option C: Expand $(A + C) (\overset{ˉ}{A} + B) = A \overset{ˉ}{A} + A B + \overset{ˉ}{A} C + B C = A B + \overset{ˉ}{A} C + B C$ . By Consensus, this equals $A B + \overset{ˉ}{A} C$ . TRUE.

Option D: Let $E$ be the expression inside the complement.

Group terms: $(A + \overset{ˉ}{B} + \overset{ˉ}{D}) (A + B + \overset{ˉ}{D}) = A + \overset{ˉ}{D}$ .

$(C + D) (\overset{ˉ}{A} + C + D) = C + D$ .

So $E = (A + \overset{ˉ}{D}) (C + D) = A C + A D + C \overset{ˉ}{D}$ .

Complement: $\overset{ˉ}{E} = (\overset{ˉ}{A} + \overset{ˉ}{C}) (\overset{ˉ}{A} + \overset{ˉ}{D}) (\overset{ˉ}{C} + D)$ .

Multiply first two: $\overset{ˉ}{A} + \overset{ˉ}{C} \overset{ˉ}{D}$ .

Multiply with third: $(\overset{ˉ}{A} + \overset{ˉ}{C} \overset{ˉ}{D}) (\overset{ˉ}{C} + D) = \overset{ˉ}{A} \overset{ˉ}{C} + \overset{ˉ}{A} D + \overset{ˉ}{C} \overset{ˉ}{D}$ .

The term $\overset{ˉ}{A} \overset{ˉ}{C}$ is the consensus of $\overset{ˉ}{A} D$ and $\overset{ˉ}{C} \overset{ˉ}{D}$ , so it is redundant.

Result: $\overset{ˉ}{A} D + \overset{ˉ}{C} \overset{ˉ}{D}$ . TRUE.

Correct options: B, C, D.

Question 7 · Digital Logic · 2025_Set1 MCQ

Consider the following four variable Boolean function in sum-of-product form

F (b_{3}, b_{2}, b_{1}, b_{0}) = Σ (0, 2, 4, 8, 10, 11, 12) .

where the value of the function is computed by considering

b_{3} b_{2} b_{1} b_{0}

as a 4-bit binary number, where

b_{3}

denotes the most significant bit and

b_{0}

denotes the least significant bit. Note that there are no don’t care terms. Which ONE of the following options is the CORRECT minimized Boolean expression for

F

A.
$\overline{b_{1}} \overline{b_{0}} + \overline{b_{2}} \overline{b_{0}} + b_{1} \overline{b_{2}} b_{3}$
B.
$\overline{b_{1}} \overline{b_{0}} + \overline{b_{2}} \overline{b_{0}}$
C.
$\overline{b_{2}} \overline{b_{0}} + b_{1} b_{2} b_{3}$
D.
$\overline{b_{0}} \overline{b_{2}} + \overline{b_{3}}$

Correct Answer:

Step-by-Step Solution

Insight: Plot the 7 minterms on a 4-variable K-map; the largest power-of-two rectangles reveal the essential prime implicants.

Exam route: Identify the three essential PIs: $\overset{ˉ}{b_{1}} \overset{ˉ}{b_{0}}$ , $\overset{ˉ}{b_{2}} \overset{ˉ}{b_{0}}$ , and $b_{3} \overset{ˉ}{b_{2}} b_{1}$ .

Learning route:

Minterms in binary ( $b_{3} b_{2} b_{1} b_{0}$ ): 0000, 0010, 0100, 1000, 1010, 1011, 1100.

K-map groups:

Quad ${0, 4, 8, 12}$ : $b_{1} = 0, b_{0} = 0 ⟹ \overset{ˉ}{b_{1}} \overset{ˉ}{b_{0}}$ .
Quad ${0, 2, 8, 10}$ : $b_{2} = 0, b_{0} = 0 ⟹ \overset{ˉ}{b_{2}} \overset{ˉ}{b_{0}}$ .
Pair ${10, 11}$ : $b_{3} = 1, b_{2} = 0, b_{1} = 1 ⟹ b_{3} \overset{ˉ}{b_{2}} b_{1}$ .

Check essentiality:

$m_{4}$ is only covered by $\overset{ˉ}{b_{1}} \overset{ˉ}{b_{0}}$ .
$m_{2}$ is only covered by $\overset{ˉ}{b_{2}} \overset{ˉ}{b_{0}}$ .
$m_{11}$ is only covered by $b_{3} \overset{ˉ}{b_{2}} b_{1}$ .

All three PIs are essential and cover all minterms.

Minimal SOP: $\overset{ˉ}{b_{1}} \overset{ˉ}{b_{0}} + \overset{ˉ}{b_{2}} \overset{ˉ}{b_{0}} + b_{3} \overset{ˉ}{b_{2}} b_{1}$ .

Matches Option A.

Question 8 · Digital Logic · 2025_Set1 MSQ

Let $X$ be a 3-variable Boolean function that produces output as ‘1’ when at least two of the input variables are ‘1’. Which of the following statement(s) is/are <b>CORRECT</b>, where $a, b, c, d, e$ are Boolean variables?

A.
$X (a, b, X (c, d, e)) = X (X (a, b, c), d, e)$
B.
$X (a, b, X (a, b, c)) = X (a, b, c)$
C.
$X (a, b, X (a, c, d)) = (X (a, b, a) AND X (c, d, c))$
D.
$X (a, b, c) = X (a, X (a, b, c), X (a, c, c))$

Correct Answer:

["B","D"]

Step-by-Step Solution

Insight: $X$ is the 3-variable majority function, which is symmetric and idempotent-friendly under self-composition.

Exam route: Use the identities $X (a, b, a) = a$ and $X (a, b, X (a, b, c)) = X (a, b, c)$ to test the options algebraically or with a strategic counterexample.

Learning route:

The function $X (u, v, w)$ outputs 1 if at least two inputs are 1. This is the majority function: $X (u, v, w) = uv + v w + w u$ .

Note the absorption-like property: $X (u, v, u) = uv + v u + u^{2} = u$ .

Option A: Test with $a = 1, b = 1, c = 0, d = 0, e = 0$ .

LHS: $X (0, 0, 0) = 0 ⟹ X (1, 1, 0) = 1$ .

RHS: $X (1, 1, 0) = 1 ⟹ X (1, 0, 0) = 0$ .

$1 \neq = 0$ , so A is FALSE.

Option B: Let $Y = X (a, b, c)$ . We want to show $X (a, b, Y) = Y$ .

$X (a, b, Y) = ab + bY + Y a = ab + Y (a + b)$ .

Substitute $Y = ab + b c + c a$ :

$Y (a + b) = (ab + b c + c a) (a + b) = a^{2} b + a b^{2} + ab c + a^{2} c + b^{2} c + ab c = ab + ab + ab c + a c + b c + ab c = ab + a c + b c = Y$ .

Thus $X (a, b, Y) = ab + Y = ab + ab + b c + c a = Y$ . TRUE.

Option C: $X (a, b, a) = a$ and $X (c, d, c) = c$ . RHS $= a c$ .

Test $a = 1, b = 1, c = 0, d = 1$ . $X (a, c, d) = X (1, 0, 1) = 1$ .

LHS $= X (1, 1, 1) = 1$ . RHS $= 1 \cdot 0 = 0$ . FALSE.

Option D: $X (a, c, c) = c$ . RHS $= X (a, X (a, b, c), c)$ .

Since $X$ is symmetric, $X (a, Y, c) = X (a, c, Y)$ .

Using the property from B with variables $a, c, b$ : $X (a, c, X (a, c, b)) = X (a, c, b) = X (a, b, c) = Y$ .

Thus RHS $= Y = X (a, b, c)$ . TRUE.

Correct options: B, D.

Question 9 · Digital Logic · 2024_Set2 MSQ

For a Boolean variable $x$ , which of the following statements is/are FALSE?

A.
$x \cdot 1 = x$
B.
$x + 1 = x$
C.
$x \cdot x = 0$
D.
$x + \overset{x}{ˉ} = 1$

Correct Answer:

["B","C"]

Step-by-Step Solution

Insight: This is a single-variable Boolean-law check. The four statements are judged as identities, so each must hold for both $x = 0$ and $x = 1$ .

Exam route: Recall the basic laws directly:

$x \cdot 1 = x, x + 1 = 1, x \cdot x = x, x + \overset{x}{ˉ} = 1.$

Comparing with the given statements, $x + 1 = x$ and $x \cdot x = 0$ are false. Hence the false statements are B and C.

Learning route:

A Boolean variable can only be $0$ or $1$ . An identity is true only if it is true for both values.
Option A: $x \cdot 1 = x$ . This is the identity law for AND. If $x = 0$ , $0 \cdot 1 = 0$ ; if $x = 1$ , $1 \cdot 1 = 1$ . True.
Option B: $x + 1 = x$ . This is not the identity law for OR. The null law says

$x + 1 = 1.$

Counterexample: if $x = 0$ , then $0 + 1 = 1 \neq = 0$ . False.

Option C: $x \cdot x = 0$ . This is not the complement law. The idempotent law says

$x \cdot x = x .$

Counterexample: if $x = 1$ , then $1 \cdot 1 = 1 \neq = 0$ . False.

Option D: $x + \overset{x}{ˉ} = 1$ . This is the complement law for OR. If $x = 0$ , $0 + 1 = 1$ ; if $x = 1$ , $1 + 0 = 1$ . True.

Tempting wrong path: a student may transfer ordinary algebra intuition and treat $1$ as an identity element for OR, concluding $x + 1 = x$ . That mistake makes the student miss statement B. It breaks exactly at the null law: $x + 1 = 1$ , not $x$ . Another wrong path is confusing $x \cdot x$ with $x \overset{x}{ˉ}$ ; $x \overset{x}{ˉ} = 0$ , but $x \cdot x = x$ . That mistake makes the student miss statement C.

Generalization: For one-variable Boolean identities, either name the standard law or test both values $0$ and $1$ . A single counterexample is enough to mark a statement false.

Verification: Substitute $x = 0$ and $x = 1$ into the selected false statements. For B: $0 + 1 = 1 \neq = 0$ . For C: $1 \cdot 1 = 1 \neq = 0$ . The unselected statements A and D hold for both values.

Question 10 · Digital Logic · 2024_Set1 MSQ

Consider a Boolean expression given by

F (X, Y, Z) = \sum (3, 5, 6, 7)

.

Which of the following statements is/are CORRECT?

A.
$F (X, Y, Z) = \prod (0, 1, 2, 4)$
B.
$F (X, Y, Z) = X Y + Y Z + X Z$
C.
$F (X, Y, Z)$ is independent of input $Y$
D.
$F (X, Y, Z)$ is independent of input $X$

Correct Answer:

["A","B"]

Step-by-Step Solution

Insight: The minterms ${3, 5, 6, 7}$ correspond to the 3-variable majority function, and maxterm indices are the complement of minterm indices.

Exam route: Simplify the minterms to $X Y + Y Z + X Z$ and find the missing indices for the maxterms.

Learning route:

Minterms: $m_{3} = \overset{ˉ}{X} Y Z$ , $m_{5} = X \overset{ˉ}{Y} Z$ , $m_{6} = X Y \overset{ˉ}{Z}$ , $m_{7} = X Y Z$ .

Combine adjacent terms:

$m_{3} + m_{7} = Y Z$

$m_{5} + m_{7} = X Z$

$m_{6} + m_{7} = X Y$

By idempotent law, $F = X Y + Y Z + X Z$ .

Option A: Maxterm indices are ${0, 1, 2, 3, 4, 5, 6, 7} ∖ {3, 5, 6, 7} = {0, 1, 2, 4}$ . TRUE.

Option B: Matches our simplified SOP. TRUE.

Option C & D: The expression $X Y + Y Z + X Z$ is symmetric with respect to $X, Y, Z$ . None of the variables can be eliminated, so $F$ depends on all three. FALSE.

Correct options: A, B.

Try a question

Login to view the complete previous-year 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 PYQs 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 previous year questions (pyqs) in this unit