Unit 8 — Boolean Algebra

Lesson 1 — TRUE, FALSE, AND, OR and NOT

Division: Elementary and above. This whole lesson is pencil-and-paper work. It is everything the ACSL Elementary Boolean Algebra test asks, and it is the starting point for every other division.

Statements that are TRUE or FALSE

A statement is a sentence that is either TRUE or FALSE. "3 + 4 > 6" is TRUE, because 7 is bigger than 6. "7 - 2 > 6" is FALSE, because 5 is not bigger than 6.

Three small words join or change statements.

In everyday speech "or" sometimes means "one or the other but not both". In Boolean algebra, OR is TRUE when both sides are TRUE too.

Example 1. Is 2 + 3 > 4 AND 6 - 1 < 5 TRUE or FALSE? The left side, 5 > 4, is TRUE. The right side, 5 < 5, is FALSE (5 is not smaller than itself). AND needs both, so the statement is FALSE.

Example 2. Is NOT (2 * 4 = 8) OR 9 - 5 > 3 TRUE or FALSE? First the brackets: 2 × 4 = 8 is TRUE, so NOT (2 * 4 = 8) is FALSE. Next, 9 − 5 > 3 means 4 > 3, which is TRUE. FALSE OR TRUE is TRUE.

Do the arithmetic first, turn each comparison into TRUE or FALSE, and only then use NOT, AND and OR.

Variables, symbols and the order of operations

Boolean algebra is named after George Boole, who invented it in the 1840s. Its variables, written with capital letters such as A and B, can only hold two values:

• 1, meaning TRUE (a switch that is on);
• 0, meaning FALSE (a switch that is off).

The ACSL Elementary test, and this book, write the three operators with symbols:

The ~ sits right in front of the letter or bracket it flips: ~A flips A, and ~(A + B) flips the whole bracket.

The symbols * and + were chosen on purpose: AND behaves like multiplying 0s and 1s, and OR almost behaves like adding them.

The only surprise is the last row: 1 + 1 is 1, because TRUE OR TRUE is simply TRUE.

The order of operations, from first to last:

1. brackets;
2. ~ (NOT);
3. * (AND);
4. + (OR).

Operators on the same level are done from left to right. This matches ordinary arithmetic, where × comes before +.

Example 3. Find the value of A + B * ~A when A = 1 and B = 0. First ~A is 0. Then B * ~A is 0 * 0 = 0. Last, A + 0 is 1 + 0 = 1. The answer is 1. If you had wrongly done the + first, you would get (1 + 0) * 0 = 0, a different answer.

Truth tables

With two variables there are exactly four ways to set them: (0,0), (0,1), (1,0) and (1,1). Each of these is an ordered pair (A,B): the first number is the value of A and the second is the value of B.

A truth table lists all four and works out an expression for each one. Build it one column at a time, each column using one operator on earlier columns.

Example 4. A truth table for ~A * B + A.

This book always lists the rows in this order, counting up in binary: 00, 01, 10, 11. When a question asks for the result column, write the last column from top to bottom as one string of digits. For Example 4 it is 0111.

The ACSL Elementary handout lists the rows the other way round, starting at (1,1). Always read the question carefully: this book's answers use the counting-up order.

Ordered pairs that make an expression TRUE or FALSE

Once the truth table is built, questions about ordered pairs are easy.

• Which ordered pairs make ~A * B + A TRUE? Read the rows with a 1 in the result column: (0,1), (1,0), (1,1).
• Which make it FALSE? The rows with a 0: (0,0).
• How many make it TRUE? Count the 1s: 3.

This book lists pairs in counting-up order, with no spaces inside a pair, and a comma and a space between pairs: (0,1), (1,0), (1,1). On a real ACSL paper, any order is accepted. If no pair works, the answer is NONE.

The laws of Boolean algebra

Just as ordinary algebra has rules such as x + 0 = x, Boolean algebra has laws. Each law is true for every value of the letters, and you can check any of them with a truth table.

~~A means ~(~A): flipping twice gets you back where you started.

