Problem set 2 solution, including
LaTeX, available online
Questions?
Logical Equivalence and Boolean Algebra
Section 2.2
Examples / problems
Warm-up: Prove that “and” and “or” are associative
i.e.,
P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R
P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R
Despite concentrating on algebraic proofs for most of today, these are simple
equivalences with no obvious relation to others to draw on algebraically, so
prove them via truth tables
P
Q
R
Q∨R
P∨(Q∨R)
P∨Q
(P∨Q)∨R
T
T
T
T
T
T
T
T
T
F
T
T
T
T
T
F
T
T
T
T
T
T
F
F
F
T
T
T
F
T
T
T
T
T
T
F
T
F
T
T
T
T
F
F
T
T
T
F
T
F
F
F
F
F
F
F
Prove that P → (Q∨R) ≡ (P ∧ ¬Q) → R (Progress
check 2.7)