Some math basics for trying to understand https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_proofs.pdf and/or MIT’s OCW on math for computer science.
Sets
for set A and B
∪ = union, Everything in A AND everything in B (including overlap)
∩ = intersection, Everything in A AND B (just the overlap)
A \ B = {x | x ∈ A and x ∈ B} = Everything in A but not in B
A ∈ B = A is part of B (smaller side of ∈ towards the smaller set)
Q.E.D. = Proof done (normally a block symbol, but wordpres….)
P iff Q = P if and only if Q = P ↔ Q) = P implies Q and vice-versa
Set proof (both statements imply eachother)
With set A,B,C:
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
the intersection of A with (B andor C)
=
(The intersection between A and B) andor (the intersection between A and C)
This looks correct, but let’s prove it.
Proof.
We show that z ∈ A ∩ (B ∪ C) implies that
z ∈ (A ∩ B) ∪ (A ∩ C) and vice-versa.
First, we show that z ∈ A ∩ (B ∪ C) implies that
z ∈ (A ∩ B) ∪ (A ∩ C):
Assume that z ∈ A ∩ (B ∪ C).
Then z is in A and z is also in B or C. Thus, z is in
either A∩B or A∩C, which implies z ∈ (A∩B)∪(A∩C)
——-
Now, we show that z ∈ (A∩B)∪(A∩C) implies that
z ∈ A ∩ (B ∪ C).
Assume that z ∈ (A ∩ B) ∪ (A ∩ C).
Then z is in both A and B or else z is in both A and
C. Thus, z is in A and z is also in B or C. This implies
that z ∈ A ∩ (B ∪ C).
Q.E.D.
Proof by contradiction
Proof by contra-positive ((P → Q) ↔ (¬Q → ¬P) is a tautology. )
In order to prove a proposition P by contradiction:
- Write, “We use proof by contradiction.”
- Write, “Suppose P is false.”
- Deduce a logical contradiction.
- Write, “This is a contradiction. Therefore, P must
be true.”
Theorem: sqrt(2) is irrational
proving something irrational is hard, so instead assume it to be rational:
sqrt(2) = a/b (in the lowest terms a and b possible)
2 = (a^2)/(b^2)
a^2 = 2(b^2)
which means a^2 is even
thus a is even
thus a^2 is a multiple of 4
thus b^2 is a multiple of 4
thus b is also even
a and b are even which is a contradiction with the lowest term rule
thus a/b is not rational