GATE Digital Logic previous year questions

Truth table (P,Q): (0,0): P̄+Q = 1, P̄Q = 0, F = 1. (0,1): 1 xor 1 = 0. (1,0): 0 xor 0 = 0. (1,1): 1 xor 0 = 1. So F = 1 exactly when P = Q: F is XNOR, the complement of P ⊕ Q. Complementing one input of XOR gives XNOR, so P̄ ⊕ Q also equals F. Complementing both inputs gives back P ⊕ Q. Answer: (A), (C).

Concept: XOR identities: x̄ ⊕ y = complement of (x ⊕ y), and x̄ ⊕ ȳ = x ⊕ y. A four-row truth table settles it faster than algebra.

8-bit sign-magnitude range is -127 to +127. X: sign 1, magnitude 0110100 = 52, so X = -52. Y: sign 0, magnitude 1001100 = 76, so Y = 76. X + Y = 24 (fine). X - Y = -128 (overflow). -X + Y = 128 (overflow). -X - Y = -24 (fine). Answer: (B), (C).

Concept: Sign-magnitude has two zeros and no -128, unlike two's complement. Students who use the two's-complement range think -128 fits.

X = 0011 0101 1100 0...: sign 0, exponent 01101011 = 107, fraction .1000 -> X = 1.1₂ × 2^(107-127) = 1.5 × 2⁻²⁰. Y = 0011 0100 1010 0...: exponent 01101001 = 105, fraction .0100 -> Y = 1.01₂ × 2⁻²² = 0.0101₂ × 2⁻²⁰. Sum: 1.1000₂ + 0.0101₂ = 1.1101₂, so Z = 1.1101₂ × 2⁻²⁰, exponent field 107 = 01101011, fraction 1101 0... Bits: 0 01101011 1101000... = 0011 0101 1110 1000 0... = 35E80000. Answer: (C) 35E80000.

Concept: IEEE 754 addition: align the smaller operand's significand to the larger exponent (including the hidden 1), add, renormalise. Forgetting the hidden bit of Y gives 35C80000-style answers.

For D flip-flops D = next state. D1 = 1 on rows (P Q1 Q0) 001, 010, 011, 111. P̄Q1 covers 010, 011; P̄Q0 covers 001, 011; Q1Q0 covers 011, 111. Union = {001, 010, 011, 111}, exact. D0 = 1 on rows 000, 010, 011, 110. P̄Q̄0 covers 000, 010; P̄Q1 covers 010, 011; Q1Q̄0 covers 010, 110. Union = {000, 010, 011, 110}, exact. Option (B) matches both; (A) has PQ1, which would set D1 at 110 where it must be 0. Answer: (B).

Concept: With D flip-flops the excitation equals the next-state column, so this is just two 3-variable K-maps. Check each candidate term against the 0 rows to eliminate options fast.

Essential prime implicants: P̄S = {1, 3, 5, 7} (only cover of 1 and 7) and QR̄ = {4, 5, 12, 13} (only cover of 4 and 13). Left: 2, 10, 14. Prime implicants covering them: P̄Q̄R {2, 3}, Q̄RS̄ {2, 10}, PRS̄ {10, 14}, PQS̄ {12, 14}. RS̄ would need 6, which is absent, so two more terms are required. Covers: P̄Q̄R + PRS̄ (2, 10, 14) and Q̄RS̄ + PQS̄ (2, 10, 14) both work with 3 literals each. (A) misses 14, (C) misses 2. Answer: (B), (D).

Concept: Pick essential prime implicants first, then solve the remaining cover. Multiple minimal SOPs exist when the leftover minterms can be paired in more than one way.

(A) and (D) are commutative laws. (C) is the complement law for OR. The complement law for AND is a . a' = 0, not 1, so (B) is false. Answer: (B).

Concept: Complement laws: a + a' = 1 and a . a' = 0. The trap is reading quickly and treating both complement laws as giving 1.