De Morgan's laws are the most useful of all. To take a ~ inside a bracket, flip every letter and swap + and *. Augustus De Morgan was a teacher of mathematics in London, and a friend of George Boole.

This truth table proves the first De Morgan law: the two last columns are the same in every row.

Watch out: ~(A + B) is not ~A + ~B. When the ~ goes inside, the + must turn into *.

Simplifying

To simplify an expression is to find a shorter expression that has exactly the same truth table. Use the laws one step at a time, and write down which law you used.

A useful plan:

1. Take every ~ inside its bracket with De Morgan, and remove double negations.
2. Multiply out brackets with the distributive law.
3. Tidy up: A * ~A is 0, A * A is A, anything + 1 is 1, and so on.
4. Look for two terms that differ in one letter only, like A * B + A * ~B, and combine them: take out the common part, A * (B + ~B), which is A * 1 = A.

Example 5. Simplify ~(~A + ~B) + A * ~B.

Example 6. Simplify ~(A * ~B) * ~B.

A handy trick. A + A * B is just A, because A + A * B = A * 1 + A * B = A * (1 + B) = A * 1 = A. In words: if A alone already makes the expression TRUE, then "A and something else" adds nothing new.

How this book writes a simplified answer. Every simplify question asks for the answer as a sum of products. That means a list of terms joined by +, where each term is letters (or letters with a ~) joined by *, such as A * ~B + ~A * B. Use the fewest terms you can, and then the fewest letters. Inside a term, write the letters in alphabetical order (~A * B, not B * ~A); put the terms in alphabetical order too, with a plain letter before its ~ form (A + ~B, and A * B + ~A * ~B). If the expression is always TRUE, the answer is 1; if it is always FALSE, the answer is 0.

Equivalent expressions and tautologies

Two expressions are equivalent when they give the same value for every ordered pair, that is, when their truth tables have the same result column. Simplifying is one way to show it; building both truth tables always works.

Example 7. Is ~(A + ~B) equivalent to ~A * B?

