Electrical Engineering › Section T · Combinational logic › Topic T.1
Combinational circuits and universal NAND and NOR gates
Wire a handful of gates together with no feedback and you get a combinational circuit: its outputs depend only on the inputs present right now. This topic shows how to read such a circuit, how to build one from a specification, and why a designer can do it all with a single type of gate.
Circuits with no memory
A combinational circuit is a network of gates in which every signal flows forward from the inputs to the outputs, with no path looping back. Its output at any moment is fixed by the present inputs alone, so a truth table describes it completely. To analyse one, label each gate output with its Boolean expression, working from the inputs towards the output, as in "Boolean simplification, standard forms, and truth tables". The final label is the circuit's expression. Circuits that remember earlier inputs are sequential; they come in the next section.
AND-OR and AND-OR-Invert
The most common two-level structure is AND-OR: a row of AND gates, one per product term, feeding a single OR gate. It builds any sum-of-products expression directly. Two 2-input AND gates and one OR gate give \(X = AB + CD\), which is HIGH for 7 of its 16 input combinations. Put an inverter after the OR gate, or use a NOR gate in its place, and you have AND-OR-Invert (AOI) logic: \(X = \overline{AB + CD}\), which is HIGH for the other 9 combinations. AOI is popular inside integrated circuits because the inverted form is the natural output of a single CMOS gate stage.
Exclusive-OR and exclusive-NOR from basic gates
The XOR function, HIGH when its two inputs differ, can be built from basic gates: \(A \oplus B = A\overline{B} + \overline{A}B\). That needs two inverters, two AND gates and an OR gate. Its complement, the XNOR, is HIGH when the inputs are equal:
Because the XNOR output says whether two bits match, it is the basic building block of the equality comparators in "Comparators, decoders, encoders, and code converters". In practice designers use a dedicated XOR package rather than wiring five gates.
From a specification to a circuit
Design runs the other way. Given an expression, give each product term its own AND gate and combine them in an OR gate; a product-of-sums uses OR gates feeding an AND gate. Given a truth table, write the standard SOP expression: one product term per row where the output is 1, complementing each variable that is 0 in that row. Then minimise it, with Boolean algebra or the maps of "Karnaugh maps, Quine-McCluskey, and VHDL". Fewer terms mean fewer gates, less power and less board space.
Worked example: a majority-vote circuit
Three sensors A, B and C each report 1 for "fault". Raise the alarm X when at least two agree. 1. Truth table:
2. Standard SOP, one term per 1:
3. Since \(ABC = ABC + ABC + ABC\), pair one copy with each other term: \(\overline{A}BC + ABC = BC\), and likewise \(AC\) and \(AB\). 4. Result: \(X = AB + BC + AC\). 5. Check: three 2-input ANDs and one 3-input OR replace four 3-input ANDs, three inverters and a 4-input OR, and all eight rows still match.
NAND and NOR are universal
A gate type is universal if it alone can make NOT, AND and OR, and therefore any function. NAND qualifies. Tie its inputs together and it inverts, since \(\overline{AA} = \overline{A}\). Follow a NAND with a NAND inverter and you have AND. Invert both inputs first and a NAND gives OR, by DeMorgan: \(\overline{\overline{A}\,\overline{B}} = A + B\). Add one more inverter for NOR. So NOT, AND, OR and NOR take 1, 2, 3 and 4 NAND gates. NOR is universal by the mirror-image argument: 1 gate for NOT, 2 for OR, 3 for AND and 4 for NAND.
Dual symbols: negative-OR and negative-AND
As "Inverter, AND, OR, NAND, NOR, and XOR gates" showed, DeMorgan's theorem gives every NAND a second symbol: since \(\overline{AB} = \overline{A} + \overline{B}\), it is also a negative-OR, an OR gate with bubbles on its inputs, and a NOR is likewise a negative-AND. The trick for reading a two-level NAND circuit is to draw the first level as NAND and the second as negative-OR. Each output bubble then meets an input bubble on the same wire, the pairs cancel, and the diagram reads as plain AND-OR. So any SOP expression maps straight onto two levels of NAND gates, and any POS expression onto two levels of NOR gates.
Worked example: the vote circuit in NAND gates only
Build \(X = AB + BC + AC\) using only NAND gates. 1. Replace each AND gate with a NAND: the first level produces \(\overline{AB}\), \(\overline{BC}\) and \(\overline{AC}\). 2. Replace the OR gate with a 3-input NAND, drawn as a negative-OR. 3. Its output is
and DeMorgan turns this back into \(AB + BC + AC\). 4. Check one row: for \(A = 1, B = 1, C = 0\), the first NAND gives 0, so the final NAND has a 0 input and outputs 1, as the table needs. All eight rows agree. 5. Parts: one quad 2-input NAND package such as a 74HC00 (one gate spare) and one 3-input NAND from a 74HC10.
Pulse waveforms and timing
Gates do not care whether their inputs are steady levels or pulse trains: at every instant the output follows the truth table. To sketch an output waveform, mark every time any input changes, then read the inputs in each interval and look up the output. For an XOR gate with A = 1, 0, 1, 1, 0 and B = 1, 1, 0, 1, 0 in five equal intervals, the output is 0, 1, 1, 0, 0. Real gates add propagation delay, typically a few nanoseconds per gate. The longest chain of gates, the critical path, sets how soon the output is valid, and unequal paths can cause brief false pulses called glitches before the output settles.
Describing the circuit in VHDL
In the dataflow style, a concurrent assignment states the Boolean expression. The vote circuit, using the standard type bit, is:
The structural style instead connects instances of predefined components, such as a 2-input NAND, with internal signals, like wiring chips on a board.
Common mistakes to avoid
First, building a truth table's SOP without minimising it. Second, writing the NAND-built OR as a NAND of A and B; the inputs must be inverted first, or you get NAND again. Third, mixing up the dual symbols: a NAND is a negative-OR, not a negative-AND. Fourth, missing input changes when drawing timing diagrams: every edge on any input starts a new interval. Fifth, troubleshooting carelessly: a circuit node joins one output to several inputs, so a short anywhere on it stops the whole node changing. An open TTL input usually acts as a HIGH, but an open CMOS input floats unpredictably.
Key takeaways
Combinational outputs depend only on present inputs. AND-OR builds SOP directly; AOI gives its complement. XNOR detects equality. To design, write SOP from the truth table, minimise, then build. NAND and NOR are each universal. A NAND is also a negative-OR and a NOR a negative-AND, so SOP becomes NAND-NAND and POS becomes NOR-NOR. Timing diagrams apply the truth table interval by interval. VHDL describes a circuit as dataflow or as connected components.
Flashcards
Flashcard
Gates with no feedback; outputs depend only on present inputs
Test your understanding
Question 1 of 5
A truth table has output 1 only in rows ABC = 011, 101, 110 and 111. Which minimised expression does it give?
Question 2 of 5
How many 2-input NAND gates are needed to make a 2-input OR function?
Question 3 of 5
Which statement about the symbols of a NAND gate is correct?
Question 4 of 5
An XOR gate has inputs A = 1, 1, 0, 0 and B = 0, 1, 1, 0 over four intervals. What is its output?
Question 5 of 5
A circuit realises X = AB + CD with two levels of gates using only one gate type. Which arrangement works?
