What are common examiner traps in Digital Logic?

Confusing A B (which equals A B) with A B (which equals A B). Forgetting that non-essential prime implicants can yield multiple distinct valid minimal SOP expressions (common in MSQ). Treating don't-care terms as mandatory 1s or mandatory 0s when converting between SOP and POS forms. Assuming XOR is distributive over OR (e.g., (x+y) z x (y+z)). Counting literals in non-minimal or un-factored forms in NAT questions. Neglecting static hazards: believing X X is unconditionally 0 when gate propagation delays exist. Counting sub-cubes (e.g. a pair of 2 minterms) as prime implicants when they are already fully covered by a larger quad. Confusing prime implicants (all maximal groupings) with essential prime implicants or the terms in the minimal cover.

Digital Logic

3 topics · 101 Qs · 5.5 marks/paper · since 2011

Start mock (30 Qs)

Boolean algebra and minimization in GATE CS tests algebraic identities, canonical form transformations, K-map minimization (SOP/POS with and without don't-cares), functional comple… Guide

Topics

Open a topic to browse, or practice it timed.

By year

Jump to the first question from that paper.

Subject guide

What does GATE test in Digital Logic?

Boolean algebra and minimization in GATE CS tests algebraic identities, canonical form transformations, K-map minimization (SOP/POS with and without don't-cares), functional completeness, and the structural properties of logic operators like XOR, XNOR, and majority functions. GATE extensively tests combinational and sequential circuit design through both analytical tracing and formal synthesis. Number representation and arithmetic in GATE CS tests a student's precise understanding of positional number systems, fixed-point signed representations (2's complement, 1's complement, sign-magnitude), and IEEE 754 floating-point standards.

Core concepts

K-map minimization (Essential Prime Implicants, non-essential PIs, multiple minimal covers)
Don't-care conditions (d / X) in SOP vs POS minimization
Boolean algebra postulates (Commutativity, Associativity, Distributivity, Idempotence, Involution)
De Morgan's Laws and duality principle
XOR / XNOR properties and algebraic identities
Functional completeness (NAND, NOR, custom multi-input operators)
Canonical SOP and POS dual relationships
Majority / threshold functions and composition laws
Combinational logic hazards and propagation delay glitches (X X)
Prime Implicant (PI) identification and counting
4-variable Karnaugh map grouping (pairs, quads, octets)
Algebraic simplification laws (Absorption, Idempotent, Distributive, De Morgan's)

High-yield formulas

Number of Self-Dual Functions

$N = 2^{2^{n-1}}$ for an $n$ -variable Boolean function$$

Used to compute how many independent self-dual functions can be formed by pairing complementary minterms.

Consensus Theorem (SOP and POS)

AB + \bar{A}C + BC = AB + \bar{A}C \quad \text{and} \quad (A+B)(\bar{A}+C)(B+C) = (A+B)(\bar{A}+C)

Used to eliminate redundant consensus terms or expand POS expressions into SOP forms.

Absorption & Redundant Literal Elimination

A + \bar{A}B = A + B \quad \text{and} \quad A(\bar{A} + B) = AB

Used during step-by-step algebraic minimization of sum-of-product terms.

XOR and XNOR Complementation Rules

\bar{A} \oplus B = A \oplus \bar{B} = \overline{A \oplus B} = A \odot B \quad \text{and} \quad \bar{A} \oplus \bar{B} = A \oplus B

Used to test equivalences of circuits and symbolic expressions involving parity operators.

Canonical SOP to POS Complement Rule

$F = \sum m(S) \iff F = \prod M(U \setminus S)$ where $U = \{0, 1, \dots, 2^n - 1\}$ $

Used when switching between sum-of-minterms and product-of-maxterms representations.

3-Variable Majority Function

M(A, B, C) = AB + BC + CA

Used to evaluate recursive/nested expressions, carry generation, or threshold logic.

De Morgan's Law

\overline{A \cdot B} = \bar{A} + \bar{B}, \quad \overline{A + B} = \bar{A} \cdot \bar{B}

Used when expanding complementation over conjunctions and disjunctions during expression simplification.

Absorption and Annihilation Laws

A + AB = A, \quad A(A + B) = A, \quad A \cdot \bar{A} = 0, \quad A + \bar{A} = 1

Used during multi-variable algebraic reduction to eliminate redundant terms.

Examiner traps in Digital Logic

Confusing A B (which equals A B) with A B (which equals A B).
Forgetting that non-essential prime implicants can yield multiple distinct valid minimal SOP expressions (common in MSQ).
Treating don't-care terms as mandatory 1s or mandatory 0s when converting between SOP and POS forms.
Assuming XOR is distributive over OR (e.g., (x+y) z x (y+z)).
Counting literals in non-minimal or un-factored forms in NAT questions.
Neglecting static hazards: believing X X is unconditionally 0 when gate propagation delays exist.
Counting sub-cubes (e.g. a pair of 2 minterms) as prime implicants when they are already fully covered by a larger quad.
Confusing prime implicants (all maximal groupings) with essential prime implicants or the terms in the minimal cover.

How questions show up

K-Map Minimization (SOP / POS with Don't Cares)
common · mixed · 2 marks · 2026, 2025, 2021, 2017
Given a list of minterms and optional don't-cares, or a visual K-map grid, determine the minimal sum-of-products or product-of-sums expression, or count the minimum number of literals/gates required.
XOR and XNOR Equivalence and Property Testing
common · mixed · 1 marks · 2026, 2019, 2018, 2016
Evaluating identities involving nested $\oplus$ and $\odot$ operators, negation of inputs, zero/one constants, or checking whether an axiomatic definition matches XOR/XNOR.
Set-Theoretic Minterm & Maxterm Manipulation across Gate Networks
occasional · MSQ · 2 marks · 2024, 2015
Analyzing multi-gate circuits where input functions are defined as minterm sets $\sum m(\dots)$ , mapping AND to intersection, OR to union, and XOR to symmetric difference, then expressing output in canonical SOP or POS form.
Boolean Identity, Complement, and Consensus Theorem Verification
common · MSQ · 2 marks · 2026, 2025, 2024, 2021
Identifying invalid or valid algebraic reductions (e.g., Consensus Theorem $AB + \bar{A}C + BC = AB + \bar{A}C$ , absorption laws, De Morgan complements) across multiple options in MSQ/MCQ format.
Functional Completeness and Custom Operator Analysis
occasional · MCQ · 1.5 marks · 2017, 2016, 2015
Determining if a given function or set of functions (like NAND, custom operator $\#$ , or multi-variable equations) can generate complete logic (NOT and AND/OR) through input fixing or negation.
Function Properties and Function Counting (Self-Dual & Majority Functions)
occasional · mixed · 1.5 marks · 2025, 2024, 2014
Analyzing higher-level structural properties of functions such as the number of self-dual functions $2^{2^{n-1}}$ , recursion/idempotence of majority voting functions, or static timing hazard behavior ( $X\bar{X}$ ).