Skip to content

Demo 4.3: The Rules of the Game

So far you have wired gates by intuition. You knew what a circuit had to do, you knew what each gate was for, and you put the two together. That works up to about three gates and then stops working.

Boolean algebra is the notation that takes over at that point. It gives you a way to write down what a circuit does, and a set of rules for rewriting what you have written without changing what it means. This demonstration covers the first of those rules, the ones that are true because of how the gates behave rather than because of anything clever.

Every rule here is of the form “these two circuits are the same circuit”. That is a claim you can test. The notation is the same as the last two demonstrations: a dot for AND, a plus for OR, and an overbar for NOT.

One warning before you start. The notation borrows its symbols from arithmetic and it does not borrow the rules that go with them. A + 1 = 1 is a true statement here. Read the plus as OR every time.

Pick a family of rules along the top, then pick which of the two forms you want. Both circuits are drawn for you, the inputs are clickable, and the truth table underneath is built from the same two circuits you are looking at.

It is helpful to predict before you click. Decide what the output should be, then set the inputs and see whether the circuit agrees with you. Use the table to check your prediction, not as the first thing you read.

The last family is different from the rest. It holds two claims that are false, and the table marks the rows where they fail. The rest of the demonstration builds up to it.

The Rules of Boolean Algebra

Each rule is two circuits and a claim that they are the same circuit. Click the inputs and decide for yourself.

Feed a gate the constant it does not care about and the gate stops doing anything at all. Which constant is harmless depends on the gate.

Rule

These two are duals of one another. Swap every AND for an OR, every OR for an AND, every 0 for a 1 and every 1 for a 0, and one becomes the other. Learn either one and you have both.

Left-hand sideA · 1
A10
Right-hand sideA
A0
  • Cyan carries a value you are holding, emerald a value a gate has produced, and amber a constant, which on a board would be a wire to ground or to the supply.
  • A dot marks a join; wires that cross without one are not connected.
Inputs
AA · 1A
000
111
Both columns agree on all 2 rows, so the two circuits are interchangeable.

An AND needs every input high before it will produce a 1. One of these is permanently high, so the only thing left in question is A, and the output copies it. Click A and watch the output follow.

Why it matters

This is what an enable line looks like when it is enabled. Hold one input of an AND at 1 and the gate becomes a piece of wire.

Click any row of the table to send that combination to the circuits.

The AND gate on its own
A1out
000
010
100
111

Struck rows cannot happen with this wiring. What survives is the rule.

Five steps, a few minutes each.

Step 1: A constant input either passes the other input or fixes the output

Section titled “Step 1: A constant input either passes the other input or fixes the output”

Select Identity and look at A · 1. One leg of the AND is held permanently high, so the only question left is A, and the output copies it. Click A and watch the output follow. Then select Null and look at A · 0. Now one leg is held permanently low, and clicking A does not move the output.

Those two rules are the same component in its two states. An AND gate with one leg used as a control line is either transparent or blocked, depending on which constant sits on that leg. This is where enable, inhibit, blank and mute pins come from, and you will meet the arrangement again the moment you look at a real chip.

Now switch each of them to their other form, A + 0 and A + 1, and notice that OR does the same job with the constants swapped over. Every rule in this demonstration except one comes in a pair like that, and the pair is always the same rule with AND and OR exchanged and 0 and 1 exchanged. That symmetry is called duality. Learning one member of each pair gives you the other for nothing.

Select Idempotent and look at the schematic rather than the algebra. There is only one signal, and a junction dot where it splits to feed both legs of the gate. The gate is unchanged. What has changed is that two of its four rows can no longer happen, because one wire cannot disagree with itself.

You saw this argument in the previous demonstration, where tying both legs of a NAND together produced an inverter. Here the same trick on an AND produces a copy of A, a less useful result from the same reasoning.

Now select Complement. The wiring puts A on one leg and NOT A on the other, so the two legs are guaranteed to disagree, and an AND that needs both legs at 1 can never output 1. Click A as much as you like. The output does not move.

Read the “Why it matters” note on that one before you move on. The rule is true of the logic and not quite true of the hardware, and you should know about the gap between those two statements early.

Select Commutative and compare the two schematics. They are the same gate with its input wires crossed, and the crossing changes nothing. Then select Associative, which moves to three signals and eight rows. The two circuits group the gates differently and produce the same column.

Neither of these will surprise you, because both are true of ordinary arithmetic as well. Spend a minute on them anyway, for two reasons. The first is that associativity is what lets you build a three-input function out of two-input parts, which is what you will be doing in the lab. The second is that these are the two rules students assume also apply to subtraction and division, and the habit of assuming is what causes trouble in the next step.

Step 4: The rule to check rather than trust

Section titled “Step 4: The rule to check rather than trust”

Select Distributive. The first form, A · (B + C) = A · B + A · C, has an arithmetic twin and will feel reasonable. Count the gates on each side: two on the left, three on the right, with identical behaviour. That is the first time in this demonstration that the two circuits are visibly different objects rather than the same object relabelled.

Now switch to the second form, A + B · C = (A + B) · (A + C). This one has no arithmetic twin. In ordinary algebra 2 + (3 x 4) is not (2 + 3) x (2 + 4), and if you are reading the plus as plus you will reject this rule on sight.

Do not take it on trust, and do not take my word for it either. Work down the table one row at a time. The four rows where A is 1 are the interesting ones: on every one of them both sides are forced high whatever B and C are doing. Then check the four rows where A is 0. When the table has agreed eight times out of eight, the rule is proved, because every possible case has been checked.

Select False friends. Both claims here are wrong, and the same table that has been confirming rules now marks the rows where a claim breaks.

Start with the first one. Set A and B so that they disagree and watch the two outputs differ. One row is enough: a claim that fails on any row is not a rule, however many other rows agree.

The second one is a distributive rule that was only half applied. It is a more realistic mistake than the first, because the result still looks like something you have seen before.

That is the skill to take away. When you are not sure whether a step is legal, you do not need to remember whether you were taught it. Build the table for both sides and look for a row where they differ. Three variables take eight rows and about a minute, and the answer it gives you is final.

Quiz
Select 0/1

A control signal EN is wired to one leg of an AND gate, and a data signal D to the other. What does the gate do when EN is 0, and what does it do when EN is 1?

Quiz
Select 0/4

Which of the following are true statements in Boolean algebra? Select all that apply.

Concept Match

Match each rule to what it says

Quiz
Select 0/1

You want to check whether (A + B) · C = A · (B + C) is a valid rule. What is the smallest amount of work that would settle it?

Quiz
Select 0/1

Why is it not true that NOT A · NOT B is the same as NOT (A · B)?

Boolean algebra holds the same information as the gates, written in a form you can manipulate, and every rule in this demonstration was visible in the schematic before it was written down.

Carry three things forward.

  1. The symbols are borrowed and the rules are not. The plus is an OR, so A + 1 = 1 and A + A = A. If a coefficient or a power ever appears in your working, you have drifted back into arithmetic.
  2. Rules come in dual pairs. Swap every AND for an OR, every OR for an AND, and every 0 for a 1, and a true statement stays true. That halves what you have to learn, and you will use it for the rest of the module.
  3. A truth table is a decision procedure. It confirms a rule and it refutes a claim, and for two or three variables it costs about a minute. Use it whenever you are unsure, and be aware that finding one bad row is enough.

The distributive rule is the one that points forward. It was the first case where two circuits with identical behaviour had different costs, and choosing between them is what simplification means. The next demonstrations build on that: De Morgan’s theorems for moving inversions around, and Karnaugh maps for finding the cheapest circuit rather than merely a correct one.