Boolean Algebra, Minimisation and Combinational Circuits
Boolean algebra is a small algebra — two elements, three operations — and the whole of it can be derived from a handful of postulates, so there is very little to memorise and a great deal to be fluent in. Two identities do most of the work in an exam. De Morgan's laws turn a complemented product into a sum of complements and vice versa, which is how any expression is pushed into NAND-only or NOR-only form; and the consensus and absorption identities are what let you cancel a term without drawing a map. Beyond the algebra, the section asks for minimisation, and this is the one place in Digital Logic with a question shape all of its own: how many prime implicants does this function have, and how many of them are essential? Those are two different numbers, and the gap between them is the whole point. A prime implicant is a product term that cannot be made larger while still implying the function — every group on a Karnaugh map that cannot be doubled. An essential prime implicant is one that covers a minterm no other prime implicant covers, so it must appear in every minimal expression. A function can be rich in prime implicants and have almost no essential ones, which is exactly the case worked below. The combinational half then applies all of it: adders, multiplexers and decoders are the standard blocks, and the useful fact to carry is that a 2^n-to-1 multiplexer can realise any function of n + 1 variables, which turns a great many implementation questions into a counting exercise.
Prime Implicants, and Which of Them Are Essential
Take f(A,B,C,D) = Σm(0,1,2,3,5,7,8,10,14,15). A Karnaugh map of it groups in several ways, and the counts that a question asks for are these: it has six prime implicants and only two essential ones. The six are A′B′, A′D, B′D′, ABC, ACD′ and BCD. The two essential ones are A′D, the only cover of minterm 5, and B′D′, the only cover of minterm 8.
| Prime implicant | Minterms it covers | Essential? |
|---|---|---|
| A′D | 1, 3, 5, 7 | Yes — sole cover of 5 |
| B′D′ | 0, 2, 8, 10 | Yes — sole cover of 8 |
| A′B′ | 0, 1, 2, 3 | No — every minterm also covered elsewhere |
| ABC | 14, 15 | No — 14 in ACD′, 15 in BCD |
| ACD′ | 10, 14 | No |
| BCD | 7, 15 | No |
🎯 Why the two counts come apart
A prime implicant is a local fact about one group — it cannot be doubled. Essentiality is a global fact about the whole function — some minterm has no other home. So a function whose minterms are each reachable several ways has many prime implicants and few essential ones, and that is what happens here: only minterms 5 and 8 sit in exactly one group, so only two prime implicants are forced. Everything else is a choice. The minimal expression here happens to be unique — A′D + ABC + B′D′, three terms and seven literals — but uniqueness is not guaranteed by the counts, and a question asking "how many minimal expressions are there" is a different question again. Read which of the three is being asked before counting anything.⚠️ A don't-care may be used, and need not be
A don't-care entry is a permission, not an obligation: include it when it makes a group bigger, ignore it when it does not. That asymmetry is where marks go. Counting prime implicants with don't-cares gives a different number from counting them without, because a don't-care can enlarge a group and so destroy a smaller group's primality. And a don't-care never creates an essential prime implicant on its own — essentiality is about covering a 1, so a group that covers only don't-cares is not needed at all, however large it is.Adders, Multiplexers and Decoders
A half adder produces sum = A ⊕ B and carry = A·B. A full adder adds a carry-in and is two half adders plus an OR. Chaining n full adders gives a ripple-carry adder, whose delay is the problem: the carry must propagate through every stage, so the worst-case delay is proportional to n — which is what carry-lookahead exists to fix, at the cost of gates.
🧠 A 2^n-to-1 multiplexer realises any function of n + 1 variables
Drive the n select lines with n of the variables. Each of the 2^n data inputs then corresponds to one combination of those variables, and the residual function of the one remaining variable is always 0, 1, that variable, or its complement — all four of which are available for free. So an 8-to-1 MUX (three selects) implements any function of four variables, and a 4-to-1 implements any function of three. The commonest error is off by one in the safe direction: assuming an 8-to-1 handles only three variables, and reaching for a 16-to-1 that is not needed. A decoder is the same idea inverted — an n-to-2^n decoder generates every minterm, so a decoder plus an OR gate implements any single function, and a decoder plus several OR gates implements several functions of the same inputs at once.Key takeaways
- De Morgan is the bridge to NAND-only and NOR-only forms; both gates are functionally complete on their own.
- XOR takes four 2-input NAND gates; a full adder is two half adders and an OR.
- A prime implicant is a group that cannot be doubled — a local fact about one group.
- An essential prime implicant is the sole cover of some minterm — a global fact about the function.
- The two counts differ freely: Σm(0,1,2,3,5,7,8,10,14,15) has six prime implicants and two essential ones.
- A don't-care is a permission, not an obligation, and never makes a prime implicant essential.
- A 2^n-to-1 multiplexer realises any function of n + 1 variables — an 8-to-1 covers four.
- A ripple-carry adder’s delay grows with the word length, which is the reason carry-lookahead exists.
Practice questions (8)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
How many prime implicants does f(A,B,C,D) = Σm(0,1,2,3,5,7,8,10,14,15) have?
Numerical answer — type the value.
Show answer
Answer: 6
They are A′B′, A′D, B′D′, ABC, ACD′ and BCD — six. The count to be careful about is that this is not the number of terms in the minimal expression, which is three, nor the number of essential prime implicants, which is two. Each of the six is a group on the map that cannot be doubled; whether it is needed is a separate question that essentiality answers. Candidates who answer 3 have found the minimal cover and answered a question that was not asked, which is the single commonest way this mark is lost.For the same function f(A,B,C,D) = Σm(0,1,2,3,5,7,8,10,14,15), how many prime implicants are essential?
Numerical answer — type the value.
Show answer
Answer: 2
Two. A′D is the only prime implicant covering minterm 5, and B′D′ the only one covering minterm 8, so both must appear in every minimal expression. Every other minterm has at least two prime implicants available, so nothing else is forced — A′B′ is redundant because 0, 1, 2 and 3 are all covered by A′D or B′D′ anyway, and 14 and 15 can be taken by ABC or by the pair ACD′ and BCD. The method is mechanical and worth doing in this order: list the prime implicants, then for each minterm count how many cover it, and the ones covered exactly once name the essential implicants.The minimum number of 2-input NAND gates required to implement a 2-input XOR is:
Show answer
Answer: B — 4
Four. The standard construction takes N1 = (A·B)′, then N2 = (A·N1)′ and N3 = (B·N1)′, and finally N4 = (N2·N3)′, which evaluates to A ⊕ B. Three is the tempting answer because XOR "looks like" three operations written algebraically, and five is what you get from a naive translation of A′B + AB′ without sharing the first NAND — the sharing is the whole economy. XNOR needs five by this route, since it is XOR plus an inverting NAND, and that difference is itself examinable.An 8-to-1 multiplexer with no additional gates can implement any Boolean function of at most:
Show answer
Answer: B — 4 variables
Three select lines take three of the variables. Each data input then handles one combination of those three, and what remains is a function of the fourth variable alone — which can only be 0, 1, that variable, or its complement, and all four are available without a gate. So an 8-to-1 MUX covers four variables, and in general a 2^n-to-1 MUX covers n + 1. Option A is the answer for a MUX used as a pure selector, ignoring the residual-function trick, and it is the reason candidates reach for a 16-to-1 they do not need.Which of the following statements about don’t-care conditions in minimisation are correct? (More than one may be correct.)
Show answer
Answer: A — A don’t-care may be included in a group when doing so enlarges it; C — Including don’t-cares can change how many prime implicants a function has
A and C. A don’t-care is a permission — use it when it doubles a group, leave it when it does not (A) — and because it can enlarge a group, it can absorb a smaller group and so change the set of prime implicants entirely (C). B is false and is the commonest misreading: an uncovered don’t-care costs nothing, since the output there is by definition unspecified. D is false for a reason worth stating precisely: essentiality means being the sole cover of a 1, and a group covering only don’t-cares covers no 1 at all, so it is not merely inessential but unnecessary.By the consensus theorem, A·B + A′·C + B·C simplifies to:
Show answer
Answer: A — A·B + A′·C
The redundant term is the one whose literals are the consensus of the other two — B·C, made from the B of A·B and the C of A′·C, with the conflicting variable A dropped. It adds nothing: wherever B·C is 1, either A is 1 and A·B covers it, or A is 0 and A′·C covers it. So the answer is A·B + A′·C. Options B and C delete a term that is doing real work, and the map shows it immediately — this is exactly the redundancy a Karnaugh map reveals as a group entirely contained in the union of two others, which is why the algebraic and graphical methods agree.A 4-bit ripple-carry adder is built from full adders each having a propagation delay of 10 ns. Its worst-case delay is about:
Show answer
Answer: C — 40 ns
The carry out of stage 0 is an input to stage 1, and so on, so in the worst case a carry generated at the least significant bit must ripple through all four stages: 4 × 10 = 40 ns. This linear growth in the word length is the entire motivation for carry-lookahead, which computes the carries from the operands directly and turns the delay from O(n) into roughly O(log n) at the cost of considerably more gates. Option A is the answer for a single stage and is what a candidate gives when reading "propagation delay" as a property of the adder rather than of one stage.A 3-to-8 decoder generates all minterms of its three inputs. To implement an arbitrary Boolean function of those three variables, what must be added?
Show answer
Answer: A — A single OR gate over the minterms in the function
Any function in sum-of-products form is an OR of the minterms where it is 1, and the decoder has already produced every minterm on a separate line — so one OR gate over the right lines completes it. An AND would compute a product of minterms, which is 0 for any two distinct minterms and therefore useless. The economy worth noticing is that the same decoder serves several functions of the same three inputs at once, one OR gate each, which is why decoder-plus-OR is a standard way to build a small multi-output block. Option D is nearly right in spirit and wrong in fact: the decoder gives you the terms, not the sum.