Digital Logic Notes for GATE CS

GATE CS Digital Logic: 4 chapters, 33 previous year questions (100% of Digital Logic), 537 practice questions and one solved question from each chapter.

About Digital Logic Notes

Full study notes for Digital Logic in GATE CS, organised across 4 chapters. Each chapter page explains concepts from the basics with worked examples and the formulas you need.

Digital Logic Weightage in GATE CS

Digital Logic accounts for 33 of 33 Digital Logic previous year questions in our bank (100%), about 3.3 per paper across 10 papers.

Digital Logic Chapter Matrix

Chapter	Topics	PYQs	Share of unit PYQs	Practice questions
Number Systems, Binary Arithmetic and Data Representation	Radix Conversion and Number Representation, Binary Fractions and Decimal Conversion, Two's Complement Arithmetic and Overflow	5	15%	79
Boolean Algebra, Canonical Forms and Logic Minimization	Boolean Laws, Identities and Expression Equivalence, Canonical Minterm and Maxterm Forms, Sum-of-Products Minimization, Karnaugh Maps and Minimal Expressions, Majority, XOR and Composite Boolean Functions	12	36%	189
Combinational Logic Circuits and Data Selectors	Logic Gate Circuit Analysis and Hazards, Decoders, Multiplexers and Address Selection, Boolean Function Realization Using Multiplexers, Cascaded Multiplexer and Decoder Circuits	8	24%	143
Flip-Flops, Counters and Finite State Machines	Flip-Flop Behaviour and Sequential Circuit Analysis, Ripple and Synchronous Counters, Counter State Transitions and Excitation Equations, Mealy Machines and Sequence Processing, FSM State Minimization	8	24%	126

One Solved Question from Each Digital Logic Chapter

Question 1 · Number Systems, Binary Arithmetic and Data Representation MCQ

Match each 4-bit signed addition in Column I with the correct description in Column II of the carries at the most significant bit and the correctness of the stored 4-bit signed result.

Column I:

P: $0001 + 0010$

Q: $1000 + 1000$

R: $0111 + 0001$

S: $1100 + 1100$

Column II:

(i) $C_{in} = 0$ , $C_{o u t} = 1$ , and the stored result is not the correct signed sum

(ii) $C_{in} = 1$ , $C_{o u t} = 0$ , and the stored result is not the correct signed sum

(iii) $C_{in} = 0$ , $C_{o u t} = 0$ , and the stored result is the correct signed sum

(iv) $C_{in} = 1$ , $C_{o u t} = 1$ , and the stored result is the correct signed sum

Here $C_{in}$ is the carry into the most significant bit and $C_{o u t}$ is the carry out of the most significant bit.

A.
P-(iii), Q-(i), R-(ii), S-(iv)
B.
P-(iii), Q-(iv), R-(ii), S-(i)
C.
P-(i), Q-(iii), R-(iv), S-(ii)
D.
P-(ii), Q-(i), R-(iii), S-(iv)

Correct Answer:

Step-by-Step Solution

Key idea: this is a carry-in/carry-out matching question. Do not decide correctness from the final carry alone. Compute the carry into the MSB and the carry out of the MSB separately, then check whether the stored result equals the true signed sum.

Step 1: P: $0001 + 0010 = 0011$ .

No carry reaches the MSB and no carry leaves it, so $C_{in} = 0$ , $C_{o u t} = 0$ . The stored result $0011$ is $+ 3$ , which is correct. Thus P matches (iii).

Step 2: Q: $1000 + 1000 = 0000$ with a carry out.

The lower three bits produce no carry into the MSB, so $C_{in} = 0$ . The sign-bit addition $1 + 1$ produces $C_{o u t} = 1$ . The true sum is $- 8 + (- 8) = - 16$ , which is not representable in 4 bits, so the stored result is not correct. Thus Q matches (i).

Step 3: R: $0111 + 0001 = 1000$ .

