EIE 342 / 327 | Digital Electronics

COMBINATIONAL
LOGIC
CIRCUITS
A complete, beginner-friendly lesson note
1. What is Combinational Logic?
When you press a light switch, the light turns on — the output depends only on what you're doing right now.
This is the idea behind combinational logic: the output depends solely on the current inputs, with no
memory of what happened before.

Definition: A combinational logic circuit is a digital circuit whose output(s) depend ONLY on the
present combination of input values — not on any previous inputs or states.

Three things that combinational logic does NOT have:

• No Memory: it cannot store past states.
• No Feedback: outputs are never routed back to inputs.
• No dependence on past inputs: only the current input combination determines the output.

Combinational vs Sequential Logic

It helps to understand combinational logic by contrasting it with the other major category:
Property Combinational Logic Sequential Logic

Output depends on Present inputs only Present inputs + past states

Memory None Has memory (flip-flops, latches)

Feedback No feedback Has feedback paths

Example Adder, Decoder, MUX Counter, Register, Shift Register

Analogy Calculator — forgets each Alarm clock — remembers the

calculation time set

Analogy: A calculator is combinational — type '5 + 3', press '=', get 8. The instant you clear it, all
memory is gone. A digital clock is sequential — it remembers what time it is and counts upward.

Common Combinational Circuit Examples

• Adders: Add binary numbers (Half Adder, Full Adder)
• Multiplexers (MUX): Select one of many input signals to forward to the output
• Decoders: Identify a specific binary code and activate a corresponding output
• Encoders: Convert a specific input signal into a coded binary output
• Comparators: Compare two binary numbers and indicate equal/greater/lesser
• Parity Generators: Check for errors in transmitted data

2. Truth Tables — The Foundation of Circuit

Design
A truth table is simply a structured list of ALL possible input combinations and the corresponding output for
each combination. It is the most important tool for understanding and designing combinational circuits.

Rule: For a circuit with N inputs, the truth table has exactly 2^N rows. So 2 inputs -> 4 rows; 3
inputs -> 8 rows; 4 inputs -> 16 rows.

2.1 AND Gate Truth Table (2 inputs)

An AND gate outputs 1 ONLY when ALL inputs are 1 — like a series switch: both switches must be closed for
current to flow.
A B Output (Y)
0 0 0
0 1 0
1 0 0
1 1 1

Y = A . B
AND Gate Boolean Expression — the dot (.) means AND

2.2 OR Gate Truth Table (2 inputs)

An OR gate outputs 1 when AT LEAST ONE input is 1.
A B Output (Y)
0 0 0
0 1 1
1 0 1
1 1 1

Y = A + B
OR Gate Boolean Expression — the plus (+) means OR

2.3 NOT Gate (Inverter)

