T09-Beweistechniken-Induktion-und-Widerspruch

Beweistechniken: Induktion & Widerspruch

Zusammenfassung

Beweistechniken sind eine querschnittliche Fähigkeit, die in mehreren Klausuraufgaben benötigt wird. In der TI-Klausur sind direkt 11 Punkte von dieser Fähigkeit abhängig:

  • A3a (7P): Beweis per Widerspruch (Primimplikanten-Anzahl)
  • A5a (4P): Induktionsbeweis (Summenformel)

Darüber hinaus werden Beweistechniken in vielen anderen Aufgaben implizit benötigt (z.B. Blatt03: Induktionsbeweis für ggt, Blatt02: Induktionsbeweis für Fibonacci).

Exam-Relevanz

Aufgabe Punkte Technik Inhalt
A3a 7P Widerspruchsbeweis "Die Anzahl an Primimplikanten ändert sich nicht, wenn ein Eintrag zur ON-Menge hinzugefügt wird" — widerlegen durch Widerspruch (mit Induktion)
A5a 4P Vollständige Induktion beweisen

Total: 11 Punkte direkt von Beweistechniken abhängig.

Vollständige Induktion

Struktur

Die vollständige Induktion beweist eine Aussage für alle in drei Schritten:

  1. Induktionsanfang (IA): Zeige (oder , je nach Startwert).
  2. Induktionsvoraussetzung (IV): Nehme an, gilt für ein festes .
  3. Induktionsschritt (IS): Zeige, dass aus folgt .

Daraus folgt für alle .

Worked Example: Geometrische Summenformel für

Behauptung: Für alle gilt:

IA ():

IV: Für ein festes gelte .

IS ():

Worked Example: Allgemeine geometrische Summenformel

Behauptung: Für alle und gilt:

IA ():

IV: Für ein festes gelte .

IS ():

Worked Example: Vorlesungsbeispiel (Teleskopsumme)

Behauptung: Für alle gilt:

IA ():

IV: Für ein festes gelte .

IS ():

Klausur-Relevanz: A5a

Die Klausur (A5a) verlangt den Induktionsbeweis für:

Hinweis: Die allgemeine geometrische Summenformel ergibt für :
Die Klausurformel stimmt nur, wenn der Summand statt lautet (denn ). Der Beweisweg ist identisch; vermutlich handelt es sich um einen Tippfehler in der Klausur.

Beweis für (korrigierte Version):

IA ():

IV: .

IS:

Beweis per Widerspruch

Struktur

Es soll die Aussage bewiesen werden.

  1. Annahme: Nehme das Gegenteil an.
  2. Folgerung: Leite aus (zusammen mit den Axiomen) schrittweise Folgerungen ab.
  3. Widerspruch: Erreiche eine Aussage, die offensichtlich falsch ist (z.B. , oder ).
  4. Schluss: Da der Widerspruch logisch aus hergeleitet wurde, muss falsch sein. Also gilt .

Spezialfall: Kontraposition

Für ist . Ergibt sich der Widerspruch speziell durch Herleitung von aus , so reduziert sich der Widerspruchsbeweis auf die Kontraposition: . Diese ist logisch äquivalent zu .

Worked Example: (aus der Vorlesung)

Behauptung: .

Annahme: . Dann existieren , so dass für alle gilt:

Wähle (so dass ). Wähle . Dann:

Aber (1) muss auch für gelten: . Widerspruch zu (2)!

Worked Example: A3a — Primimplikanten-Anzahl (Klausur)

Behauptung (zu widerlegen): "Die Anzahl an Primimplikanten ändert sich nicht, wenn ein Eintrag zu der ON-Menge hinzugefügt wird."

Annahme: Die Behauptung sei wahr.

Schritt 1 — Induktion: Unter dieser Annahme zeigen wir per Induktion, dass alle ON-Mengen dieselbe Anzahl an Primimplikanten haben wie die leere ON-Menge.

  • IA: Die leere ON-Menge hat Primimplikanten (für irgendein ). Die leere ON-Menge hat offensichtlich Primimplikanten.
  • IV: Eine ON-Menge mit Elementen hat Primimplikanten.
  • IS: Fügen wir ein Element hinzu, ändert sich die Anzahl nicht (nach unserer Annahme). Also hat die ON-Menge mit Elementen ebenfalls Primimplikanten.

Damit haben alle ON-Mengen genau Primimplikanten — einschließlich der vollen ON-Menge (alle Minterme).

Schritt 2 — Widerspruch:

  • Die leere ON-Menge hat 0 Primimplikanten (keine Einsen kein Implikant).
  • Die volle ON-Menge (alle Minterme sind in der ON-Menge) hat genau 1 Primimplikanten: das leere Monom (die konstante Funktion 1), da dieses alle Minterme abdeckt und nicht weiter vergrößert werden kann.

Es gilt . Widerspruch!

Schluss: Die Annahme ist falsch. Die Anzahl an Primimplikanten kann sich ändern, wenn ein Eintrag zur ON-Menge hinzugefügt wird.

