Hausaufgabe 1
Geben Sie diese Hausaufgabe bis 30. April 2015 ab. Entweder bis
16:00 per Email an 
Tillmann Rendel
AlumniTillmann Rendel (schreiben Sie “pl2” in den
Betreff!) oder zu Beginn der Vorlesung auf Papier.
Gruppen
Sie können in Gruppen von bis zu 3 Personen arbeiten. Schreiben Sie in jedem Fall die Namen und Matrikelnummern aller Gruppenmitglieder mit auf die Hausaufgabe / in die Email. Wenn Sie in einer Gruppe arbeiten, achten Sie darauf, daß alle Mitglieder der Gruppe den Stoff verstehen. Nur dann sind die Hausaufgaben eine gute Vorbereitung auf die Prüfung.
Punkte
Sie können für die Aufgaben dieser Woche jeweils zwischen 0 und 3 Punkten bekommen. Insgesamt also zwischen 0 und 6 Punkten. Sie bekommen für die Aufgaben jeweils:
-
1 Punkt, wenn Ihre Abgabe zeigt, daß Sie sich mit der Aufgabe ernsthaft beschäftigt haben.
-
2 Punkte, wenn Sie die Aufgabe weitgehend korrekt gelöst haben.
-
3 Punkte, wenn Sie die Aufgabe vollständig korrekt gelöst und Ihre Lösung gut verständlich dargestellt haben.
Die Punktevergabe für die weiteren Hausaufgaben im Semester wird ähnlich sein.
Aufgabe 1
In der Vorlesung haben wir eine Sequenz von Mengen Si wie folgt definiert:
S0 = ∅
Si + 1 = { true, false } ∪ { if t1 then t2 else t3 ∣ t1, t2, t3 ∈ Si }
Beweisen Sie: Si ⊆ Si + 1 für alle i.
Aufgabe 2
Hier ist die Syntax einer kleinen Sprache:
t ::= true ∣ false ∣ t ∧ t
Die Semantik dieser Sprache können wir durch eine Relation → zwischen Termen beschreiben:
true ∧ t → t
false ∧ t → false
t1 → t1′
t1 ∧ t2 → t′1 ∧ t2
Welche dieser Regeln sind Computation-Regeln, welche sind Congruence-Regeln?
Schreiben Sie zusätzliche Regeln, um folgende Ideen zu beschreiben:
- t ∧ false bedeutet false, egal was t bedeutet.
- t ∧ t bedeutet dasselbe wie t.
- Man kann auch das rechte Argument von ∧ zuerst auswerten.
Welche der neuen Regeln sind Computation-Regeln, welche sind Congruence-Regeln?