Propositional Logic · Proofs

Rules of Inference
& Equivalence

Proofs in propositional logic work by applying rules one step at a time. Inference rules let you derive new lines from existing ones. Equivalence rules let you replace a formula — or part of a formula — with a logically equivalent form.

Type 1
Inference Rules
Applied to whole lines. Given certain lines already in the proof, you may write a new line. The arrow goes one way only — you cannot run inference rules backwards.
premises ∴ conclusion
Type 2
Equivalence Rules
Applied to whole lines or parts of lines. Two forms are logically equivalent — either can replace the other in either direction. They are reversible.
P ≡ Q  ·  works both ways
I
Inference Rules
Modus Ponens
MP
P → Q
P
∴ Q
If you have a conditional and its antecedent, you may derive the consequent.
Modus Tollens
MT
P → Q
~Q
∴ ~P
If you have a conditional and the negation of its consequent, you may derive the negation of the antecedent.
Hypothetical Syllogism
HS
P → Q
Q → R
∴ P → R
Chain two conditionals together when the consequent of the first matches the antecedent of the second.
Disjunctive Syllogism
DS
P ∨ Q
~P
∴ Q
If you have a disjunction and the negation of one disjunct, the other disjunct follows.
Simplification
Simp
P ∧ Q
∴ P  (or ∴ Q)
From a conjunction you may derive either conjunct separately.
Conjunction
Conj
P
Q
∴ P ∧ Q
If you have two lines separately, you may conjoin them into a single line.
Addition
Add
P
∴ P ∨ Q
From any line you may derive a disjunction with any formula you choose. Q can be anything.
Constructive Dilemma
CD
(P → Q) ∧ (R → S)
P ∨ R
∴ Q ∨ S
Given two conditionals and a disjunction of their antecedents, derive a disjunction of their consequents.
E
Equivalence Rules
Double Negation
DN
P ≡ ~~P
A formula and its double negation are equivalent. You can add or remove two negation signs at any time.
De Morgan's Laws
DeM
~(P ∧ Q) ≡ (~P ∨ ~Q)
~(P ∨ Q) ≡ (~P ∧ ~Q)
Negation distributes over conjunction/disjunction — and flips the connective.
Contraposition
Contra
(P → Q) ≡ (~Q → ~P)
A conditional is equivalent to its contrapositive. Flip direction and negate both sides.
Material Implication
Impl
(P → Q) ≡ (~P ∨ Q)
A conditional can be rewritten as a disjunction. Useful for converting between forms in a proof.
Commutation
Com
(P ∧ Q) ≡ (Q ∧ P)
(P ∨ Q) ≡ (Q ∨ P)
Order doesn't matter for conjunction or disjunction.
Association
Assoc
P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R
P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R
Grouping doesn't matter for conjunction or disjunction — you can re-bracket freely.
ex
Worked Proofs
Each line in a proof must be either a premise (given) or follow from earlier lines by a named rule. Write the line numbers used and the rule name as your justification. The goal is always to derive the conclusion on the last line.
Proof 1 · using MP and HS
show R
# Formula Justification
1 P → Q Premise
2 Q → R Premise
3 P Premise
4 P → R 1, 2 HS
5 R 4, 3 MP
Proof 2 · using MT and DS
show R
# Formula Justification
1 P → Q Premise
2 ~Q Premise
3 ~P ∨ R Premise
4 ~P 1, 2 MT
5 R 3, 4 DS
Proof 3 · using DeM and DS
Q
# Formula Justification
1 ~(P ∧ ~Q) Premise
2 P Premise
3 ~P ∨ ~~Q 1 DeM
4 ~P ∨ Q 3 DN
5 Q 4, 2 DS
Proof 4 · using Simp, MP, Conj
Q ∧ S
# Formula Justification
1 P ∧ R Premise
2 P → Q Premise
3 R → S Premise
4 P 1 Simp
5 R 1 Simp
6 Q 2, 4 MP
7 S 3, 5 MP
8 Q ∧ S 6, 7 Conj