Values: N1 = -5, N2 = -3, N3 = -6, N4 = -7. Range is -8 to 7. N1 + N2 = -8: fits. N2 + N3 = -9: overflow. N3 - N4 = -6 + 7 = 1: fits. N1 + N4 = -12: overflow. Answer: (B) and (D).

Concept: Overflow occurs when the true result lies outside [-8, 7]; adding two negatives can overflow, subtracting a negative from a negative cannot here. The trap is forgetting -8 is representable, so N1 + N2 is fine.

0xC2710000 = 1 10000100 11100010000000000000000. Sign = 1 (negative). Exponent = 10000100₂ = 132, unbiased 132 - 127 = 5. Significand = 1.1110001₂. Value = -1.1110001₂ x 2⁵ = -111100.01₂ = -(32 + 16 + 8 + 4 + 0.25) = -60.25. Answer: -60.25.

Concept: IEEE 754 decoding: 1 sign bit, 8-bit exponent with bias 127, implicit leading 1. Traps: forgetting the hidden 1, using bias 128, or misaligning the hex nibbles across the sign/exponent boundary.

Minterms 0-3 are 00xx (A'B') and minterms 8-11 are 10xx (AB'). Together they are all minterms with B = 0 regardless of A, C, D: F = A'B' + AB' = B'. Answer: (B) B'.

Concept: Group the eight 1-cells in a K-map; an octet eliminates three variables. The trap is (C), which replaces AB' with AB.

D0 = A'B', D3 = AB. S1S0 = 00: Y = D0, true for AB = 00 only: 1 combination. S1S0 = 01: Y = 0: 0. S1S0 = 10: Y = 1 for all four AB: 4. S1S0 = 11: Y = D3, true for AB = 11: 1. Total = 1 + 0 + 4 + 1 = 6. Answer: 6.

Concept: Enumerate by select-line value: each mux input contributes the number of AB values that make it 1. The trap is counting only distinct select values, or treating the decoder outputs as active low.

X is the majority function; X(p, q, p) = p. (A) a = b = 1, c = d = e = 0: LHS = X(1, 1, 0) = 1, RHS = X(1, 0, 0) = 0. False. (B) If a = b the result is a, which equals X(a, b, c); if a ≠ b the third argument decides, giving X(a, b, c). True. (C) RHS = a AND c. With a = b = 1, c = d = 0: LHS = X(1, 1, 0) = 1, RHS = 0. False. (D) X(a, c, c) = c; let m = X(a, b, c). X(a, m, c): if a = c the result is a = c = m; if a ≠ c the result is m. Always m. True. Answer: (B), (D).

Concept: Majority-function identities; use X(p, q, p) = p and case-split on equal arguments. The trap is assuming majority is associative like AND/OR - it is not.

Widening a 2's complement number uses sign extension: copy the sign bit (1) into all new high bits. 1010 becomes 1111 1010 in 8 bits and 1111 1111 1111 1010 in 16 bits. Check: 1111 1010 = -128 + 122 = -6. 1000 1010 = -128 + 10 = -118, not -6. Answer: (B), (D).

Concept: Sign extension. The trap is padding with zeros after the sign bit, which works for sign-magnitude, not 2's complement.

(x' denotes NOT x.) b1'b0' (b1 = 0, b0 = 0) covers 0, 4, 8, 12. b2'b0' (b2 = 0, b0 = 0) covers 0, 2, 8, 10. Remaining minterm 11 = 1011 pairs with 10 = 1010 to give b3 b2' b1. All three are essential prime implicants and they cover exactly the 7 minterms. Option (B) misses 11; (C) and (D) include non-minterms. Answer: b1'b0' + b2'b0' + b1b2'b3 (A).

Concept: K-map grouping with edge/corner wrap. The trap is (B): the four-corner groups look complete, but the isolated 11 needs its own pair.

Partition by outputs: P1 = {A, B, C, E} (00), {D, H} (10), {F} (11), {G} (01). Refine by next-state classes. D: (G, A), H: (G, A): identical, D ≡ H. In P1: A → (F, P1), C → (F, P1), B → (DH, P1), E → (DH, P1): split into {A, C} and {B, E}. B and E both go to (D, C): equivalent. A → (F, B) and C → (F, E) with B ≡ E: equivalent. Final classes {A, C}, {B, E}, {D, H}, {F}, {G}. Answer: 5.

Concept: State minimisation by partition refinement: start from output classes and split until next-state classes agree. Equivalences can depend on each other (A ≡ C needs B ≡ E).

A shift register with the inverted last output fed back is a Johnson (twisted ring) counter. With n = 4 flip-flops it cycles through 2n = 8 states, e.g. 0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → 0000 (Q0Q1Q2Q3). The 16 states split into two cycles of 8, so from any initial value the circuit returns after 8 clocks. Answer: 8 (7 also accepted by the official key, if the initial state is not counted).

Concept: Ring counter (Q3 fed back) has n states; Johnson counter (Q3' fed back) has 2n. The official range 7-8 reflects whether the initial state is counted.

F = (XY)' + X' + XY' = X' + Y' + X' + XY'. Since XY' is absorbed by Y', F = X' + Y' = (XY)'. (A) (XY)' = X' + Y': equal. (B) X' + Y' + XY' = X' + Y': equal. (C) is the unsimplified circuit expression: equal. (D) X + Y' is 0 at X=0, Y=1 while F = 1 there: not equal. Answer: (A), (B), (C).

Concept: Read the gate outputs, OR them, then simplify with De Morgan and absorption. Several algebraically different forms can be equal; check each against the simplified function.

Booth's algorithm scans multiplier bit pairs (Qi, Qi-1) from the LSB with Q-1 = 0: 10 means subtract M, 01 means add M, 00 and 11 do nothing. Q = 1010 0100 1010 1010. From the LSB the bits are 0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,1. Pairs for i = 0..15: 00, 10, 01, 10, 01, 10, 01, 10, 01, 00, 10, 01, 00, 10, 01, 10. Non-00/11 pairs: 8 (i = 1 to 8) + 2 (i = 10, 11) + 3 (i = 13, 14, 15) = 13. The multiplicand M does not affect the count. Answer: 13.

Concept: Count bit transitions in the multiplier with an implicit 0 appended at the right. Alternating bit patterns are Booth's worst case. The trap is counting operations on M, or forgetting Q-1.

Each flip-flop in a ripple counter divides the frequency by 2, so the 4th flip-flop output has frequency f/16. Its period is 64 µs, so its frequency is 1/64 µs = 15.625 kHz. Clock frequency f = 16 x 15.625 = 250 kHz. Answer: 250.

Concept: An n-bit ripple counter is a divide-by-2ⁿ chain. The trap is reporting the last stage's 15.625 kHz instead of the counter's clock frequency.

The four corner cells (x = 0, z = 0) are 1: group x'z'. The central 2x2 block (x = 1, z = 1) is 1: group xz. All other cells are 0, so F = x'z' + xz. (A) the four minterms are exactly the corners (x'z') plus xz: equal. (B) contains wx'yz, which has x = 0, z = 1, a 0 cell: wrong. (C) contains wx'y'z, also x = 0, z = 1: wrong. (D) is the minimal form. Answer: (A) and (D).

Concept: K-maps wrap around, so the four corners form one group. A sum is correct only if it covers every 1 and no 0; a single stray minterm on a 0 cell disqualifies it.

0xC1100000 = 1 10000010 00100...: sign -, exponent 130 - 127 = 3, mantissa 1.001₂ = 1.125, so X = -9. 0x40C00000 = 0 10000001 100...: exponent 2, mantissa 1.5, so Y = 6. 0x41400000 = 0 10000010 100...: exponent 3, mantissa 1.5, so Z = 12. (A) 4(-3) + 12 = 0: true. (B) 12 - 12 = 0: true. (C) -36 + 36 = 0: true. (D) -9 + 6 + 12 = 9: false. Answer: (A), (B), (C).

Concept: Decode by splitting into sign (1), biased exponent (8, bias 127) and fraction (23) with the hidden leading 1. Forgetting the hidden bit or the bias is the usual error.

(A) LHS minterms (ABC) are 011, 100, 000, 101, 111 = {0, 3, 4, 5, 7}. RHS: BC = {3, 7}, B'C' = {0, 4}, A'B' = {0, 1}, giving {0, 1, 3, 4, 7}: it includes 1 and misses 5. False. (B) Consensus theorem: BC is redundant. True. (C) (A + C)(A' + B) = AA' + AB + A'C + BC = AB + A'C + BC = AB + A'C. True. (D) By De Morgan, the complement of the product is the sum of complements: A'BD + C'D' + AC'D' + A'B'D = A'D(B + B') + C'D'(1 + A) = A'D + C'D'. True. Answer: (B), (C), (D).

Concept: Tests the consensus theorem, product-of-sums expansion and De Morgan over a whole product. Comparing minterm sets is the safest check for (A)-type claims.

5-bit 2's complement range is −16 to 15. A = 10, B = 11010 = −6. A + B = 4 (fine). A − B = 16 (exceeds 15: overflow). B − A = −16 (representable). 2B = −12 (fine). Answer: (B) A − B.

Concept: Decode both operands, compute in decimal and compare with [−2ⁿ⁻¹, 2ⁿ⁻¹ − 1]. The trap is thinking −16 is out of range; the negative side has one extra value.

Without delays Y = X · X' = 0 always, so (A) is true and (B) false. With a NOT delay, when X rises 0 → 1 the inverter output is still 1 for a moment, so both AND inputs are 1 and Y glitches to 1: (C) true. When X falls 1 → 0, the direct input is already 0, so Y stays 0; and Y was already 0 before, so there is no transient zero to speak of: (D) false. Answer: (A), (C).

Concept: A static hazard: a signal ANDed with its own delayed complement produces a brief pulse on one edge only. The trap is expecting a glitch on both edges.

The maxterms are the remaining indices 0, 1, 2, 4, so (A) holds. Minterms 3 (011), 5 (101), 6 (110), 7 (111) are the inputs with at least two 1s, the majority function XY + YZ + XZ, so (B) holds. Majority depends on every input (e.g., F(1,0,0) = 0 but F(1,1,0) = 1), so (C) and (D) are false. Answer: (A), (B).

Concept: Σ and Π use complementary index sets. The trap is writing Π with the same indices as Σ.

Q1 = 1 whatever A is (both inputs 1). Q2 = 0 whatever B is (both inputs 0). Y = Q1 when C = 0 and Q2 when C = 1, so Y = 1 exactly when C = 0. A and B are free: 2 × 2 = 4 combinations. Answer: 4.

Concept: A mux with equal data inputs ignores its select line. The trap is counting only combinations where A or B take a specific value.

Exponent 1111 1111 (255) is reserved: with a non-zero mantissa, option (C) is NaN, not a number at all. Among the valid numbers the larger biased exponent wins. (A) and (D) have exponent 127 (unbiased 0), values 2 − 2⁻²³ and 1.0. (B) has exponent 254 (unbiased 127) with an all-ones mantissa: (2 − 2⁻²³) × 2¹²⁷, the largest finite single-precision value. Answer: (B).

Concept: IEEE 754 special values: exponent all ones means infinity (mantissa 0) or NaN (mantissa non-zero). The trap is picking the all-ones pattern as the largest.

(A) x · 1 = x is the identity law - true. (B) x + 1 = 1, not x - false. (C) x · x = x by idempotence, not 0 - false. (D) x + x̄ = 1 is the complement law - true. The FALSE statements are B and C. Answer: (B), (C).

Concept: Basic Boolean identities. Note the question asks for FALSE statements, and option C has x · x (idempotent), not x · x̄.

224 in base 5 = 2·25 + 2·5 + 4 = 64. (A) 64 in base 10 = 64. (B) 100 in base 8 = 64. (C) 50 in base 16 = 5·16 = 80. (D) 121 in base 7 = 49 + 14 + 1 = 64. Answer: (A), (B), (D).

Concept: Convert everything to decimal with positional weights. Hex 50 is 80, not 50 - the usual slip is reading the digits as decimal.

Y = (f1 · f2) ⊕ (f3 + f4). f1 · f2 = common minterms = {3,5,7,11,13}. f3 + f4 = {0,1,2,4,6,11,13}. XOR keeps minterms in exactly one of them: 11 and 13 cancel, leaving {3,5,7} ∪ {0,1,2,4,6} = {0,1,2,3,4,5,6,7}. So Y = Σ(0,1,2,3,4,5,6,7) = Π(8,9,10,11,12,13,14,15). Answer: (C), (D).

Concept: AND is intersection, OR is union and XOR is symmetric difference of minterm sets. Options in Π form list the maxterms, i.e. the complement set.

Let the external input on line 1 be D. When S = 1 the mux passes input 1, so Q = D (transparent). When S = 0 it passes input 0, which is Q itself, so Q holds its previous value. Q = S·D + S'·Q: the output follows D while S is high and holds while S is low. That is level-triggered storage with S as enable, i.e. a D latch, not an edge-triggered flip-flop. Answer: (B) D Latch.

Concept: A mux with output fed back to one input is the classic gated D latch. The trap is choosing D flip-flop: there is no edge detection, so the output is transparent for the whole time S is high.

132 in radix 4 = 1×16 + 3×4 + 2 = 30 in decimal. Convert 30 to radix 5: 30 = 1×25 + 1×5 + 0, so the digits are 1, 1, 0. Answer: 110.

Concept: Base conversion via decimal. A common slip is reading 132 as decimal or reversing the digits when dividing repeatedly by 5.

Next state: Q1+ = Q1 XOR Q3', Q2+ = Q1, Q3+ = Q3 XOR Q2. From (0,1,1): T1 = 0, so (0,0,0). Then (1,0,0), (0,1,0), (1,0,1), (1,1,1), (1,1,0), and back to (0,1,1). The cycle visits 011, 000, 100, 010, 101, 111, 110 - seven states. The only missing state is (0,0,1). Answer: (A) (0, 0, 1).

Concept: Write the next-state equations and trace from the given initial state. T flip-flops toggle when T = 1; the D flip-flop copies Q1. Options (B), (C), (D) all appear in the cycle.

Simplify: A' + A'C' = A', so F = A' + AB'C. B = 0 selects M1: F = A' + AC; inputs indexed by (A, C): 00 gives 1, 01 gives 1, 10 gives 0, 11 gives 1, so X0..X3 = 1, 1, 0, 1. B = 1 selects M2: F = A'; (A, C) = 00, 01 give 1, 10, 11 give 0, so X4..X7 = 1, 1, 0, 0. Answer: (C) (1, 1, 0, 1, 1, 1, 0, 0).

Concept: Split the function on the M3 select variable (B), then fill each 4-input mux with the truth table in its own select order (A as S1, C as S0). Using the wrong select order swaps X1 and X2.

P = 0xC1800000: sign 1, exponent 1000 0011 = 131, so 2^(131-127) = 2⁴, mantissa 0: P = -16. Q = 0x3F5C2EF4: sign 0, exponent 0111 1110 = 126, fraction 0x5C2EF4, Q = 1.f × 2⁻¹. P × Q = -(1.f) × 2³: same fraction, exponent 126 + 4 = 130 = 1000 0010, sign 1. Bits: 1 10000010 then fraction 0x5C2EF4, i.e. 0xC1000000 + 0x5C2EF4 = 0xC15C2EF4. Answer: (C).

Concept: Multiplying by a power of two only changes the exponent (and here the sign); the fraction bits are copied. The trap is forgetting the sign or adding 4 to the wrong field.

4-bit 2's complement range is −8 to 7. (A) 1011 = −5, 1110 = −2, sum −7: fine. (B) 1100 = −4, 1010 = −6, sum −10: below −8, overflow (bit-wise 1100 + 1010 = 0110, a positive result from two negatives). (C) 3 + 4 = 7: fine. (D) 1001 = −7, 1111 = −1, sum −8: representable. Answer: (B) R1 = 1100 and R2 = 1010.

Concept: Overflow happens only when both operands have the same sign and the result's sign differs. The trap is (D): −8 is still representable in 4 bits.

S has 1024 = 2¹⁰ words, so its address field is 10 bits and P must turn 10 address bits into one of 1024 word-select lines: a 10:2¹⁰ decoder. R has 32 = 2⁵ words, so Q is a 5:2⁵ decoder. T chooses between two data words (from S or R) under the control of M: a 2:1 multiplexer. Bits check: 1 + 10 + 5 = 16. Answer: (C).

Concept: Address bits select a word through a decoder; choosing one of several data inputs is a multiplexer. The trap is calling T an encoder.

RA = 1100 0001 0100 0...: sign 1, exponent 1000 0010 = 130, so 2³; fraction .1 = 0.5; A = −1.5 × 8 = −12. RB = 0100 0010 0001 0...: exponent 1000 0100 = 132, so 2⁵; fraction .001 = 0.125; B = 1.125 × 32 = 36. RC = 0100 0001 0100 0...: C = +12. Check: A + C = 0 true; A + B = 24 ≠ 12, so C = A + B is false; 3C = 36 = B true; B − C = 24 > 0 true. Answer: (B).

Concept: Decode sign, biased exponent (bias 127) and fraction with the hidden 1. Note the question asks for the FALSE statement.

(A) XNOR is the complement of XOR: correct. (B) Complementing one input of XOR complements the output: P̄ ⊕ Q = ¬(P ⊕ Q) = P ⊙ Q: correct. (C) Complementing both inputs leaves XOR unchanged: correct. (D) Left: P ⊕ P̄ = 1, and 1 ⊕ Q = Q̄. Right: P ⊙ P̄ = 0, and 0 ⊙ Q̄ = ¬(0 ⊕ Q̄) = ¬Q̄ = Q. Q̄ ≠ Q, so (D) is NOT correct. Answer: (D).

Concept: XOR/XNOR identities: x ⊕ 1 = x̄, x ⊙ 0 = x̄, and complementing one input flips the result. The trap is mis-evaluating 0 ⊙ Q̄; XNOR with 0 inverts its other input.

This is a 2-bit shift register. State (Q1, Q2); on a clock edge the next state is (in, Q1). A self-loop needs (in, Q1) = (Q1, Q2), that is Q1 = Q2 and in = Q1. State 00 stays 00 on in = 0, state 11 stays 11 on in = 1. State 01 goes to 00 or 10, and 10 goes to 01 or 11, never itself. So 2 states have a self-loop. Answer: 2.

Concept: Derive next-state equations from the D inputs and check which states can map to themselves. The trap is assuming every state can hold its value, as with an enable-controlled register.

5 integer bits give 0 to 31, and 3 fraction bits give multiples of 1/8 = 0.125. (i) 31.5 = 11111.100: representable. (ii) 0.875 = 7/8 = 00000.111: representable. (iii) 0.1 is not a multiple of 1/8, so 12.1 is not exact. (iv) 0.001 is not a multiple of 1/8, so 3.001 is not exact. Answer: (C) Only (iii) and (iv) cannot be exactly represented.

Concept: With f fraction bits, exactly representable fractions are multiples of 2^(-f). The trap is thinking 31.5 overflows; 31 is exactly the 5-bit maximum.

Prime implicants (using don't cares): Q'S' = {0, 2, 8, 10}; PQ' = {8, 9, 10, 11}; Q'R = {2, 3, 10, 11}; P'QS = {5, 7}; P'RS = {3, 7}; PS' = {8, 10, 12, 14} (only don't cares plus none of the minterms, so irrelevant). Minterm 0 is covered only by Q'S', minterm 5 only by P'QS, and minterm 9 only by PQ', so these three are essential. Together they cover 0, 2, 5, 7, 9, 11, i.e. the whole function. Number of essential prime implicants = 3.

Concept: An essential prime implicant is the only prime implicant covering some required minterm; don't cares help form implicants but never need covering. The trap is counting implicants made only of don't cares, or treating don't-care cells as minterms that make a prime essential.

The properties give the truth table: y = 0 gives x, y = 1 gives x̄. So x # y = 1 exactly when x ≠ y, which is XOR: x # y = xȳ + x̄y. Check: x # x = 0 and x # x̄ = 1 hold. Answer: (A).

Concept: Recognising XOR from its identities. The trap is option (D), XNOR, which gives x # x = 1.

The MSB is 1, so the number is negative. Its magnitude is the 2's complement: invert 1111 1111 1111 0101 to get 0000 0000 0000 1010, add 1 to get 0000 0000 0000 1011 = 11. So the value is -11. Answer: -11.

Concept: Reading a negative 2's complement number. The trap is reading it as unsigned (65525) or forgetting to add 1 after inverting (giving -10).

The sequence has 6 distinct steps (the three 0s are different states because each is followed by a different value). Distinguishing 6 states needs ⌈log₂ 6⌉ = 3 flip-flops, with combinational logic decoding the output; this gives 3. If instead the counter's output must come directly from flip-flops, the 2 value bits are not enough to tell the three 0 states apart and an extra state bit is needed, giving 4. The official key accepts 3 to 4. Answer: 3 (or 4).

Concept: A counter with repeated output values needs extra state to remember its position. The trap is answering 2 because the largest output value is 3.

First MUX: output = P̄·0 + P·R = PR. Second MUX: X = Q̄·R̄ + Q·(PR) = Q̄R̄ + PQR. The two terms share no adjacent minterms that would allow further merging (Q̄R̄ covers minterms with Q = 0, R = 0; PQR has Q = 1, R = 1), so this is minimal. Answer: (D).

Concept: A 2-to-1 MUX computes s̄·I0 + s·I1; cascade by substitution. The trap is mixing up which input is selected by 0 versus 1.

A carry lookahead adder computes each carry as cᵢ = Gᵢ + PᵢGᵢ₋₁ + ... + PᵢPᵢ₋₁...P₀c₀, which involves AND/OR terms of up to about n inputs. With gates of fan-in at most 2, an n-input AND or OR must be built as a binary tree of depth Θ(log n). So the addition takes Θ(log n) time. Answer: (B).

Concept: With unlimited fan-in the CLA would be Θ(1) depth; the fan-in-2 restriction forces logarithmic trees. The trap is answering Θ(1) from the textbook 'constant time' claim.

A = 1 = 00000001. Latency is longest when a carry generated at bit 0 propagates through all eight stages, which needs every bit of B to be 1 so each stage passes the carry on: B = 11111111. In 2's complement that is -1, and 1 + (-1) ripples a carry from bit 0 to bit 7. Answer: -1.

Concept: Ripple-carry worst case is a full carry chain: generate at the LSB, propagate everywhere else. The trap is answering 255 or 127 without reading 11111111 as a 2's complement value.

x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄ = 0 means x₁ ⊕ x₃ = x₂ ⊕ x₄. Complementing both inputs of an XOR leaves it unchanged (x̄ ⊕ ȳ = x ⊕ y), so x̄₁ ⊕ x̄₃ = x₁ ⊕ x₃ = x₂ ⊕ x₄ = x̄₂ ⊕ x̄₄. All xᵢ = 1 satisfies the premise but breaks (A), (B) and (D). Answer: (C).

Concept: XOR as parity (an even number of 1s). Rearranging XOR terms plus the identity x̄ ⊕ ȳ = x ⊕ y settles it; all-ones is the quick counterexample for the rest.

In 16-bit 2's complement every bit pattern is a distinct integer: X = 2¹⁶. Sign-magnitude has two zeros (+0 and -0), so Y = 2¹⁶ - 1 distinct integers. X - Y = 1. Answer: 1.

Concept: Sign-magnitude (and 1's complement) spend one pattern on negative zero; 2's complement does not. Counting patterns instead of distinct values gives the wrong answer 0.

F = PQ + P'QR + P'QR'S = Q[P + P'R + P'R'S] (factor out Q) = Q[P + P'(R + R'S)] (factor out P' from the last two terms) = Q[P + P'(R + S)] (identity: X + X'Y = X + Y, applied with X=R, Y=S) = Q[P + (R + S)] (identity: X + X'Y = X + Y again, applied with X=P, Y=(R+S)) = QP + QR + QS = PQ + QR + QS

Concept: This simplifies entirely with two applications of the same absorption-style identity (X + X'Y = X + Y) - recognising that pattern twice is much faster than building a 4-variable K-map for a question with only three product terms.

Factor out Q: F = Q(P + P̄R + P̄R̄S). P + P̄R = P + R, so F = Q(P + R + P̄R̄S). P + R + P̄R̄S: the term P̄R̄S is covered except when P = 0 and R = 0, where it reduces to S, so P + R + P̄R̄S = P + R + S. F = Q(P + R + S) = PQ + QR + QS. Check with minterms: F = {5, 6, 7, 12, 13, 14, 15}; QR covers 6, 7, 14, 15, QS covers 5, 7, 13, 15, PQ covers 12-15. Answer: (A) PQ + QR + QS.

Concept: Absorption: X + X̄Y = X + Y, applied twice after factoring the common literal Q. The trap is reading the third term as P̄Q̄R̄S; the Q in that term is not complemented.

Required 1s: 0, 5, 10, 15; don't cares: 2, 7, 8, 13. Q̄S̄ (Q = 0, S = 0) is minterms 0, 2, 8, 10 - covers 0 and 10 using don't cares 2 and 8. QS (Q = 1, S = 1) is minterms 5, 7, 13, 15 - covers 5 and 15 using don't cares 7 and 13. Two quads cover everything. Answer: (B) Q̄S̄ + QS.

Concept: Using don't cares to enlarge groups in a K-map (the corner quad here). The trap is option C or D, which ignore the don't cares and leave four-literal or three-literal terms.

JK rules: J=1,K=0 sets; J=0,K=1 resets; J=K=1 toggles; J=K=0 holds. From 000: J₂=Q̄₁=1, K₂=Q₀=0 -> Q₂=1. J₁=Q₂=0, K₁=1 -> Q₁=0. J₀=Q₁=0, K₀=Q̄₀=1 -> Q₀=0. State 100. From 100: J₂=1, K₂=0 -> 1. J₁=1, K₁=0 -> 1. J₀=0, K₀=1 -> 0. State 110. From 110: J₂=0, K₂=0 -> hold 1. J₁=1, K₁=0 -> 1. J₀=1, K₀=1 -> toggle to 1. State 111. Answer: (C) 100, 110, 111.

Concept: Next-state analysis of JK flip-flops using the present state for every input simultaneously. The trap is updating one flip-flop and then using its new value for the next one within the same clock.