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 single time and you will be fine.

How to use it

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. The table is there to settle arguments, and not to be read first.

The last family is different from the rest. It holds two claims that are false, and the table marks the rows where they fail. Getting there is the point of the whole demonstration.

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.

derekmolloy.ie

IdentityNullIdempotentComplementDouble negationCommutativeAssociativeDistributiveFalse friends

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.

RuleA · 1 = AA + 0 = A

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

Right-hand sideA

• 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.

InputsA0

A	A · 1	A
0	0	0
1	1	1

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

A	1	out
0	0	0
0	1	0
1	0	0
1	1	1

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

Walkthrough

Five steps, a few minutes each.

Step 1: A constant input either does nothing or does everything

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 no amount of clicking A moves the output at all.

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.

Step 2: Some rules are about the wiring, not the gate

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 nothing at all, which is a duller result and 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 them to agree can never fire. 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 the gap between those two statements is worth knowing about early.

Step 3: The rules you already believe

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. They are worth a minute 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 actually 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

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, and it is proved in the only way that counts.

Step 5: Turn the table into a test

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 part company. One row is all it takes: a claim that fails anywhere is not a rule, no matter how well it behaves on the other three rows.

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.

Check your understanding

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?

derekmolloy.ie

Quiz

Select 0/4

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

derekmolloy.ie

Concept Match

Match each rule to what it says

derekmolloy.ie

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?

derekmolloy.ie

Quiz

Select 0/1

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

derekmolloy.ie

Wrap-up

Boolean algebra is not a second subject sitting alongside the gates. It is the same information written in a form you can manipulate, and every rule in this demonstration was visible in the schematic before it was written down.

Three things are worth carrying 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 it will keep paying out 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 genuinely different costs, and choosing between them is what simplification means. The next demonstrations take that seriously: De Morgan’s theorems for moving inversions around, and Karnaugh maps for finding the cheapest circuit rather than merely a correct one.