Propositional logic

Propositional logic is the simplest useful logic. It studies statements that are either true or false and the ways those statements combine. It is the logic of Python's Boolean expressions, of digital circuits and of the conditions in every if statement you have written. This lesson defines propositions and connectives, shows how to compute truth values with truth tables, and translates between English, logic and code.

Propositions

A proposition is a declarative statement that is either true or false, but not both. The number 7 is prime is a proposition, and it is true. Every even number greater than 2 is prime is a proposition, and it is false. Some sentences are not propositions: questions (Is it raining?), commands (Close the door) and statements whose truth depends on an unspecified variable (x is greater than 3). The last kind becomes a proposition once \(x\) is given a value, and lesson 4 handles such statements with predicates.

We name propositions with lowercase letters, called propositional variables: \(p\), \(q\), \(r\) and so on. A propositional variable stands for some statement whose truth value is either T (true) or F (false). In Python these values are True and False, and in digital hardware they are 1 and 0.

The logical connectives

Connectives build compound propositions from simpler ones. Five are standard. Each is defined completely by a truth table that gives the value of the compound for every combination of values of its parts.

In formulas we write negation as \(\neg p\), conjunction as \(p \wedge q\), disjunction as \(p \vee q\), the conditional as \(p \to q\) and the biconditional as \(p \longleftrightarrow q\). The exclusive or, \(p \oplus q\), is not usually counted among the basic five but appears constantly in computing: in parity checks, in encryption and in the XOR operator ^ on bits.

Truth tables

A truth table lists every possible assignment of truth values to the variables and the resulting value of the formula. With \(n\) variables there are \(2^n\) rows, because each variable independently takes one of two values. Two variables give 4 rows, three give 8, and ten give 1,024. The standard order counts in binary with T before F, so the first variable alternates slowest.

Python generates truth tables easily with itertools.product, which produces every combination of values. The program below prints the table for the main connectives; it is worth running yourself and modifying.

from itertools import product

def implies(p, q):
    return (not p) or q

def show(b):
    return "T" if b else "F"

print(" p  q | not p  p and q  p or q  p -> q  p <-> q  p xor q")
for p, q in product([True, False], repeat=2):
    row = [not p, p and q, p or q, implies(p, q), p == q, p != q]
    print(f" {show(p)}  {show(q)} |   " + "        ".join(show(x) for x in row))

 p  q | not p  p and q  p or q  p -> q  p <-> q  p xor q
 T  T |   F        T        T        T        T        F
 T  F |   F        F        T        F        F        T
 F  T |   T        F        T        T        F        T
 F  F |   T        F        F        T        T        F

The conditional deserves special attention

The conditional \(p \to q\) causes more confusion than any other connective. Here \(p\) is called the hypothesis (or antecedent) and \(q\) the conclusion (or consequent). The conditional is false in exactly one case: when the hypothesis is true and the conclusion is false. In particular, if the hypothesis is false the conditional is true no matter what the conclusion is. This is called vacuous truth.

A promise makes the rule natural. Suppose a teacher says: if you score over 90 on the final, you will get an A. When has the teacher broken the promise? Only if you score over 90 and do not get an A. If you score below 90, the promise says nothing about your grade, so whatever happens it has not been broken. The conditional records exactly whether the promise was kept.

English expresses \(p \to q\) in many ways, and some of them reverse the apparent order. All of the following mean \(p \to q\): if p then q; q if p; p implies q; p only if q; p is sufficient for q; q is necessary for p; q whenever p; q unless not p. The phrase only if is the most common trap. You can get into the building only if you have a badge means: if you get in, then you have a badge. It does not say that having a badge gets you in.

Converse, inverse and contrapositive

From a conditional \(p \to q\) we can form three related statements. The converse is \(q \to p\). The inverse is \(\neg p \to \neg q\). The contrapositive is \(\neg q \to \neg p\). The contrapositive always has the same truth value as the original; the converse and inverse do not, although they agree with each other. Confusing a conditional with its converse is one of the most common errors in reasoning, in mathematics and in everyday life.

