Klausurtraining · Aufgabe 1 · 10 Punkte

Hornformel und Markierungsalgorithmus

Diese Aufgabe steckt in allen drei Altklausuren. Erst die sechs Handgriffe einzeln, dann die komplette Aufgabe aus WS24 unter Zeit.

Handgriffe 0/12
—

Stufe 1 — die sechs Handgriffe

erst rechnen, dann aufdecken

Stufe 2 — Klausur WS24, Aufgabe 1

18 Minuten · 10 Punkte
Bedingungen18:00

Ein DIN-A4-Blatt Notizen ist erlaubt — sonst nichts. Kein Nachschlagen in Stufe 1. Wer über der Zeit ist, schreibt trotzdem zu Ende und notiert die Überzeit.

φ₁gegeben
φ₁ := (¬x₅ ∨ ¬x₄) ∧ ¬(x₃ ∧ x₂ ∧ ¬x₆) ∧ (¬x₆ ∨ (x₄ ∧ (x₁ ∨ ¬x₅))) ∧ (x₂ ↔ x₃) ∧ (x₂ ∨ (¬x₃ ∧ x₃)) ∧ (¬x₁ → ¬x₂ ∨ ¬x₃)
a)Klauselmenge + Implikationen5 P.

Gib eine zu φ₁ semantisch äquivalente KNF an — in Klauselschreibweise Φ und in Implikationsschreibweise φimp.

b)Tabelle + Satz5 P.

Ist φ₁ erfüllbar? Begründe mit dem Markierungsalgorithmus. Begründungsspalte nicht leer lassen — die gibt Punkte.

Programmschrittx₁x₂x₃x₄x₅x₆Begründung
Musterlösung a) · 5 Punkte

Zweig für Zweig, jeder einzeln:

1. (¬x₅ ∨ ¬x₄) → {¬x₄, ¬x₅} → x₄ ∧ x₅ → 0 2. ¬(x₃ ∧ x₂ ∧ ¬x₆) → {¬x₂, ¬x₃, x₆} → x₂ ∧ x₃ → x₆ (De Morgan) 3. ¬x₆ ∨ (x₄ ∧ (x₁ ∨ ¬x₅)) → {¬x₆, x₄} → x₆ → x₄ (Distributiv) → {x₁, ¬x₅, ¬x₆} → x₅ ∧ x₆ → x₁ 4. (x₂ ↔ x₃) → {¬x₂, x₃} → x₂ → x₃ → {x₂, ¬x₃} → x₃ → x₂ 5. x₂ ∨ (¬x₃ ∧ x₃) → {x₂} → 1 → x₂ (¬x₃ ∧ x₃ ≡ 0) 6. ¬x₁ → (¬x₂ ∨ ¬x₃) → {x₁, ¬x₂, ¬x₃} → x₂ ∧ x₃ → x₁

Kontrolle: jede Klausel hat höchstens ein positives Literal — also Hornformel.

Musterlösung b) · 5 Punkte
Init x₁0 x₂1 x₃0 x₄0 x₅0 x₆0 wegen (1 → x₂) x₁0 x₂1 x₃1 x₄0 x₅0 x₆0 (x₂ → x₃), da x₂=1 x₁0 x₂1 x₃1 x₄0 x₅0 x₆1 (x₂ ∧ x₃ → x₆), da x₂=x₃=1 x₁1 x₂1 x₃1 x₄0 x₅0 x₆1 (x₂ ∧ x₃ → x₁) x₁1 x₂1 x₃1 x₄1 x₅0 x₆1 (x₆ → x₄), da x₆=1 Ausgabe „Erfüllbar"

Ziel-Klausel x₄ ∧ x₅ → 0: x₅ = 0, Prämisse also nicht vollständig markiert → kein Widerspruch. x₅ ∧ x₆ → x₁ greift ebenfalls nicht (x₅ = 0).

Modell: I(x₁) = I(x₂) = I(x₃) = I(x₄) = I(x₆) = 1, I(x₅) = 0, also I ⊨ φ₁.

Punkteschema — gib dir selbst
  • a) 1 P. je korrekt umgeformtem Zweig (2, 3, 4 sind die Stolpersteine), 1 P. für die vollständige Implikationsschreibweise mit 1 → und → 0.
  • b) 3 P. Tabelle mit gefüllter Begründungsspalte, 1 P. Ausgabe „Erfüllbar", 1 P. explizit hingeschriebenes Modell.
  • Abzug: „unerfüllbar" mit Modell, fehlende 1 →-Form, leere Begründungsspalte.