Digital Electronics I · 96 h · Topic 1 of 3

Combinational logic

Circuits whose output depends only on what is on their inputs at that instant. It is the gateway to all of digital electronics: this is where the adders in a calculator, the decoders of a display and the arithmetic unit of a microcontroller come from.

Digital logic Gates Boolean algebra TTL / CMOS Adders Decoders

01What a combinational circuit is

A digital circuit makes decisions with only two values: 0 and 1. These two values represent everything — a switch open or closed, a sensor that detects or does not detect, one bit of a number.

A circuit is called combinational when its output is determined solely by the combination of inputs present at that moment. It remembers nothing: if 1011 comes in today it gives one output, and if 1011 comes in again tomorrow it gives exactly the same one. That is the whole difference from sequential logic, which does have memory and whose output also depends on past history.

The central idea

Combinational = no memory. The output is a mathematical function of the inputs. That is why every combinational circuit can be written as a truth table, and every truth table can be turned into a circuit. That back-and-forth is the working tool of the subject.

Figure 1. On the left, a combinational block: information flows in one direction only. On the right, a sequential one: feedback creates memory.

02From voltage to bit: logic levels

On paper we write 0 and 1, but on the circuit board there are voltages. A digital circuit does not measure an exact value: it defines two voltage bands and discards the region in between.

Family	Supply	Input = 0	Input = 1	Output = 0	Output = 1
TTL (74LSxx)	5 V ± 0.25 V	< 0.8 V	> 2.0 V	< 0.5 V	> 2.7 V
CMOS (40xx) at 5 V	3 to 15 V	< 1.5 V	> 3.5 V	≈ 0 V	≈ V_DD

The intermediate band (between 0.8 V and 2.0 V in TTL) is a forbidden zone: if an input sits there, the output is unpredictable and the IC may oscillate and heat up. That distance between what an output guarantees and what the next input requires is called the noise margin, and it is the reason digital is so robust: a 300 mV noise spike does not change the bit.

A classic lab mistake

A floating input is not 0. In TTL it floats toward 1 and in CMOS it sits at an undefined level that makes the IC oscillate and draw extra current. Every unused input must be tied to V_CC (through 1 kΩ) or to ground, whichever suits the function.

03Logic gates

A gate is the elementary block: it receives one or more bits and delivers one. With seven types you can build any combinational circuit that exists.

Figure 2. Standard symbols (ANSI). The small circle at the output always means negation: NAND is AND with a small circle, NOR is OR with a small circle.

Truth table of the two-input gates

A	B	AND	OR	NAND	NOR	XOR	XNOR
0	0	0	0	1	1	0	1
0	1	0	1	1	0	1	0
1	0	0	1	1	0	1	0
1	1	1	1	0	0	0	1

It is best to learn them by their rule in words, not by memorizing row by row:

AND — the output is 1 only if all the inputs are 1. “And.”
OR — is 1 if at least one input is 1. “Or.”
NOT — inverts. It is the only one with a single input.
NAND — is 0 only when all the inputs are 1. It is the negated AND.
NOR — is 1 only when all the inputs are 0.
XOR — is 1 when the inputs are different. Difference detector.
XNOR — is 1 when the inputs are equal. One-bit comparator.

A truth table with $n$ inputs always has $2^{n}$ rows: 2 inputs → 4 rows, 3 inputs → 8 rows, 4 inputs → 16 rows. The combinations are filled in ascending binary order so that none is skipped.

🔢 Interactive Digital Logic course Gates with symbols and their ICs, circuit builder with Karnaugh map and automatic simplification, and sequential logic. A publication of this site. ›

04Boolean algebra

Boolean algebra is the mathematics of digital circuits. It works with variables that can only be 0 or 1 and with three operations: product (AND, written $\cdot$ or nothing), sum (OR, written $+$ ) and complement (NOT, written with a bar on top).

Law	Product form (AND)	Sum form (OR)
Identity element	A · 1 = A	A + 0 = A
Null element	A · 0 = 0	A + 1 = 1
Idempotence	A · A = A	A + A = A
Complement	A · A̅ = 0	A + A̅ = 1
Commutative	A · B = B · A	A + B = B + A
Associative	(A·B)·C = A·(B·C)	(A+B)+C = A+(B+C)
Distributive	A·(B+C) = A·B + A·C	A + B·C = (A+B)·(A+C)
Absorption	A · (A+B) = A	A + A·B = A
Double negation	A̅̅ = A

