Two circuits, one job

You already know what the gates do. AND needs both inputs on. OR needs at least one. NOT flips it. XOR wants them different. ⚠️ THIS MODULE IS NOT ABOUT THAT, AND IF THAT IS ALL YOU REVISE YOU WILL BE READY FOR ABOUT HALF THIS TOPIC. Here is the half that gets missed. ⭐⭐ TWO CIRCUITS THAT LOOK NOTHING ALIKE CAN DO EXACTLY THE SAME JOB. Build one from four gates and another from two. Draw them side by side and they share nothing. Feed them every possible combination of inputs, and they produce identical outputs every single time. ⚠️ THEY ARE THE SAME FUNCTION WEARING DIFFERENT CIRCUITRY. And that is not a curiosity. It is the entire point of Boolean algebra. ⭐ THE RULES IN YOUR APPENDIX ARE NOT A LIST TO RECITE. THEY ARE THE LEGAL MOVES FOR TURNING ONE CIRCUIT INTO ANOTHER THAT DOES THE SAME THING. Somebody wrote them down because rearranging an expression on paper is enormously cheaper than building the wrong circuit and finding out. ⚠️ AND CHEAPER IS LITERAL HERE. Every gate is real hardware: silicon, power, heat, and a tiny delay while the signal passes through it. A chip contains billions of them. ⭐ SO A REARRANGEMENT THAT SAVES TWO GATES IN A CIRCUIT USED A BILLION TIMES IS NOT TIDINESS. IT IS A SMALLER, COOLER, FASTER, CHEAPER CHIP. Which brings in the two gates this topic names that the others often skip. ⭐⭐ NAND AND NOR ARE THE CHEAP ONES, AND EITHER OF THEM ALONE CAN BUILD ANYTHING. Every gate you know, and every circuit you could design, can be made out of NAND gates and nothing else. ⚠️ THAT IS WHY THEY ARE IN YOUR SPECIFICATION ALONGSIDE THE FAMILIAR FOUR RATHER THAN AS AN AFTERTHOUGHT. And one last thing, which is the most useful sentence in this module. ⭐⭐ YOU NEVER HAVE TO TRUST A BOOLEAN RULE. YOU CAN PROVE ANY OF THEM YOURSELF, IN FOUR ROWS, WITH A TRUTH TABLE. If two expressions give the same column, they are the same expression. If they do not, they are not. One question to carry through the rest of this module: could this be done with fewer gates, and how would I prove that it still works?

Six gates, and what each one costs you

The four you know and the two this specification adds. The third column is the part the other modules do not cover.

Tap what this module actually claims

Tap the TWO statements that follow from two different circuits being able to do the same job.

The rules of Boolean algebra are legal moves for turning one circuit into an equivalent one, rather than facts to recite
You can check any rule yourself with a truth table, so you never have to take one on trust
The circuit with the fewest gates is always the cheapest one to build
Two circuits that look completely different will produce different outputs for at least some inputs

Same column, different circuit

Two students design circuits for the same task. One uses five gates, the other three. Both truth tables come out identical for every combination of inputs. What follows?

They are the same function, so the three-gate version does the whole job and the other two gates are doing no work at all
They happen to agree on the cases tested, but might differ on an input nobody tried
The five-gate version must be more reliable, since it does more checking
They must have solved slightly different problems, since the circuits differ

Five terms for the second half

Five terms, each defined by what it is. How they are used, and which ones do the work, is what the steps that follow are for.

Match each gate to the only case that decides it

AND
OR
NOT
XOR
NAND
NOR

Outputs 1 in exactly one row of a two-input table: the row where both inputs are 1
Outputs 0 in exactly one row: the row where both inputs are 0
Takes a single input and returns the opposite of it
Outputs 1 in the two rows where the inputs disagree, and 0 where they match
Outputs 0 in exactly one row: the row where both inputs are 1
Outputs 1 in exactly one row: the row where both inputs are 0

Two that follow from simplification

Select the TWO statements that follow from Boolean algebra being a way of rewriting circuits.

Removing a gate from a circuit that will be manufactured many times saves real silicon, power and delay
A simplification can always be checked by building the truth table of the original and of the result
The circuit with fewer gates is always the cheaper one to build
Simplifying an expression requires remembering the rules, so an answer you cannot justify by rule is worthless

You can prove every rule yourself

Your specification points you at an appendix of Boolean algebra rules. ⚠️ GO AND LOOK AT WHICH ONES YOUR OWN APPENDIX ACTUALLY LISTS, BECAUSE BOARDS DIFFER AND A REVISION GUIDE WRITTEN FOR SOMEBODY ELSE MAY GIVE YOU MORE OR FEWER THAN YOU NEED. ⭐⭐ BUT HERE IS WHY THAT MATTERS LESS THAN IT SOUNDS: NO BOOLEAN RULE HAS TO BE TAKEN ON TRUST. EVERY ONE OF THEM CAN BE PROVED IN FOUR ROWS. The method never changes. WRITE OUT EVERY POSSIBLE COMBINATION OF INPUTS. Two inputs give four rows. Three inputs give eight. There is no fifth possibility with two inputs, which is what makes this a proof rather than a spot check. WORK OUT THE LEFT-HAND SIDE FOR EACH ROW, IN ITS OWN COLUMN. Then the right-hand side, in another. ⭐ COMPARE THE TWO COLUMNS. IF THEY MATCH IN EVERY ROW, THE TWO SIDES ARE THE SAME THING. IF ONE ROW DIFFERS, THEY ARE NOT, AND YOU HAVE FOUND EXACTLY WHERE THE MISTAKE IS. ⚠️ THAT IS A MORE USEFUL SKILL THAN MEMORISING RULE NAMES, because it works on a rule you have forgotten, on a rule you were taught wrongly, and on your own answer in an exam. A shape for a simplification question: WRITE THE EXPRESSION THE CIRCUIT REPRESENTS, working from the inputs forward. APPLY ONE MOVE AT A TIME, AND SAY WHICH MOVE YOU MADE. ⚠️ A page of working with no labels is hard to give method marks for. STOP WHEN NOTHING FURTHER CAN BE REMOVED, and say why you have stopped. ⭐ THEN CHECK THE TWO TRUTH TABLES AGAINST EACH OTHER. If they match, your answer is right whether or not you remembered what the rule was called. ⚠️ TWO HABITS THAT COST MARKS ON THIS TOPIC. ⚠️ THE FIRST IS SIMPLIFYING BY EYE. An expression that looks redundant sometimes is not, and the table is four rows long. ⚠️ AND THE SECOND IS ASSUMING FEWER GATES MEANS CHEAPER. It usually does, and it does not always, because the kind of gate matters as well as the number.

