Digital Logic Design: A Complete Study

Guide
Boolean Algebra, Gates, K-Maps & Sequential Circuits

Digital logic is the bridge between abstract Boolean algebra and physical hardware.
Every processor, memory, and controller is built from logic gates that manipulate 1s and
0s according to Boolean rules. This guide covers Boolean algebra, logic gates,
simplification with Karnaugh maps, and the combinational and sequential building blocks
that follow from them.

From equations to circuits. A Boolean expression and a logic circuit are two views of the same
thing. Simplifying the expression directly reduces the number of gates — saving cost, power, and
delay in real silicon.

1. Boolean Algebra
Boolean algebra works with two values, 0 and 1, and three basic operations: AND (·),
OR (+), and NOT (′). AND is true only when both inputs are true; OR is true when at least
one input is true; NOT inverts.

1.1 Fundamental laws

Law AND form OR form

Identity A·1 = A A+0=A

Null A·0 = 0 A+1=1

Idempotent A·A = A A+A=A

Complement A·A′ = 0 A + A′ = 1

Absorption A·(A + B) = A A + A·B = A

De Morgan (A·B)′ = A′ + B′ (A + B)′ = A′·B′

Table 1. The core identities of Boolean algebra. De Morgan's laws are the most frequently used in simplification.

1.2 Simplifying expressions

Worked Example 1. Simplify F = A·B + A·B′ + A′·B.

Digital Logic Design: A Complete Study Guide Page 1

 Group the first two: A·B + A·B′ = A·(B + B′) = A.

Now F = A + A′·B. By the identity A + A′·B = A + B.

F = A + B.

Worked Example 2. Simplify F = (A + B)·(A + B′).

Expand: A·A + A·B′ + B·A + B·B′.

A·A = A and B·B′ = 0, so F = A + A·(B′ + B) = A + A = A.

F = A.

Worked Example 3. Apply De Morgan to simplify F = (A·B + C)′.

Outer NOT over a sum: = (A·B)′·C′.

Inner NOT over a product: = (A′ + B′)·C′.

Digital Logic Design: A Complete Study Guide Page 2

 2. Logic Gates
Each Boolean operation has a corresponding gate. Combinations of gates implement
any Boolean function. NAND and NOR are called universal gates because any circuit
can be built from NAND alone or NOR alone.

Gate Symbol Output is 1 when...

AND A·B both inputs are 1

OR A+B at least one input is 1

NOT A′ the input is 0

NAND (A·B)′ not both inputs are 1

NOR (A + B)′ both inputs are 0

XOR A⊕B the inputs differ

XNOR (A ⊕ B)′ the inputs are equal

2.1 Truth tables

A truth table lists the output for every possible input combination. For n inputs there are
2n rows. It is the definitive specification of a combinational function.

Worked Example 4. Build the truth table for F = A·B + C.

A B C A·B F

0 0 0 0 0

0 0 1 0 1

0 1 0 0 0

0 1 1 0 1

1 0 0 0 0

1 0 1 0 1

Digital Logic Design: A Complete Study Guide Page 3

 A B C A·B F

1 1 0 1 1

1 1 1 1 1

Digital Logic Design: A Complete Study Guide Page 4

 3. Canonical Forms
Any Boolean function can be written in two standard forms. Sum of Products (SOP)
ORs together the input combinations (minterms) that make the output 1. Product of
Sums (POS) ANDs together the maxterms for which the output is 0. SOP is the more
common starting point for simplification.

Worked Example 5. Write the SOP for a function that is 1 for the minterms
m(1, 2, 4).
Minterm 1 = A′B′C, minterm 2 = A′BC′, minterm 4 = AB′C′.

F = A′B′C + A′BC′ + AB′C′.

4. Karnaugh Map Simplification

A Karnaugh map (K-map) is a grid arrangement of a truth table that makes simplification
visual. Adjacent 1s that form groups of 1, 2, 4, 8... (powers of two) can be combined,
eliminating the variable that changes across the group. The grid uses Gray-code
ordering so that neighbouring cells differ in exactly one variable.

Grouping rules. Make groups as large as possible (fewer literals), use only powers of two, allow
groups to overlap and wrap around edges, and cover every 1 at least once. Larger groups mean
simpler expressions.

Worked Example 6. Minimize F(A,B,C) = Σm(1, 3, 5, 7).

These are exactly the minterms where C = 1. A and B take every combination.

A and B are eliminated, leaving F = C.

Worked Example 7. Minimize F(A,B,C,D) = Σm(0, 1, 2, 3, 8, 9, 10, 11).

All eight minterms lie in the B = 0 region (rows for A=0,B=0 and A=1,B=0), spanning
every value of C and D.