from itertools import product
T = lambda b: "T" if b else "F"
imp = lambda a, b: (not a) or b
print(" p  q | p->q  converse  inverse  contrapositive")
for p, q in product([True, False], repeat=2):
    print(f" {T(p)}  {T(q)} |  {T(imp(p,q))}       {T(imp(q,p))}        {T(imp(not p, not q))}           {T(imp(not q, not p))}")

 p  q | p->q  converse  inverse  contrapositive
 T  T |  T       T        T           T
 T  F |  F       T        T           F
 F  T |  T       F        F           T
 F  F |  T       T        T           T

For example, the statement if a number is divisible by 4, then it is even is true. Its converse, if a number is even, then it is divisible by 4, is false: 6 is a counterexample. Its contrapositive, if a number is not even, then it is not divisible by 4, is true, and lesson 5 will use exactly this equivalence as a proof technique.

Precedence and parentheses

To avoid writing parentheses everywhere, logic uses precedence rules, just as arithmetic does. Negation binds most tightly, then conjunction, then disjunction, then the conditional, then the biconditional. So \(\neg p \wedge q \vee r\) means \(((\neg p) \wedge q) \vee r\). The conditional is usually taken to group to the right, so \(p \to q \to r\) means \(p \to (q \to r)\), but good style is to use parentheses whenever a reader might hesitate.

Python's precedence for not, and and or follows the same order. One difference to remember is that Python has no implication operator, so you must write (not p) or q. Comparison operators bind more tightly than not, so not x == y means not (x == y).

from itertools import product
T = lambda b: "T" if b else "F"
print(" p  q  r | p or q   not r   (p or q) -> not r")
for p, q, r in product([True, False], repeat=3):
    a, b = p or q, not r
    print(f" {T(p)}  {T(q)}  {T(r)} |   {T(a)}        {T(b)}            {T((not a) or b)}")

 p  q  r | p or q   not r   (p or q) -> not r
 T  T  T |   T        F            F
 T  T  F |   T        T            T
 T  F  T |   T        F            F
 T  F  F |   T        T            T
 F  T  T |   T        F            F
 F  T  F |   T        T            T
 F  F  T |   F        F            T
 F  F  F |   F        T            T

Translating English into logic

Translation is a skill that takes practice. Identify the atomic propositions, give each a letter, and then find the connectives. Words like but, although and however are logically just and; they add emphasis or contrast but not a different truth condition. Neither p nor q means \(\neg p \wedge \neg q\). Not both p and q means \(\neg (p \wedge q)\).

The last step of that example illustrates a common gap between requirements and their formalization. Most people who write if X then Y in a specification also mean that Y should not happen otherwise. Logic forces you to say which you mean, and many bugs live exactly in that gap.

Logic in bits

Computers apply connectives to many bits at once. Python's bitwise operators &, | , ^ and ~ apply and, or, xor and not to each pair of corresponding bits in two integers. Network masks, permission flags and graphics operations all rely on this. A file permission like 0o755 in Unix is three groups of three bits, and checking whether a permission is set is a bitwise and with a mask.

READ, WRITE, EXEC = 0b100, 0b010, 0b001
perm = READ | EXEC            # 0b101
print(f"perm = {perm:03b}")
print("can read?   ", bool(perm & READ))
print("can write?  ", bool(perm & WRITE))
perm ^= WRITE                 # toggle write
print(f"after toggling write: {perm:03b}")
print(f"5 xor 3 = {5 ^ 3} ({5:03b} xor {3:03b} = {5 ^ 3:03b})")

perm = 101
can read?    True
can write?   False
after toggling write: 111
5 xor 3 = 6 (101 xor 011 = 110)

Short-circuit evaluation is the other place where logic meets programming. Python evaluates p and q from left to right and stops as soon as the answer is known: if p is false, q is never evaluated. This is why a guard like i < len(xs) and xs[i] > 0 is safe. Logically, \(p \wedge q\) and \(q \wedge p\) are equivalent, but in a program with side effects or errors the order matters.