Wie vorhin gewünscht habe ich die Lösungen elektronisch erfasst. :)
Ich möchte fragen, ob ich die folgenden Aufgaben korrekt gelöst habe. Es handelt sich um aussagenlogische Formeln. Ich bin da noch nicht so sehr sattelfest, daher bitte ich euch mir zu sagen, ob ich richtig liege. :-)
Aufgrund der recht beträchtlichen Anzahl an Übungen müsst ihr nicht alles anschauen, Aufgabe 3 und 4 wären mir am Wichtigsten.
Meine Lösungen sind in rot.
Aufgabe 1
Gegeben sind die beiden aussagenlogischen Formeln
F := p1 → (p2 ∧ p5) und G :=(p3 ∧ p2) → p4
sowie eine Belegung B mit B(pn) = 1 wenn n eine Primzahl ist und 0 für sonst.
(a) Berechnen Sie B(F) und B(G).
B(F) = 1, B(G) = 0
(b) Geben Sie zwei verschiedene Belegungen an, unter denen F zu 0 und G zu 1
evaluiert wird.
für F: B(pn) = 1 wenn n eine ungerade Zahl ist und 0 wenn n eine gerade Zahl ist
für G: B(pn) = 1 wenn n eine gerade Zahl ist und 0 wenn n eine ungerade Zahl ist
Aufgabe 2
Geben Sie von folgenden Formeln an, ob sie in DNF und/oder in KNF sind.
(a) p
DNF und KNF
(b) p ∧ (¬q ∧ p1)
DNF
(c) p ∨ (q → p)
KNF
(d) p ∨ ¬p
DNF und KNF
(e) (p ∨ q) ∧ (p ∨ p ∨ p)
KNF
Aufgabe 3
Bringen Sie folgende aussagenlogischen Formeln in DNF und KNF.
(a) p → (q ∨ (p1 ∧ p2))
¬ p ∨ (q ∨ p1) ∧ (q ∨ p2) KNF
¬ p ∨ (q ∧ q) ∨ (p1 ∧ q) ∨ ((q ∧ p2) ∨ (p1 ∧ p2)) DNF
(b) p → (q → p1)
(¬ p ∨ q) ∧ (¬p ∨ ¬p1) KNF
((¬ p ∧ ¬ p) ∨ (q ∧ ¬p)) ∨ ((¬ p ∧ ¬ p1) ∨ (q ∧ ¬ p1)) DNF
(c) (p → q) → p1
(p∧ q) ∨p1 DNF
(p ∨p1)∧ (q∨ p1) KNF
Aufgabe 4
Zeigen Sie, dass die aussagenlogische Formel F genau dann unerfüllbar ist, wenn die
Formel ¬F allgemeingültig ist.
F unerfüllbar genau dann wenn ¬F allgemeingültig
∀B(B(F) = 0) → ∀B(¬F) = 1
∀B(B(¬F) = 1) → ∀B(1-B(F) = 1)
Aufgabe 5
Bestimmen Sie mithilfe von Wahrheitstabellen ob folgende Formeln allgemeingültig,
erfüllbar oder unerfüllbar sind.
(a) p → (q → p)
allgemeingültig
(b) (p → q) → (¬q → ¬p)
allgemeingültig
(c) (p → q) → (q → p)
erfüllbar
(d) (p → q) ∧ (p ∧ ¬q)
unerfüllbar