Only B stays constant at 0; everything else drops out. F = B′.

Worked Example 8. Minimize F(A,B,C) = Σm(0, 2, 4, 6).

These are the even minterms — all have C = 0.

F = C′.

Digital Logic Design: A Complete Study Guide Page 5

 4.1 Don't-care conditions
Sometimes certain input combinations can never occur (for example, invalid BCD codes
1010-1111). These are marked X (don't-care) on the K-map and may be treated as 0 or
1 — whichever helps form larger groups and a simpler expression.

Worked Example 9. F(A,B,C) has 1s at m(1, 3) and don't-cares at m(5, 7).

Simplify.
Treat the don't-cares as 1s. Then m(1,3,5,7) are all covered — the C = 1 column.

F = C, simpler than the two-term expression without the don't-cares.

Digital Logic Design: A Complete Study Guide Page 6

 5. Combinational Building Blocks
5.1 Half and full adders
A half adder adds two bits, producing a sum S = A ⊕ B and a carry C = A·B. A full
adder also takes a carry-in, giving S = A ⊕ B ⊕ C■■ and C■■■ = A·B + C■■·(A ⊕ B).
Chaining full adders builds a ripple-carry adder for multi-bit numbers.

Worked Example 10. Give the half-adder outputs for A = 1, B = 1.

Sum = 1 ⊕ 1 = 0; Carry = 1·1 = 1. Result: sum 0, carry 1 (binary 10 = 2).

5.2 Multiplexers and decoders

A multiplexer (MUX) selects one of several inputs to pass to a single output, controlled
by select lines: a 2n-to-1 MUX needs n select bits. A decoder does the reverse,
activating one of 2n outputs based on an n-bit input code — used for address decoding
in memory.

6. Sequential Logic
Combinational circuits depend only on current inputs. Sequential circuits also depend
on stored state, giving them memory. The basic storage element is the latch; clocked
latches become flip-flops.

• SR latch: Set/Reset inputs; the invalid state S = R = 1 must be avoided.

• D flip-flop: captures the D input on a clock edge — the workhorse register bit.

• JK flip-flop: like SR but the J = K = 1 case toggles the output.

• T flip-flop: toggles on each clock pulse when T = 1 — the basis of counters.

The clock. A synchronous system updates all flip-flops together on the clock edge, keeping the
whole circuit in a known state. This discipline is why complex digital systems remain predictable.

6.1 Practice problems

P1. Simplify A·B + A. P2. Minimize F(A,B,C) = Σm(0,1,2,3). P3. Full-adder sum and carry
for A=1, B=0, carry-in=1.

Digital Logic Design: A Complete Study Guide Page 7

 Answers. P1: absorption → A. P2: all A=0 minterms → F = A′. P3: sum = 1⊕0⊕1 = 0,
carry = 1·0 + 1·(1⊕0) = 1 → sum 0, carry 1.

Digital Logic Design: A Complete Study Guide Page 8

 7. More Karnaugh Map Practice
Four-variable maps are the sweet spot where K-maps really shine. The map is a 4×4
grid; rows are labelled by AB and columns by CD, both in Gray-code order (00, 01, 11,
10) so that adjacent cells differ in one variable.

Worked Example 11. Minimize F(A,B,C,D) = Σm(0, 1, 4, 5, 12, 13).

Plot the six 1s. Minterms 0,1,4,5 share A=0,C=0; minterms 4,5,12,13 share B=1,C=0.

Group 1 (0,1,4,5) gives A′C′. Group 2 (4,5,12,13) gives BC′.

F = A′C′ + BC′ = C′(A′ + B).

Worked Example 12. Minimize F(A,B,C,D) = Σm(5, 7, 13, 15).

All four have B=1 and D=1; A and C vary across the group.

F = BD.

Sanity check. A group of 2k cells eliminates k variables. Four cells (22) eliminate 2 variables, which is
exactly what happened above — a quick way to verify you grouped correctly.

8. More Combinational Blocks

8.1 Encoder
An encoder is the inverse of a decoder: it takes 2n input lines (one active) and produces
the n-bit code of the active line. A priority encoder resolves the case where several
inputs are active by outputting the code of the highest-priority one.

8.2 Magnitude comparator

A comparator takes two numbers and asserts one of three outputs: A > B, A = B, or A <
B. Equality is detected with XNOR gates on each bit pair (bits equal), while the
greater-than logic works from the most significant differing bit downward.

Worked Example 13. For 2-bit inputs A = 10 and B = 01, which comparator
output is active?
Compare MSBs: A■ = 1, B■ = 0, so A > B is decided immediately.

The A > B output is asserted; the lower bits do not need to be examined.

Digital Logic Design: A Complete Study Guide Page 9

 9. Sequential Design: A Counter
Flip-flops assembled with combinational logic build state machines. A simple example is
a 2-bit binary counter that cycles 00 → 01 → 10 → 11 → 00 on each clock edge, built
from two T flip-flops.

Present state Next state T1 T0

00 01 0 1

01 10 1 1

10 11 0 1

11 00 1 1

The low bit toggles every clock (T0 = 1 always). The high bit toggles only when the
low bit is 1 (T1 = Q0). This T1 = Q0, T0 = 1 rule generalises to any width of ripple
counter.

10. Timing Considerations

Real gates and flip-flops are not instantaneous. Two constraints govern reliable clocked
design: setup time (data must be stable before the clock edge) and hold time (data
must remain stable just after the edge). Violating either can drive a flip-flop into a
metastable state where its output is momentarily undefined. The maximum clock
frequency is set by the longest combinational path (the critical path) plus these timing
margins.

11. Common Mistakes to Avoid

• Grouping non-adjacent cells on a K-map — groups must be powers of two and
physically adjacent (including wrap-around).

• Missing De Morgan on a bar over a whole expression — the complement of a

sum is a product of complements, and vice versa.

• Using the invalid SR latch input S = R = 1, which produces an undefined output.

Digital Logic Design: A Complete Study Guide Page 10

 • Ignoring don't-cares — treating them as 0 by default often misses a simpler
expression.

• Forgetting that XOR means 'differ' — a frequent slip when filling truth tables by
hand.

Digital Logic Design: A Complete Study Guide Page 11

 12. Implementing Functions with a Multiplexer
A multiplexer is a universal building block: a 2n-to-1 MUX can implement any Boolean
function of n variables by wiring the select lines to the inputs and setting each data line to
the function's output for that combination.

Worked Example 14. Implement F(A,B) = A XOR B using a 4-to-1 MUX with
A,B as select lines.
List F for each AB: F(00)=0, F(01)=1, F(10)=1, F(11)=0.

Wire MUX data inputs I■=0, I■=1, I■=1, I■=0; connect A,B to the select lines. The
MUX now outputs XOR for every input.

Why this matters. Lookup-table (LUT) based FPGAs implement logic exactly this way — a small
memory whose address is the inputs and whose contents are the truth table. Any function fits.

13. BCD and Seven-Segment Displays

A seven-segment display shows a decimal digit using seven lit bars (labelled a-g). A
BCD-to-seven-segment decoder takes a 4-bit BCD digit (0000-1001) and drives the
correct segments. Input codes 1010-1111 never occur for valid BCD, so they become
don't-cares that simplify the segment logic.

Worked Example 15. For the digit 1 (BCD 0001), which segments light on a
standard display?
The numeral 1 uses only the two right-hand vertical bars, segments b and c.

So segments b and c are 1; a, d, e, f, g are 0 for that digit.

14. Building a Full Adder from Gates

Tying the whole guide together, here is how the full adder of Section 5 maps to actual
gates, built from two half adders plus an OR.

Half adder 1: inputs A, B → partial sum P = A XOR B, carry G■ = A AND B.

Half adder 2: inputs P, carry-in C■■ → final sum S = P XOR C■■, carry G■ = P AND
C■■.

Digital Logic Design: A Complete Study Guide Page 12

 Carry-out C■■■ = G■ OR G■. That is a full adder from two XORs, two ANDs, and
one OR — five gates.

Chaining n full adders, each carry-out feeding the next carry-in, produces an n-bit
ripple-carry adder — the arithmetic heart of a simple ALU.

15. Extended Boolean Simplification

Worked Example 16. Simplify F = A·B·C + A·B·C′ + A·B′·C.
Combine the first two: A·B·(C + C′) = A·B.

F = A·B + A·B′·C = A·(B + B′·C) = A·(B + C).

F = A·(B + C).

Worked Example 17. Simplify F = (A + B)·(A′ + C)·(B + C).

By the consensus theorem the term (B + C) is redundant: it is implied by the other
two.

F = (A + B)·(A′ + C).

16. Summary
Digital logic connects Boolean algebra to physical circuits. The fundamental laws —
especially absorption and De Morgan — let us shrink expressions, and Karnaugh maps
turn that simplification into a visual grouping task, with don't-cares giving extra freedom.
Universal NAND and NOR gates can build any function. Combinational blocks like
adders, multiplexers, and decoders assemble into datapaths, while flip-flops add the
memory that makes registers, counters, and ultimately whole processors possible.

Digital Logic Design: A Complete Study Guide Page 13