Chapter 2: Logic and Boolean Algebra

Every if statement you write is a small piece of logic. Should the user see the discount? Is the password long enough and does it contain a digit? Has the payment failed or timed out? The maths of true and false is called Boolean algebra, after the English mathematician George Boole, who studied it in the 1800s, long before computers existed. Today it lives inside every processor and every program.

AND, OR, NOT and XOR

Boolean values have only two possibilities: True and False (or 1 and 0). There are four operations you must know by heart:

• AND: true only when both inputs are true. In Python: a and b.
• OR: true when at least one input is true. In Python: a or b.
• NOT: flips the value. In Python: not a.
• XOR (exclusive or): true when the inputs are different. For Booleans in Python: a != b or a ^ b.

A truth table lists every combination of inputs and the result. With two inputs there are only four rows, so you can let Python print the whole table for you:

from itertools import product

print("A     B     AND   OR    XOR")
for a, b in product([False, True], repeat=2):
    print(f"{a!s:5} {b!s:5} {a and b!s:5} {a or b!s:5} {a ^ b!s:5}")
# A     B     AND   OR    XOR
# False False False False False
# False True  False True  True
# True  False False True  True
# True  True  True  True  False

Notice that OR in programming is inclusive: true or true is true. In daily speech, "tea or coffee?" usually means one, not both. That everyday meaning is XOR. Keeping the two apart avoids many bugs.

De Morgan's laws and short-circuiting

Two rules discovered by Augustus De Morgan help you rewrite conditions cleanly:

not (A and B) is the same as (not A) or (not B)
not (A or B) is the same as (not A) and (not B)

— De Morgan's laws

In words: to negate a condition, flip each part and swap AND with OR. Suppose a ticket is free when the passenger is a child or a senior citizen. When is it not free? When the passenger is not a child and not a senior. This trick is very handy when you want to turn if not (...): into something easier to read, or when you write a while loop that must stop on the opposite condition.

for a, b in product([False, True], repeat=2):
    assert (not (a and b)) == ((not a) or (not b))
    assert (not (a or b)) == ((not a) and (not b))
print("De Morgan holds for every row")   # De Morgan holds for every row

Python evaluates and and or lazily, from left to right. This is called short-circuiting. In a and b, if a is false the answer is already false, so b is never checked. In a or b, if a is true, b is skipped. Programmers use this on purpose to guard against errors:

x = 0
if x != 0 and 10 / x > 2:      # 10 / x never runs, so no ZeroDivisionError
    print("big")
else:
    print("safe")                 # safe

name = "" or "Guest"             # 'or' returns the first truthy value
print(name)                       # Guest

Put the cheap or protective test first and the expensive or risky test second. That one habit makes code both faster and safer.

Bitwise operators and masks

The same logic can work on every bit of an integer at once. Python's bitwise operators are & (AND), | (OR), ^ (XOR), ~ (NOT), << (shift left) and >> (shift right). Take 12 (1100) and 10 (1010). Line them up and apply the rule column by column: AND gives 1000 = 8, OR gives 1110 = 14 and XOR gives 0110 = 6. Shifting left by one place doubles a number, and shifting right by one place halves it (dropping any remainder).

print(12 & 10, 12 | 10, 12 ^ 10)  # 8 14 6
print(~12)                          # -13  (two's complement: -(12+1))
print(1 << 3, 20 >> 2)              # 8 5
print(7 & 1, 8 & 1)                 # 1 0  -> lowest bit tells odd or even

A mask is a number chosen so that certain bits are switched on. Masks let one integer store many yes/no flags, which is common in file permissions, game settings and network protocols. Use OR to turn a flag on, AND to test it, AND with NOT to turn it off, and XOR to toggle it.

READ, WRITE, EXEC = 1, 2, 4      # 001, 010, 100

perms = READ | WRITE              # 3  -> 011
print(bool(perms & WRITE))        # True
print(bool(perms & EXEC))         # False

perms |= EXEC                     # switch EXEC on   -> 7
perms &= ~WRITE                   # switch WRITE off -> 5
print(perms, format(perms, "03b"))  # 5 101

perms ^= READ                     # toggle READ      -> 4
print(perms)                      # 4

A famous one-line trick: a positive integer n is a power of two exactly when n & (n - 1) == 0. A power of two has a single 1 bit, and subtracting one turns that bit off and all lower bits on, so nothing overlaps.

Practice problems

1. What is (True and not False) or False?
2. Work out 6 & 3, 6 | 3 and 6 ^ 3 by hand.
3. Rewrite not (is_admin or is_owner) using De Morgan's law.
4. In user and user.is_active, why is there no error when user is None?
5. Using the flags above, what value means READ and EXEC are on but WRITE is off?

Answers

1. True.
2. 6 is 110, 3 is 011: AND = 010 = 2, OR = 111 = 7, XOR = 101 = 5.
3. (not is_admin) and (not is_owner).
4. Short-circuiting: None is falsy, so Python never evaluates user.is_active.
5. 1 + 4 = 5 (binary 101).