De Morgan's theorems

They are the two most useful identities in the entire subject. They let you swap sums for products and vice versa, which is what makes it possible to build any circuit with a single type of gate.

(A · B) negated = A̅ + B̅
(A + B) negated = A̅ · B̅

The mnemonic: break the bar and change the sign. In words: “it is not true that A and B” is equivalent to “not A, or not B.”

One detail that causes confusion in the third distributive law: A + B·C = (A+B)·(A+C) has no equivalent in the algebra of ordinary numbers. In Boole it holds, and you can check it by building the truth table of both sides and verifying that they match row by row. That is, in fact, the universal method for proving any Boolean identity.

05From the truth table to the circuit

This is the procedure you must master, because it solves all the design problems of the subject. You start from the problem statement, build the table and arrive at the schematic.

Step 1 — Sum of products (SOP)

Look only at the rows where the output is 1. Each of those rows generates a product (an AND) in which each variable appears uncomplemented if it is 1 in that row, and complemented if it is 0. Then all those products are summed (OR).

Worked example · Majority circuit

A three-person jury (A, B, C) approves a proposal if two or more vote in favor. Design the circuit that turns on light S.

A	B	C	S	Product it contributes
0	0	0	0	—
0	0	1	0	—
0	1	0	0	—
0	1	1	1	A̅·B·C
1	0	0	0	—
1	0	1	1	A·B̅·C
1	1	0	1	A·B·C̅
1	1	1	1	A·B·C

Unsimplified expression:

S = A̅·B·C + A·B̅·C + A·B·C̅ + A·B·C

As it stands it requires 4 AND gates with 3 inputs each, 3 inverters and 1 OR with 4 inputs. It can be done much better.

Step 2 — Simplify

You can simplify with Boole's laws or with a Karnaugh map. In the example, the trick is to duplicate the term A·B·C (by idempotence, $X + X = X$ , so it can be used three times) and group in pairs:

A̅·B·C + A·B·C = B·C·(A̅ + A) = B·C
A·B̅·C + A·B·C = A·C·(B̅ + B) = A·C
A·B·C̅ + A·B·C = A·B·(C̅ + C) = A·B

S = A \cdot B + A \cdot C + B \cdot C

Simplified majority circuit: 3 ANDs with 2 inputs each and 1 OR with 3 inputs. No inverters.

From 8 gates it dropped to 4, and the inverters disappeared. The final expression also reads better: “it passes if A and B agree, or A and C, or B and C.” Simplifying is not an academic whim: fewer gates means fewer ICs, less power consumption, less circuit board and less delay.

Step 3 — Draw the schematic

Figure 3. Majority circuit, animated: it runs through the eight possible combinations of A, B and C. The green wires are the ones at 1, and the filled dots are connection nodes.

Drawing convention

In a schematic, two lines that cross are not connected unless there is a thick dot at the intersection. It is the number-one cause of misread schematics in exams and in the workshop.

06Equivalent circuits and universal gates

Two circuits are equivalent if they have the same truth table, no matter how they are built inside. This opens a very practical possibility: any function can be built using only NANDs or only NORs. That is why they are called universal gates.

What is that good for? If the workshop has a 74LS00 (four NANDs) and you need an inverter, there is no need to go looking for a 74LS04. You solve it with a NAND.

Desired function	Built with NANDs	Quantity
NOT A	NAND with both inputs tied to A	1
A · B	NAND followed by a NAND used as an inverter	2
A + B	Invert A and B with NANDs, plus a final NAND (De Morgan)	3
A ⊕ B	Classic four-NAND network	4

The justification for the OR row is pure De Morgan: A + B = (A̅ · B̅) negated. That is, I negate each input and apply a NAND: that gives exactly an OR. The same reasoning, reversed, lets you build everything with NORs.

Why the industry cares

