Aufgabe:
Eine DNF-Formel ist genau dann erfüllbar, wenn sie ein Disjunkt ohne Literale
der Form x, ¬x enthält.
Problem/Ansatz:
Bietet sich hier ein Widerspruchsbeweis an?
x = Eine DNF-Formel ist erfüllbar
y = DNF-Formel enthält ein Disjunkt ohne Literale der Form x, ¬x
f = beliebige Formel aus DNF
für Alle f gilt (x ↔ y)
Aussage negieren:
Es existiert ein f für das gilt ¬(x ↔ y)
¬(x ↔ y) ≡ (x ↔ ¬y)
Dann gebe ich DNF Formel mit Literal x und -x an, und zeige das diese erfüllbar ist -> Widerspruch
Ist dieses Vorgehen korrekt?
