Aussagenlogik Beweise führen (DNF, KNF)?
Komme auf folgende Aufgabe nicht klar:
zu i) Wieso soll ich zeigen, dass der Konjuntionsterm mindestens zwei positiven Literale hat. Ist das nicht in der Aufgabenstellung ('enthält mind. zwei EInsen' ) defininiert.
gleiches gilt für ii)
iii) Wenn die zweielementigen Teilmengen als n über 2 definiert sind und die DFN mindestens zwei positive Literale hat, dann hat sie doch schon mal mindestens zwei Teilemengen, oder?
iv) Eine DNF mit möglichst wenig Konjunktionstermen. Wenn D mindestens zwei pos. Literale enthält, wäre das wenigstense doch zwei, oder?
2 Antworten
zu i) Das folgt nicht SO direkt aus der Aufgabenstellung. Sagen wir, wir haben z.B. 2 Variablen x,y und nehmen die Belegung B(x) = 1, B(y) = 1.
Die disjunktive Normalform (x and y) or (not x and not y) liefert offensichtlich 1 zurück; was auch gut ist, da die Belegung tatsächlich zwei Einsen hat.
ABER: Einer der Konjunktionsterme (der zweite nämlich) hat kein einziges positives Literal. Wenn die Aussage in i) stimmt, muss es also eine Belegung geben, für die diese DNF das falsche Ergebnis zurückliefert.
Wir können uns um den Rest der Aufgaben kümmern, wenn du i) verstanden hast ;)
Ich glaube, du hast eine falsche Vorstellung vom Wort "Literal". Nehmen wir eine einfachere DNF, etwa die Formel (x and not y).
Die "Literale" in dieser Formel sind einmal 'x' und einmal 'not y'. Das Literal 'x' ist positiv (weil kein "not" davor steht) und das Literal 'not y' ist negativ.
Ob ein Literal positiv oder negativ ist, hat erst einmal nichts mit der Belegung zu tun. Wenn jetzt etwa B(x) = 0 und B(y) = 1 ist, dann ist 'x and not y' = '0 and 0', aber dennoch bleibt das Literal x positiv, weil es in nicht-negierter Form in der DNF auftaucht.
Die Aufgabenstellung sagt jetzt: Wenn auch nur ein einziger Konjunktionsterm höchstens ein positives Literal besitzt, dann ist die DNF keine Formel für chi. Die Frage ist: warum?
Also zu i) und ii)
Literale sind meines Wissens nach die "Variablen", wie sie in einer Klausel vorkommen. Das heißt du musst zeigen, dass jede der UND-Formeln, die disjunktiv miteinander verknüpft werden, zwei positive Literale enthält.
Das hat nichts mit zu tun, dass deine grundlegende Variablenbelegung zwei positive Werte enthält.
wären z.B. deine Variablen, von denen mindestens 2 Eins sindwäre z.B. eine Formel mit drei Literalen.
Ohne Gewähr, aber ich meine, dass das so ist.
Danke dir. Aber wenn ich zwei Belegungen habe und sie mit dem Gegenteil verunde, kommt doch immer etwas Wahrenr aus. B (x) = 1 und B (y) = 1 haben zwei Einsen. Wenn ich B = 1 und B (y) = 0 nehme, hat die Form 'x and y' eine 1 und die Form 'not x and not y' auch eine 1. Also gilt das doch immer, was zu zeigen ist?