DL · previous year questions

All PYQs: Digital Logic

54 real GATE CSE questions from 2012 to 2025, with the official answer key and a worked solution for each. Filter by year, topic, type, marks or keyword.

Questions belong to the GATE organising institutes; this copy is for personal study. Coverage varies by year: questions that need a figure I could not read, or whose answer I could not verify, were left out.

Showing 54 of 54 questions · 0 correct of 0 attempted · marks 0 / 81

GATE 2025 CS1 · Q24MSQ1 markBoolean Algebra, Canonical Forms & K-Maps
Let X be a 3-variable Boolean function that produces output '1' when at least two of the input variables are '1'. Which of the following statement(s) is/are CORRECT, where a, b, c, d, e are Boolean variables?

One or more options may be correct. Select all that apply, then submit.

GATE 2025 CS2 · Q31MSQ1 markBoolean Algebra, Canonical Forms & K-Maps
Consider the following logic circuit diagram with inputs X and Y: the top gate is a NAND of X and Y; the second gate is an inverter on X; the third gate is an AND of X and the inverted Y. The three gate outputs feed one 3-input OR gate with output F. Which is/are the CORRECT option(s) for the output function F?

One or more options may be correct. Select all that apply, then submit.

GATE 2025 CS2 · Q34NAT1 markCounters, Registers & State Machines
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ______. (Answer in integer)
GATE 2025 CS1 · Q42MCQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Consider the following four variable Boolean function in sum-of-product form F(b₃, b₂, b₁, b₀) = Σ(0, 2, 4, 8, 10, 11, 12), where the value of the function is computed by considering b₃b₂b₁b₀ as a 4-bit binary number, where b₃ denotes the most significant bit and b₀ 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?
GATE 2025 CS2 · Q43MSQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Given the following Karnaugh Map for a Boolean function F(w, x, y, z): rows wx = 00, 01, 11, 10 and columns yz = 00, 01, 11, 10. Row 00: 1 0 0 1. Row 01: 0 1 1 0. Row 11: 0 1 1 0. Row 10: 1 0 0 1. Which one or more of the following Boolean expression(s) represent(s) F?

One or more options may be correct. Select all that apply, then submit.

GATE 2025 CS2 · Q50MSQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Which of the following Boolean algebraic equation(s) is/are CORRECT?

One or more options may be correct. Select all that apply, then submit.