The lower bits generate a carry into the MSB, so $C_{in} = 1$ . At the MSB, $0 + 0 + 1 = 1$ with no carry out, so $C_{o u t} = 0$ . The true sum is $7 + 1 = 8$ , not representable in 4-bit signed form, so the stored result is not correct. Thus R matches (ii).

Step 4: S: $1100 + 1100 = 1000$ with a carry out.

The bit below the MSB generates a carry into the MSB, so $C_{in} = 1$ . At the MSB, $1 + 1 + 1$ gives sum bit 1 and carry out 1, so $C_{o u t} = 1$ . The true sum is $- 4 + (- 4) = - 8$ , which is representable, and the stored result $1000$ is $- 8$ . Thus S matches (iv).

Step 5: Elimination confirms the only matching satisfying all four rows is P-(iii), Q-(i), R-(ii), S-(iv).

Answer: option A.

Question 2 · Boolean Algebra, Canonical Forms and Logic Minimization MCQ

Consider the Boolean function $F (A, B, C, D) = A \overline{B} + \overline{A} C + \overline{B} C + \overline{A} \overline{B} C D$ . It is given that the inputs $A$ and $B$ are never both $0$ simultaneously in the operating environment. What is the MINIMUM number of literals in the simplified sum-of-products (SOP) expression for $F$ under this constraint?

A.
3
B.
4
C.
5
D.
7

Correct Answer:

Step-by-Step Solution

Key idea: This is a constrained simplification question. The operating environment provides a hidden constraint that eliminates specific minterms, allowing further reduction via the consensus theorem.

Step 1: Translate the constraint. " $A$ and $B$ are never both $0$ " means the input combination $\overline{A} \overline{B}$ is impossible. Thus, $\overline{A} \overline{B} = 0$ .

Step 2: Apply the constraint to the function. The term $\overline{A} \overline{B} C D$ contains $\overline{A} \overline{B}$ , so it evaluates to $0$ . The function simplifies to $F = A \overline{B} + \overline{A} C + \overline{B} C$ .

Step 3: Apply the consensus theorem. For the terms $A \overline{B}$ and $\overline{A} C$ , the consensus term is formed by multiplying the non-complementary literals: $\overline{B} C$ .

Step 4: Eliminate the redundant term. Since $\overline{B} C$ is the consensus of $A \overline{B}$ and $\overline{A} C$ , it is completely redundant and can be removed. The minimal SOP is $F = A \overline{B} + \overline{A} C$ .

Step 5: Count the literals. The expression $A \overline{B} + \overline{A} C$ has exactly 4 literals.

Answer: 4 (Option B).

Question 3 · Combinational Logic Circuits and Data Selectors NAT

Consider the Boolean function $F (A, B, C, D) = \sum m (0, 1, 2, 5, 6, 7, 8, 10, 14, 15)$ . The function is implemented using a minimal two-level Sum-of-Products (SOP) circuit. Assuming all logic gates have non-zero but identical propagation delays, and only one input variable changes at a time, the number of distinct input transitions (from one minterm to an adjacent minterm) that will produce a static-1 hazard is ______.

Correct Answer:

4.00

Step-by-Step Solution

Key idea: A static-1 hazard in a minimal SOP circuit occurs when a single-variable transition moves between two adjacent 1s on the K-map that are not covered by the same prime implicant loop.

Step 1: Plot the minterms on a 4-variable K-map and identify the minimal prime implicants (PIs).

Minterms: 0, 1, 2, 5, 6, 7, 8, 10, 14, 15.

The essential prime implicants are:

$\overline{B} \overline{D}$ covering {0, 2, 8, 10}
$B C$ covering {6, 7, 14, 15}
$\overline{A} \overline{C} D$ covering {1, 5}

These three PIs cover all the 1s minimally.

Step 2: Identify all adjacent pairs of 1s (transitions where exactly one variable changes).