In CMOS technology, the NAND is made with 4 transistors and is faster and smaller than the AND (which takes 6: a NAND plus an inverter). That is why integrated-circuit libraries are built on NAND and NOR, and AND/OR gates are synthesized from them. “Universality” is not a clever game: it is how chips are made.

07TTL and CMOS technologies

Gates are bought as ICs. The two families used in the technical school are TTL (74 series) and CMOS (40 series and 74HC).

TTL — 74LSxx series

Built with bipolar transistors.
Fixed supply: 5 V ± 0.25 V. Out of range it does not work.
Fast (typical delay 10 ns in LS).
Draws current even when not switching (≈ 2 mA per gate in LS).
Floating input = behaves as 1.
Little sensitivity to static electricity.
Typical fan-out: 20 LS inputs.

CMOS — 40xx / 74HCxx series

Built with complementary MOSFET transistors.
Wide supply range: 3 to 15 V (40xx series).
Almost zero quiescent consumption (µA). Ideal for battery operation.
Output swings practically to 0 V and to V_DD.
Floating input = undefined level, it oscillates.
Very sensitive to static: it must be handled with care.
High input impedance: huge fan-out at DC.

The ICs used in the workshop

Function	TTL	CMOS	Contents
2-input NAND	74LS00	CD4011	4 gates
2-input NOR	74LS02	CD4001	4 gates
Inverter	74LS04	CD4069	6 gates
2-input AND	74LS08	CD4081	4 gates
3-input NAND	74LS10	CD4023	3 gates
2-input OR	74LS32	CD4071	4 gates
2-input XOR	74LS86	CD4030 / CD4070	4 gates
4-bit full adder	74LS83	CD4008	1 block
BCD → 7-segment decoder	74LS47 (common anode)	CD4511 (common cathode)	1 block

Precautions that prevent burning out ICs

Never connect the power supply backwards. On a 14-pin DIP, V_CC is pin 14 and GND pin 7 in TTL; on a 14-pin CMOS, V_DD is pin 14 and V_SS pin 7. On 16-pin packages it changes: always check the datasheet.
Decoupling capacitor of 100 nF between V_CC and GND, as close as possible to each IC. Without it, false switching appears because of current spikes.
CMOS and static: touch ground before handling, do not shuffle your feet, store the ICs in conductive foam.
Do not mix families carelessly: a CMOS output at 5 V drives a TTL input fine, but a CMOS powered at 12 V destroys a 5 V TTL input.
Disconnect the power supply before changing any wire on the breadboard.

08Typical combinational blocks

In practice you do not design everything from loose gates: there are ready-made blocks that come in a single IC. You need to know what they do and how they are connected.

Half adder and full adder

Adding two bits gives a result and sometimes a carry. The half adder adds two bits and delivers sum and carry:

A	B	S (sum)	C_o (carry)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Looking at column S you recognize the XOR, and looking at C_o you recognize the AND:

S = A \oplus B

C_{o} = A \cdot B

Half adder: one XOR and one AND. Nothing more.

The half adder is no use from the second column onward, because there the carry from the previous column comes in. That is what the full adder is for, with three inputs (A, B, C_in):

S = A \oplus B \oplus C_{i n}

C_{o u t} = A \cdot B + C_{i n} \cdot (A \oplus B)

Full adder. Note that C_out is a majority circuit in disguise: there is a carry when two or more of the three inputs are 1.

Chaining four full adders (the C_out of one to the C_in of the next) gives a 4-bit adder, which is exactly what is inside the 74LS83 or the CD4008. This chaining is called ripple carry (or serial carry), and its limit is time: the carry has to propagate stage by stage.

Decoder

A decoder takes a binary number of $n$ bits and activates only one of its $2^{n}$ outputs: the one that corresponds to that number. A 3-to-8 decoder (74LS138) has 3 inputs and 8 outputs.

The most widely used case in school is the BCD to 7-segment decoder, which takes a digit in binary (0000 to 1001) and lights the corresponding segments of a display:

Figure 4. BCD to 7-segment decoder, animated: counts from 0 to 9 showing the four input bits and the segments that light up. Each segment has its series current-limiting resistor.

Encoder

It does the inverse: it receives several lines and delivers the binary number of the one that is active. If two keys are pressed at once the result would be ambiguous, so priority encoders are used (74LS147, 10 lines to BCD), which serve the highest-weight input and ignore the others. It is what is behind a numeric keypad.

