Propositional Logic

Logic gives precise meaning to statements and arguments. It underlies circuit design, program verification and database queries, and GATE asks about it every year.

Propositions and connectives

A proposition is a statement that is either true (T, 1) or false (F, 0): "7 is prime" is a proposition, "x > 3" is not (until x is known). Compound propositions are built with connectives:

The implication is the one people get wrong: p → q is true whenever p is false ("if pigs fly, then I am the Pope" is true). It is equivalent to ¬p ∨ q. Ways of saying p → q in English: "p only if q", "q if p", "q whenever p", "p is sufficient for q", "q is necessary for p".

Precedence: ¬ first, then ∧, then ∨, then →, then ↔.

Converse, inverse and contrapositive

For the implication p → q:

Tautologies, contradictions and equivalence

• A tautology is true in every row of its truth table (p ∨ ¬p); a contradiction is false in every row (p ∧ ¬p); otherwise the formula is contingent.
• A formula is satisfiable if at least one row makes it true (every formula that is not a contradiction).
• p and q are logically equivalent (p ≡ q) if p ↔ q is a tautology.

A truth table with n variables has 2ⁿ rows, so a program can check any small formula:

from itertools import product

implies = lambda a, b: (not a) or b

formulas = {
    "(p -> q) <-> (~q -> ~p)":           lambda p, q, r: implies(p, q) == implies(not q, not p),
    "((p -> q) & (q -> r)) -> (p -> r)": lambda p, q, r: implies(implies(p, q) and implies(q, r), implies(p, r)),
    "(p -> q) -> (q -> p)":              lambda p, q, r: implies(implies(p, q), implies(q, p)),
    "(p -> (q -> r)) <-> ((p & q) -> r)": lambda p, q, r: implies(p, implies(q, r)) == implies(p and q, r),
    "(p | q) -> (p & q)":                lambda p, q, r: implies(p or q, p and q),
}
for text, f in formulas.items():
    true_rows = sum(bool(f(*row)) for row in product([False, True], repeat=3))
    kind = "tautology" if true_rows == 8 else "contradiction" if true_rows == 0 else "contingent"
    print(f"{text:38} true in {true_rows}/8 rows: {kind}")

(p -> q) <-> (~q -> ~p)                true in 8/8 rows: tautology
((p -> q) & (q -> r)) -> (p -> r)      true in 8/8 rows: tautology
(p -> q) -> (q -> p)                   true in 6/8 rows: contingent
(p -> (q -> r)) <-> ((p & q) -> r)     true in 8/8 rows: tautology
(p | q) -> (p & q)                     true in 4/8 rows: contingent

Important equivalences

Note that implication is not associative: (p → q) → r and p → (q → r) differ (try p = q = r = F).

Normal forms

• CNF (conjunctive normal form): an AND of clauses, each an OR of literals: (p ∨ ¬q) ∧ (q ∨ r).
• DNF (disjunctive normal form): an OR of terms, each an AND of literals.

Every formula has equivalent CNF and DNF forms (read them off the truth table, as with minterms and maxterms in Boolean algebra). Deciding whether a CNF formula is satisfiable (SAT) is the classic NP-complete problem.

Arguments and rules of inference

An argument with premises P₁, …, Pₙ and conclusion C is valid if (P₁ ∧ … ∧ Pₙ) → C is a tautology: whenever all premises are true, the conclusion is true.

Two common fallacies: affirming the consequent (from p → q and q, conclude p) and denying the antecedent (from p → q and ¬p, conclude ¬q). Both are invalid.

Practice questions