Disjunktivní normální forma

Ve výrokové logice je formule v disjunktivní normální formě (DNF), pokud je ve tvaru disjunkcí P-termů, kde P-term definujeme jako konjunkce literálů (a je-li ${\displaystyle x}$ výroková proměnná, tak jí určené literály jsou právě ${\displaystyle x}$ a ${\displaystyle \neg x}$).

Každá konjunkce literálů a také každá disjunkce literálů je DNF, protože je můžeme považovat za disjunkci P-termů s jedním literálem, resp. za konjunkci jednoho P-termu. Podobně jako v konjunktivní normální formě (KNF), jediné logické spojky v DNF jsou logická spojka a, nebo a negace. Negace může být pouze součástí literálu, tzn. že negovat lze pouze výrokovou proměnnou.

Platí, že pro každou formuli A lze sestrojit ekvivalentní formule K a D (tedy ${\displaystyle \vdash }$ A ↔ K a ${\displaystyle \vdash }$ A ↔ D), kde K je v KNF a D je v DNF. Toto tvrzení lze dokázat indukcí podle složitosti formule užitím De Morganových zákonů a distributivity.

Příklady

Příklady formulí, které jsou v DNF:

${\displaystyle \neg A\vee (B\wedge C)}$ (negace smí stát jen před výrokovou proměnnou)

${\displaystyle (A\wedge B)\vee (\neg B\wedge C\wedge \neg D)\vee (D\wedge \neg E)}$

${\displaystyle A\vee B}$ (tato formule je zároveň i v KNF)

${\displaystyle A\wedge B}$ (tato formule je zároveň i v KNF)

Příklady formulí, které nejsou v DNF:

${\displaystyle \neg (B\wedge C)}$

${\displaystyle (A\vee B)\wedge C}$

${\displaystyle A\vee (B\wedge (D\vee E))}$

Výše uvedené formule lze ovšem do DNF převést, tedy sestrojit k nim ekvivalentní formule, které jsou v DNF:

${\displaystyle \neg B\vee \neg C}$

${\displaystyle (A\wedge C)\vee (B\wedge C)}$

${\displaystyle A\vee (B\wedge D)\vee (B\wedge E)}$

Související články

• Konjunktivní normální forma
• Logika