Propositions and truth tables

Discrete mathematics is the mathematics of separate, countable things: true and false, whole numbers, sets, graphs. It is the mathematics computers run on, and the language that algorithms, databases and proofs about programs are written in. In this course, Python checks every idea.

Propositions

A proposition is a statement that is either true or false:

• "Dhaka is the capital of Bangladesh." (true)
• "7 is an even number." (false)

"Close the door!" and "What time is it?" are not propositions. Neither is "x > 3": it depends on x. (That is a predicate, two lessons on.)

We name propositions with letters, p, q, r, and build bigger ones with connectives:

"Or" in logic is inclusive: p ∨ q is true when both are. For "one or the other but not both", use ⊕.

Truth tables

A truth table lists every combination of values. n letters have 2ⁿ combinations: 4 rows for p and q, 8 for p, q and r.

from itertools import product

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

print("p      q      p→q    p↔q")
for p, q in product([True, False], repeat=2):
    print(f"{p!s:6} {q!s:6} {implies(p, q)!s:6} {p == q}")

product([True, False], repeat=2) gives the four pairs in the usual order: TT, TF, FT, FF.

Implication

p → q is the hardest to accept. Think of it as a promise: "If you pass the exam (p), I will buy you a phone (q)."

• You pass and get the phone: promise kept (T).
• You pass and get no phone: promise broken (F). This is the only false row.
• You fail: whatever happens, the promise was not broken (T and T).

So p → q is true whenever p is false. That is called vacuous truth: "if 2 + 2 = 5, then the moon is cheese" is true.

p is the hypothesis, q the conclusion. Other ways to say p → q: "p implies q", "q if p", "p only if q", "p is sufficient for q", "q is necessary for p".

When no brackets are written, ¬ binds first, then ∧, then ∨, then →, then ↔.

Type your own formulas: not (p or q), p xor q, (p -> q) and (q -> p).

Mark lesson complete