Complete the NAND column

A NAND gate outputs _____ in every row of a two-input table except one. It outputs _____ only in the row where the inputs are _____. Row by row, its output is always the _____ of what an AND gate would give for the same inputs.

1 0 both 1 both 0 opposite same different from each other sum

Cutting a circuit down to size

A circuit takes two inputs, A and B. It works out A AND B, and separately it works out A AND (NOT B), and then it feeds both of those into an OR. Four components in total, and it looks like it is doing something quite involved. Write down what it computes: (A AND B) OR (A AND NOT B). Now think about what that is actually saying. ⭐ THE OUTPUT IS 1 IF A IS ON AND B IS ON, OR IF A IS ON AND B IS OFF. But B is always either on or off, so the second half of the sentence covers everything the first half does not. ⚠️ WHICH MEANS THE WHOLE THING DEPENDS ONLY ON A. B DOES NOTHING AT ALL. The rearrangement on paper says the same: A is common to both halves, so pull it out and you get A AND (B OR NOT B). And B OR NOT B is 1 whatever B is. And anything ANDed with 1 is itself. So the answer is just A. ⭐⭐ FOUR COMPONENTS REDUCED TO A PIECE OF WIRE. Now do not trust a word of that, and check it, which takes four rows. When A is 0 and B is 0: the first half gives 0, the second gives 0, so the output is 0. A is 0. They agree. When A is 0 and B is 1: 0 and 0 again, output 0. A is 0. They agree. When A is 1 and B is 0: the first half gives 0, the second gives 1, so the output is 1. A is 1. They agree. When A is 1 and B is 1: the first half gives 1, output 1. A is 1. They agree. ⭐ FOUR ROWS, ALL MATCHING, AND THERE IS NO FIFTH ROW TO WORRY ABOUT. THAT IS A COMPLETE PROOF, AND YOU DID NOT NEED TO REMEMBER WHAT ANY OF THE MOVES WERE CALLED. ⚠️ AND NOTICE WHAT THIS WOULD HAVE COST IF NOBODY HAD CHECKED. Three components and their wiring, in every copy of the chip ever manufactured, doing nothing whatever except drawing power and slowing the signal down. ⭐ THAT IS THE REASON THIS TOPIC EXISTS, AND IT IS WHY THE RULES WERE WRITTEN DOWN IN THE FIRST PLACE.

Order how to simplify and check

Put these six steps into the order you would follow to reduce a circuit and prove your answer is right.

Write down the expression the circuit computes, working forward from the inputs
Apply one rule at a time, naming each move as you make it
Stop when nothing further can be removed, and say why
Build the truth table of the original expression
Build the truth table of your simplified expression
Compare the two output columns row by row to confirm they match

Build the sentence that proves it

This is how an equivalence claim has to be stated to earn the mark. Assemble it.

The logic and algebra run

Five questions on equivalence, simplification and the cheap gates. Three lives.

Complete the logic and algebra facts

A physical component producing one output from its inputs according to a fixed rule is a _____. A written form of a circuit, using operators rather than drawn symbols, is a _____. Two expressions giving the same output for every possible combination of inputs are _____. A gate from which every other gate can be built is a _____.

logic gate Boolean expression logically equivalent universal gate truth table logic circuit an input an output

Three answers to put right

Three students working on logic questions. In each case the mark is in the reasoning, not the verdict.

A student simplifies an expression by eye, gets the right answer, and shows no working at all. Why is that risky even when correct?
Asked whether two circuits do the same job, a student tests three combinations of two inputs, finds they agree, and concludes the circuits are equivalent. What is wrong?
A student argues that a redesign using six NAND gates must be worse than the original using four mixed gates, because it uses more gates. How would you respond?

Explain why a simpler circuit is worth finding

A colleague has designed a working circuit and says there is no point simplifying it, because it already does the job. Explain why they should simplify it anyway, and how they could be certain the simpler version still works.

Explain what it means for two circuits to be equivalent, in terms of inputs and outputs rather than appearance
Explain what a redundant gate actually costs when a circuit is manufactured in large numbers
Explain how the rules of Boolean algebra are used to get from one expression to a simpler one
Explain how a truth table proves the two versions behave identically, and why checking every row matters
Explain why a circuit with more gates can still be cheaper if those gates are of the right kind
Finish by explaining why a student who has forgotten a rule can still produce a correct, provable simplification

Logic Gates and Boolean Algebra

Get the method right under pressure

What you'll cover