Boolean algebra: learning to calculate with true and false

Reading a truth table is not enough. To design a circuit, you need to calculate with these expressions: write them, transform them, simplify them and, above all, check that their meaning has not changed.

The stakes are concrete: in a circuit, a shorter expression needs fewer gates, so the component is smaller, cheaper and uses less power.

The article follows three steps. First we learn to calculate (parts 1 to 5: read, evaluate, prove, simplify). Then we learn to negate an expression (part 6: De Morgan's laws). Finally we build the component that carries out an expression, the logic gate, with its standard symbols (part 7). Parts 8 and 9 open further leads and set out the limits.

It is written for two audiences: beginners, who follow the main thread with worked numbers, and specialists, who will find deeper material in the “Going further” boxes. Every term is defined when it first appears and listed in the glossary.

01Quick reminder: variables, operations, truth tables

A Boolean variable is a quantity that can only be 0 (false) or 1 (true). It stands for a yes-or-no question: A = “the door is open”, B = “it is raining”.

Three basic operations, familiar from everyday language:

• NOT (negation, written ¬A): flips the value.
• AND (conjunction, written A·B): is 1 only if both are 1.
• OR (disjunction, written A+B): is 1 if at least one of the two is 1.

A truth table lists every combination of inputs and the matching output:

These operations can be built with switches: in series for AND, in parallel for OR (see the article on binary).

A fourth operation is widely used: exclusive OR (XOR, written A⊕B). It is 1 when the two inputs are different: one or the other, but not both. We will see that it can be built from the first three.

02Reading an expression: order of precedence

When you write an expression such as A + B·C, you need to know where to start. As in arithmetic, where multiplication comes before addition, the order is: NOT, then AND, then OR. So A + B·C means A + (B·C).

Worked check: with A = 1, B = 0, C = 0. First B·C = 0·0 = 0, then A + 0 = 1. Had we wrongly read (A + B)·C, we would have found (1 + 0)·0 = 0. The two readings give different results, hence the importance of precedence, and of brackets when in doubt.

Method for evaluating an expression: replace the variables with their values, work out the NOTs first, then brackets and ANDs, then ORs. With a little practice, you can do it in your head.

03Careful: this is not school algebra

• 1 + 1 = 1 (“true OR true” is still “true”). There is no 2 in Boolean algebra: only 0 and 1 exist.
• A·A = A and A + A = A: repeating a condition changes nothing. “It is raining AND it is raining” just means “it is raining”.
• A + B·C = (A + B)·(A + C): distribution works “both ways”, which is not true for ordinary numbers. Let us check with A = 1, B = 0, C = 0: left side 1 + 0·0 = 1; right side (1+0)·(1+0) = 1·1 = 1. With A = 0, B = 1, C = 1: left side 0 + 1 = 1; right side (0+1)·(0+1) = 1. And a case that gives 0, with A = 0, B = 1, C = 0: left side 0 + 1·0 = 0; right side (0+1)·(0+0) = 1·0 = 0.

Three cases do not prove a rule. The full table of 8 combinations does: the “A + B·C” and “(A + B)·(A + C)” columns are identical on every row.

04The rules of calculation, explained

These rules are called laws. They appear, sometimes under slightly different names, in every Boolean algebra course.

Two ways to prove a rule

1. With a truth table: test every case. Take absorption, A + A·B = A:

With n variables there are 2 to the power n rows: 4 rows for 2 variables, 8 for 3, 16 for 4. It is the safest method, but it gets long as n grows.

2. By calculation: apply the rules from the table, step by step:

A + A·B = A·1 + A·B (identity) = A·(1 + B) (distributivity) = A·1 (1 + B = 1, annulment) = A (identity).

Calculation is shorter, but you need to know which rule to apply. That is what the following examples are for.

05Three guided examples and a method

Example 1: simplifying an expression

We want to simplify A·B + A·¬B.

1. Factor out A (distributivity in reverse): A·(B + ¬B).
2. Now B + ¬B = 1 (complement: one of the two is necessarily 1).
3. So A·1 = A (identity).

The expression reduces to A: B had no influence. In practice: “the door is open and it is raining, or the door is open and it is not raining” just means “the door is open”.

Example 2: a house alarm

An alarm must ring if it is armed (E) AND a door is open (P) OR a window is broken (V). It can be written in two equivalent ways:

• Factored form: S = E·(P + V). It needs 2 gates (an OR, then an AND).
• Expanded form: S = E·P + E·V. It needs 3 gates (two ANDs, then an OR).

Worked check: E = 1, P = 0, V = 1. Factored form: 1·(0+1) = 1·1 = 1. Expanded form: 1·0 + 1·1 = 0 + 1 = 1. Same result, but the first costs one gate less. Multiplied across millions of circuits, the saving matters: it is exactly what Shannon was after with relays.

Example 3: from truth table to expression (majority vote)

A circuit must output 1 when at least two of its three inputs A, B, C are 1. Its truth table:

Step 1: write one term per row where the output is 1. Each term is an AND that is true only for that combination (variables equal to 0 are negated):

M = ¬A·B·C + A·¬B·C + A·B·¬C + A·B·C

Step 2: simplify. Use idempotence to write the last term A·B·C three times (the result does not change), then group in pairs:

• ¬A·B·C + A·B·C = B·C·(¬A + A) = B·C
• A·¬B·C + A·B·C = A·C·(¬B + B) = A·C
• A·B·¬C + A·B·C = A·B·(¬C + C) = A·B

Result: M = A·B + A·C + B·C. Three ANDs and two ORs instead of four three-variable terms. This “majority” function is no toy: it is the carry of a full adder (part 7).

Method: simplify in 5 steps

1. Look. Spot the terms (separated by +) and the factors they share.
2. Reorder. Use commutativity and associativity to place similar terms side by side.
3. Find a pair. Two terms that differ by only one variable (A·B + A·¬B): factor, apply the complement (B + ¬B = 1), then identity.
4. Look for a special case. Absorption (A + A·B), idempotence (A + A), null element (A·0, A + 1), double negation, and De Morgan's laws for any negation sitting over a bracket. These laws say how to negate a compound expression: negating an AND gives the OR of the negations, negating an OR gives the AND of the negations, i.e. ¬(A·B) = ¬A + ¬B and ¬(A + B) = ¬A·¬B. They are explained and checked in part 6.
5. Check. Test the result on at least two sets of values, or with a full truth table. An unchecked simplification is not a simplification.

Example. Simplify B·A + A·¬B. (2) Commutativity: B·A = A·B, so A·B + A·¬B. (3) Pair: A·(B + ¬B) = A·1 = A. (5) Check: A = 1, B = 0 → 0 + 1 = 1 = A; A = 0, B = 1 → 0 + 0 = 0 = A. Answer: A.

06De Morgan's laws: negating a compound statement

These two laws say how to negate an AND or an OR:

• ¬(A·B) = ¬A + ¬B
• ¬(A+B) = ¬A · ¬B

A mnemonic sums up the method: “break the line, change the sign”. You “break” the negation bar, put it on each variable, and swap AND and OR.

In plain English: negating “it is raining AND it is windy” gives “it is not raining OR it is not windy” (one of the two missing is enough). And negating “I'll have tea OR coffee” gives “I'll have no tea AND no coffee” (neither one).

Worked check for the first law: with A = 1 and B = 0, the left side is ¬(1·0) = ¬0 = 1; the right side ¬1 + ¬0 = 0 + 1 = 1. With A = 1 and B = 1: ¬(1·1) = 0 and ¬1 + ¬1 = 0 + 0 = 0.

Where is it used? In circuit design (to turn an AND into an OR and cut down the number of gate types), but also in search engines and programs: looking for documents that do not contain both “cats” AND “dogs” is the same as looking for those that lack “cats” OR lack “dogs”.

07From rules to logic gates

A logic gate is an electronic circuit that carries out a Boolean operation: it takes one or more bits as input and outputs one bit. Boolean algebra provides the rules; gates implement them in hardware.

The common gates

• NOT (inverter): one input, inverted output.
• NAND = “NOT-AND”: the inverse of AND. NOR = “NOT-OR”: the inverse of OR.
• XOR: is 1 if the two inputs are different. It is built from the three basic operations: A⊕B = A·¬B + ¬A·B. Check: A = 1, B = 0 → 1·1 + 0·0 = 1; A = 1, B = 1 → 1·0 + 0·1 = 0.

Gate symbols

On a circuit diagram, each gate has a symbol. Those below are the “distinctive-shape” symbols of the ANSI/IEEE 91-1984 standard. The international standard IEC 60617-12 also offers rectangular symbols, and both families are in use. Three reading rules: the shape gives the basic function (flat back for AND, curved back for OR, triangle for NOT); a small circle, the bubble, on an output means “inverted”; XOR is recognised by the extra curved line at the input of the OR symbol.

What are they for? Adding two bits

The “Sum” column is exactly the XOR table, and the “Carry” column is the AND table. Two gates are therefore enough to build a half adder. It is “half” because it cannot take in a carry from the previous column.

A full adder takes three bits: A, B and the incoming carry. Its sum is an XOR of all three, and its outgoing carry is 1 if at least two of the three inputs are 1: the “majority” function from example 3. By chaining full adders, numbers of several bits can be added. Claude Shannon already presented a base-two adder at the end of his 1937 thesis.

Worked example: 5 + 3 on 4 bits. 0101 + 0011: rightmost column 1+1 = 0, carry 1; second column 0+1+1 = 0, carry 1; third column 1+0+1 = 0, carry 1; fourth column 0+0+1 = 1. Result: 1000, i.e. 8. The calculation is correct.

Beyond addition

Combined, gates also make comparators (is A equal to B?), multiplexers (choosing one input among several, like a railway switch) and decoders (activating one line according to a code). A processor's arithmetic unit is an assembly of these building blocks.

08Going further

09Limits and misconceptions

• The “+” is not addition. This is the most common confusion: 1 + 1 = 1 in Boolean algebra.
• A truth table describes a single instant. It says nothing about time: a Boolean expression has no memory. The flip-flop, subject of the next article in the series, is what brings memory.
• Rule names are not universal. Some rules (such as A·B + A·¬B = A) have different names depending on the course, or no name at all. What matters is being able to check them, not recite them.
• Boole was not thinking of computers. He wanted to describe the laws of thought; it was Shannon, Nakashima and others who showed, in the 1930s, that the same algebra describes circuits.

10Conclusion

Boolean algebra is a surprisingly simple algebra: two values, three operations, about ten rules, and the ability to check everything with a truth table. It lets you simplify an expression without changing its meaning, and so build smaller circuits and write clearer conditions. The worked exercises (coming soon) will let you check, step by step, that the rules have sunk in.

But a Boolean expression remembers nothing: it computes a result from the inputs present now. For a circuit to remember, a different kind of component is needed. That is the subject of the next article in the series: the flip-flop, or how data becomes memory.

11Glossary

• Absorption: the rule A + A·B = A (and its dual A·(A + B) = A).
• Annulment (null element): A·0 = 0 and A + 1 = 1.
• Associativity: (A·B)·C = A·(B·C) and (A + B) + C = A + (B + C); brackets in a chain of ANDs or ORs do not matter.
• Boolean algebra: an algebra whose variables are only 0 or 1, with the operations AND, OR, NOT.
• Boolean variable: a quantity that can only be 0 or 1.
• Commutativity: A·B = B·A and A + B = B + A; order does not matter.
• Complement: the rules A·¬A = 0 and A + ¬A = 1.
• De Morgan's laws: rules for negating an AND or an OR: ¬(A·B) = ¬A + ¬B and ¬(A+B) = ¬A·¬B.
• Disjunctive normal form: an expression written as a sum (OR) of products (AND), one term per row equal to 1 in the truth table.
• Distributivity: A·(B + C) = A·B + A·C, and also A + B·C = (A + B)·(A + C).
• Double negation: ¬(¬A) = A.
• Duality: the principle that a rule remains true when AND and OR, and 0 and 1, are swapped.
• Full adder: a circuit that adds three bits (A, B and the incoming carry).
• Half adder: a circuit that adds two bits; sum = XOR, carry = AND.
• Idempotence: the rules A·A = A and A + A = A.
• Identity: A·1 = A and A + 0 = A.
• Karnaugh map: a grid that lays out a truth table so that simplifications can be spotted at a glance.
• Logic gate: a circuit that carries out a Boolean operation.
• Multiplexer: a circuit that selects one input among several, like a railway switch.
• NAND, NOR: “NOT-AND” and “NOT-OR” gates, the inverses of AND and OR.
• Truth table: a table of outputs for every possible input.
• XOR (exclusive OR): is 1 if the two inputs differ; A⊕B = A·¬B + ¬A·B.