7 min read
On this page

Propositional Logic

What is a Proposition?

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

Examples of propositions:

  • "The earth is round." (true)
  • "2 + 3 = 6" (false)
  • "There are infinitely many prime numbers." (true)

Non-propositions:

  • "What time is it?" (question)
  • "Close the door." (command)
  • "x + 1 = 2" (depends on x — not a proposition until x is bound)

We typically use lowercase letters p, q, r, ... to denote propositional variables.

Logical Connectives

Logical Connectives Overview

Connectives combine propositions into compound propositions.

| Connective | Symbol | Name | Meaning | |---|---|---|---| | NOT | ¬p | Negation | "not p" | | AND | p ∧ q | Conjunction | "p and q" | | OR | p ∨ q | Disjunction | "p or q" (inclusive) | | XOR | p ⊕ q | Exclusive Or | "p or q, but not both" | | IMPLIES | p → q | Implication | "if p then q" | | IFF | p ↔ q | Biconditional | "p if and only if q" |

Negation (¬)

Flips the truth value.

| p | ¬p | |---|---| | T | F | | F | T |

Conjunction (∧)

True only when both operands are true.

| p | q | p ∧ q | |---|---|---| | T | T | T | | T | F | F | | F | T | F | | F | F | F |

Disjunction (∨)

True when at least one operand is true (inclusive or).

| p | q | p ∨ q | |---|---|---| | T | T | T | | T | F | T | | F | T | T | | F | F | F |

Exclusive Or (⊕)

True when exactly one operand is true.

| p | q | p ⊕ q | |---|---|---| | T | T | F | | T | F | T | | F | T | T | | F | F | F |

Equivalently: p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q)

Implication (→)

p → q is false only when p is true and q is false.

| p | q | p → q | |---|---|---| | T | T | T | | T | F | F | | F | T | T | | F | F | T |

Key terminology:

  • p is the hypothesis (antecedent)
  • q is the conclusion (consequent)

Related forms:

  • Converse: q → p
  • Inverse: ¬p → ¬q
  • Contrapositive: ¬q → ¬p (logically equivalent to p → q)

The implication p → q is logically equivalent to ¬p ∨ q.

Biconditional (↔)

True when both operands have the same truth value.

| p | q | p ↔ q | |---|---|---| | T | T | T | | T | F | F | | F | T | F | | F | F | T |

p ↔ q ≡ (p → q) ∧ (q → p)

Truth Tables

A truth table lists all possible combinations of truth values for the propositional variables and the resulting truth value of the compound proposition.

For n propositional variables, there are 2^n rows.

Example: Evaluate (p → q) ∧ (q → r)

| p | q | r | p → q | q → r | (p → q) ∧ (q → r) | |---|---|---|---|---|---| | T | T | T | T | T | T | | T | T | F | T | F | F | | T | F | T | F | T | F | | T | F | F | F | T | F | | F | T | T | T | T | T | | F | T | F | T | F | F | | F | F | T | T | T | T | | F | F | F | T | T | T |

Tautologies, Contradictions, and Contingencies

  • Tautology: A compound proposition that is always true regardless of the truth values of its components. Example: p ∨ ¬p
  • Contradiction: A compound proposition that is always false. Example: p ∧ ¬p
  • Contingency: A proposition that is neither a tautology nor a contradiction. Example: p → q

Logical Equivalences

Two propositions p and q are logically equivalent (written p ≡ q) if they have the same truth value in every possible interpretation.

Fundamental Equivalences

Identity Laws:

  • p ∧ T ≡ p
  • p ∨ F ≡ p

Domination Laws:

  • p ∨ T ≡ T
  • p ∧ F ≡ F

Idempotent Laws:

  • p ∨ p ≡ p
  • p ∧ p ≡ p

Double Negation:

  • ¬(¬p) ≡ p

Commutative Laws:

  • p ∨ q ≡ q ∨ p
  • p ∧ q ≡ q ∧ p

