Negativní normální forma - Negation normal form

v matematická logika, vzorec je v negace normální forma pokud negace operátor (${ displaystyle lnot}$, ne) se použije pouze na proměnné a pouze na další povolené Booleovské operátory jsou spojení (${ displaystyle land}$, a) a disjunkce (${ displaystyle lor}$, nebo).

Normální forma negace není kanonická forma: například ${ Displaystyle a land (b lor lnot c)}$ a ${ Displaystyle (a land b) lor (a land lnot c)}$ jsou ekvivalentní a oba jsou v negační normální formě.

V klasické logice a mnoho modální logika, každý vzorec lze vnést do této formy nahrazením implikací a ekvivalencí jejich definicemi pomocí De Morganovy zákony tlačit negaci dovnitř a eliminovat dvojí negace. Tento proces lze reprezentovat pomocí následujícího přepsat pravidla (Příručka automatizovaného uvažování 1, s. 204):

${ displaystyle { begin {zarovnáno} A Rightarrow B ~ & to ~ lnot A lor B lnot (A lor B) ~ & to ~ lnot A land lnot B lnot (A land B) ~ & to ~ lnot A lor lnot B lnot lnot A ~ & to ~ A lnot existuje xA ~ & to ~ forall x lnot lnot forall xA ~ & to ~ existuje x lnot A end {zarovnáno}}}$

[V těchto pravidlech ${ displaystyle Rightarrow}$ symbol označuje logickou implikaci v přepisovaném vzorci a ${ displaystyle to}$ je operace přepisování.]

Transformace do normální formy negace může zvětšit velikost vzorce pouze lineárně: počet výskytů atomových vzorců zůstává stejný, celkový počet výskytů ${ displaystyle land}$ a ${ displaystyle lor}$ se nemění a počet výskytů ${ displaystyle lnot}$ se může zdvojnásobit.

Vzorec v negační normální formě lze vložit do silnějšího konjunktivní normální forma nebo disjunktivní normální forma aplikováním distribučnost. Opakované použití distributivity může exponenciálně zvětšit velikost vzorce. V klasické výrokové logice nemá transformace na normální formu negace vliv na výpočetní vlastnosti: problém uspokojivosti je i nadále NP-úplný a problém s platností je i nadále spolu-NP-úplný. U vzorců v CNF je problém platnosti řešitelný v polynomiálním čase a u vzorců v DNF je problém uspokojivosti řešitelný v polynomiálním čase.

Příklady a protiklady

Následující vzorce jsou v normální formě negace:

${ displaystyle (A vee B) klín C}$

${ displaystyle (A klín ( lnot B vee C) klín lnot C) vee D}$

${ displaystyle A vee lnot B}$

${ displaystyle A klín ne B}$

První příklad je také v konjunktivní normální forma a poslední dva jsou v obou konjunktivní normální forma a disjunktivní normální forma, ale druhý příklad není ani v jednom.

Následující vzorce nejsou v normální formě negace:

${ displaystyle A Rightarrow B}$

${ displaystyle lnot (A vee B)}$

${ displaystyle lnot (A klín B)}$

${ displaystyle lnot (A vee lnot C)}$

Jsou však příslušně ekvivalentní následujícím vzorcům v normální formě negace:

${ displaystyle lnot A vee B}$

${ displaystyle lnot A wedge lnot B}$

${ displaystyle lnot A vee lnot B}$

${ displaystyle lnot A klín C}$

Reference

• Alan J.A. Robinson a Andrej Voronkov, Příručka automatizovaného uvažování 1:203ff (2001) ISBN  0444829490.

externí odkazy

• Java applet pro převod logického vzorce na Negation Normal Form, zobrazující použité zákony