Transcript
Institut für Theoretische Informatik
ITI
Prof. Dr. J. Adámek · Dipl.-Math. Dipl.-Inf. H. Urbat
Einführung in die Logik Probeklausur Bearbeitungszeit: 120 Minuten Aufgabe 1 [22 PUNKTE] Zeigen Sie die Gültigkeit der Sequenz ¬A ∨ C , B ⇒ C |= A ∨ B ⇒ C (a) [6 PUNKTE] mit einer Wahrheitstabelle. (b) [16 PUNKTE] mit natürlicher Deduktion. Der Deduktionsbeweis soll vollständig sein und ausschlieÿlich die in der Vorlesung eingeführten Deduktionsregeln verwenden.
Aufgabe 2 [10 PUNKTE] Testen Sie die folgende Hornformel mit dem Markierungsalgorithmus auf Erfüllbarkeit: B ∧ (¬F ∨ G) ∧ (¬D ∨ ¬C ∨ E) ∧ A ∧ (¬E ∨ ¬A ∨ ¬G) ∧ D ∧ (¬B ∨ C) ∧ (¬F ∨ ¬D).
Falls die Formel erfüllbar ist, geben Sie eine erfüllende Belegung an.
Aufgabe 3 [20 PUNKTE] Der Freistaat Bayern möchte ein groÿes Wassersportereignis ausrichten, das an mehreren Austragungsorten statt nden soll. Als mögliche Orte kommen der Ammersee, der Bodensee, der Chiemsee und die Donau in Frage. Im Verlauf der recht komplizierten Planungen stellt sich folgendes heraus: Falls man den Ammersee nutzt, müssen auch Wettkämpfe auf der Donau ausgetragen werden. Wird der Bodensee Austragungsort, muss man das aus politischen Gründen auch dem Chiemsee zugestehen. Sofern Veranstaltungen auf der Donau statt nden, muss man aus Kostengründen auf den Bodensee als Austragungsort verzichten. Und falls man den Chiemsee nutzt, benötigt man auch die Donau oder den Ammersee für die Wettkämpfe. (a) [8 PUNKTE] Formalisieren Sie die beschriebenen Zusammenhänge in Aussagenlogik. (b) [12 PUNKTE] Zeigen Sie mit der Resolutionsmethode, dass der Bodensee als Austragungsort wegfällt.
Aufgabe 4 [16 PUNKTE] Beweisen Sie mittels Strukturinduktion: Der Syntaxbaum einer aussagenlogischen Formel F hat genau n(F ) + 2 · m(F ) + 1 Knoten, wobei n(F ) die Anzahl der Negationssymbole (¬) und m(F ) die Anzahl der zweistelligen Junktoren (∨, ∧, ⇒, ⇔) in F ist.
Aufgabe 5 [15+10 PUNKTE] Sei Σ die Signatur mit dem Konstantensymbol 0, den Funktionssymbolen f (einstellig) und d (zweistellig) sowie dem Prädikatensymbol < (zweistellig). Sei R eine Σ-Struktur mit Trägermenge R, dR (x, y) = |x − y| und der üblichen Bedeutung von 0 und <. Formulieren Sie die folgenden Aussagen über die Funktion f : R → R jeweils als prädikatenlogische Formel in der Signatur Σ. (a) [4 PUNKTE] f (x) ≥ 0 für alle x ∈ R. (b) [5 PUNKTE] f hat höchstens zwei Nullstellen. (c) [6 PUNKTE] f (x) → 0 für x → ∞. (d) [10 PUNKTE] Bonusaufgabe: f hat nur endlich viele Nullstellen.
Aufgabe 6 [16 PUNKTE] Sei Σ die Signatur mit dem einstelligen Funktionssymbol f und dem zweistelligen Prädikatensymbol E . Beweisen oder widerlegen Sie die Allgemeingültigkeit der Formel ∀x : E(x, f (x)) ⇒ ∃z : E(y, z)
Argumentieren Sie detailliert, unter Verwendung der formalen Semantik der Prädikatenlogik.
Aufgabe 7 [21 PUNKTE] Beantworten Sie die folgenden Wissens- und Verständnisfragen. Knappe Antworten genügen! (a) [4 PUNKTE] Beweisen oder widerlegen Sie: Es gibt eine Sequenz Γ |= F , die mittels natürlicher Deduktion beweisbar ist, jedoch nicht im Hilbertkalkül. (b) [4 PUNKTE] Beweisen oder widerlegen Sie: Es gibt eine dreielementige Menge {F0 , F1 , F2 } von aussagenlogischen Formeln, die nicht erfüllbar ist und deren echte Teilmengen alle erfüllbar sind. (c) [4 PUNKTE] Beweisen oder widerlegen Sie: Es gibt es eine abzählbar unendliche Menge {F0 , F1 , F2 , F3 , . . .} von aussagenlogischen Formeln, die nicht erfüllbar ist und deren echte Teilmengen alle erfüllbar sind. (d) [4 PUNKTE] Beweisen oder widerlegen Sie: Zu jeder prädikatenlogischen Formel gibt es eine äquivalente Formel, in der keines der Symbole ∃, ∧ und ⇒ vorkommt. (e) [5 PUNKTE] Welche Eigenschaft muss eine Signatur Σ haben, damit eine prädikatenlogische Formel über Σ existiert, in der keine Variablen vorkommen?