Associative Laws:

  • (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
  • (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

Distributive Laws:

  • p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
  • p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

Absorption Laws:

  • p ∨ (p ∧ q) ≡ p
  • p ∧ (p ∨ q) ≡ p

Negation Laws:

  • p ∨ ¬p ≡ T
  • p ∧ ¬p ≡ F

De Morgan's Laws

Two of the most important equivalences in logic:

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

In words:

  • The negation of a conjunction is the disjunction of the negations.
  • The negation of a disjunction is the conjunction of the negations.

Generalized De Morgan's Laws (for n propositions):

¬(p₁ ∧ p₂ ∧ ... ∧ pₙ) ≡ ¬p₁ ∨ ¬p₂ ∨ ... ∨ ¬pₙ
¬(p₁ ∨ p₂ ∨ ... ∨ pₙ) ≡ ¬p₁ ∧ ¬p₂ ∧ ... ∧ ¬pₙ

Example: Simplify ¬(p → q)

¬(p → q)
≡ ¬(¬p ∨ q)        (implication equivalence)
≡ ¬(¬p) ∧ ¬q       (De Morgan's)
≡ p ∧ ¬q            (double negation)

So the negation of "if p then q" is "p and not q".

Implication Equivalences

Several useful equivalences involving implication:

p → q ≡ ¬p ∨ q                     (material implication)
p → q ≡ ¬q → ¬p                    (contrapositive)
p ∨ q ≡ ¬p → q                     (disjunction as implication)
p ∧ q ≡ ¬(p → ¬q)                  (conjunction via implication)
p ↔ q ≡ (p → q) ∧ (q → p)         (biconditional)
p ↔ q ≡ ¬p ↔ ¬q                   (biconditional negation)

Operator Precedence

From highest to lowest:

  1. ¬ (negation)
  2. ∧ (conjunction)
  3. ∨ (disjunction)
  4. → (implication)
  5. ↔ (biconditional)

So p ∨ q ∧ r means p ∨ (q ∧ r), not (p ∨ q) ∧ r.

Functional Completeness

A set of connectives is functionally complete if every Boolean function can be expressed using only connectives from that set.

Functionally complete sets:

  • {¬, ∧}
  • {¬, ∨}
  • {¬, →}
  • {↓} (NOR alone — also called Peirce's arrow)
  • {↑} (NAND alone — also called Sheffer stroke)

NAND (↑): p ↑ q ≡ ¬(p ∧ q)

Expressing all connectives with NAND:

¬p      ≡ p ↑ p
p ∧ q   ≡ (p ↑ q) ↑ (p ↑ q)
p ∨ q   ≡ (p ↑ p) ↑ (q ↑ q)
p → q   ≡ p ↑ (q ↑ q)

Propositional Satisfiability

A compound proposition is satisfiable if there exists an assignment of truth values that makes it true.

  • Every tautology is satisfiable.
  • No contradiction is satisfiable.
  • A contingency is satisfiable.

The Boolean satisfiability problem (SAT) asks: given a propositional formula, is it satisfiable? This is the foundational NP-complete problem (Cook-Levin theorem — covered in topic 11).

Normal Forms

Conjunctive Normal Form (CNF)

A formula is in CNF if it is a conjunction of clauses, where each clause is a disjunction of literals.

(p ∨ ¬q ∨ r) ∧ (¬p ∨ q) ∧ (q ∨ r)

Disjunctive Normal Form (DNF)

A formula is in DNF if it is a disjunction of terms, where each term is a conjunction of literals.

(p ∧ q ∧ r) ∨ (¬p ∧ q) ∨ (p ∧ ¬r)

Every propositional formula can be converted to both CNF and DNF.

Conversion to DNF: Read off the rows of the truth table where the result is T. Each row gives a minterm (conjunction of all variables, negated if F in that row).

Conversion to CNF: Read off the rows where the result is F. Each row gives a maxterm (disjunction of all variables, negated if T in that row).

Real-World Applications

  • Digital circuit design: Logic gates implement propositional connectives directly. Circuit simplification uses logical equivalences.
  • Database queries: SQL WHERE clauses are propositional formulas over conditions.
  • Programming: Boolean expressions in if-statements, loop conditions, and assertions.
  • SAT solvers: Used in hardware verification, software testing, AI planning, and scheduling. Modern SAT solvers (DPLL, CDCL) can handle millions of variables.
  • Type checking: Compilers use propositional reasoning to verify type constraints.