Digital Logic: Gates, Boolean Algebra, K-Maps & Sequential Circuits
What it is
Digital logic design is the layer beneath every digital system: a small set of simple building blocks called logic gates combine into circuits that add numbers, choose between signals, remember a bit, and count events. Boolean algebra is the mathematics describing what those gates do, letting a circuit be simplified on paper before a single wire is drawn. Two broad families sit on top of the gates: combinational circuits, whose output depends only on present inputs, and sequential circuits, whose output depends on present inputs plus a stored history of past inputs. Flip-flops, registers, counters, decoders, multiplexers, and the memory unit are either specific blocks within these families or ways of adding memory to make a circuit sequential.
Core concepts
Logic gates. A gate takes one or two binary inputs and produces one binary output according to a fixed rule. The truth table for each 2-input gate (inputs A and B) is:
| Gate | A=0, B=0 | A=0, B=1 | A=1, B=0 | A=1, B=1 |
|---|---|---|---|---|
| AND | 0 | 0 | 0 | 1 |
| OR | 0 | 1 | 1 | 1 |
| NAND | 1 | 1 | 1 | 0 |
| NOR | 1 | 0 | 0 | 0 |
| XOR | 0 | 1 | 1 | 0 |
| XNOR | 1 | 0 | 0 | 1 |
NOT takes a single input and inverts it:
| Input | Output |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND outputs 1 only when every input is 1. OR outputs 1 when at least one input is 1. NAND and NOR are AND and OR with the output inverted, so NAND is 0 only when every input is 1, and NOR is 1 only when every input is 0. XOR outputs 1 only when its inputs differ (an odd number of 1s, for more than two inputs), and XNOR outputs 1 only when its inputs match.
Boolean algebra laws let an expression be rewritten into an equivalent, usually shorter, one:
- Identity: A+0=A, A·1=A
- Null: A+1=1, A·0=0
- Idempotent: A+A=A, A·A=A
- Complement: A+A'=1, A·A'=0
- Commutative: A+B=B+A, A·B=B·A
- Associative: (A+B)+C=A+(B+C)
- Distributive: A·(B+C)=A·B+A·C
- Absorption: A+A·B=A
De Morgan's laws are the most frequently misremembered rule, so fix the direction carefully: (A+B)' = A'·B' and (A·B)' = A'+B'. In words, the complement of a sum is the product of the complements, and the complement of a product is the sum of the complements — AND becomes OR (and OR becomes AND) whenever the complement is pushed inside, and each term gets its own separate complement.
Combinational vs sequential. A combinational circuit's output is a pure function of its current inputs alone: the same inputs always give the same output, because there is no memory involved. A sequential circuit's output depends on the current inputs and a stored internal state, so the same inputs can produce different outputs depending on what happened before.
Half adder, the simplest combinational arithmetic circuit, adds two single bits A and B and produces Sum and Carry:
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Sum = A XOR B, and Carry = A AND B. A full adder extends this to three inputs — A, B and a carry-in — so multi-bit numbers can be added by chaining full adders together.
Decoders and multiplexers are the other core combinational blocks. A decoder takes n input lines and activates exactly one of up to 2ⁿ output lines, chosen by the binary value on the inputs — a 2-to-4 decoder turns a 2-bit code into one active line out of four. A multiplexer (MUX) does the reverse: it picks one of several inputs and routes it to a single output, based on select lines. A 4-to-1 MUX needs 2 select lines (2²=4 inputs); an 8-to-1 MUX needs 3 (2³=8).
Flip-flops are the basic memory element of sequential circuits: each stores one bit, updating only at a clock edge. An SR (Set-Reset) flip-flop sets or clears that bit on command, but has one input combination left undefined. A JK flip-flop refines SR to remove exactly that gap, so every input combination is valid. A D (Data) flip-flop simply captures whatever is on its D input at the clock edge and holds it — the simplest of the four:
| D | Q (after the clock edge) |
|---|---|
| 0 | 0 |
| 1 | 1 |
A T (Toggle) flip-flop flips its stored bit on every clock edge it is enabled for, which makes it a natural building block for counters.
Registers and counters are groups of flip-flops working together. A register is several flip-flops sharing a clock, holding a multi-bit value as one unit — an 8-bit register holds one byte. A counter is a sequential circuit that steps through a defined sequence of states, typically counting up or down in binary, once per clock pulse.
Memory unit and integrated circuits, conceptually: a memory unit is built from many such storage elements, organised so a given address selects one stored value; an integrated circuit is simply many gates, or an entire processor, fabricated on one chip rather than wired from separate components.
Error detection. A parity bit is the simplest scheme: an extra bit is added to a group of bits so the total count of 1s is always even (even parity) or always odd (odd parity). If a single bit flips during transmission, the received count no longer matches, and the error is detected — though not corrected or located.
Worked example
Simplify F(A,B,C) = A'B'C + A'BC + AB'C + ABC using a 3-variable K-map, then confirm the result algebraically.
On the K-map, all four terms share C=1, while A and B between them cover every combination (00, 01, 10, 11). These four cells sit together as one block, and since their count is a power of 2, they form a single valid group of 4. A group of 4 out of 3 variables eliminates 2 variables, keeping only the one constant across the group — here, C=1 — so the map gives F = C directly.
Now confirm the same result using Boolean algebra alone:
- F = A'B'C + A'BC + AB'C + ABC
- Factor C out of every term (distributive law, in reverse): F = C·(A'B' + A'B + AB' + AB)
- Factor A' out of the first pair and A out of the second pair (distributive law): F = C·(A'·(B'+B) + A·(B'+B))
- Apply the complement law, B'+B=1: F = C·(A'·1 + A·1)
- Apply the identity law, A·1=A: F = C·(A' + A)
- Apply the complement law, A'+A=1: F = C·1
- Apply the identity law, C·1=C: F = C
Both methods agree: the four-term expression reduces to the single literal C. This is exactly what a K-map group of four adjacent 1s means — the two variables that change across the group (A and B) cancel out, and only the variable that stays fixed (C) survives.
Common traps
- Reversing De Morgan's laws — writing (A+B)' as A'+B' instead of A'·B' is the single most common slip; the operator always flips, AND to OR or OR to AND, when the complement is distributed inward.
- Calling a circuit "sequential" just because it has many gates — the test is whether the output depends on stored past state, not gate count; a large multi-gate adder is still purely combinational.
- Grouping K-map cells in threes, fives, or other non-powers-of-2 — valid groups are always 1, 2, 4, 8 cells, and every group must form a rectangle (wraparound edges count), never an L-shape or a diagonal.
- Swapping which gate is "0 unless every input is 1" (NAND) with which is "1 unless every input is 0" (NOR) — they invert different base gates and are easy to mix up under time pressure.
- Treating a decoder and a multiplexer as the same idea — a decoder activates one of many outputs from a binary code, while a multiplexer selects one of many inputs for a single output; the data flow runs in opposite directions.
Speed technique
For De Morgan's laws, use one line: break the bar, flip the operator, give each variable its own bar. Pushing a complement through a plus or dot always switches the operator between the terms.
To recall a gate's truth table fast, memorise only its "special" row: AND is all-1s-only; OR fails only on all-0s; NAND and NOR are AND and OR with every output bit flipped; XOR and XNOR flip on whether the inputs match, not on any single input.
For an n-input decoder or an n-select-line multiplexer, the count is always 2ⁿ, so 3 select lines always mean 8 data lines without drawing the circuit.
For K-maps, a group's size tells you how many variables survive: a group of size 2ᵏ, out of n variables, eliminates k and keeps (n − k) — a single cell keeps all n variables, and a group covering the whole map leaves a constant 1.
Check yourself
- What does a NAND gate output when both of its inputs are 1?
Show answer
0 — NAND is 0 only when every input is 1, and 1 otherwise. - Apply De Morgan's law to (A·B)'.
Show answer
A' + B' — the complement of a product is the sum of the complements. - In the half adder, what is the Carry output when A=1 and B=1?
Show answer
1 — Carry = A AND B, and both inputs are 1. - How many select lines does an 8-to-1 multiplexer need?
Show answer
3 — since 2³=8. - In a K-map, what is the only valid size for a group of cells?
Show answer
A power of 2 — 1, 2, 4, 8, and so on.
What the exam tests here
None of the 3 papers we hold has asked this. It is on the syllabus, so it can appear — but nothing in the paper record tells us how it would be framed. Treat it as insurance, not as a priority.
Try it: Digital Logic Design: Boolean Algebra, Gates & Circuits questions
Real questions from the CUET PG CS bank on exactly this skill. Pick an answer to see the full solution — the intuition, the worked steps, the faster methods and the traps.
According to the identity law of Boolean algebra, what does the expression A + 0 simplify to?
Show the answer and worked solution
Answer: option A
The identity law for OR states that A + 0 = A — ORing with 0 changes nothing, because 0 contributes no truth of its own.
Checking both values of A confirms this: 0 + 0 = 0, and 1 + 0 = 1, so the result always equals A back.
Therefore A + 0 simplifies to A, option A.
According to the null law of Boolean algebra, what does the expression A + 1 simplify to?
Show the answer and worked solution
Answer: option B
The null law for OR states that A + 1 = 1 — once one OR input is a guaranteed 1, the whole expression is pinned to 1 no matter what A is.
Checking both values of A confirms this: 0 + 1 = 1, and 1 + 1 = 1, so the result is a constant 1 either way.
Therefore A + 1 simplifies to 1, option B.
According to the complement law of Boolean algebra, what does the expression A · A' simplify to?
Show the answer and worked solution
Answer: option C
The complement law's AND form states that A · A' = 0 — a variable and its own complement can never both be 1 at the same time, so ANDing them always fails.
Checking both cases confirms this: if A=0 then A'=1, giving 0·1=0; if A=1 then A'=0, giving 1·0=0.
Therefore A · A' simplifies to 0, option C.
Simplify the Boolean expression A + A'B.
Show the answer and worked solution
Answer: option C
Apply the distributive law in its OR-over-AND form: A + A'B = (A + A')(A + B).
The complement law gives A + A' = 1, so this becomes 1 · (A + B).
The identity law gives 1 · (A + B) = A + B.
Therefore A + A'B simplifies to A + B, option C.
Simplify the Boolean expression AB + A'C + BC.
Show the answer and worked solution
Answer: option D
Test the term BC against the other two terms in the only case it contributes, B=1 and C=1: substituting into AB gives A, and into A'C gives A'.
By the complement law, A + A' = 1, so AB + A'C already equals 1 whenever B=1 and C=1 — exactly the case BC represents.
Since BC never changes the expression's value on its own, it is redundant and can be dropped.
Therefore AB + A'C + BC simplifies to AB + A'C, option D — this is the consensus theorem.
Answer above — every one shows its working.