WikiDer > Disjunktive Normalform

In dem Logik ist eine Formel in disjunktiv Normalform (Englisch: disjunktive Normalform, DNF) wenn es aus a . besteht Disjunktion von Konjunktionen. In einer disjunktiven Normalform sind nur drei boolesche Operatoren vor dem: und, oder und Negation. Außerdem kann die Negation nur als Teil von a . verwendet werden Atomformel Aussehen. Da ist auch ein Konjunktive Normalform, eine Konjunktion von Disjunktionen.

Beispiele

Beispiele für Formeln in disjunktiver Normalform:

${displaystyle (Awedge B)Rinder (Bwedge D)}$

${displaystyle zB Pwedge Q}$

${displaystyle Rvee (Pwedge Q)vee (Qwedge zB P)}$

Die folgenden Formeln sind jedoch nicht in disjunktiver Normalform:

${Anzeigestil zB (Avee B)}$ (Negation ist als äußeres Bindeglied nicht erlaubt)

${displaystyle(Avee(Bwedge(CveeD)))}$ (eine Disjunktion steht in einer Konjunktion)

Erfüllbarkeit

Eintreten ist möglich Polynomzeit um zu prüfen, ob eine Formel in disjunktiver Normalform vorliegt erfüllbar ist. Der Algorithmus in Pseudocode:

isDNFSerfüllbar(Formel f):

für jedes zusammenhangslos dimf:

wennd enthält keine komplementären Literale:

true zurückgeben

falsch zurückgeben

Eine Formel in disjunktiver Normalform ist nämlich erfüllbar, wenn mindestens eine ihrer Disjunkten erfüllbar ist; jede dieser Disjunkte ist eine Konjunktion von Literale. Eine Konjunktion von Literalen ist erfüllbar, wenn sie es nicht ist ergänzende Literale (beide p wenn seine Negation). Man kann also die Formel durchgehen und für jede der Disjunkten prüfen, ob sie komplementäre Literale enthält. Ist dies bei einer Disjunktion der Fall, so ist sie erfüllbar und damit auch die gesamte Formel erfüllbar.

Besonderheit

• EIN Disjunktion ist auch in disjunktiver Normalform; jede der Konjunktionen enthält genau 1 Literal.

Siehe auch

• Konjunktive Normalform