Proof Techniques in Propositional Logic
Propositional Equivalences
Propositional equivalences are tools for replacing a statement with another that has the same truth value. They are used to simplify and validate arguments.
| Name | Law |
|---|---|
| Idempotence | P ≡ P ∨ P ; P ≡ P ∧ P |
| Commutative | (P ∨ Q) ≡ (Q ∨ P) ; (P ∧ Q) ≡ (Q ∧ P) |
| Associative | (P ∨ (Q ∨ R)) ≡ ((P ∨ Q) ∨ R) ; similar for ∧ |
| De Morgan's | ¬(P ∨ Q) ≡ (¬P ∧ ¬Q) ; ¬(P ∧ Q) ≡ (¬P ∨ ¬Q) |
| Distributive | (P ∧ (Q ∨ R)) ≡ ((P ∧ Q) ∨ (P ∧ R)) ; similar for ∨ |
| Material Equivalence | (P ↔ Q) ≡ ((P → Q) ∧ (Q → P)) |
| Involution | P 𠪪P |
| Material Implication | (P → Q) ≡ (¬P ∨ Q) |
| Exportation | ((P ∧ Q) → R) ≡ (P → (Q → R)) |
| Identity (OR True) | (P ∨ TRUE) ≡ TRUE |
| Identity (OR False) | (P ∨ FALSE) ≡ P |
| Identity (AND True) | (P ∧ TRUE) ≡ P |
| Identity (AND False) | (P ∧ FALSE) ≡ FALSE |
| Contradiction | (P ∧ ¬P) ≡ FALSE |
What each law means in plain language:
- Idempotence: "A is smart" is equivalent to "A is smart or A is smart." Redundant but logically valid.
- Commutative: Order doesn't matter in ∧ and ∨: "A and B" is the same as "B and A."
- Associative: Grouping doesn't matter in ∧ and ∨: (A ∨ B) ∨ C = A ∨ (B ∨ C).
- De Morgan's: The negation of a conjunction is a disjunction of negations, and vice versa.
- Distributive: AND distributes over OR, and OR over AND.
- Material Implication: P → Q is equivalent to ¬P ∨ Q. Useful for converting conditionals.
- Involution: Double negation cancels: ¬¬P = P.
- Exportation: "If A and B, then C" can be rewritten as "If A, then if B then C."
Rules of Inference
Rules of inference allow us to derive new true statements from known premises.
| Rule | Form |
|---|---|
| Addition | P ∴ P ∨ Q |
| Simplification | P ∧ Q ∴ P (or ∴ Q) |
| Conjunction | P, Q ∴ P ∧ Q |
| Absorption | P → Q ∴ P → (P ∧ Q) |
| Modus Ponens | P → Q, P ∴ Q |
| Modus Tollens | P → Q, ¬Q ∴ ¬P |
| Disjunctive Syllogism | P ∨ Q, ¬P ∴ Q |
| Hypothetical Syllogism | P → Q, Q → R ∴ P → R |
| Constructive Dilemma | (P → Q) ∧ (R → S), P ∨ R ∴ Q ∨ S |
| Destructive Dilemma | (P → Q) ∧ (R → S), ¬Q ∨ ¬S ∴ ¬P ∨ ¬R |
| Decomposing a Conjunction | P ∧ Q, P ∴ Q |
Rule explanations:
- Modus Ponens: "If P then Q; P is true; therefore Q is true." The workhorse of logical deduction.
- Modus Tollens: "If P then Q; Q is false; therefore P must be false." Uses contrapositive reasoning.
- Hypothetical Syllogism (Chain): If A leads to B and B leads to C, then A leads to C.
- Disjunctive Syllogism: "Either A or B is true; A is false; therefore B must be true."
Worked Example: Proof of Validity
Given premises:
- a. ¬Q → R
- b. ¬R ∧ P
- c. ¬(Q ∧ ¬R) / ∴ R
| Step | Statement | Justification |
|---|---|---|
| 1 | ¬Q → R | Premise (a) |
| 2 | ¬R ∧ P | Premise (b) |
| 3 | ¬(Q ∧ ¬R) | Premise (c) |
| 4 | ¬R | Simplification (from 2) |
| 5 | ¬Q ∨ ¬¬R | De Morgan's (from 3) |
| 6 | ¬Q ∨ R | Double Negation (from 5) |
| 7 | ¬¬Q | Modus Tollens (from 1 and 4) |
| 8 | R | Disjunctive Syllogism (from 6 and 7) |
Arguments and Validity
An argument has two components: one or more premises (the given statements) and a conclusion.
An argument is valid when the conclusion is true whenever all premises are true. If it fails this test, it's a fallacy.
Method for checking validity using truth tables:
- Rewrite the argument as a conditional: [(P₁ ∧ P₂ ∧ ... ∧ Pₙ) → C]
- Build the truth table.
- If the final column is all T (a tautology), the argument is valid.
Example:
Premises: P → Q (If one loves biology, one loves science), P (loves biology) Conclusion: ∴ Q (loves science)
Conditional to test: [(P → Q) ∧ P] → Q
| P | Q | P→Q | (P→Q) ∧ P | [(P→Q) ∧ P] → Q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |
All T → tautology → argument is valid.
Exercises — Proof Techniques
ProReviewer — locked
Drills, code labs, and full solutions.