A NOT gate flips the input. If input is 1, output is 0, and vice versa.
A Output (Y = A')
0 1
1 0

Y = A' or Y = A-bar
NOT Gate (complement) — a bar or apostrophe over the variable
2.4 Reading a Combinational Truth Table
Here is a truth table where the output is 1 only when both inputs are EQUAL (both 0 or both 1):
A B Y (A equals B?)
0 0 1
0 1 0
1 0 0
1 1 1

Reading the truth table to build a Boolean expression: collect the rows where Y = 1 and write a product term
for each:
Row 1 (A=0, B=0): A is 0 -> write A'. B is 0 -> write B'. Term = A'B'
•
• Row 4 (A=1, B=1): A is 1 -> write A. B is 1 -> write B. Term = AB
Combine the terms with OR:

Y = A'B' + AB
Output equals 1 when inputs are equal (XNOR function)

Why Truth Tables Matter

• They completely and unambiguously describe the circuit's behaviour.
• They are the starting point for deriving Boolean expressions.
• They verify a circuit design before building it.

3. The Combinational Circuit Design Process

Every combinational circuit — no matter how complex — is designed using these four steps in order:

Ste What you do Output of this step

p

1 Understand the problem — identify inputs, Clear specification

outputs, and rules

2 Build the truth table — list all 2^N input Complete truth table
combinations and determine each output

3 Write the Boolean expression — read 1-output Boolean equation

rows and combine with OR

4 Draw the logic circuit — implement the Boolean Circuit diagram

expression using gates

Important: Always build the truth table FIRST before writing any Boolean expression. Skipping
this step leads to errors. The truth table is your contract with the design problem.
Full Worked Example — Design a Circuit for Equal Inputs
Problem: Design a circuit whose output is 1 when both inputs are equal.

Step 1 — Understand the Problem

Inputs: A and B (each can be 0 or 1). Output Y = 1 when A = B (both 0 or both 1).

Step 2 — Build the Truth Table

With 2 inputs -> 2^2 = 4 rows:
A B Y Reason
0 0 1 Both equal (both 0) -> Y = 1
0 1 0 Not equal -> Y = 0
1 0 0 Not equal -> Y = 0
1 1 1 Both equal (both 1) -> Y = 1

Step 3 — Write the Boolean Expression

Identify rows where Y = 1: rows 1 and 4.
• Row 1 (A=0, B=0): Both inputs complemented -> term: A'B'
• Row 4 (A=1, B=1): Both inputs true -> term: AB

Y = A'B' + AB
Sum of Products (SOP) expression

Step 4 — Draw the Logic Circuit

From the Boolean expression Y = A'B' + AB:
1. Invert A using a NOT gate -> A'
2. Invert B using a NOT gate -> B'
3. AND gate 1: inputs A' and B' -> output A'B'
4. AND gate 2: inputs A and B -> output AB
5. OR gate: inputs A'B' and AB -> final output Y

Gate count: This circuit uses: 2 NOT gates, 2 AND gates, 1 OR gate. This is a standard XNOR
circuit — it outputs 1 when both inputs are the same.

4. Practice Problems — Circuit Design

Exercise 1 — Alarm System

A classroom has:
 • C: Control unit (1 = ON, 0 = OFF)
• M: Motion sensor (1 = triggered)
• D: Door sensor (1 = triggered)
• G: Glass-break sensor (1 = triggered)

Rules:
• The alarm activates (A=1) when: C=1 AND any of M, D, or G is triggered.
• Additionally: the alarm also activates when G=1 regardless of C.

Step 1 — Truth Table (simplified — showing key cases)

With 4 inputs -> 16 rows. Key insight from the rules:

Deriving the Boolean Expression

Rule 1: C=1 AND (M=1 OR D=1 OR G=1) -> Alarm ON
Expression 1: C . (M + D + G)

Rule 2: G=1 alone -> Alarm ON (regardless of C)

Expression 2: G

Combine with OR (alarm if either rule is satisfied):

A = C . (M + D + G) + G

Simplify using Boolean algebra:

A = CM + CD + CG + G
A = CM + CD + G(C + 1)
A = CM + CD + G (since X + 1 = 1)

Final expression: A = G + CM + CD

A = G + C.M + C.D
Alarm is ON when: glass breaks, OR (control ON AND motion), OR (control ON AND door)

Exercise 2 — 3-Input Majority Voting System

Design a circuit that outputs 1 when the majority of 3 votes is YES (i.e., 2 or more inputs are 1).

Truth Table — 3 inputs, 8 rows

A B C Y (Majority)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
 1 1 0 1
1 1 1 1

Deriving the Boolean Expression

Rows where Y = 1: (0,1,1), (1,0,1), (1,1,0), (1,1,1)

Write a product term for each:

Row (0,1,1): A'BC
Row (1,0,1): AB'C
Row (1,1,0): ABC'
Row (1,1,1): ABC

Sum of Products expression:

Y = A'BC + AB'C + ABC' + ABC

Simplify (grouping terms that differ by one variable):

Group ABC' + ABC = AB(C' + C) = AB
Group AB'C + ABC = AC(B' + B) = AC
Group A'BC + ABC = BC(A' + A) = BC

Final simplified expression:

Y = AB + AC + BC

Y = AB + AC + BC
Output is 1 when any two (or all three) inputs are 1

Gate implementation: 3 AND gates (AB, AC, BC) + 1 three-input OR gate = 4 gates total.

Exercise 3 — Smart Home Lighting

