Universit¨ at Heidelberg / Institut f¨ ur Informatik Prof. Dr. Klaus Ambos-Spies Dipl.-Math. Martin Monath 19. Oktober 2014 ¨ Ubungen zur Vorlesung Mathematische Logik Blatt 1 Aufgabe 1 (4 Punkte) Schreiben Sie die folgende Formel ϕ, die hier in abgek¨ urzter Schreibweise angegeben ist, aus und geben Sie lz(ϕ), l(ϕ) und ρ(ϕ) an. (¬A → B ∨ (B → C) → A) ↔ (B ∧ A ↔ C) Aufgabe 2 (4 Punkte) In einer Stahlbaufirma haben die Vorbereitungen f¨ ur die Montage einer Br¨ ucke begonnen. Die vormontierten Baugruppen sollen mit Hilfe von Hydraulikpressen in die erforderliche Stellungen gebracht werden. Bei einerm dieser Montageschritte muss unbedingt vermieden werden, dass die Ventile zur Bet¨atigung der Hydraulikpressen in einer der folgenden Konstellationen kommen: 1. Ventil E geschlossen und Ventile B oder D offen. 2. Ventile A oder C geschlossen und Ventil F offen. 3. Ventile D, E und A offen. 4. Ventile B und D geschlossen. 5. Ventile B offen und Ventil A geschlossen. 6. Ventil D geschlossen und Ventile B und E offen. 7. Ventile B und C geschlossen und Ventile D und E offen. (a) F¨ uhren Sie geeignete Aussagenvariable ein und formalisieren Sie damit den Sachverhalt, dass diese 7 Konstellationen vermieden werden sollen. (2 Punkte) (b) Wie lautet die Stellung der Ventile, bei der alle genannten Konstellationen vermieden werden? (2 Punkte) Aufgabe 3 (4 Punkte) Zeigen Sie durch Induktion nach dem Aufbau von ϕ, dass l(ϕ) ≤ 2ρ(ϕ)+2 − 3 gilt. Aufgabe 4 (4 Punkte) Zeigen Sie, dass das Prinzip der vollst¨andigen Induktion ¨aquivalent zum Minimumsprinzip ist. Abgabe: Bis Montag, den 27. Oktober 2014, 14 Uhr in den Briefk¨asten im Foyer im ¨ EG der Angewandten Mathematik. Die aktuellen Ubungsbl¨ atter werden in Zukunft montags in der Vorlesung verteilt und sind als PDF-Dateien im Internet auf der Seite der Vorlesung abrufbar: http://www.math.uni-heidelberg.de/logic/ws14/mathlogik_ws14.html