Konjunktivní normální forma

Ve výrokové logice je formule v konjunktivní normální formě (KNF nebo CNF z anglického conjunctive normal form), pokud je ve tvaru konjunkcí klauzulí, kde klauzuli definujeme jako disjunkci literálů (a je-li x {\displaystyle x} výroková proměnná, tak jí určené literály jsou právě x {\displaystyle x} a ¬ x {\displaystyle \neg x} ). Jako normální forma se používá v automatickém dokazování vět. Podobná kanonická forma se používá v teorii obvodů.

Každá konjunkce literálů a také každá disjunkce literálů je KNF, protože je můžeme považovat za konjunkci klauzulí s jedním literálem, resp. za disjunkci jedné klauzule. Podobně jako v disjunktivní normální formě (DNF), jediné logické spojky v KNF 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 KNF:

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

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

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

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

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

Související články

Pahýl
Pahýl
Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.