Beweis durch Widerspruch

Einfache Sprache

Es soll gezeigt werden, dass aus einer Aussage $A$ eine Aussage $B$ folgt. Bei einem Beweis durch Widerspruch zeigen wir dies, in dem wir $A$ und die Negation von $B$ annehmen und zeigen das daraus einen Widerspruch folgt (Also das beides zusammen nie wahr sein kann).

Def. Beweis durch Widerspruch

$A\implies B$ g.d.w $\neg (A\land \neg B)$

Beweis

$\left[\mathrm{Z\kern-.4em\raise-0.6ex\hbox{Z}}\;A\implies B \iff \neg (A\land \neg B) \right]$

$$\begin{align}A\implies B &\iff \neg A \lor B &\Huge|\normalsize\text{Def. Implikation}\\&\iff \neg A \lor \neg\neg B &\Huge|\normalsize\text{Erweitern}\\&\iff \neg (A \land\neg B) &\Huge|\normalsize\text{De-morgansche Gesetze}\end{align}$$