Same column, so yes (De Morgan's law says so too).

A tautology is an expression that is TRUE for every ordered pair: its result column is all 1s, and it simplifies to 1. A + ~A is a tautology.

Example 8. Is ~(~A * B) + B a tautology? De Morgan gives ~~A + ~B + B, which is A + ~B + B. ~B + B is 1, and A + 1 is 1. So yes: the door would open whatever the switches say.

Option questions. A question may list several expressions labelled (A), (B), (C), … and ask which of them are tautologies, or which are equivalent to a given expression. Write the labels of every correct option, in order, separated by a comma and a space, such as A, C; write NONE if no option is correct. (The labels are just names for the options; they have nothing to do with the variables A and B inside the expressions.)

Back to the clubhouse door

Write "switch A is on" as A and "switch B is on" as B. The card says: NOT (A is off OR B is on), OR (A AND B). In symbols:

~(~A + B) + A * B

Question 1. With A = 1 and B = 0: ~A is 0, 0 + 0 is 0, ~0 is 1, so the first part is 1, and the whole rule is 1 + 0 = 1. The door opens.

Question 2. A truth table:

The door opens for (1,0), (1,1).

Question 3. Simplify:

The whole card means just A: the door opens exactly when switch A is on. Switch B does nothing at all! Look at the truth table again: the rule column is the same as the A column.

Optional. This unit's folder also holds a small Python program, assets/l1.py, that prints the truth table of an expression. You do not need it for the Elementary test: everything in this lesson is done with pencil and paper. Students going on to Lesson 2 meet it there.

Elementary checklist. You can now:

• decide whether a statement with AND, OR, NOT and arithmetic is TRUE or FALSE;
• use ~, * and + in the right order;
• build a truth table and write its result column;
• list or count the ordered pairs that make an expression TRUE or FALSE;
• simplify with the laws, including De Morgan's laws, and write the answer as a sum of products;
• decide whether two expressions are equivalent, and whether an expression is a tautology.

That is the whole Elementary test. Exercises 1 to 6 are an Elementary mock test: try all six in 30 minutes, as in the real contest. Exercises 7 to 9 are extra Elementary practice. Junior, Intermediate and Senior students continue with Lessons 2 and 3.

Lesson 2 — Three variables, XOR, XNOR and real ACSL papers

Division: Junior and above.

Three variables

From Junior up, expressions can use three variables, A, B and C. There are now 2 × 2 × 2 = 8 ordered triples (A,B,C), again listed by counting up in binary:

The result column is 01011101, and the triples that make it TRUE are (0,0,1), (0,1,1), (1,0,0), (1,0,1), (1,1,1). Each variable adds a factor of 2: four variables give 16 rows.

Two more operators: XOR and XNOR

XOR is the "one or the other but not both" meaning of or. XNOR is the NOT of XOR. A hallway light with a switch at each end is an XOR: flipping either switch changes the light.

XOR and XNOR identities:

• A ⊙ B = ~(A ⊕ B) = A ⊕ ~B = ~A ⊕ B
• A ⊕ B = ~A ⊕ ~B and A ⊙ B = ~A ⊙ ~B
• A ⊕ 0 = A, A ⊕ 1 = ~A, A ⊕ A = 0, A ⊕ ~A = 1

Every one of them can be checked with a four-row truth table.

The full order of operations

1. brackets;
2. ~ (NOT);
3. * (AND);
4. ⊕ and ⊙ (XOR and XNOR), on the same level;
5. + (OR).

Operators on the same level go from left to right.

Example 1. Find A ⊕ B * C + ~A ⊙ C when (A,B,C) = (0,0,0). First ~A is 1. Then B * C is 0. Then the XOR and XNOR, left to right: A ⊕ 0 is 0 ⊕ 0 = 0, and ~A ⊙ C is 1 ⊙ 0 = 0 (these two sit on either side of the +, so they are separate pieces). Last, 0 + 0 is 0. If you had done the + too early, as in A ⊕ B * (C + ~A) ⊙ C, you would get 1.

Reading a real ACSL paper

ACSL's Junior, Intermediate and Senior papers write Boolean expressions differently from this book. Here is how to translate.

The two things to watch:

• Letters written side by side are ANDed. $A\overline{B}C$ means A * ~B * C.
• A long bar is a bracket. Everything under one bar is NOTed together, so put brackets round it when you translate. $\overline{A}\,\overline{B}$ (two short bars) is ~A * ~B, while $\overline{AB}$ (one long bar) is ~(A * B). By De Morgan these are different.

Example 2 (the first sample on ACSL's Boolean Algebra page). Simplify $\overline{\overline{A(A+B)} + B\overline{A}}$.

Translated: ~(~(A * (A + B)) + B * ~A).

Step 3 uses absorption in the form A * (A + B) = A.

The full list of laws

Lesson 1's laws all still hold, with three variables or more. Here are the rest.

The third absorption law is the surprising one. Check it: when A is 1 both sides are 1; when A is 0 both sides are B.

Example 3. Simplify (A + B) * (A + ~C) as a sum of products. The OR form of the distributive law gives A + B * ~C straight away. (Multiplying out also works: A * A + A * ~C + A * B + B * ~C, and absorption swallows the middle two terms into A.)

Example 4. Simplify ~A * B + A + ~B * C as a sum of products. First, ~A * B + A is A + ~A * B, which is A + B by absorption. Now the expression is A + B + ~B * C. By the same law, B + ~B * C is B + C. The answer is A + B + C.

Example 5. Simplify A ⊕ B + ~A * ~B. Replace the XOR: A * ~B + ~A * B + ~A * ~B. The last two terms differ only in B, so they combine to ~A: now it is A * ~B + ~A. By absorption (~A + A * ~B = ~A + ~B), the answer is ~A + ~B.

Writing the answer. As in Lesson 1: a sum of products with the fewest terms, then the fewest letters. Inside a term the letters go in alphabetical order. Terms are ordered by comparing them letter by letter: the term whose first letter comes earlier in the alphabet goes first; if they share a letter, the plain letter goes before its ~ form; if one term runs out first, it goes first. So A * B + ~A * C (not ~A * C + A * B), and A + ~B (not ~B + A). No ⊕ or ⊙ appears in a simplified answer.

Watch out: ACSL's wiki says "simplify" means using the fewest operators, so a real paper might accept ~(A + B) where this book writes ~A * ~B. This book always asks for a sum of products, so there is exactly one right answer to write.

Finding every solution

A question may ask for all ordered pairs or triples that make an expression TRUE (or FALSE). There are two ways.

• Simplify first, until you can read off the solutions.
• Build a truth table with one column per operator. It is slower, but it never misses a row.

Example 6 (the second sample on ACSL's page). Find all ordered pairs (A,B) that make $\overline{\overline{(A+B)} + \overline{A}B}$ TRUE.

Translated: ~(~(A + B) + ~A * B). De Morgan: ~~(A + B) * ~(~A * B), which is (A + B) * (A + ~B). The OR form of the distributive law gives A + B * ~B, which is A + 0 = A. So the expression is TRUE exactly when A is 1: (1,0), (1,1).

Reading solutions from a sum of products. Each term is TRUE on a group of rows. In A * ~B + C, the term A * ~B is TRUE whenever A = 1 and B = 0 (with C free: (1,0,0) and (1,0,1)), and C is TRUE whenever C = 1 (four triples). The solutions are all of these together, each listed once, in counting-up order: (0,0,1), (0,1,1), (1,0,0), (1,0,1), (1,1,1). That matches the truth table at the start of this lesson.

A self-checker for Lessons 1 and 2

If you can run a Python program, this one prints the truth table of an expression written as a sum of products, using ~, * and + with the letters A, B and C (no brackets). Use it to check a simplified answer: its table must match the table of the original expression. It is saved as assets/l1.py; you do not need to understand the code yet, and Lesson 3 explains every line.

def literal_value(literal, a, b, c):
    name = literal
    if literal[0] == "~":
        name = literal[1]
    if name == "A":
        value = a
    elif name == "B":
        value = b
    else:
        value = c
    if literal[0] == "~":
        value = 1 - value
    return value


def sop_value(tokens, a, b, c):
    answer = 0
    term = 1
    for token in tokens:
        if token == "+":
            if term == 1:
                answer = 1
            term = 1
        elif token != "*":
            if literal_value(token, a, b, c) == 0:
                term = 0
    if term == 1:
        answer = 1
    return answer


text = input()
tokens = text.split()
c_values = 1
if "C" in text:
    c_values = 2
for a in range(2):
    for b in range(2):
        for c in range(c_values):
            row = str(a) + " " + str(b)
            if c_values == 2:
                row = row + " " + str(c)
            print(row + " : " + str(sop_value(tokens, a, b, c)))

To run it, open a terminal in this unit's folder, type python assets/l1.py, then type an expression such as A * ~B + ~A * C and press Enter. It prints eight rows, from 0 0 0 : 0 to 1 1 1 : 0. Type spaces around every * and +, and no space after ~. With only A and B it prints four rows: python assets/l1.py < assets/l1/2.in checks ~A + B and prints the column 1101, one row per line.

Longer expressions and four variables

Division: Intermediate and above.

Intermediate and Senior questions use longer expressions, NOTs inside NOTs, and a fourth variable D. The method does not change: take the ~s in from the outside, one bar at a time.

Example 7. Simplify ~(~(A + ~B) * ~(~A * C)) as a sum of products.

Counting with four variables. Four variables give 16 quadruples (A,B,C,D). A product term that leaves out k of the variables is TRUE on 2 × 2 × … (k times) rows, since the missing variables are free. For A * B + C * D: A * B is TRUE on 4 rows, C * D on 4 rows, and both at once only on (1,1,1,1). So the count is 4 + 4 − 1 = 7. When in doubt, write out all 16 rows: it takes a few minutes, and it is always right.

Watch out: XOR and XNOR chains go left to right, like everything else on one level. A ⊕ B ⊙ C means (A ⊕ B) ⊙ C.

Lesson 3 — Boolean algebra in Python

Division: Junior and above.

0, 1, True and False

Python has its own Boolean values, True and False, and the words and, or and not. They work on the numbers 0 and 1 too: Python treats 0 as FALSE and 1 as TRUE. The function int turns True into 1 and False into 0.

a = 1
b = 0
print(int(a and b))
print(int(a or b))
print(int(not a))
print(int(True), int(False))

0
1
0
1 0

for a in range(2):
    for b in range(2):
        value = int((not a and b) or (a and not b))
        print(a, b, value)

0 0 0
0 1 1
1 0 1
1 1 0

parts = input().split()
a = int(parts[0])
b = int(parts[1])
door = (not (not a or b)) or (a and b)
print(int(door))

Run it from this unit's folder:

python assets/l2.py < assets/l2/3.in

The input 1 0 prints 1: the door opens. Try the other three files in assets/l2, and check that the door opens exactly when the first number is 1.

Listing every solution

A truth table in Python is a nest of loops, one per variable, each for going over range(2). The loops run through the rows in exactly the counting-up order this book uses.

To list the solutions, build the answer as text: for each row that is TRUE, add a comma and a space if something is already there, and then the triple in brackets. A count goes up by 1 at the same time.

answer = ""
found = 0
for a in range(2):
    for b in range(2):
        for c in range(2):
            value = int((a and not b) or c)
            if value == 1:
                if found > 0:
                    answer = answer + ", "
                answer = answer + "(" + str(a) + "," + str(b) + "," + str(c) + ")"
                found = found + 1
print(found)
print(answer)

5
(0,0,1), (0,1,1), (1,0,0), (1,0,1), (1,1,1)

want = int(input())
answer = ""
found = 0
for a in range(2):
    for b in range(2):
        for c in range(2):
            value = int(((a and b) != c) or (not a and not c))
            if value == want:
                if found > 0:
                    answer = answer + ", "
                answer = answer + "(" + str(a) + "," + str(b) + "," + str(c) + ")"
                found = found + 1
print(found)
if found == 0:
    print("NONE")
else:
    print(answer)

Run it from this unit's folder:

python assets/l3.py < assets/l3/2.in

The input 0 prints 2 and then (1,0,0), (1,1,1). With the input 1 (in assets/l3/1.in) it prints the other six triples.

Reading an expression from the input

The programs so far have their expression written into the code. The self-checker assets/l1.py from Lesson 2 instead reads an expression, such as A * ~B + ~A * C, as text. It only has to handle sums of products, so it needs two small functions.

• literal_value(literal, a, b, c) gives the value of one literal, a letter such as B or a NOT-letter such as ~B. If the first character is ~, the letter is the second character, and the value is flipped with 1 - value.
• sop_value(tokens, a, b, c) walks through the tokens of the expression, A, *, ~B, +, and so on. It keeps term, the value of the product term it is in the middle of, which starts at 1 and becomes 0 as soon as one literal in it is 0. At each +, and once more at the end, a finished term that is still 1 makes the whole answer 1.

def literal_value(literal, a, b, c):
    name = literal
    if literal[0] == "~":
        name = literal[1]
    if name == "A":
        value = a
    elif name == "B":
        value = b
    else:
        value = c
    if literal[0] == "~":
        value = 1 - value
    return value


def sop_value(tokens, a, b, c):
    answer = 0
    term = 1
    for token in tokens:
        if token == "+":
            if term == 1:
                answer = 1
            term = 1
        elif token != "*":
            if literal_value(token, a, b, c) == 0:
                term = 0
    if term == 1:
        answer = 1
    return answer


tokens = "A * ~B + ~A * C".split()
print(tokens)
print(sop_value(tokens, 1, 0, 0))
print(sop_value(tokens, 1, 1, 0))

['A', '*', '~B', '+', '~A', '*', 'C']
1
0