Institut für Theoretische Informatik ITI Prof. Dr. J. Adámek · Dipl.-Math. Dipl.-Inf. H. Urbat Einführung in die Logik Aufgabenblatt 9 Übungsaufgabe 1 Beweisen Sie die Gültigkeit der Sequenz A ⇒ B, B ⇒ C |= A ⇒ C im Hilbertkalkül. Hausaufgabe 1 [22 PUNKTE] Beweisen Sie die Gültigkeit der Sequenz C ⇒ ¬A ∨ ¬B, ¬A ⇒ ¬B, B |= ¬C (a) [4 PUNKTE] mit einer Wahrheitstabelle. (b) [8 PUNKTE] mit natürlicher Deduktion. (c) [5 PUNKTE] mit dem Markierungsalgorithmus. (d) [5 PUNKTE] mit einer SLD-Resolution. Hinweis. Transformieren Sie in (c) und (d) die Formeln der Sequenz in Hornklauseln, und beachten Sie Hausaufgabe 2(c) von Blatt 7. Hausaufgabe 2 [10 PUNKTE] Beweisen Sie die Gültigkeit der Sequenz A ⇒ (B ⇒ C), B |= A ⇒ C im Hilbertkalkül. Hausaufgabe 3 [8 PUNKTE] Zeigen Sie die Korrektheit des Hilbertkalküls: Jede beweisbare Sequenz ist semantisch gültig. Hinweis. Induktion nach der Beweislänge. Abgabe bis Freitag, 26.6., 14:00 Uhr, in den Briefkästen vor Raum IZ 343
© Copyright 2024 ExpyDoc
