Transcript
Universit¨ at Koblenz-Landau Institut f¨ ur Informatik Bernhard Beckert · Vladimir Klebanov · Claudia Obermaier · Cristoph Gladisch ·
SS ’06
www.uni-koblenz.de/~beckert www.uni-koblenz.de/~vladimir www.uni-koblenz.de/~obermaie www.uni-koblenz.de/~gladisch
¨ Ubung zur Vorlesung
Logik fu ¨ r Informatiker Aufgabenblatt 3 Aufgabe 8 Geben Sie f¨ ur die folgenden Formeln jeweils eine a¨quivalente Formel in (a) disjunktiver sowie (b) konjunktiver Normalform an. Geben Sie diese auch als Klauselmenge an. (a)
mit Hilfe einer Wahrheitstafel: (A ∧ (B → C)) → B
(b)
¨ mittels Aquivalenzumformungen: ((A → B) ∧ (B → C)) → (¬A → C)
Aufgabe 9 ¨ Zeigen Sie mittels Aquivalenzumformungen: (a)
p ∨ ¬(p ∧ q) ist eine Tautologie
(b)
(p ∨ ¬q) ∧ (¬p ∧ q) ist unerf¨ ullbar
Geben Sie bei jeder Umformung das verwendete Gesetz an.
Aufgabe 10 (a) Seien F und G erf¨ ullbar. Ist F ∨ ¬G immer eine Tautologie? (b) Seien A und A → B erf¨ ullbar. Ist B immer erf¨ ullbar? (c) Sei M eine beliebige Formelmenge und F eine Tautologie. Gilt immer M |= F ? (d) Sei G unerf¨ ullbar und F |= G. Was gilt dann f¨ ur F ∨ G? Geben Sie jeweils einen Beweis oder ein Gegenbeispiel an.
Aufgabe 11 Gegeben seien die Formeln A = (q → r) ∧ s und B = (p → q) → (p → r) Bestimmen Sie, ob A |= B oder B |= A gilt. Bestimmen Sie die Craig-Interpolante von A und B.
Abgabe bis 22.5. Schriftliche L¨osungen k¨onnen Sie jederzeit bis zum o.g. Datum ¨ in der Vorlesung oder Ubung abgeben.
Bernhard Beckert: Zi. B218, Tel. 287-2775,
[email protected] Vladimir Klebanov : Zi. B224, Tel. 287-2781,
[email protected] Claudia Obermaier : Zi. B207, Tel. 287-2768,
[email protected] Christoph Gladisch:
[email protected] Materialien: http://www.uni-koblenz.de/~beckert/Lehre/Logik/
2
