In der boolean Logik ist eine abtrennende normale Form (DNF) eine Standardisierung (oder Normalisierung) von einer logischen Formel, die eine Trennung von verbindenden Klauseln ist. Als eine normale Form ist es im automatisierten Lehrsatz-Beweis nützlich. Wie man betrachtet, ist eine logische Formel in DNF, wenn, und nur wenn es eine Trennung von einer oder mehr Verbindungen von einem oder mehr Druckfehlern ist. Eine DNF Formel ist in der vollen abtrennenden normalen Form, wenn jede seiner Variablen genau einmal in jeder Klausel erscheint. Als in der verbindenden normalen Form (CNF) sind die einzigen Satzmaschinenbediener in DNF und, oder, und nicht. Der nicht Maschinenbediener kann nur als ein Teil eines Druckfehlers verwendet werden, was bedeutet, dass er nur einer Satzvariable vorangehen kann. Zum Beispiel sind alle folgenden Formeln in DNF:

::::

Jedoch sind die folgenden Formeln NICHT in DNF:

: — NICHT ist der äußerste Maschinenbediener

: — ODER wird innerhalb UND verschachtelt

Das Umwandeln einer Formel zu DNF ist mit verwendenden logischen Gleichwertigkeiten, wie die doppelte negative Beseitigung, die Gesetze von De Morgan und das verteilende Gesetz verbunden.

Alle logischen Formeln können in die abtrennende normale Form umgewandelt werden.

Jedoch in einigen Fällen kann die Konvertierung zu DNF zu einer Exponentialexplosion der Formel führen. Zum Beispiel, in DNF, haben logische Formeln der folgenden Form 2 Begriffe:

:

Jede besondere Funktion von Boolean kann durch eine und nur eine volle abtrennende normale Form, eine der zwei kanonischen Formen vertreten werden.

Der folgende ist eine formelle Grammatik für DNF:

1. disjunct  verbundener
2. disjunct  disjunct  verbundener
3. verbundener  wörtlicher
4. verbundener  (verbundener  Druckfehler)
5. wörtliche  Variable
6. wörtlicher  ¬ Variable

Wo Variable als jede Variable gedacht wird.

Siehe auch

Algebraische normale Form

• Boolean fungieren
• GeBoolean-schätzte Funktion
• Verbindende normale Form

Hornklausel

• Logischer Graph
• Satzlogik
• Quine-McCluskey Algorithmus
• Wahrheitstabelle

Links

• Java applet, um boolean Logikausdrücke zu CNF und DNF umzuwandeln, die Gesetze zeigend, hat verwendet