Multiplexer and demultiplexer

The multiplexer (74LS151) is an electronic selector switch: it has several data inputs, some select lines and a single output; it connects to the output the input that the selection indicates. The demultiplexer does the opposite, routing one input to the chosen output. With multiplexers you save wires — the same idea a microcontroller uses to read eight sensors with a single A/D converter.

09In the lab

Lab 1 · Verifying a truth table

Materials: breadboard, 74LS00 (or CD4011), 5 V supply, 2 switches or wires to V_CC/GND, 1 LED, 1 resistor (330 Ω), 100 nF capacitor.

Power up: pin 14 to +5 V, pin 7 to GND. Place the 100 nF capacitor across them.
Connect inputs 1 and 2 (first NAND) to the switches. Each switch takes the input to +5 V or to GND — never floating.
The output (pin 3) goes to the LED with the 330 Ω resistor in series to ground.
Run through the four combinations and note the state of the LED.
Also measure the output voltage with the multimeter in each case and compare it with the values in the logic levels table.

Lab 2 · The majority circuit

Build the circuit of Figure 3 with a 74LS08 (three ANDs) and a 74LS32 (a 2-input OR used twice in cascade, since the 74LS32 does not have a 3-input OR). Verify the eight combinations against the calculated truth table. It is the same circuit that decides by majority in redundant aviation systems.

Lab 3 · Universality of the NAND

With a single 74LS00, build in succession a NOT, an AND and an OR. Verify each one with the LED. It is the practical check of De Morgan and makes it perfectly clear why the NAND is universal.

10Common mistakes

Symptom	Usual cause
The output changes by itself or flickers	Floating inputs, or the decoupling capacitor is missing.
The IC heats up	Reversed supply, shorted output, or two outputs tied together.
Two outputs connected together	This is never done: one drives 0 and the other 1, and they destroy each other. To join outputs, open-collector or three-state outputs are used.
The LED does not light at all	Missing current-limiting resistor, LED backwards, or the TTL output cannot source current in the high state (it is better to connect the LED to V_CC and turn it on with a 0).
The truth table does not match	The combinations were counted wrong: you must go in binary order, from 000 to 111, without skipping any.
The simplification gives something different	A negation bar was forgotten. It is a good idea to check the simplified expression by building its truth table again.

11Self-assessment

Answer before opening each answer.

How many rows does the truth table of a 5-input circuit have?

2⁵ = 32 rows. The rule is always 2ⁿ.

Write A + B·C̅ as a sum of products and say in which rows it is 1 (with A, B, C).

It is 1 when A = 1 (rows 100, 101, 110, 111) or when B = 1 and C = 0 (rows 010 and 110, the latter already counted). Total: 100, 101, 110, 111 and 010 — five rows.

Apply De Morgan to (A + B̅ + C) negated.

Break the bar and change the sign: A̅ · B · C̅. Note that B̅ negated becomes B again, by double negation.

Why is an unconnected TTL input read as 1?

Because of the internal input structure of TTL: the emitter of the input transistor is left floating and the junction ends up biased so that the circuit interprets a high level. It still should not be done: it is an input with no noise margin, very sensitive to interference.

Simplify A·B + A·B̅.

A·(B + B̅) = A·1 = A. It is the same grouping used in the majority circuit: when a variable appears uncomplemented and complemented in two terms that are otherwise identical, that variable disappears.

What is the practical difference between the 74LS47 and the CD4511?

Both decode BCD to 7 segments, but the 74LS47 has active-low outputs and drives common-anode displays, whereas the CD4511 has active-high outputs and drives common-cathode displays. Choosing the wrong one makes the display stay off or light up inverted.

A circuit must give 1 only when all three inputs are equal. Write the expression.

Only two rows give 1: 000 and 111. So S = A̅·B̅·C̅ + A·B·C. With gates: two 3-input ANDs (one with the inputs inverted) and an OR.

Why does the full adder need three inputs and the half adder two?

Because when adding multi-bit numbers, each column also receives the carry generated by the previous column. The half adder only works for the least-significant column, where there is no incoming carry.

Next topic →

Sequential logic