Turn the light ON when: it is DARK (D=1) AND someone is in the room (P=1) AND it is NOT daytime (T=0, so
T'=1).

L = D . P . T'
Light turns ON only when dark, occupied, and not daytime

D (Dark) P (Person) T (Daytime) L (Light ON)

0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
5. Decoders
A decoder is a combinational circuit designed to detect a specific binary pattern and activate the
corresponding output.

Definition: A decoder detects the presence of a particular digital code and activates exactly one
output for that code. With N inputs, a decoder can have up to 2^N outputs.

The key idea: for every unique combination of input bits, ONE and only one output line goes HIGH (or LOW,
for active-low decoders).

5.1 Single-Gate Decoders

The simplest decoder is a single AND or NAND gate — possibly combined with NOT gates — that fires when a
specific input pattern is present.

Example: Detect binary code 1010 (A=1, B=0, C=1, D=0)

We need output HIGH only when A=1, B=0, C=1, D=0.

Step 1 — Complement the inputs that must be 0:

B=0 -> use B' D=0 -> use D'

Step 2 — AND all terms together:

Y = A . B' . C . D'

Gate circuit: feed A, B', C, D' into a 4-input AND gate.

Output Y = 1 ONLY when the input is 1010.

5.2 Multiple-Output Decoders (Full Decoder)

A full decoder has one output for EVERY possible input combination. For a 2-to-4 decoder (2 inputs, 4
outputs):
A B Y0 (00) Y1 (01) Y2 (10) Y3 (11)
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1

Boolean expressions for each output:

• Y0 = A'B' — active when input is 00
• Y1 = A'B — active when input is 01
• Y2 = AB' — active when input is 10
• Y3 = AB — active when input is 11
5.3 Seven-Segment Display Decoder
A seven-segment display has 7 LED segments (labelled a-g) arranged like the number 8. By lighting different
combinations, you can display any digit 0-9.

How it works: A BCD (Binary-Coded Decimal) to 7-segment decoder takes a 4-bit binary input
(0000 to 1001 = digits 0 to 9) and activates the correct segments to display that digit.

Segment layout (viewed from the front):

Seven-Segment Display — Segment Positions

_
|a|
f | | b
|g|
e | | c
|d|

Digit 0: segments a, b, c, d, e, f ON (g = OFF)

Digit 1: segments b, c ON (all others OFF)
Digit 7: segments a, b, c ON
Digit 8: ALL segments ON

Digit BCD (ABCD) a b c d e f g

0 0000 1 1 1 1 1 1 0

1 0001 0 1 1 0 0 0 0

2 0010 1 1 0 1 1 0 1

3 0011 1 1 1 1 0 0 1

4 0100 0 1 1 0 0 1 1

5 0101 1 0 1 1 0 1 1

6 0110 1 0 1 1 1 1 1

7 0111 1 1 1 0 0 0 0

8 1000 1 1 1 1 1 1 1

9 1001 1 1 1 1 0 1 1

6. Introduction to Sequential Logic Circuits

So far, all circuits we've seen are combinational — the output depends only on current inputs. Now we move
to sequential circuits, where the output also depends on the history of inputs.
 Definition: A sequential circuit is a digital circuit whose output depends on both the PRESENT
inputs AND the PAST state of the circuit. Sequential circuits contain memory elements.

Aspect Combinational Sequential

Output depends on Present inputs only Present inputs + stored state

Memory elements None Latches or Flip-Flops

Clock required No Usually yes

Examples Adder, Decoder Counter, Register, Memory

7. Latches — The Simplest Memory Element

A latch is the most basic sequential circuit. It can store a single bit — either a 0 or a 1 — and holds that value
until it is explicitly changed.

Definition: A latch is a sequential circuit with two inputs called SET and RESET. SET stores a logic
1. RESET stores a logic 0. The stored value is held (latched) until the next SET or RESET command.

Key terms:
• SET: Makes the output Q = 1 (stores a HIGH). Also called the stored HIGH state.
• RESET: Makes the output Q = 0 (stores a LOW). Also called the stored LOW state.
• Q: The output of the latch — the stored value.
• Q' (Q-bar): The complement output — always opposite to Q.

7.1 SR (Set-Reset) Latch

The basic SR latch has two inputs (S and R) and two outputs (Q and Q'). It is built from two cross-coupled
NOR gates (or NAND gates).

SR Latch Truth Table

S R Q (Next State) Action
0 0 Q (unchanged) No Change — latch holds its value
0 1 0 RESET — Q goes to 0
1 0 1 SET — Q goes to 1
1 1 ? FORBIDDEN — both outputs undefined!

Forbidden State: When S=1 and R=1 simultaneously in an SR latch, both outputs try to be the
same — this is a contradiction. This state is FORBIDDEN and must be avoided in design.
 Latch memory: When S=0 and R=0 (No Change row), the latch does nothing — it just holds
whatever value it stored last. This is how memory works: the circuit remembers without needing
a constant input.

7.2 Gated SR Latch

A Gated SR latch adds an extra ENABLE input that controls WHEN the latch is allowed to respond to its S and
R inputs. This solves the problem of latches being sensitive to noise at all times.

• ENABLE = 1: The latch is active — S and R inputs are passed through to the latch gates.
• ENABLE = 0: The latch is inhibited — S and R inputs are blocked. Outputs hold their state.

The ENABLE input can be used in two ways:

6. As an ON/OFF switch: disable the latch when you don't want it to change.
7. As a synchronising signal: connect to a clock so the latch only changes at specific times.

Gated SR Latch Truth Table

ENABLE S R Function
1 0 0 No Change — latch holds its
current state
1 0 1 RESET — Q = 0
1 1 0 SET — Q = 1
1 1 1 FORBIDDEN — avoid this
combination!
0 X X Inhibited — inputs ignored,
state held

8. Flip-Flops — Edge-Triggered Memory

8.1 Latch vs Flip-Flop

A gated latch changes its output whenever ENABLE is HIGH and S or R changes. This can cause problems if
the inputs are noisy — the output might change multiple times during a single clock pulse.

A flip-flop solves this by responding ONLY to the edge (transition) of the clock signal, not the full level.

Property Gated Latch Flip-Flop

Responds to Level of ENABLE (whole HIGH period) Edge of clock only (instant of
transition)

Output changes Any time while ENABLE is HIGH Only once per clock edge
 Sensitivity to noise Higher (level-sensitive) Lower (edge-sensitive)

Stability Less stable More stable and predictable

Key terms for flip-flops:

• Clock: An enabling input sensitive to the positive or negative EDGE of a waveform.
• Edge: The HIGH-to-LOW (negative/falling) or LOW-to-HIGH (positive/rising) transition of a pulse.
• Edge-Triggered: Enabled only by the edge of the clock, not its level.
• Toggle: To alternate between 0 and 1 with each applied clock pulse.
• Edge Detector: A circuit that converts the active clock edge to a brief pulse for the internal latch.

8.2 D Flip-Flop (Data / Delay Flip-Flop)

The D flip-flop is the simplest and most widely used flip-flop. It has one data input (D) and one clock input.
On the active clock edge, the output Q simply copies the input D.

D Flip-Flop rule: Q (after clock edge) = D (before clock edge). Whatever is on D gets latched into
Q when the clock ticks. D stands for Data (or Delay — the value is 'delayed' to appear on Q at the
next clock edge).

D Flip-Flop Truth Table

Clock Edge D Q (next) Action
^ (rising) 0 0 Q is reset to 0
^ (rising) 1 1 Q is set to 1
No edge X Q Q holds previous value
(unchanged)

• Primary use: Data storage, registers, memory cells, pipeline stages.

• Advantage: Eliminates the forbidden state of the SR latch — D can only be 0 or 1.

8.3 JK Flip-Flop
The JK flip-flop is an improved version of the SR flip-flop. J behaves like S (SET) and K behaves like R (RESET).
The key improvement: when J=1 and K=1, instead of a forbidden state, the output TOGGLES (switches to
opposite state).

JK Flip-Flop Truth Table

CLK Edge J K Function Q (next)
^ 0 0 No Change Q (holds)
^ 0 1 RESET 0
^ 1 0 SET 1
^ 1 1 TOGGLE Q' (flips)
No edge X X Inhibited Q (holds)
The Toggle feature: When J=K=1, the JK flip-flop toggles — if Q=0 it becomes 1, if Q=1 it
becomes 0 — on every clock edge. This makes JK flip-flops ideal for binary counters and
frequency dividers.

• Primary use: Counters, frequency dividers, shift registers, state machines.

• Advantage over SR: No forbidden state — J=K=1 is defined as TOGGLE.

9. Summary — Sequential Memory Elements

Element Inputs Triggered by Forbidden state? Key use

SR Latch S, R Level (S or R Yes — S=R=1 Simple storage

change)

Gated SR Latch S, R, ENABLE Level (ENABLE high) Yes — S=R=1 when Controlled storage
enabled

D Flip-Flop D, Clock Clock EDGE No Registers, memory

JK Flip-Flop J, K, Clock Clock EDGE No — J=K=1 = Toggle Counters, dividers

10. Chapter Summary & Key Formulas

In a nutshell: Combinational logic circuits output a value based solely on present inputs — no
memory. Sequential circuits add memory (latches/flip-flops) so outputs depend on both present
inputs AND the stored history. The design process always starts with a truth table.

Concept Key fact / Formula

Combinational logic Output = f(current inputs only). No memory, no feedback.

Truth table size 2^N rows for N inputs

AND Gate Y = A . B — output 1 ONLY when all inputs are 1

OR Gate Y = A + B — output 1 when ANY input is 1

NOT Gate Y = A' — output is always opposite of input

SOP expression Write product term for each row where Y=1, then OR them
together

2-to-4 Decoder One of 4 outputs active for each of the 4 input combinations

SR Latch S=1->Q=1 (set); R=1->Q=0 (reset); S=R=0->hold; S=R=1-

>forbidden

D Flip-Flop Q(next) = D, sampled at clock edge. No forbidden state.

 JK Flip-Flop J=K=0->hold; J=1,K=0->set; J=0,K=1->reset; J=K=1->toggle

Majority vote (3 in) Y = AB + AC + BC — output 1 when 2+ inputs are 1