BSIT Survival Kit

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

ProPro activity

ProReviewer — locked

Drills, code labs, and full solutions.

Unlock →