Disjunktivní normální forma

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Ve výrokové logice je formule v disjunktivní normální formě (DNF), pokud je ve tvaru disjunkcí mintermů, kde minterm definujeme jako konjunkce literálů (a je-li x výroková proměnná, tak jí určené literály jsou právě x a \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 mintermů s jedním literálem, resp. za konjunkci jednoho mintermu. 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 \vdash A ↔ K a \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[editovat | editovat zdroj]

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

\neg A \vee (B \wedge C) (negace smí stát jen před výrokovou proměnnou)
(A \wedge B) \vee (\neg B \wedge C \wedge \neg D) \vee (D \wedge \neg E)
A \vee B (tato formule je zároveň i v KNF)
A \wedge B (tato formule je zároveň i v KNF)

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

\neg (B \wedge C)
(A \vee B) \wedge C
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:

\neg B \vee \neg C
(A \wedge C) \vee (B \wedge C)
A \vee (B \wedge D) \vee (B \wedge E)

Související články[editovat | editovat zdroj]