Propositional Logic
Propositional logic (also called sentential logic or zeroth-order logic) is the branch of formal logic that studies the logical relationships between sentences treated as atomic units — propositions that are either true or false — and the compound sentences formed from them by logical connectives: negation (not), conjunction (and), disjunction (or), material implication (if...then), and biconditional (if and only if). It is the simplest non-trivial formal system in which the notions of validity, consistency, and logical consequence can be rigorously defined.
Propositional logic makes no claims about the internal structure of propositions — it does not analyze 'Socrates is mortal' into subject and predicate, as predicate logic does. It treats it as an unstructured atom, 'P', and concerns itself only with how truth values of complex propositions depend on the truth values of their atomic components. This simplification is the source of propositional logic's tractability and its limitations.
Syntax and Semantics
The syntax of propositional logic specifies which strings of symbols count as well-formed formulas. A propositional variable (P, Q, R, ...) is a formula. If A and B are formulas, then so are ¬A (not-A), A ∧ B (A and B), A ∨ B (A or B), A → B (if A then B), and A ↔ B (A if and only if B). This recursive definition generates the full language from a small base.
The semantics specifies the truth conditions of complex formulas in terms of truth assignments to atomic variables. A truth assignment maps each propositional variable to one of two values: truth (1) or falsehood (0). A truth table systematically enumerates all possible truth assignments and computes the truth value of a complex formula under each. Any formula that is true under every possible truth assignment is a tautology — a logical truth. Any formula true under some but not all assignments is contingent. Any formula true under no assignment is a contradiction.
Material implication — the connective 'if A then B', written A → B — is the connective that most reliably generates philosophical puzzlement. Its truth table defines it as false only when A is true and B is false; in all other cases (including when A is false), it is true. This means that any proposition with a false antecedent is automatically true as a conditional: 'if 2+2=5, then the Moon is made of cheese' is a true proposition of propositional logic. This paradox of material implication has driven extensive work on alternative logics — relevance logic, conditional logic — that attempt to capture a notion of 'if' that requires a genuine connection between antecedent and consequent.
Proof Systems
Three proof systems for propositional logic are in common use, each capturing the notion of valid inference differently:
- Truth tables: Mechanical verification of validity by enumeration of all truth assignments. Correct but exponentially slow: a formula with n variables requires checking 2^n rows.
- Natural deduction: A system of rules of inference (introduction and elimination rules for each connective) that mirrors ordinary mathematical reasoning. A proof is a tree of formulas, each step justified by a rule. Proof theory's most important results concern the structure of natural deduction proofs.
- Resolution refutation: The basis of automated theorem proving. Converts formulas to conjunctive normal form and repeatedly applies the resolution rule until either a contradiction is derived (proving the original formula valid) or no further progress is possible. Resolution is complete for propositional logic and extends to predicate logic.
Propositional logic is decidable: there exists an algorithm (truth tables) that, for any formula, terminates and correctly reports whether the formula is a tautology. This is in stark contrast to predicate logic (whose decision problem is undecidable) and to arithmetic (which is both undecidable and, by Gödel's incompleteness theorems, incomplete). The decidability of propositional logic is its principal theoretical virtue.
The Limits of the Propositional
The crucial limitation of propositional logic is that it cannot express quantification — claims of the form 'all', 'some', 'none'. 'All humans are mortal' and 'Socrates is human, therefore Socrates is mortal' — the canonical syllogism — cannot be formalized in propositional logic; they require predicate logic.
This limitation is mathematically precise: propositional logic has no expressive power over the internal structure of propositions. It can tell you that 'P and Q implies P', but it cannot tell you that 'if every A is B and every B is C, then every A is C.' The inference from universal quantifiers requires a richer language. Mathematical logic is, in one sense, the project of finding languages expressive enough to capture mathematical reasoning while remaining formally tractable — a project in which propositional logic is the simplest and most tractable case, and in which tractability decreases as expressive power increases.
Propositional logic is where formal logic begins and where naive rationalism ends: every extension that makes the system more expressive — predicate logic, modal logic, higher-order logic — adds power by adding complexity, and the complexity always outpaces our ability to decide, verify, or fully axiomatize. The lesson of propositional logic is that simplicity and completeness come together exactly once, at the bottom of the expressive hierarchy.