Boolean Logic

True and false

Boolean logic is the algebra of two values: true and false. Instead of adding and multiplying numbers, you combine truth values with logical operators, and the result is again true or false. The English mathematician George Boole described this algebra in 1847 and 1854; almost a century later, Claude Shannon showed in 1937 that electrical switching circuits follow exactly the same rules. That insight is why every digital computer is built from Boolean logic.

Programming languages have a Boolean type for these two values — True and False in Python, true and false in C (via <stdbool.h>; keywords since C23), JavaScript and Java. In hardware and in many textbooks they are written as 1 and 0. Every if statement and every loop condition is a Boolean expression: a question with a yes-or-no answer, such as "is the basket empty?" or "is the password at least 12 characters long?"

NOT, AND and OR

Each operator is fully described by a truth table: a table with one row for every possible combination of input values and a column with the result. One input has two combinations, two inputs have four, and n inputs have 2ⁿ. Because the table is complete, it is also a proof: if two expressions give the same column for every row, they are equivalent.

NOT

NOT takes a single input and flips it. It is a unary operator; all the others on this page take two inputs.

AND and OR

AND is true only when both inputs are true: "the door opens when the card is valid AND the PIN is correct". OR is true when at least one input is true, including when both are: "a discount applies to students OR to people over 65". This is the inclusive or, which is not always what "or" means in everyday speech.

XOR

XOR, short for exclusive or, is true when exactly one of its two inputs is true — in other words, when the inputs are different. "Tea or coffee?" usually means XOR: one of the two, not both. For Boolean values, XOR is the same as "not equal", which is how most languages write it.

XOR has two properties that make it popular in computing. Applying XOR with the same value twice gives back the original (A ⊕ K ⊕ K = A), which is the basis of simple encryption and of RAID parity. And XOR of two bits is exactly the last digit of their sum, which is why it appears in every adder circuit (see the half adder below).

NAND and NOR

NAND ("not and") is AND followed by NOT: it is false only when both inputs are true. NOR ("not or") is OR followed by NOT: it is true only when both inputs are false. Both are universal: every other operator can be built from NAND alone, or from NOR alone. NOT A, for example, is A NAND A. Chip makers like this because a whole circuit can then be made from one kind of building block. The two main kinds of flash memory, NAND flash and NOR flash, are named after the gate arrangement their memory cells resemble.

Operator precedence

When an expression mixes operators without parentheses, a fixed order decides what is evaluated first, just as multiplication comes before addition in arithmetic. For logical operators, the order is the same in almost every language:

1. NOT — binds tightest
2. AND
3. OR — binds loosest

So A OR B AND C means A OR (B AND C), and NOT A AND B means (NOT A) AND B. A handy memory aid: AND behaves like multiplication and OR like addition — with 1 and 0, A AND B is A × B, and A OR B is A + B capped at 1.

is_member = True
has_coupon = False
order_over_50 = False

# AND before OR: is_member or (has_coupon and order_over_50)
print(is_member or has_coupon and order_over_50)

# Parentheses change the meaning
print((is_member or has_coupon) and order_over_50)

True
False

De Morgan's laws

De Morgan's laws, named after the logician Augustus De Morgan, tell you how to push a NOT into a parenthesized expression. The NOT moves onto each part, and AND and OR swap places:

NOT (A AND B)  =  (NOT A) OR  (NOT B)
NOT (A OR B)   =  (NOT A) AND (NOT B)

In words: "not both" is the same as "at least one is not", and "neither" is the same as "not the one and not the other". A truth table proves the first law — the last two columns are identical in every row:

Worked example: simplifying a condition

A cinema refuses a ticket to anyone who is under 16 or who has no valid ID. You want the opposite condition: when may the ticket be sold? A direct translation gives a NOT around the whole rule:

sell ← NOT (age < 16 OR NOT has_id)

Apply De Morgan's second law: the NOT moves inside, OR becomes AND.

sell ← (NOT (age < 16)) AND (NOT (NOT has_id))

Now simplify each part. NOT (age < 16) is age ≥ 16, and a double negation cancels out:

sell ← age ≥ 16 AND has_id

The result reads like the rule a cashier would actually use. Because the laws are exact, you can check the rewrite by trying every combination:

for age in (12, 16, 30):
    for has_id in (False, True):
        original = not (age < 16 or not has_id)
        simplified = age >= 16 and has_id
        print(age, has_id, original, simplified)

12 False False False
12 True False False
16 False False False
16 True True True
30 False False False
30 True True True

Short-circuit evaluation

