Objektorientierte Programmierung und Modellierung (Fach) / Beweisen von Eigenschaften (Lektion)
In dieser Lektion befinden sich 1 Karteikarten
WS 15/16
Diese Lektion wurde von RouHim erstellt.
- Welche Beweismethode wird verwendet und wie funktioniert Sie? Beim Beweisen von Eigenschaften verwenden wir Vollständige Induktion als Methode. Meistens wird ein Gesetzt wie Kommutiativgesetzt o.ä. als zu beweisen vorgegeben.Ebenso wird die ASL Spezifikation für eine bestimmte Sort vorgegben z.B. List oder Stack. Diese Methode kann in verschiedene Teile aufgesplittet werden: Induktionsbehauptung (IB)Hier wird die vorgegebene Behauptung nocheinmal in Formaler schreibweise dargestellt. Induktionsanfang (IA)Hier beweisen wir mithilfe von vorgegebenen "Regeln" aus der ASL-Spezifikation das unsere IB für den kleinsten / ersten Wert der Sort gilt.Vorgehen:- Man wählt eine Seite der IB und setzt den kleinsten Wert ein.- Anschließend stellt man die gewählte Seite mithilfe der "Regeln" so um, das die andere Seite herauskommt.- Wichtig: Die Regeln und die Anwendungsrichtung müssen vor die jeweilige Zeile geschrieben werden, in der Sie angewendet wurden. Somit ist der IA fertig. Induktionsschritt / BeweisHier beweisen wir ähnlich wie in Punk 2., nur das unsere IB für einen Schritt (n+1) gilt.Wichtig ist das man die Induktionsvorraussetzung (IV) gleich wie IB nocheinmal aufschreibt, da man sie im Laufe des Beweises einsetzen muss.Vorgehen:- Man entscheidet sich wieder für eine Seite- Man setzt für eine Variable z.B. x = n+1 und schreibt die Seite mit dem eingesetzten Wert auf- Jetzt stellt man mithilfe von Regeln so um, dass man die IV einsetzten kann- Ist die IV eingesetzt muss jetzt so umgestellt werden dass die andere Seite als am Anfang gewählt herauskommt.- ggf. die Variable wieder für n+1 einsetzten.