Konkretes Gegenbeispiel (zur Veranschaulichung)

Funktion :

  • ON-Menge : 0 Primimplikanten.
  • ON-Menge : 1 Primimplikant ().
  • ON-Menge : 1 Primimplikant ().
  • ON-Menge : 1 Primimplikant (, leeres Monom).

Beim Übergang von zu ändert sich die Anzahl von 0 auf 1. Die Behauptung ist also falsch.

Weitere Beweistechniken

Direkter Beweis (Sukzessive Folgerungen)

Aus folgt , aus folgt , aus folgt , also gilt .

Beispiel (aus Vorlesung): und .

  1. Aus : für .
  2. Aus : für .
  3. Wähle , . Für :
  4. Also .

Beweis durch Kontraposition

Statt direkt zu beweisen, beweist man (logisch äquivalent).

Beispiel: "Wenn gerade ist, dann ist gerade."

  • Kontraposition: "Wenn ungerade ist, dann ist ungerade."
  • — ungerade.

Fallunterscheidung

Man zerlegt den Beweis in disjunkte Fälle, die zusammen alle Möglichkeiten abdecken.

Beispiel: Für alle gilt .

  • Fall 1: . Dann , also .
  • Fall 2: . Dann , also .

Geometrische Summenformel

Allgemeine Form

ü

Spezialfälle:

Formel Kontext
Zweierkomplement, Binärzahlen
Zehnerkomplement
Zehnerkomplement (alle Ziffern = 9)

Anwendung: Zweierkomplement (Blatt03 A3)

Das Lemma aus der Vorlesung besagt: Für in Zweierkomplement-Darstellung gilt:

wobei durch Invertieren aller Bits entsteht.

Beweis-Skizze (mit geometrischer Summenformel):

Hierbei wurde (geometrische Summenformel mit ) verwendet.

Typische Klausuraufgaben

A3a — Widerspruchsbeweis (7P)

Betrachten Sie folgende Behauptung: Die Anzahl an Primimplikanten ändert sich nicht, wenn ein Eintrag zu der ON-Menge hinzugefügt wird.

Beweisen Sie durch Widerspruch, dass dies falsch ist, in dem:

  1. Sie per Induktion zeigen, dass unter der Annahme dieser Behauptung alle ON-Mengen genau so viele Primimplikanten haben wie die leere ON-Menge und auch so viele Primimplikanten wie die ON-Menge mit allen Mintermen.
  2. Sie daraus einen Widerspruch ableiten.

Lösungsstrategie: Annahme Induktion (alle ON-Mengen haben gleich viele PI) Widerspruch (leere ON-Menge hat 0 PI, volle hat 1 PI). Siehe Worked Example oben.

A5a — Induktionsbeweis (4P)

Beweisen Sie per Induktion im Detail, dass:

Lösungsstrategie: Standard-Induktion (IA, IV, IS). Siehe Worked Example oben. Hinweis: Die Formel in der Klausur enthält vermutlich einen Tippfehler; korrekt ist oder .

Siehe: Exam A3a/A5a, probeklausur A3a/A5a

Übungsblätter

Blatt Aufgabe Technik Inhalt Punkte
Blatt-00d A4a Induktion Minimales Element in Mengen der Größe 3P
Blatt-00d A4c Induktion Minimales Element für totale Ordnung 4P
Blatt02 A2a Induktion (Fibonacci-Additionen) 5P
Blatt02 A2b Induktion Äquivalenz zweier Fibonacci-Definitionen (Teil von 5P)
Blatt03 A3 Beweis mit Summenformel Zweierkomplement-Lemma 3P
Blatt03 A4b Induktion ggt braucht Schritte für Fibonacci-Zahlen 5P

Quellen

  • k110-Mathematische_Grundlagen — Beweistechniken: direkter Beweis, Widerspruch, Induktion (Folien 29–37)
  • Blatt-00d — A4: Induktion (minimales Element)
  • Blatt02 — A2: Induktion (Fibonacci)
  • Blatt03 — A3: Summenformel, A4b: Induktion (ggt)
  • Exam — A3a: Widerspruchsbeweis (7P), A5a: Induktionsbeweis (4P)
  • probeklausur — A3a: Widerspruchsbeweis (7P), A5a: Induktionsbeweis (4P)

Priorität

CRITICAL — Beweistechniken werden in zwei separaten Klausuraufgaben (A3a und A5a) mit zusammen 11 Punkten direkt geprüft. Zudem sind sie eine Grundfähigkeit, die in vielen Übungsblättern benötigt wird.

Wichtig:

  • A3a kombiniert Induktion und Widerspruch in einer Aufgabe — beide Techniken müssen beherrscht werden.
  • A5a erfordert einen sauberen, detaillierten Induktionsbeweis mit expliziter Angabe von IA, IV und IS.
  • Die geometrische Summenformel (insbesondere für ) ist zentral für das Zweierkomplement.