Formal · I
Propositional logic
logica propositionum · ‘the logic of whole sentences’
The smallest formal system that handles real arguments. Atomic propositions, five connectives, a truth-functional semantics, and a small set of rules that license every classically valid inference.
Vocabulary
Atoms, formulas, connectives
An atomic proposition (or propositional variable) is a symbol — conventionally P, Q, R, … — representing a sentence whose internal structure the system does not look inside. A well-formed formula is either an atom or a combination of formulas formed by one of the five connectives below.
| Symbol | Name | English | Behaviour |
|---|---|---|---|
| ¬ | Negation | not P | Unary. Inverts the truth value of P. |
| ∧ | Conjunction | P and Q | True iff both P and Q are true. |
| ∨ | Disjunction | P or Q (inclusive) | True iff at least one of P, Q is true. |
| → | Material conditional | if P then Q | False only when P is true and Q is false. Equivalent to ¬P ∨ Q. |
| ↔ | Biconditional | P if and only if Q | True iff P and Q share a truth value. |
Semantics
Truth tables
The meaning of each connective is given by a truth table: the truth value of a compound formula is determined by the truth values of its parts. This is what makes the semantics truth-functional — and decidable.
| 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 |
A formula true on every row of its truth table is a tautology; one false on every row is a contradiction; one true on some rows and false on others is a contingency. An argument is valid iff the conditional formed by premises → conclusion is a tautology.
Rules
Rules of inference
Each rule below is a pattern: given the premises in the form shown, the conclusion follows. They are the standard propositional inference rules — the set used in most natural- deduction systems and undergraduate texts.
Modus ponens
modus ponendo ponens
If a conditional holds and its antecedent holds, the consequent follows. The foundational rule of detachment.
P → QP∴QModus tollens
modus tollendo tollens
If a conditional holds and its consequent fails, the antecedent fails. The contrapositive of modus ponens.
P → Q¬Q∴¬PHypothetical syllogism
Chains conditionals. The transitivity of implication.
P → QQ → R∴P → RDisjunctive syllogism
If one of two alternatives is denied, the other is affirmed.
P ∨ Q¬P∴QConstructive dilemma
Two conditionals and the disjunction of their antecedents yield the disjunction of their consequents.
(P → Q) ∧ (R → S)P ∨ R∴Q ∨ SSimplification
A conjunction entails each of its conjuncts.
P ∧ Q∴PConjunction
Two propositions can be combined into their conjunction.
PQ∴P ∧ QAddition
Any proposition entails a disjunction including itself — useful when the form of a later premise demands a disjunctive shape.
P∴P ∨ QAbsorption
Inside the consequent of a conditional, the antecedent can be conjoined for free.
P → Q∴P → (P ∧ Q)
Equivalences
Logical equivalences
Equivalences are two-way rewrites: where one form appears the other can be substituted, in any sub-formula of any proof. Sometimes called replacement rules.
Double negation
Two negations cancel.
¬¬P ≡ PDe Morgan's laws
Negation distributes over conjunction and disjunction by swapping the connective.
¬(P ∧ Q) ≡ ¬P ∨ ¬Q¬(P ∨ Q) ≡ ¬P ∧ ¬QCommutativity
Order does not matter for ∧ and ∨.
P ∧ Q ≡ Q ∧ PP ∨ Q ≡ Q ∨ PAssociativity
Grouping does not matter for ∧ and ∨.
(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)(P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)Distribution
∧ and ∨ distribute over each other.
P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)Material implication
The conditional is rewritten as a disjunction — the canonical reduction.
P → Q ≡ ¬P ∨ QTransposition (contraposition)
A conditional and its contrapositive are equivalent.
P → Q ≡ ¬Q → ¬PMaterial equivalence
Biconditional decomposed as two conditionals.
P ↔ Q ≡ (P → Q) ∧ (Q → P)Exportation
A conditional with a conjoined antecedent can be uncurried into nested conditionals.
(P ∧ Q) → R ≡ P → (Q → R)Idempotence (tautology)
A proposition is equivalent to its conjunction or disjunction with itself.
P ≡ P ∧ PP ≡ P ∨ P
Worked proof
A small example
Given premises P → Q, Q → R, and P, derive R.
- 1.P → Qpremise
- 2.Q → Rpremise
- 3.Ppremise
- 4.Qmodus ponens, 1, 3
- 5.Rmodus ponens, 2, 4
The same conclusion is reachable in a single step by hypothetical syllogism (from lines 1 and 2 to P → R), followed by modus ponens. Either route is a proof.
Lineage
How it arrived
Propositional logic begins with the Stoics, especially Chrysippus (c. 280–207 BC), who treated whole propositions as the units of inference and gave a recognisable account of modus ponens, modus tollens, and the disjunctive syllogism. The Stoic line was eclipsed by Aristotelian syllogistic in late antiquity and effectively lost.
The modern revival is George Boole's The Mathematical Analysis of Logic (1847) and The Laws of Thought (1854), which gave the connectives an algebraic treatment. Frege, Russell, and the Principia tradition then re-built the field on the new foundations. Truth tables in their modern form were standardised by Wittgenstein in the Tractatus (1921) and by Emil Post (1921), working independently.