Details of proof by contradiction I realize this is pretty basic but recently became unsure of how to justify proof by contradiction. Is it that case that I can show $A\Rightarrow B$ by assuming $A$ and NOT $B$, and showing this leads to a contradiction? How can this be justified?
Also, let's say I want to show $A$ and $B$ imply $C$. Is it sufficient to show $A, B$ and NOT $C$ leads to a contradiction? Seems this would not be the case, as a contrapositive would be NOT $C$ implies NOT $A$ OR NOT $B$.
Thanks!
 A: If you want to prove by contradiction that ($A$ AND $B$)$\implies C$, you assume that $A$ AND $B$ AND (NOT $C$) and show that this leads to a contradiction. Here's why:
$a\implies b$ means $b$ OR (NOT $a$). So [($A$ AND $B$)$\implies C$] means [$C$ OR (NOT ($A$ AND $B$))] ie [$C$ OR (NOT $A$) OR (NOT $B$)]. If you negate this, you get $A$ AND $B$ AND (NOT $C$). 
A: I write $\top$ for true and $\bot$ for false. The basic principle is that to prove $\varphi$, it suffices to:


*

*assume $\neg \varphi,$

*and then derive $\bot$ (i.e. a contradiction).


Intuitively, this works because (and only because) it is a theorem of Boolean algebra that for all $\varphi \in \{\top,\bot\}$, we have: $$\varphi = (\neg \varphi \rightarrow \bot).$$
This means that to prove $\alpha \rightarrow \beta$, it suffices to assume $\neg(\alpha \rightarrow \beta)$ and derive $\bot$. But some basic Boolean algebra tells us that:
$$\neg(\alpha \rightarrow \beta) = \neg(\neg\alpha \vee \beta) = \neg \neg \alpha \wedge \neg \beta = \alpha \wedge \neg \beta.$$
So assuming $\neg(\alpha \rightarrow \beta)$ is the same as assuming $\alpha$ and $\neg \beta$. Hence, to prove $\alpha \rightarrow \beta$, you should assume $\alpha$ and $\neg \beta$, and attempt to derive $\bot$.
A: A and NOT B leading to a contradiction, means:
A and NOT B simultaneous can not both be, means:
If A occurs, it will be impossible for NOT B to occur, means:
If A occurs, then B must occur, means:
A $\implies$ B.
===
"Also, let's say I want to show A and B imply C. Is it sufficient to show A,B and NOT C leads to a contradiction?"
Yes.  By the same reasons.
=====
"Seems this would not be the case, as a contrapositive would be NOT C implies NOT A OR NOT B."
This is consistent.  You can prove $(A \& B) \implies C$ in one of three ways:
1) directly:  Assume $A$ and $B$ and show directly that $C$ must follow.
2) contradiction Assume $A$ and $B$ and $NOT C$ and show this leads to a contradiction.  (Thus $NOT C$ can not exist with $A \& B$ so $A \& B \implies  C$)
3) contrapositive:  Assume $NOT C$ and show this leads to NOT $A$ OR NOT $B$. (Thus NOT $C$ can only exist with either NOT A or NOT B so NOT $C$ can not exist with both $A$ and $B$ so $A \& B \implies  C$.
The three methods are all compatible.  2 and 3 are very closely related and as NOT A OR NOT B is a contradiction to A AND B, 3 can be seen as a subset of 2. (That is; assuming A and B and NOT C and concluding NOT A OR NOT B is an adequate contradiction.  But 2 can be demonstrated by any contradiction.)  
A: If you want to prove $A \implies B$, you assume $A \not \implies B$ and show this leads to some contradiction, so it is impossible. Since the impossibility is only based on the assumption $A \not \implies B$, this assumption must be incorrect. Hence $A \implies B$.
