The logic of sentential connectives -- and, or, not, if-then, if-and-only-if -- as a formal system. Covers syntax (well-formed formulas), semantics (truth tables), satisfiability, validity, logical equivalence, normal forms (CNF, DNF), natural-deduction rules, and common translation pitfalls. Use when formalizing arguments with propositional structure, checking validity mechanically, or teaching the foundations of formal reasoning.
Propositional logic (also called sentential logic or zeroth-order logic) is the formal study of how truth values combine under sentential connectives. It is the entry point to formal logic and the foundation of every downstream system: predicate logic extends it with quantifiers, modal logic extends it with possibility and necessity, and computer science uses it everywhere from circuit design to SAT solvers. This skill covers the syntax, semantics, proof theory, and translation discipline of propositional logic as taught in introductory logic courses.
Agent affinity: boole (algebraic treatment), frege (axiomatic framing), russell (translation from natural language)
Concept IDs: log-propositional-logic, log-truth-tables, log-if-then-relationships, log-argument-structure
The alphabet of propositional logic consists of:
A well-formed formula (WFF) is defined recursively:
Precedence (to reduce parentheses): ¬ binds tightest, then ∧, then ∨, then →, then ↔. So p ∨ q → r means (p ∨ q) → r, not p ∨ (q → r).
Every connective is defined by a truth table -- a function from truth values of inputs to truth value of output. T denotes true, F denotes false.
| p | q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Note on the conditional. "p → q" is false only when p is true and q is false. When p is false, p → q is true regardless of q. This "vacuous truth" is the single most common source of confusion for beginners. The textbook example: "If the moon is made of cheese, then 2 + 2 = 5" is true in propositional logic because the antecedent is false.
Three central concepts:
p ∧ q is satisfiable (T, T).p ∧ ¬p is unsatisfiable.p ∨ ¬p is valid.p → q is equivalent to ¬p ∨ q.The dual principle. A formula φ is valid if and only if ¬φ is unsatisfiable. This is the foundation of proof-by-contradiction and of SAT-solver-based validity checking.
These equivalences appear constantly and must be known cold:
| Name | Equivalence |
|---|---|
| Double negation | ¬¬p ≡ p |
| Idempotence | p ∧ p ≡ p; p ∨ p ≡ p |
| Commutativity | p ∧ q ≡ q ∧ p; p ∨ q ≡ q ∨ p |
| Associativity | (p ∧ q) ∧ r ≡ p ∧ (q ∧ r); same for ∨ |
| Distribution | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r); dual for ∨ over ∧ |
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Implication | p → q ≡ ¬p ∨ q |
| Contrapositive | p → q ≡ ¬q → ¬p |
| Biconditional | p ↔ q ≡ (p → q) ∧ (q → p) |
| Excluded middle | p ∨ ¬p is valid |
| Contradiction | p ∧ ¬p is unsatisfiable |
Every propositional formula can be rewritten into two canonical forms:
A conjunction of disjunctions of literals. Example: (p ∨ ¬q) ∧ (¬p ∨ q ∨ r) ∧ (¬r).
CNF is the input format for most SAT solvers. The Tseitin transformation converts any formula to equisatisfiable CNF in linear time.
A disjunction of conjunctions of literals. Example: (p ∧ q) ∨ (¬p ∧ r) ∨ (q ∧ ¬r).
DNF is useful for defining functions by case but can blow up exponentially. The Karnaugh map technique in digital logic is DNF minimization.
Natural deduction is the most common proof system for beginners because its rules match the way humans actually reason.
| Connective | Rule |
|---|---|
| ∧I | From φ and ψ, conclude φ ∧ ψ |
| ∨I | From φ, conclude φ ∨ ψ (for any ψ) |
| →I | Assume φ, derive ψ, conclude φ → ψ |
| ¬I | Assume φ, derive a contradiction, conclude ¬φ |
| ↔I | From φ → ψ and ψ → φ, conclude φ ↔ ψ |
| Connective | Rule |
|---|---|
| ∧E | From φ ∧ ψ, conclude φ; from φ ∧ ψ, conclude ψ |
| ∨E | From φ ∨ ψ, if assuming φ lets you conclude χ and assuming ψ lets you conclude χ, then χ |
| →E (modus ponens) | From φ → ψ and φ, conclude ψ |
| ¬E | From φ and ¬φ, conclude anything (ex falso) |
| ↔E | From φ ↔ ψ and φ, conclude ψ (and vice versa) |
Most practical use of propositional logic starts with translating English sentences into formulas. Pitfalls:
"If it rains, the street gets wet" formalizes as R → W. The conditional asserts truth-functional implication, not causal connection. "If 2 + 2 = 4, then grass is green" is true in propositional logic.
"The picnic is on unless it rains" formalizes as picnic ∨ rain. The natural reading "if it does not rain, the picnic is on" is logically equivalent: ¬rain → picnic ≡ rain ∨ picnic.
"Only if p, then q" formalizes as q → p. The "only if" direction is the implication from q to p. The most common error is conflating "only if" with "if," which gives the wrong direction.
"Neither p nor q" is ¬p ∧ ¬q (equivalently ¬(p ∨ q)).
"Either it's Tuesday or it's Wednesday" is typically T ∨ W (inclusive -- true if both, which is impossible for days but logically fine). Exclusive or is rare in natural language.
Propositional logic has no tense and no modality. "It might rain" cannot be distinguished from "it will rain" at this level. This is the motivation for modal logic.
Claim: The argument "If Socrates is a man, then Socrates is mortal. Socrates is a man. Therefore, Socrates is mortal" is valid.
Formalization: Let p = "Socrates is a man," q = "Socrates is mortal." The argument is:
Premise 1: p → q
Premise 2: p
Conclusion: q
Validity check by truth table:
| p | q | p → q | p | q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | T |
| F | F | T | F | F |
We need: every row where both premises are true, the conclusion is also true. Row 1 is the only row where p → q and p are both T; in that row, q is also T. Valid.
This is modus ponens, the single most-used rule in all of logic.
Propositional logic is decidable: there is an algorithm that, given any formula, determines in finite time whether it is valid, satisfiable, or unsatisfiable.
Exhaustive enumeration. Guaranteed to work. Exponential in the number of variables ($2^n$ rows for $n$ variables). Practical for up to 10-12 variables.
Modern SAT solvers use the Davis-Putnam-Logemann-Loveland algorithm with conflict-driven clause learning. They routinely solve formulas with millions of variables, though the worst case remains exponential. NP-complete in theory, practically efficient for most real instances.
Not a decision procedure by itself -- finding a proof requires search -- but valid formulas always have natural-deduction proofs (completeness) and found proofs are trustworthy (soundness).
predicate-logic.modal-logic.critical-argumentation.informal-fallacies.mathematical-proof-logic for the proof structure; propositional logic is a building block within it.When formalizing an argument, follow this sequence: