Einführung in die Logik

Institut für
Theoretische Informatik
ITI
Dr. Jürgen Koslowski
Einführung in die Logik
Aufgabenblatt 5, 2016-05-23
Übungsaufgabe 25
Γ und Γ0 sind Formelmengen, F und G Formeln. Beweisen oder widerlegen Sie:
(a) Wenn Γ |= F , dann auch Γ ∪ Γ0 |= F .
(b) Γ |= F und Γ0 |= F implizieren Γ ∩ Γ0 |= F .
(c) Γ |= F und Γ0 |= G implizieren Γ ∪ Γ0 |= F ∧ G.
Lösungsvorschlag:
(a) Korrekt: Jede Belegung, die Γ ∪ Γ0 erfüllt, erfüllt auch Γ, nach Voraussetzung dann also
auch F .
(b) Falsch: Zwar gilt immer F ∧ G |= F und F ∧ H |= F , falls F keine Tautologie ist, gilt aber
nicht |= F .
(c) [3 punkte] Korrekt: Jede Γ ∪ Γ0 erfüllende und für F sowie G passende Belegung α erfüllt
sowohl Γ als auch Γ0 , also bildet α
b sowohl F als auch G auf 1 ab, daher auch F ∧ G.
Existiert keine derartige Belegung, ist Γ ∪ Γ0 |= F ∧ G trivialerweise korrekt.
Aufgabe 26 [10 PUNKTE]
Beweisen Sie Satz 6.0.2 der Vorlesung: Γ |= F gilt genau dann, wenn Γ ∪ {¬F } nicht erfüllbar
ist. Dabei ist Γ eine nicht notwendig endliche Menge von Formeln und F eine einzelne Formel.
Aufgabe 27 [9 PUNKTE]
Es sei Γ eine unerfüllbare Menge von aussagenlogischen Formeln. Zeigen Sie die Gültigkeit der
folgenden Sequenzen:
(a) [4 punkte] Γ |= ⊥.
(b) [5 punkte] Γ − {G} |= ¬G für jede Formel G ∈ Γ.
Aufgabe 28 [10 PUNKTE]
Zeigen oder widerlegen Sie: wenn Γ |= G ≡ H dann auch Γ |= H.
Die folgende Aufgabe bezieht sich auf die Vorlesumg am 25. Mai:
Aufgabe 29 [10 PUNKTE]
In der Vorlesung wurde der Kompaktheitssatz der Aussagenlogik wie folgt formuliert:
Kompaktheitssatz 0. Wenn Γ |= F , existieren endlich viele Formeln Gi ∈ Γ, i < n, mit
G0 , . . . , Gn−1 |= F .
In der Literatur ist darüber hinaus auch die folgende Aussage als Kompaktheitssatz bekannt:
Kompaktheitssatz 1. Eine Menge von Formeln ist erfüllbar, wenn jede ihrer endlichen Teilmengen erfüllbar ist.
(Dabei heißt eine Formelmenge Γ erfüllbar, wenn eine Belegung existiert, die jede Formel in Γ
wahr macht.)
Beweisen Sie, dass beide Aussagen in den Varianten des Kompaktheitssatzes gleichwertig sind,
d.h. die Aussage in Kompaktheitssatz 0 impliziert die Aussage in Kompaktheitssatz 1 und
umgekehrt.
Abgabe bis Montag, 2016-05-30, im Kasten neben IZ 343

Download Report