Propositional Logic

Logic is the language of precise reasoning. It underlies every if statement you write, digital circuits, database queries and mathematical proof.

#Propositions

A proposition is a declarative statement that is either true (T) or false (F), but not both.

We name propositions with letters p, q, r …

#Connectives

#Implication: the tricky one

"If you score above 90, you get an O grade." The promise is broken only when you score above 90 and do not get an O. If you score below 90, the promise says nothing — so the implication is true (vacuously).

Ways to say p → q in English: "if p, then q", "p implies q", "q if p", "p only if q", "p is sufficient for q", "q is necessary for p", "q whenever p".

From p → q we form three related statements:

"If it rains, the ground is wet." Contrapositive: "If the ground is not wet, it did not rain" — same meaning. Converse: "If the ground is wet, it rained" — not the same (a sprinkler could have wet it).

#Build any truth table

Type a formula and press Enter. Use ! or ~ for NOT, & for AND, | for OR, ^ for XOR, -> for implies and <-> for if and only if.

#Truth tables in code

With n variables a truth table has 2ⁿ rows. Python can generate it:

from itertools import product

def implies(a, b):
    return (not a) or b

print(f"{'p':5} {'q':5} {'r':5} | (p→q)∧(q→r) → (p→r)")
for p, q, r in product([True, False], repeat=3):
    value = implies(implies(p, q) and implies(q, r), implies(p, r))
    print(f"{p!s:5} {q!s:5} {r!s:5} | {value}")

p     q     r     | (p→q)∧(q→r) → (p→r)
True  True  True  | True
True  True  False | True
True  False True  | True
True  False False | True
False True  True  | True
False True  False | True
False False True  | True
False False False | True

Every row is True: this formula (the hypothetical syllogism) is a tautology.

#Tautology, contradiction, contingency

#Precedence

¬ binds tightest, then ∧, then ∨, then →, then ↔. So ¬p ∨ q ∧ r means (¬p) ∨ (q ∧ r). Use brackets when in doubt.

#Translating English

Let p = "it is raining", q = "I carry an umbrella", r = "I get wet".