In the truth table of AND, once the first input is false the result is false whatever the second input is. Likewise, once the first input of OR is true the result is true. Most programming languages use this: they evaluate the left operand first and skip the right one when it cannot change the result. This is called short-circuit evaluation, and C, Java, JavaScript, Python and many others do it for their logical AND and OR.

It matters for two reasons. It saves work when the right-hand side is expensive, and — more importantly — it lets the left-hand side act as a guard that keeps the right-hand side from running when it would fail:

orders = 0
revenue = 0.0

# The division is never evaluated, because orders > 0 is already False
if orders > 0 and revenue / orders > 25:
    print("Big average order")
else:
    print("No orders, or a small average")

No orders, or a small average

Swap the two operands and the program stops with a ZeroDivisionError. So the order of operands in a logical expression is not only a matter of style. Python's and and or also return one of their operands rather than always True or False; the details are in Operators and Expressions.

Logic gates

A logic gate is an electronic circuit that implements one Boolean operator: it takes one or more input signals, each a high or low voltage standing for 1 or 0, and produces an output signal according to the operator's truth table. Modern gates are built from a few transistors each, and a processor contains billions of them. Everything a CPU does — adding, comparing, choosing which instruction comes next — comes down to combinations of gates.

Two drawing standards exist. The IEC standard, common in Europe, draws every gate as a rectangle with a label inside, as listed in the table. The American ANSI/IEEE standard uses distinctive shapes: a D shape for AND, a curved shield for OR, a shield with an extra curved line for XOR, and a triangle for NOT. In both, a small circle on an output means "inverted", which is how NAND and NOR are drawn.

Worked example: a half adder

Adding two single bits has four cases: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10 in binary — a sum digit of 0 with a carry of 1. Write that as a truth table and two familiar columns appear:

The sum column is A XOR B and the carry column is A AND B. So two gates side by side add two bits. This circuit is called a half adder:

def half_adder(a, b):
    """Add two bits; return (carry, sum)."""
    return a & b, a ^ b


for a in (0, 1):
    for b in (0, 1):
        carry, total = half_adder(a, b)
        print(f"{a} + {b} = {carry}{total}")

0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10

A half adder cannot take a carry in from a previous column, so it only works for the rightmost bit. A full adder has three inputs (A, B and carry-in) and is built from two half adders plus an OR gate. Chain 64 full adders, each passing its carry to the next, and you can add two 64-bit numbers. Real processors use faster variants of this idea, but it is the heart of a CPU's arithmetic unit. Binary numbers themselves are explained in Number Systems and Data Representation.

Bitwise versus logical operators

Many languages have two families of operators that look alike. Logical operators (and, or, not in Python; &&, ||, ! in C and JavaScript) treat each operand as a single truth value and short-circuit. Bitwise operators (&, |, ^, ~) apply the operator to every pair of bits in two integers separately, and always evaluate both sides.

print(5 & 3)      # 101 AND 011, bit by bit = 001
print(5 | 3)      # 101 OR 011 = 111
print(5 ^ 3)      # 101 XOR 011 = 110
print(5 and 3)    # logical: 5 is truthy, so the result is the second operand
print(True & False)

1
7
6
3
False

On the Booleans True and False, the bitwise operators happen to give the same results as the logical ones (without short-circuiting). The trap is precedence: in Python, & binds tighter than comparisons, while and binds looser.

width = 5
height = 3

print(width > 0 and height > 0)
print(width > 0 & height > 0)      # read as: width > (0 & height) > 0
print((width > 0) & (height > 0))

True
False
True

Generating truth tables with code

Writing truth tables by hand gets tedious beyond three inputs, and it is easy to miss a row. A short program can list every combination for you. itertools.product([0, 1], repeat=n) yields all 2ⁿ combinations of n bits, in counting order.

from itertools import product


def truth_table(name, rule, inputs=2):
    """Print the truth table of rule, a function of 0/1 values."""
    letters = "ABC"[:inputs]
    print(" ".join(letters), "|", name)
    for values in product([0, 1], repeat=inputs):
        result = int(rule(*values))
        print(" ".join(str(v) for v in values), "|", result)
    print()


truth_table("A XOR B", lambda a, b: a != b)
truth_table("NOT (A AND B)", lambda a, b: not (a and b))
truth_table("majority", lambda a, b, c: a + b + c >= 2, inputs=3)

A B | A XOR B
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

A B | NOT (A AND B)
0 0 | 1
0 1 | 1
1 0 | 1
1 1 | 0

A B C | majority
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1

The "majority" function is true when at least two of three inputs are true — a rule used in fault-tolerant systems, where three computers vote and the majority wins. The same program can check an equivalence: generate the tables of two expressions and compare the result columns.