Definition D1
Two propositions are equivalent, written ⟺, when they have the same value under every assignment of truth values.
Proof.
Equivalence is not the claim that two expressions mean the same thing, but the claim that their values always move together.convention
∎
Definition D2
x ∈ A ∩ B means (x ∈ A) ∧ (x ∈ B), x ∈ A ∪ B means (x ∈ A) ∨ (x ∈ B), and x ∈ Aᶜ means ¬(x ∈ A).
Proof.
The three set operations are conjunction, disjunction, and negation carried over to membership.convention
∎
Lemma L1
Every proposition p is true or false.
Proof.
(1)p ∨ ¬pA4
(2)The disjunction is true, so p is true or ¬p is true.(1), A2
(3)If ¬p is true, then p is false.A3
(4)Hence p is true or false.(2), (3)
∎
Lemma L2
In each of the four cases of assigning true or false to p and q, the values of ¬(p ∧ q) and ¬p ∨ ¬q are equal.
Proof.
(1)p true, q true: p ∧ q is true, so ¬(p ∧ q) is false. ¬p and ¬q are both false, so ¬p ∨ ¬q is false as well.A1, A2, A3
(2)p true, q false: p ∧ q is false, so ¬(p ∧ q) is true. ¬q is true, so ¬p ∨ ¬q is true as well.A1, A2, A3
(3)p false, q true: p ∧ q is false, so ¬(p ∧ q) is true. ¬p is true, so ¬p ∨ ¬q is true as well.A1, A2, A3
(4)p false, q false: p ∧ q is false, so ¬(p ∧ q) is true. ¬p and ¬q are both true, so ¬p ∨ ¬q is true as well.A1, A2, A3
(5)In all four cases the two expressions have equal values.(1), (2), (3), (4)
∎
Theorem T1
For all propositions p, q, ¬(p ∧ q) ⟺ ¬p ∨ ¬q
Proof.
(1)p is true or false, and so is q.L1
(2)Hence there are only four ways of assigning values to p and q.(1)
(3)In all four cases the two expressions have equal values.L2
(4)The values agree under every assignment, so the two expressions are equivalent.(2), (3), D1
∎
Theorem T2
For all propositions p, q, ¬(p ∨ q) ⟺ ¬p ∧ ¬q
Proof.
(1)T1 holds for all propositions, so putting ¬p in place of p and ¬q in place of q gives ¬(¬p ∧ ¬q) ⟺ ¬¬p ∨ ¬¬qT1
(2)¬¬p ⟺ p and ¬¬q ⟺ qA5
(3)¬(¬p ∧ ¬q) ⟺ p ∨ q(1), (2), E
(4)Negating both sides gives ¬¬(¬p ∧ ¬q) ⟺ ¬(p ∨ q)(3), E
(5)¬¬(¬p ∧ ¬q) ⟺ ¬p ∧ ¬qA5
(6)¬(p ∨ q) ⟺ ¬p ∧ ¬q(4), (5), E
∎
Corollary C
For subsets A, B of a universal set, (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
Proof.
(1)x ∈ (A ∩ B)ᶜ ⟺ ¬(x ∈ A ∩ B)D2
(2) ⟺ ¬((x ∈ A) ∧ (x ∈ B))(1), D2, E
(3) ⟺ ¬(x ∈ A) ∨ ¬(x ∈ B)(2), T1
(4) ⟺ (x ∈ Aᶜ) ∨ (x ∈ Bᶜ)(3), D2, E
(5) ⟺ x ∈ Aᶜ ∪ Bᶜ(4), D2
(6)The two sets have the same elements, so (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ(1), (5), A6
(7)In the same way, T2 gives (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ.T2, D2, A6
∎