Informatik 2: Wesentliche Beweistechniken – Vorlesung 4 📚

In Verlaufe des Kurses müssen wir immer wieder Aussagen beweisen und wenngleich es grundsätzlich praktikabel erscheinen mag, sich für jeden Beweis eine individuelle Vorgehensweise zu überlegen, ist es unbedingt zu empfehlen, sich an bewährten Techniken für Beweise zu orientieren. In dieser Vorlesung besprechen wir drei grundlegende Techniken, die dazu genutzt werden können, eine Vielzahl von Aussagen zu beweisen. Wir beginnen mit der vollständigen Induktion, die für über den natürlichen Zahlen indizierte Aussagen geeignet ist und betrachten dann den Widerspruchsbeweis. Schließlich betrachten wir eine Technik, die einen Spezialfall des Widerspruchsbeweises darstellt: Die Diagonalisierung.