GATE 2025 CS1 · Q60NAT2 marksCounters, Registers & State Machines
Consider the given sequential circuit designed using D flip-flops. Four D flip-flops D0, D1, D2, D3 share one clock; D1 = Q0, D2 = Q1, D3 = Q2, and D0 is fed by Q3′ (the complement output of the last flip-flop). The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is ______. (Answer in integer)
GATE 2024 CS1 · Q28MSQ1 markCombinational Circuits
Consider the circuit shown below where the gates may have propagation delays. Assume that all signal transitions occur instantaneously and that wires have no delays. The circuit: input X goes directly to one input of an AND gate and also through an inverter (NOT gate) to the other input of the AND gate; the AND output is Y. Which of the following statements about the circuit is/are CORRECT?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS2 · Q30MSQ1 markBoolean Algebra, Canonical Forms & K-Maps
For a Boolean variable x, which of the following statements is/are FALSE?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q47MSQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Consider a Boolean expression given by F(X, Y, Z) = Σ(3, 5, 6, 7). Which of the following statements is/are CORRECT?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS2 · Q50MSQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Consider 4-variable functions f₁, f₂, f₃, f₄ expressed in sum-of-minterms form as given below. f₁ = Σ(0, 2, 3, 5, 7, 8, 11, 13), f₂ = Σ(1, 3, 5, 7, 11, 13, 15), f₃ = Σ(0, 1, 4, 11), f₄ = Σ(0, 2, 6, 13). The circuit: f₁ and f₂ go into an AND gate, f₃ and f₄ go into an OR gate, and the outputs of the AND and the OR go into an XOR gate with output Y. Which of the following options is/are CORRECT?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q64NAT2 marksCombinational Circuits
Consider a digital logic circuit consisting of three 2-to-1 multiplexers M1, M2 and M3. X1 and X2 are inputs 0 and 1 of M1, X3 and X4 are inputs 0 and 1 of M2. A, B and C are the select lines of M1, M2 and M3 respectively; the outputs of M1 and M2 go to inputs 0 and 1 of M3, whose output is Y. For an instance of inputs X1 = 1, X2 = 1, X3 = 0 and X4 = 0, the number of combinations of A, B, C that give the output Y = 1 is ______.
GATE 2023 · Q21MCQ1 markLatches & Flip-Flops
The output of a 2-input multiplexer is connected back to one of its inputs as shown in the figure: the output Q is wired back to data input 0, data input 1 is a free input (call it D) and the select line is S. Match the functional equivalence of this circuit to one of the following options.
GATE 2023 · Q43MCQ2 marksCounters, Registers & State Machines
Consider a sequential digital circuit consisting of T flip-flops and D flip-flops. CLKIN is the common clock input. The first flip-flop (output Q1) is a T flip-flop whose T input is Q3′ (the output of the last flip-flop, inverted); the second (output Q2) is a D flip-flop with D = Q1; the third (output Q3) is a T flip-flop with T = Q2. At the beginning, Q1, Q2 and Q3 have values 0, 1 and 1, respectively. Which one of the given values of (Q1, Q2, Q3) can NEVER be obtained with this digital circuit?
GATE 2023 · Q44MCQ2 marksCombinational Circuits
A Boolean digital circuit is composed using two 4-input multiplexers (M1 and M2) and one 2-input multiplexer (M3). X₀ to X₇ are the inputs of the multiplexers M1 (X₀ to X₃) and M2 (X₄ to X₇) and could be connected to either 0 or 1. The select lines S₁S₀ of both M1 and M2 are A and C. The outputs of M1 and M2 go to inputs 0 and 1 of M3, whose select line is B. Which one of the following set of values of (X₀, X₁, X₂, X₃, X₄, X₅, X₆, X₇) will realise the Boolean function A′ + A′C′ + AB′C?
GATE 2022 · Q40MCQ2 marksCombinational Circuits
Consider a digital display system (DDS) that displays the contents of register X. A 16-bit code word (a mode bit M, a 10-bit S-address and a 5-bit R-address) is used to load a word in X, either from S or from R. S is a 1024-word memory segment and R is a 32-word register file. Based on the value of mode bit M, T selects an input word to load in X. P and Q interface with the corresponding bits in the code word to choose the addressed word. Which one of the following represents the functionality of P, Q, and T?
GATE 2021 Set 2 · Q5MCQ1 markCombinational Circuits
Which one of the following circuits implements the Boolean function f(x, y, z) = m₀ + m₁ + m₃ + m₄ + m₅ + m₆, where mᵢ is the iᵗʰ minterm? Each option is a 4×1 multiplexer with select lines S₁ = y and S₀ = z and data inputs I₀ I₁ I₂ I₃ connected as follows.
GATE 2021 Set 1 · Q28MCQ2 marksCounters, Registers & State Machines
Consider a 3-bit counter, designed using T flip-flops. All three flip-flops (outputs P, Q, R) share one clock pulse. The T inputs are connected as T_P = R, T_Q = P′ and T_R = Q′. Assuming the initial state of the counter given by PQR as 000, what are the next three states?
GATE 2021 Set 2 · Q28MCQ2 marksCounters, Registers & State Machines
Suppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1's by a 0. Example: input sequence 00100011000011100, output sequence 00000001000001100. A Mealy machine is a state machine where both the next state and the output are functions of the present state and the current input. The circuit can be designed as a two-state Mealy machine, with states represented by Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit by s, t, b and y respectively. The initial state is 0. What are the Boolean expressions corresponding to t and y in terms of s and b?
GATE 2021 Set 1 · Q42MSQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Consider the following Boolean expression. F = (X + Y + Z)(X′ + Y)(Y′ + Z). Which of the following Boolean expressions is/are equivalent to F′ (complement of F)?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 2 · Q52NAT2 marksBoolean Algebra, Canonical Forms & K-Maps
Consider a Boolean function f(w, x, y, z) such that f(w, 0, 0, z) = 1, f(1, x, 1, z) = x + z, f(w, 1, y, z) = wz + y. The number of literals in the minimal sum-of-products expression of f is ______.
GATE 2020 · Q28MCQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Consider the Boolean function z(a, b, c). The circuit: input b goes through an inverter into one input of an AND gate whose other input is c; the AND output and the input a go into an OR gate whose output is z. Which one of the following minterm lists represents the circuit given above?
GATE 2019 Set 2 · Q30MCQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Consider three 4-variable functions f₁, f₂ and f₃, which are expressed in sum-of-minterms as f₁ = Σ(0, 2, 5, 8, 14), f₂ = Σ(2, 3, 6, 8, 14, 15), f₃ = Σ(2, 7, 11, 14). For the following circuit with one AND gate and one XOR gate (f₁ and f₂ go into the AND gate; the AND output and f₃ go into the XOR gate), the output function f can be expressed as:
GATE 2019 Set 2 · Q50NAT2 marksBoolean Algebra, Canonical Forms & K-Maps
What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as f = Σ(0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available. Answer: ______.
GATE 2018 · Q4MCQ1 markBoolean Algebra, Canonical Forms & K-Maps
Let ⊕ and ⊙ denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?
GATE 2018 · Q22NAT1 markCounters, Registers & State Machines
Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops. The input "in" feeds the first flip-flop, the output of the first flip-flop feeds the second, and the output of the second flip-flop is "out" (both share the clock). The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of "in" is ______.
GATE 2018 · Q49NAT2 marksBoolean Algebra, Canonical Forms & K-Maps
Consider the minterm list form of a Boolean function F given below. F(P, Q, R, S) = Σm(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14). Here, m denotes a minterm and d denotes a don't care term. The number of essential prime implicants of the function F is ______.
GATE 2017 Set 2 · Q1MCQ1 markNumber Systems & Binary Arithmetic
The representation of the value of a 16-bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is
GATE 2017 Set 1 · Q21NAT1 markBoolean Algebra, Canonical Forms & K-Maps
Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0. Columns are ba = 00, 01, 11, 10 and rows are dc = 00, 01, 11, 10. Row dc = 00: blank, X, X, blank. Row dc = 01: 1, blank, blank, X. Row dc = 11: 1, blank, blank, 1. Row dc = 10: blank, X, X, blank. Assume for all inputs (a, b, c, d), the respective complements (a′, b′, c′, d′) are also available. The above logic is implemented using 2-input NOR gates only. The minimum number of gates required is ______.
GATE 2017 Set 2 · Q24NAT1 markNumber Systems & Binary Arithmetic
Consider a quadratic equation x² − 13x + 36 = 0 with coefficients in a base b. The solutions of this equation in the same base b are x = 5 and x = 6. Then b = ______.
GATE 2017 Set 2 · Q27MCQ2 marksBoolean Algebra, Canonical Forms & K-Maps
If w, x, y, z are Boolean variables, then which one of the following is INCORRECT?
GATE 2017 Set 2 · Q28MCQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Given f(w, x, y, z) = Σm(0, 1, 2, 3, 7, 8, 10) + Σd(5, 6, 11, 15), where d represents the don't-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of f(w, x, y, z)?
GATE 2017 Set 1 · Q33MCQ2 marksLatches & Flip-Flops
Consider a combination of T and D flip-flops connected as shown. The output of the D flip-flop is connected to the input of the T flip-flop and the output of the T flip-flop is connected to the input of the D flip-flop. Both flip-flops share one clock. The T flip-flop output is Q₁, the D flip-flop output is Q₀. Initially, both Q₀ and Q₁ are set to 1 (before the 1st clock cycle). The outputs
GATE 2017 Set 2 · Q42MCQ2 marksCounters, Registers & State Machines
The next state table of a 2-bit saturating up-counter is given below. Q₁Q₀ → Q₁⁺Q₀⁺: 00 → 01, 01 → 10, 10 → 11, 11 → 11. The counter is built as a synchronous sequential circuit using T flip-flops. The expressions for T₁ and T₀ are
GATE 2016 Set 1 · Q6MCQ1 markBoolean Algebra, Canonical Forms & K-Maps
Consider the Boolean operator # with the following properties: x # 0 = x, x # 1 = x′, x # x = 0 and x # x′ = 1. Then x # y is equivalent to
GATE 2016 Set 2 · Q7NAT1 markCombinational Circuits
Consider an eight-bit ripple-carry adder for computing the sum of A and B, where A and B are integers represented in 2′s complement form. If the decimal value of A is one, the decimal value of B that leads to the longest latency for the sum to stabilize is ______.
GATE 2016 Set 2 · Q8MCQ1 markBoolean Algebra, Canonical Forms & K-Maps
Let x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄ = 0 where x₁, x₂, x₃, x₄ are Boolean variables, and ⊕ is the XOR operator. Which one of the following must always be TRUE?
GATE 2016 Set 1 · Q8NAT1 markCounters, Registers & State Machines
We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is ______.
GATE 2016 Set 2 · Q9NAT1 markNumber Systems & Binary Arithmetic
Let X be the number of distinct 16-bit integers in 2′s complement representation. Let Y be the number of distinct 16-bit integers in sign magnitude representation. Then X − Y is ______.
GATE 2016 Set 1 · Q30MCQ2 marksCombinational Circuits
Consider the two cascaded 2-to-1 multiplexers. The first MUX has data inputs 0 (input 0) and R (input 1), and select line P. The second MUX has data inputs R′ (input 0) and the output of the first MUX (input 1), and select line Q; its output is X. The minimal sum of products form of the output X is
GATE 2014 Set 2 · Q6MCQ1 markBoolean Algebra, Canonical Forms & K-Maps
The dual of a Boolean function F(x₁, x₂, …, xₙ, +, ·, ′), written as FD, is the same expression as that of F with + and · swapped. F is said to be self-dual if F = FD. The number of self-dual functions with n Boolean variables is
GATE 2014 Set 1 · Q7MCQ1 markBoolean Algebra, Canonical Forms & K-Maps
Consider the following Boolean expression for F: F(P, Q, R, S) = PQ + P′QR + P′QR′S. The minimal sum-of-products form of F is
GATE 2014 Set 3 · Q7MCQ1 markBoolean Algebra, Canonical Forms & K-Maps
Consider the following minterm expression for F: F(P, Q, R, S) = Σ(0, 2, 5, 7, 8, 10, 13, 15). The minterms 2, 7, 8 and 13 are 'do not care' terms. The minimal sum-of-products form for F is
GATE 2014 Set 2 · Q7MCQ1 markCounters, Registers & State Machines
Let k = 2ⁿ. A circuit is built by giving the output of an n-bit binary counter as input to an n-to-2ⁿ bit decoder. This circuit is equivalent to a
GATE 2014 Set 1 · Q8NAT1 markNumber Systems & Binary Arithmetic
The base (or radix) of the number system such that the following equation holds is ______. 312 / 20 = 13.1
GATE 2014 Set 2 · Q8NAT1 markNumber Systems & Binary Arithmetic
Consider the equation (123)₅ = (x8)ᵧ with x and y as unknown. The number of possible solutions is ______.
GATE 2014 Set 3 · Q8MCQ1 markCombinational Circuits
Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output.
f(x, y, a, b) {
  if (x is 1) y = a;
  else y = b;
}
Which one of the following digital logic blocks is the most suitable for implementing this function?
GATE 2014 Set 1 · Q45MCQ2 marksCombinational Circuits
Consider the 4-to-1 multiplexer with two select lines S₁ and S₀. Data inputs are I₀ = 0, I₁ = 1, I₂ = R, I₃ = R′. The select lines are S₁ = P and S₀ = Q. The minimal sum-of-products form of the Boolean expression for the output F of the multiplexer is
GATE 2014 Set 3 · Q45MCQ2 marksCounters, Registers & State Machines
A synchronous sequential circuit is built using three JK flip-flops with outputs Q₂, Q₁, Q₀ and a common clock. Connections: J₂ = Q₀′, K₂ = Q₀; J₁ = Q₂, K₁ = Q₂′; J₀ = Q₁, K₀ = Q₁′. The circuit is initialized with Q₂Q₁Q₀ = 000. The state sequence for this circuit for the next 3 clock cycles is
GATE 2014 Set 3 · Q55MCQ2 marksBoolean Algebra, Canonical Forms & K-Maps
Let ⊕ denote the Exclusive OR (XOR) operation. Let '1' and '0' denote the binary constants. Consider the following Boolean expression for F over two variables P and Q: F(P, Q) = ((1 ⊕ P) ⊕ (P ⊕ Q)) ⊕ ((P ⊕ Q) ⊕ (Q ⊕ 0)). The equivalent expression for F is
GATE 2013 Code A · Q5MCQ1 markCombinational Circuits
In the following truth table, V = 1 if and only if the input is valid. Inputs D₀ D₁ D₂ D₃, outputs X₀ X₁ V: 0000 → x x 0; 1000 → 0 0 1; x100 → 0 1 1; xx10 → 1 0 1; xxx1 → 1 1 1. What function does the truth table represent?
GATE 2013 Code A · Q21MCQ1 markBoolean Algebra, Canonical Forms & K-Maps
Which one of the following expressions does NOT represent exclusive NOR of x and y?
GATE 2012 Code A · Q6MCQ1 markBoolean Algebra, Canonical Forms & K-Maps
The truth table: X Y f(X, Y): 0 0 → 0, 0 1 → 0, 1 0 → 1, 1 1 → 1. It represents the Boolean function
GATE 2012 Code A · Q30MCQ2 marksBoolean Algebra, Canonical Forms & K-Maps
What is the minimal form of the Karnaugh map shown below? Assume that X denotes a don't care term. Columns are ab = 00, 01, 11, 10 and rows are cd = 00, 01, 11, 10. Row cd = 00: 1, X, X, 1. Row cd = 01: X, blank, blank, 1. Row cd = 11: all blank. Row cd = 10: 1, blank, blank, X.