+1 Daumen
4,3k Aufrufe

ich soll folgende Formel in eine Hornformel umwandeln. Leider scheitere ich an einer Stelle...

$$F=(!A\vee B)\wedge (A\vee C)\wedge (!C\vee !D)\wedge !E\wedge !G\wedge (A\vee E\vee G)\wedge !D$$

"!" Bedeutet hier die Negation.

Aber um das ganze in eine Hornformel zu Überführen müsste ich doch den Term: $$(A\vee C)$$

Umwandeln und laut meiner Vorlesung kann dies nicht in einer Hornformel äquivalent ausgedrückt werden.

Bisher habe ich das ganze so umgewandelt.

$$F=(!A\vee B)\wedge (A\vee C)\wedge (!C\vee !D)\wedge !E\wedge !G\wedge (!A\vee G)\wedge (!E\vee G)\wedge !D$$

Es ist ja bis auf $$(A\vee C)$$ immer nur maximal ein positives Literal vorhanden

Avatar von

kannst du vielelciht einfach de morgan gesetze anwenden und die klammer aufösen dann erhältst du die knf und hast zwei weitere negative literale zu dem negierten D ganz hinten

so ??

$$  (...)\wedge (A \vee C) \wedge (....) \\ (...)\wedge (\lnot A \wedge \lnot C) \wedge (...) \\ (...)\wedge \lnot A \wedge \lnot C \wedge (....)  $$

Das stimmt so nicht, richtig wäre:

$$(A\vee C)=\neg(\neg A\wedge\neg C).$$
Das lässt sich aber nicht auflösen.

1 Antwort

+1 Daumen
 
Beste Antwort
Wie hast du (\(A\vee E\vee G)\) in \((!A\vee G)\wedge(!E\vee G)\) umgewandelt? Diese sind nicht äquivalent, genauer sind sie nie äquivalent, wenn nur G falsch ist!

Bespiel: $$A=1, E=0, G=0: A\vee E\vee G=1\vee 0\vee 0=1\neq0=0\wedge1=(0\vee0)\wedge(1\vee0)=(!A\vee G)\wedge(!E\vee G)$$

Für \(A=B=1\) und \(D=E=G=0\) ist das ursprüngliche \(F\) wahr, deines aber falsch.

Was du hier tun musst, ist, bereits bestehende Aussagen in die Umformung miteinzubeziehen. Wenn bereits eine andere Klausel falsch ist, ist es egal, ob diese Klausel wahr oder falsch ist, wichtig für eine Äquivalenz ist nur, dass man den Wert nicht ändert, wenn alle anderen Klauseln wahr sind. Also:

$$F=(!A\vee B)\wedge(A\vee C)\wedge(!C\vee !D)\wedge!E\wedge!G\wedge(A\vee E\vee G)\wedge!D.$$

\(F\) ist immer falsch, wenn \(G\) wahr ist, also ist es egal, ob (\(A\vee E\vee G)\) oder (\(A\vee E)\) da steht. Nochmal: Wichtig ist nur, dass F nicht plötzlich falsch wird, wenn es vorher wahr war, oder wahr, wenn es vorher falsch war, für denselben Input.

Dasselbe kann man über \(E\) sagen, also kann man \(F\) vereinfachen zu:

$$F=(!A\vee B)\wedge(A\vee C)\wedge(!C\vee !D)\wedge!E\wedge!G\wedge A\wedge!D.$$

Wenn \(A\) wahr ist, ist auch \(A\vee C\) wahr, also kann man \((A\vee C)\) ganz weglassen.

$$F=A\wedge(!A\vee B)\wedge(!C\vee !D)\wedge !D\wedge!E\wedge!G.$$

Hier hast du bereits eine Horn-Formel. Das\(!C\vee!D\) und das \(!A\) sind zwar auch überflüssig, aber zumindest hast du schon mal die richtige Form erreicht. Minimales \(F\) ist jedoch:

$$F=A\wedge B\wedge!D\wedge!E\wedge!G.$$
Avatar von 1,0 k

Super, vielen Dank für die tolle Erklärung. Das hilft mir definitiv weiter.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community