0(0000) and 1(0001): 0 is in $\overline{B} \overline{D}$ , 1 is in $\overline{A} \overline{C} D$ . Not in the same PI. $\to$ Hazard.
1(0001) and 5(0101): Both are in $\overline{A} \overline{C} D$ . No hazard.
2(0010) and 6(0110): 2 is in $\overline{B} \overline{D}$ , 6 is in $B C$ . Not in the same PI. $\to$ Hazard.
5(0101) and 7(0111): 5 is in $\overline{A} \overline{C} D$ , 7 is in $B C$ . Not in the same PI. $\to$ Hazard.
10(1010) and 14(1110): 10 is in $\overline{B} \overline{D}$ , 14 is in $B C$ . Not in the same PI. $\to$ Hazard.

(Other adjacent pairs like 0-2, 0-8, 6-7, etc., are within the same PI and do not cause hazards).

Step 3: Count the hazardous transitions. There are exactly 4 such transitions.

Answer: 4

Question 4 · Flip-Flops, Counters and Finite State Machines MCQ

Match the flip-flop configurations in List I with their corresponding next-state equations $Q^{+}$ in List II.

\textbf{List I}

P. D flip-flop with $D = \overline{X} \cdot \overline{Q}$

Q. JK flip-flop with $J = X, K = \overline{X} \cdot \overline{Q}$

R. T flip-flop with $T = X \oplus Q$

S. D flip-flop with $D = X \oplus Q$

\textbf{List II}

$Q^{+} = X$
$Q^{+} = X \oplus Q$
$Q^{+} = X + Q$
$Q^{+} = \overline{X} \cdot \overline{Q}$

Options:

A) P-4, Q-3, R-1, S-2

B) P-4, Q-1, R-3, S-2

C) P-2, Q-3, R-1, S-4

D) P-4, Q-3, R-2, S-1

A.
P-4, Q-3, R-1, S-2
B.
P-4, Q-1, R-3, S-2
C.
P-2, Q-3, R-1, S-4
D.
P-4, Q-3, R-2, S-1

Correct Answer:

Step-by-Step Solution

Key idea: This is a matching question testing your ability to derive the next-state equation $Q^{+}$ from the excitation equations of different flip-flop types. You must apply the characteristic equation for each FF type and simplify using Boolean algebra.

Step 1: Evaluate P. D flip-flop with $D = \overline{X} \cdot \overline{Q}$ .

Characteristic equation: $Q^{+} = D$ .

Therefore, $Q^{+} = \overline{X} \cdot \overline{Q}$ . This matches 4.

Step 2: Evaluate Q. JK flip-flop with $J = X, K = \overline{X} \cdot \overline{Q}$ .

Characteristic equation: $Q^{+} = J \overline{Q} + \overline{K} Q$ .

Substitute: $Q^{+} = X \overline{Q} + \overline{(\overline{X} \cdot \overline{Q})} Q$ .

Apply De Morgan's: $Q^{+} = X \overline{Q} + (X + Q) Q$ .

Simplify: $Q^{+} = X \overline{Q} + X Q + Q^{2} = X (\overline{Q} + Q) + Q = X + Q$ .

This matches 3.

Step 3: Evaluate R. T flip-flop with $T = X \oplus Q$ .

Characteristic equation: $Q^{+} = T \oplus Q$ .

Substitute: $Q^{+} = (X \oplus Q) \oplus Q$ .

Since $A \oplus A = 0$ and $A \oplus 0 = A$ , we have $Q^{+} = X \oplus (Q \oplus Q) = X \oplus 0 = X$ .

This matches 1.

Step 4: Evaluate S. D flip-flop with $D = X \oplus Q$ .

Characteristic equation: $Q^{+} = D$ .

Therefore, $Q^{+} = X \oplus Q$ . This matches 2.

Final Matching: P-4, Q-3, R-1, S-2.

Answer: P-4, Q-3, R-1, S-2.

A question from this chapter

Login to view the complete notes

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

Digital Logic Notes for GATE CS

About Digital Logic Notes

Digital Logic Weightage in GATE CS

Digital Logic Chapter Matrix

More from Digital Logic

One Solved Question from Each Digital Logic Chapter

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution