I was given this explanation in my notes to understand Proof by Contradiction:
Proof by Contradiction
We want to prove that $\ P(n) \to Q(n) $ is true. In a proof by contradiction, we assume by contradiction that $\ P(n) \to Q(n) $ is false, that is, that: $\ \neg (P(n) \to Q(n)) $ is true.
The only way this might happen, is if $\ P(n) $ is true and $\ Q(n)$ is false. Thus we start with $\ P(n)$ true and $\ Q(n)$ false. If from there we deduce a contradiction, that is a statement of the form $\ C \wedge \neg C $, which is always false, what we have proven is :
$\ \neg (P(n) \to Q(n)) \to C \wedge \neg C$ , is true.
This is equivalent to $\ P(n) \to Q(n) $. To see that, set $\ S(n) = "P(n) \to Q(n)"$, and look at the truth table:
What I don't understand is this line: "$\ \neg (P(n) \to Q(n)) \to C \wedge \neg C$ , is true."
How is it true if previously stated that
$\ \neg (P(n) \to Q(n))$ is True
$\ C \wedge \neg C$ is False (a contradiction)
But we know that... $\ P \to Q $ is always False?
How am I interpreting this explanation wrongly? I am really confused right now... any help/explanation is very much appreciated, thanks!!!
Original screenshot (in case I formatted the equations wrongly... I'm new to mathjax/latex thing):