Mengen, Relationen, Logik und die fünf Beweistechniken, die jede Argumentation in der Klausur tragen — ohne sie liest man keinen Induktionsbeweis und keinen Widerspruch zur Pumping-Lemma-Anwendung sauber. Diese Seite enthält jetzt auch durchgerechnete Rechenaufgaben.
Klausur-Relevanz: sehr hoch — Lesen UND Rechnen
TL;DR. Diese Seite enthält jetzt auch durchgerechnete Rechenaufgaben — nicht nur Konzepte lesen, sondern selbst Beweise Schritt für Schritt hinschreiben.
1. Eine Menge ist durch ihre Elemente definiert; Reihenfolge und Wiederholung zählen nicht.
2. Eine Relation $R \subseteq A \times B$ ist eine Menge geordneter Paare; eine Funktion ist eine rechtseindeutige Relation.
3. Aussagenlogik verknüpft Wahrheitswerte mit $\land, \lor, \neg, \to, \leftrightarrow$. Prädikatenlogik quantifiziert Aussagen über Individuen mit $\forall$ und $\exists$.
4. Die fünf Standard-Beweistechniken lauten: direkt, Kontraposition, Widerspruch, vollständige Induktion, Fallunterscheidung. Ein Gegenbeispiel widerlegt eine Allaussage.
5. In der Klausur musst du einen fremden Beweis lesen und benennen können, welche Technik verwendet wurde und an welcher Stelle die entscheidende Umformung liegt.
Definitionen & Formalismen
Menge
Eine Menge $M$ ist eine ungeordnete Zusammenfassung wohlunterscheidbarer Objekte. Notation über Aufzählung oder Prädikat.
Formal: $M = \{ x \mid P(x) \}$, $x \in M$, Teilmenge $A \subseteq B \Leftrightarrow \forall x\, (x \in A \to x \in B)$.
Kartesisches Produkt & Relation
Das kartesische Produkt liefert alle geordneten Paare. Eine binäre Relation ist eine Teilmenge davon.
Formal: $A \times B = \{ (a,b) \mid a \in A \land b \in B \}$, Relation $R \subseteq A \times B$. Eigenschaften einer Relation auf $A$: reflexiv, symmetrisch, transitiv, antisymmetrisch.
Funktion
Eine Funktion ist eine spezielle Relation, die jedem Element des Definitionsbereichs genau ein Element des Wertebereichs zuordnet.
Formal: $f: A \to B$ mit $\forall a \in A\ \exists!\, b \in B : (a,b) \in f$. Klassen: injektiv, surjektiv, bijektiv.
Aussagenlogik
Verknüpfung von Aussagenvariablen mit Junktoren. Bedeutung wird durch Wahrheitstabellen festgelegt.
Junktoren: $\neg A$, $A \land B$, $A \lor B$, $A \to B$, $A \leftrightarrow B$. Äquivalenz: $A \to B \equiv \neg A \lor B \equiv \neg B \to \neg A$.
Prädikatenlogik erster Stufe
Erweitert Aussagenlogik um Prädikate, Variablen und Quantoren über einem Individuenbereich.
Notation: $\forall x\, P(x)$ — für alle $x$ gilt $P(x)$; $\exists x\, P(x)$ — es existiert ein $x$ mit $P(x)$. Negation vertauscht die Quantoren: $\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$.
Beweisziel $A \Rightarrow B$
Zu zeigen ist, dass unter der Voraussetzung $A$ stets $B$ folgt. Die fünf Vorgehensweisen unterscheiden sich darin, wie diese Implikation strukturell hergestellt wird.
Alternativen: direkt ($A \to B$), Kontraposition ($\neg B \to \neg A$), Widerspruch ($A \land \neg B \to \bot$), Induktion (Basis + Schritt), Fallunterscheidung ($A = A_1 \lor \dots \lor A_n$, jeder Fall zeigt $B$).
Kernkonzepte — die fünf Techniken systematisch
Direkter Beweis. Nimm $A$ an und schließe über eine Kette von Implikationen $A \to A_1 \to A_2 \to \dots \to B$. Jeder Schritt muss durch Definition, Axiom oder bereits bewiesenen Satz gerechtfertigt sein. Am häufigsten in Rechen- und Umformungsaufgaben.
Kontraposition. Statt $A \to B$ zeige $\neg B \to \neg A$. Logisch äquivalent, aber oft technisch einfacher, wenn die Negation von $B$ eine handhabbare Struktur hat. Beispiel: $n^2$ gerade $\Rightarrow$ $n$ gerade wird als $n$ ungerade $\Rightarrow$ $n^2$ ungerade geführt.
Widerspruchsbeweis (indirekt). Nimm zusätzlich zu $A$ die Negation $\neg B$ an und leite einen Widerspruch ($0 = 1$, $x < x$, etc.) her. Der klassische Fall: $\sqrt{2}$ ist irrational. In der Theo Inf zentral für Nicht-Regularitäts- und Nicht-Kontextfreiheits-Beweise via Pumping-Lemma.
Vollständige Induktion. Zeige eine Aussage $P(n)$ für alle $n \in \mathbb{N}$ in zwei Schritten: Induktionsanfang $P(n_0)$ und Induktionsschritt $P(n) \to P(n+1)$. Verwendung überall dort, wo die Struktur eine natürliche Zahl (Wortlänge, Ableitungslänge, Anzahl Zustände) enthält.
Fallunterscheidung. Zerlege die Voraussetzung in endlich viele disjunkte Fälle, die zusammen den ganzen Bereich abdecken, und beweise $B$ in jedem Fall separat. Häufig kombiniert mit den anderen Techniken.
Gegenbeispiel. Eine Allaussage $\forall x\, P(x)$ wird durch ein einziges $x$ mit $\neg P(x)$ widerlegt. Für den umgekehrten Beweis (Existenz einer Allaussage) reicht ein Beispiel dagegen niemals aus.
Beispiel durchgerechnet — $\sqrt{2}$ ist irrational
Das Standardbeispiel für den Widerspruchsbeweis. Wir zeigen: es gibt keine ganzen Zahlen $p, q$ mit $q \neq 0$ und $\sqrt{2} = p/q$, wobei $p$ und $q$ teilerfremd sind.
Struktur des Beweises
Vorannahme: √2 sei rational.
Also: ∃ p, q ∈ ℤ, q ≠ 0, ggT(p, q) = 1 mit √2 = p/q.
Schritt 1: Quadrieren: 2 = p² / q² ⇒ p² = 2·q².
Schritt 2: p² ist gerade ⇒ p ist gerade (Kontraposition!).
Also p = 2k für ein k ∈ ℤ.
Schritt 3: Einsetzen: (2k)² = 2·q² ⇒ 4k² = 2q² ⇒ q² = 2k².
Schritt 4: q² ist gerade ⇒ q ist gerade.
Widerspruch: p und q sind beide gerade, also ggT(p,q) ≥ 2.
Das widerspricht ggT(p, q) = 1.
Fazit: Die Annahme war falsch, √2 ist irrational. ∎
Was hier passiert. Die äußere Struktur ist Widerspruch. In Schritt 2 steckt zusätzlich Kontraposition (aus $n^2$ gerade folgt $n$ gerade — bewiesen wird das üblicherweise über die Kontraposition, weil ungerade $\cdot$ ungerade wieder ungerade ist). Ein guter Beweisleser erkennt beide Techniken ineinander verschachtelt.
Zweites Beispiel — Induktion: Summe $1 + 2 + \dots + n = n(n+1)/2$
Behauptung: P(n): 1 + 2 + … + n = n(n+1)/2 für alle n ≥ 1.
Induktionsanfang (n = 1):
Linke Seite = 1.
Rechte Seite = 1·(1+1)/2 = 1.
✓
Induktionsvoraussetzung:
Es gelte P(n) für ein festes n ≥ 1, also 1+…+n = n(n+1)/2.
Induktionsschritt (n → n+1):
1 + 2 + … + n + (n+1)
= n(n+1)/2 + (n+1) (nach IV)
= (n+1) · ( n/2 + 1 )
= (n+1) · (n+2)/2
= (n+1) · ((n+1)+1) / 2.
Das ist P(n+1). ✓
Fazit: P(n) gilt für alle n ≥ 1. ∎
Rechenaufgaben mit Lösung
Trainiere hier den Klausur-Modus: Aufgabe lesen, selbst probieren, dann Lösung aufklappen und Schritt für Schritt vergleichen. Jeder Beweis unten ist vollständig ausformuliert — inklusive Induktionsanfang, Voraussetzung, Schritt und expliziter Verwendung der Voraussetzung.
Aufgabe 1 — Gaußsche Summenformelleicht
Beweise mit vollständiger Induktion, dass für alle $n \in \mathbb{N}, n \geq 1$ gilt:
$$\sum_{k=1}^{n} k \;=\; \frac{n(n+1)}{2}.$$
Führe Induktionsanfang, Induktionsvoraussetzung und Induktionsschritt getrennt aus.
Lösung anzeigen
Schritt 1 — Behauptung fixieren: Sei $P(n)$ die Aussage $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$. Zu zeigen ist $P(n)$ für alle $n \geq 1$.
Schritt 2 — Induktionsanfang $n = 1$: Linke Seite: $\sum_{k=1}^{1} k = 1$. Rechte Seite: $\frac{1 \cdot (1+1)}{2} = \frac{2}{2} = 1$. Beide Seiten sind gleich, also gilt $P(1)$. $\checkmark$
Schritt 3 — Induktionsvoraussetzung (IV): Für ein festes, aber beliebiges $n \geq 1$ gelte $$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}.$$ Diese Annahme darf im Schritt verwendet werden — sie ist der einzige Ort, wo die IV eingeht.
Schritt 4 — Induktionsschritt $n \to n+1$: Zu zeigen ist $P(n+1)$, also $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$. Wir rechnen:
$$\sum_{k=1}^{n+1} k \;=\; \underbrace{\sum_{k=1}^{n} k}_{\text{IV}} + (n+1) \;\stackrel{\text{IV}}{=}\; \frac{n(n+1)}{2} + (n+1).$$
Schritt 6 — Zielform erreicht: Beachte $(n+2) = (n+1)+1$. Damit ist $\sum_{k=1}^{n+1} k = \frac{(n+1)\bigl((n+1)+1\bigr)}{2}$, was genau $P(n+1)$ ist. $\checkmark$
Ergebnis: Nach dem Prinzip der vollständigen Induktion gilt $P(n)$ für alle $n \in \mathbb{N}, n \geq 1$. $\blacksquare$
Beweise mit vollständiger Induktion, dass für alle $n \in \mathbb{N}, n \geq 1$ gilt:
$$2^n \;>\; n.$$
Achte darauf, im Schritt tatsächlich die Induktionsvoraussetzung zu nutzen und nicht etwa die Behauptung.
Lösung anzeigen
Schritt 1 — Behauptung fixieren: $P(n): 2^n > n$ für alle $n \geq 1$.
Schritt 2 — Induktionsanfang $n = 1$: $2^1 = 2 > 1$. Also gilt $P(1)$. $\checkmark$
Schritt 3 — Induktionsvoraussetzung: Für ein festes $n \geq 1$ gelte $2^n > n$.
Schritt 4 — Induktionsschritt $n \to n+1$: Zu zeigen ist $2^{n+1} > n+1$. Es gilt:
$$2^{n+1} \;=\; 2 \cdot 2^n \;\stackrel{\text{IV}}{>}\; 2 \cdot n \;=\; n + n.$$
Schritt 5 — Abschätzung $n + n \geq n + 1$: Da $n \geq 1$, gilt $n \geq 1$ und damit $n + n \geq n + 1$. Zusammen mit Schritt 4:
$$2^{n+1} \;>\; n + n \;\geq\; n + 1.$$
Streng genommen ist $2 \cdot 2^n > 2n$ eine strikte Ungleichung, und $2n \geq n+1$ für $n \geq 1$, also folgt $2^{n+1} > n+1$. $\checkmark$
Ergebnis: Nach dem Prinzip der vollständigen Induktion gilt $2^n > n$ für alle $n \in \mathbb{N}, n \geq 1$. $\blacksquare$
Anmerkung zur Falle: Der häufigste Fehler ist zu schreiben $2^{n+1} = 2 \cdot 2^n > 2 \cdot (n+1)$ — das würde die Behauptung $P(n+1)$ selbst nutzen und wäre ein Zirkelschluss. Wir dürfen nur $2^n > n$ (die IV) verwenden.
Aufgabe 3 — Direkter Beweis: gerade Zahlenleicht
Beweise direkt: für alle $n \in \mathbb{Z}$ gilt
$$n \text{ gerade} \;\Longrightarrow\; n^2 \text{ gerade}.$$
Lösung anzeigen
Schritt 1 — Voraussetzung ausbuchstabieren: Sei $n \in \mathbb{Z}$ gerade. Nach Definition heißt das: es existiert ein $k \in \mathbb{Z}$ mit $n = 2k$.
Schritt 3 — Struktur wiedererkennen: Setze $m := 2k^2$. Da $k \in \mathbb{Z}$, ist auch $m = 2k^2 \in \mathbb{Z}$. Damit gilt $n^2 = 2m$ mit $m \in \mathbb{Z}$, also ist $n^2$ nach Definition gerade.
Ergebnis: Aus $n$ gerade folgt $n^2$ gerade. $\blacksquare$
Anmerkung: Das ist ein Musterbeispiel für einen direkten Beweis — Voraussetzung einsetzen, umformen, Zielform erreichen. Kein Widerspruch, keine Kontraposition nötig.
Aufgabe 4 — Widerspruchsbeweis: $\sqrt{2}$ ist irrationalmittel
Zeige mit einem Widerspruchsbeweis, dass $\sqrt{2}$ irrational ist, dass es also keine ganzen Zahlen $p, q$ mit $q \neq 0$ und $\sqrt{2} = \frac{p}{q}$ gibt.
Lösung anzeigen
Schritt 1 — Annahme $\neg B$: Angenommen, $\sqrt{2}$ sei rational. Dann existieren $p, q \in \mathbb{Z}$ mit $q \neq 0$ und $\sqrt{2} = \frac{p}{q}$. Wir dürfen $\frac{p}{q}$ als vollständig gekürzt annehmen, also $\gcd(p, q) = 1$.
Schritt 2 — Quadrieren: Aus $\sqrt{2} = \frac{p}{q}$ folgt durch Quadrieren
$$2 \;=\; \frac{p^2}{q^2} \quad\Longleftrightarrow\quad p^2 \;=\; 2 q^2.$$
Schritt 3 — $p^2$ gerade $\Rightarrow$ $p$ gerade: Wegen $p^2 = 2 q^2$ ist $p^2$ gerade. Aus dem Hilfssatz $n^2$ gerade $\Rightarrow$ $n$ gerade (vgl. Aufgabe 5, Kontraposition) folgt: $p$ ist gerade. Also existiert $k \in \mathbb{Z}$ mit $p = 2k$.
Zeige mit Kontraposition: für alle $n \in \mathbb{Z}$ gilt
$$n^2 \text{ gerade} \;\Longrightarrow\; n \text{ gerade}.$$
Lösung anzeigen
Schritt 1 — Kontraposition aufstellen: Die Aussage $A \to B$ mit $A: n^2$ gerade, $B: n$ gerade ist logisch äquivalent zu $\neg B \to \neg A$, also
$$n \text{ ungerade} \;\Longrightarrow\; n^2 \text{ ungerade}.$$
Wir beweisen die Kontraposition direkt.
Schritt 2 — Voraussetzung $\neg B$: Sei $n$ ungerade. Nach Definition heißt das: es existiert $k \in \mathbb{Z}$ mit $n = 2k+1$.
Schritt 4 — Struktur wiedererkennen: Setze $m := 2k^2 + 2k \in \mathbb{Z}$. Dann ist $n^2 = 2m + 1$, also $n^2$ ungerade — d.h. $\neg A$.
Schritt 5 — Kontraposition liefert die Ursprungsaussage: Wir haben $\neg B \to \neg A$ gezeigt. Wegen der logischen Äquivalenz $(A \to B) \equiv (\neg B \to \neg A)$ folgt: $A \to B$, also $n^2$ gerade $\Rightarrow$ $n$ gerade.
Anmerkung: Ein direkter Beweis wäre schwierig, weil man aus $n^2 = 2m$ nicht unmittelbar auf $n = 2\ell$ schließen kann, ohne den Fundamentalsatz der Arithmetik zu bemühen. Die Kontraposition ist die elegante Standardlösung.
Aufgabe 6 — Fallunterscheidung: $n^2 + n$ ist gerademittel
Beweise per Fallunterscheidung: für alle $n \in \mathbb{N}$ gilt
$$n^2 + n \;\text{ ist gerade}.$$
Lösung anzeigen
Schritt 1 — Fälle festlegen: Jede natürliche Zahl $n$ ist entweder gerade oder ungerade. Wir unterscheiden also:
Fall 1: $n$ ist gerade, d.h. $\exists k \in \mathbb{N}_0: n = 2k$.
Fall 2: $n$ ist ungerade, d.h. $\exists k \in \mathbb{N}_0: n = 2k+1$.
Die Fälle sind disjunkt und decken alle $n \in \mathbb{N}$ ab.
Schritt 2 — Fall 1 ($n = 2k$):
$$n^2 + n \;=\; (2k)^2 + 2k \;=\; 4k^2 + 2k \;=\; 2\,(2k^2 + k).$$
Mit $m := 2k^2 + k \in \mathbb{Z}$ folgt $n^2 + n = 2m$, also gerade. $\checkmark$
Schritt 3 — Fall 2 ($n = 2k+1$):
$$n^2 + n \;=\; (2k+1)^2 + (2k+1) \;=\; 4k^2 + 4k + 1 + 2k + 1 \;=\; 4k^2 + 6k + 2 \;=\; 2\,(2k^2 + 3k + 1).$$
Mit $m := 2k^2 + 3k + 1 \in \mathbb{Z}$ folgt wieder $n^2 + n = 2m$, also gerade. $\checkmark$
Schritt 4 — Fälle zusammenführen: In beiden Fällen ist $n^2 + n$ gerade. Da die Fälle den gesamten Bereich abdecken, gilt die Aussage für alle $n \in \mathbb{N}$.
Ergebnis: $n^2 + n$ ist für alle $n \in \mathbb{N}$ gerade. $\blacksquare$
Alternative: Man kann auch direkt argumentieren: $n^2 + n = n(n+1)$, und von zwei aufeinanderfolgenden ganzen Zahlen ist stets genau eine gerade. Ein Produkt mit einem geraden Faktor ist gerade. Die Fallunterscheidung ist aber die formal saubere Standardlösung.
Widerlege durch Angabe eines Gegenbeispiels folgende Behauptung: Für alle $n \in \mathbb{N}$ ist $n^2 - n + 41$ eine Primzahl.
Erkläre, warum ein einziges Gegenbeispiel die Allaussage widerlegt.
Lösung anzeigen
Schritt 1 — Aussage präzisieren: Die Behauptung lautet $\forall n \in \mathbb{N}: p(n) := n^2 - n + 41 \text{ ist prim}$. Zum Widerlegen genügt nach $\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$ ein einziges $n$ mit $p(n)$ nicht prim.
Schritt 2 — Werte testen (Beobachtung): Für kleine $n$ liefert das Polynom tatsächlich Primzahlen:
$n$
$p(n) = n^2 - n + 41$
Prim?
1
41
ja
2
43
ja
3
47
ja
10
131
ja
40
1601
ja
Das reicht als Argument NICHT — es sind nur endlich viele Belege für eine Allaussage.
Schritt 3 — Verdachtsstelle $n = 41$: Setze $n = 41$:
$$p(41) \;=\; 41^2 - 41 + 41 \;=\; 41^2 \;=\; 1681.$$
Das ist $41 \cdot 41$, also durch $41$ teilbar und offensichtlich nicht prim (mehr als zwei Teiler: $1, 41, 1681$).
Schritt 4 — Warum genügt das? Ein einziges konkretes $n = 41$ mit $p(n)$ nicht prim ist eine Instanz von $\neg P$. Wegen der logischen Äquivalenz $\neg \forall n\, P(n) \equiv \exists n\, \neg P(n)$ ist damit die Allaussage widerlegt. Es ist unerheblich, dass $p(n)$ für viele andere $n$ prim ist.
Ergebnis: Die Behauptung ist falsch. Gegenbeispiel: $n = 41$, denn $p(41) = 1681 = 41^2$ ist nicht prim. $\blacksquare$
Aufgabe 8 — Induktion: geometrische Summeschwer
Beweise per vollständiger Induktion, dass für alle $n \in \mathbb{N}_0$ und alle $q \in \mathbb{R}$ mit $q \neq 1$ gilt:
Schritt 6 — Zielform: Wegen $q^{n+2} = q^{(n+1)+1}$ ist das genau $\frac{q^{(n+1)+1}-1}{q-1}$, also $P(n+1)$. $\checkmark$
Ergebnis: Nach vollständiger Induktion gilt $\sum_{k=0}^{n} q^k = \frac{q^{n+1}-1}{q-1}$ für alle $n \in \mathbb{N}_0$, $q \neq 1$. $\blacksquare$
Typische Klausurfragen — was wird gelesen?
Aufgabentyp
Was liest man?
Falle
Beweis zuordnen
Ein fertiger Text: erkenne, ob direkt, kontraponiert, per Widerspruch, per Induktion oder per Fallunterscheidung.
Widerspruch und Kontraposition werden häufig verwechselt — Kontraposition zeigt $\neg B \to \neg A$, Widerspruch nimmt $A \land \neg B$ an und leitet $\bot$ her.
Induktion prüfen
Basis, Voraussetzung, Schritt — sind alle drei sauber ausgezeichnet?
Fehlender oder falscher Induktionsanfang. Verwendung der Behauptung $P(n+1)$ im Schritt statt der Voraussetzung $P(n)$.
Logik-Äquivalenz lesen
Formel wie $\neg(A \to B) \equiv A \land \neg B$ verifizieren.
Vergessen, dass $A \to B$ äquivalent zu $\neg A \lor B$ ist.
Quantoren negieren
Aussage der Form $\forall x\, \exists y\, P(x,y)$ negieren.
Reihenfolge der Quantoren umdrehen und beide flippen: $\exists x\, \forall y\, \neg P(x,y)$.
Gegenbeispiel angeben
Behauptung wie „jede stetige Funktion ist differenzierbar" widerlegen.
Ein einziges Beispiel reicht — mehrere sind kein Fehler, aber die Argumentation muss klar sagen: dieses $x$ erfüllt $A$ und nicht $B$.
Fragen zum Selbsttest
1. Was ist der Unterschied zwischen Kontraposition und Widerspruchsbeweis?
Beide sind indirekte Techniken, aber strukturell verschieden. Kontraposition ersetzt die Zielaussage $A \to B$ durch die logisch äquivalente Aussage $\neg B \to \neg A$ und beweist letztere direkt — es entsteht kein Widerspruch. Der Widerspruchsbeweis nimmt hingegen $A$ und $\neg B$ gleichzeitig an und leitet daraus eine offensichtlich falsche Aussage (z. B. $0 = 1$) her. Merksatz: Kontraposition dreht die Implikation um, Widerspruch fügt $\neg B$ zur Prämisse hinzu und sucht $\bot$.
2. Ist die folgende Argumentation ein Induktionsbeweis? „Für $n = 1, 2, 3, 4, 5$ gilt die Formel, also gilt sie für alle $n$."
Nein. Das ist keine Induktion, sondern eine unzulässige Verallgemeinerung. Vollständige Induktion verlangt zwei Bausteine: den Induktionsanfang für ein konkretes $n_0$ (meist 1 oder 0) und den Induktionsschritt, der aus $P(n)$ die Aussage $P(n+1)$ folgert. Nur die Kombination aus Basis und Schritt liefert $P(n)$ für alle $n \geq n_0$.
Alle Quantoren werden geflippt und die innerste Implikation wird zu einer Konjunktion mit Negation der Konklusion. Ergebnis: $\exists \varepsilon > 0\ \forall \delta > 0\ \exists x \in \mathbb{R}\ (|x - x_0| < \delta \land |f(x) - f(x_0)| \geq \varepsilon)$. Das ist genau die Definition der Unstetigkeit an $x_0$.
4. Warum reicht ein Gegenbeispiel, um eine Allaussage zu widerlegen, aber nicht, um eine Existenzaussage zu bestätigen?
Weil $\neg \forall x\, P(x)$ logisch äquivalent zu $\exists x\, \neg P(x)$ ist — ein einziges konkretes $x$, das $P$ nicht erfüllt, erledigt die Allaussage. Umgekehrt ist $\exists x\, P(x)$ bereits eine Existenzbehauptung, für die man tatsächlich ein $x$ mit $P(x)$ angeben muss; ein Beispiel ist also nicht Widerlegung, sondern direkter Beweis dieser Aussage.
5. Erkläre, welche Beweistechnik für den Satz „Es gibt unendlich viele Primzahlen" (Euklid) benutzt wird.
Widerspruchsbeweis. Man nimmt an, es gäbe nur endlich viele Primzahlen $p_1, \dots, p_n$, bildet das Produkt $N = p_1 \cdot \dots \cdot p_n + 1$ und zeigt, dass $N$ durch keine der $p_i$ teilbar ist. Damit hat $N$ einen Primteiler außerhalb der Liste — Widerspruch zur Annahme, die Liste sei vollständig.
6. Warum ist die Aussage $A \to B$ logisch äquivalent zu $\neg A \lor B$?
Weil die Wahrheitstabelle beider Formeln übereinstimmt: $A \to B$ ist genau dann falsch, wenn $A$ wahr und $B$ falsch ist, in allen anderen drei Fällen wahr. $\neg A \lor B$ ist genau dann falsch, wenn $\neg A$ falsch (also $A$ wahr) und $B$ falsch ist — dieselben Zeilen. Aus dieser Äquivalenz folgt auch die Kontraposition, denn $\neg A \lor B \equiv B \lor \neg A \equiv \neg(\neg B) \lor \neg A \equiv \neg B \to \neg A$.
7. Welche Eigenschaften muss eine Äquivalenzrelation erfüllen, und was ist ein typisches Beispiel?
Eine Äquivalenzrelation $R$ auf einer Menge $A$ ist reflexiv ($\forall a: aRa$), symmetrisch ($aRb \to bRa$) und transitiv ($aRb \land bRc \to aRc$). Standardbeispiel: die Restklassenrelation modulo $n$ auf $\mathbb{Z}$, also $a \equiv b \pmod{n}$. Diese Eigenschaften ermöglichen die Zerlegung von $A$ in disjunkte Äquivalenzklassen — ein Konstrukt, das später bei Nerode-Klassen und Minimal-DEA wiederkommt.
8. Ein Beweistext beginnt mit „Angenommen, es gäbe ein $x \in L$ mit …". Welche Technik ist das wahrscheinlich?
Widerspruchsbeweis. Die Formulierung „Angenommen, es gäbe …" ist der typische Einstieg, wenn die Behauptung eine Nicht-Existenz oder Allaussage ist und man $\neg B$ zur Prämisse hinzunimmt. In der Theo Inf tritt dieses Muster überall bei Nicht-Regularitätsbeweisen mit dem Pumping-Lemma auf: man nimmt an, $L$ sei regulär, und leitet einen Widerspruch her.
9. Was ist der Unterschied zwischen einer injektiven und einer surjektiven Funktion? Wann heißt sie bijektiv?
Eine Funktion $f: A \to B$ ist injektiv, wenn verschiedene Argumente stets verschiedene Werte liefern: $f(a_1) = f(a_2) \Rightarrow a_1 = a_2$. Sie ist surjektiv, wenn jedes $b \in B$ mindestens ein Urbild besitzt: $\forall b \in B\ \exists a \in A: f(a) = b$. Bijektiv heißt sie, wenn sie injektiv und surjektiv zugleich ist — dann existiert eine Umkehrfunktion $f^{-1}: B \to A$.
10. Lies den folgenden Beweis-Ansatz und benenne die Technik: „Wir zerlegen die Wortlänge $|w|$ in die Fälle $|w| = 0$, $|w|$ ungerade, $|w|$ gerade und positiv." Welche Technik liegt vor, und worauf muss man achten?
Fallunterscheidung. Zu prüfen ist, dass die Fälle (a) einander ausschließen und (b) den gesamten Bereich der Voraussetzung abdecken — hier: alle $n \in \mathbb{N}_0$. $|w| = 0$ und $|w|$ gerade und positiv sind disjunkt, $|w|$ ungerade ebenfalls disjunkt dazu, und zusammen ergeben sie alle nichtnegativen ganzen Zahlen. Fehlt ein Fall, ist der Beweis unvollständig; überlappen Fälle, ist der Beweis nur unelegant, aber nicht falsch.
Dos & Donts in der Klausur
Dos
Beweisziel und Voraussetzung zu Beginn explizit hinschreiben.
Bei Induktion: Anfang, Voraussetzung und Schritt klar auszeichnen.
Beim Widerspruch die Annahme $\neg B$ ausdrücklich formulieren und am Ende den Widerspruch benennen.
Quantoren korrekt setzen — Reihenfolge ist bedeutungstragend.
Nach dem Beweis mit $\blacksquare$ oder q.e.d. abschließen.
Donts
Beispiele mit Beweis verwechseln — drei bestätigende $n$ sind kein Induktionsbeweis.
Induktionsvoraussetzung stillschweigend ohne Nennung benutzen.
Gegenbeispiel zur Bestätigung einer Allaussage anbieten.
Quantoren beim Negieren stehen lassen ($\forall$ und $\exists$ müssen kippen).
Beim Widerspruchsbeweis vergessen, welche Aussage nun eigentlich als falsch gezeigt wurde.