Negasjon normal form - Negation normal form

I matematisk logikk er en formel i negasjonsnormal form (NNF) hvis negasjonsoperatoren ( , ikke ) bare brukes på variabler og de eneste andre tillatte boolske operatørene er sammenheng ( , og ) og disjunktion ( , eller ). ${\ displaystyle \ lnot}$${\ displaystyle \ land}$${\ displaystyle \ lor}$

Negasjon normal form er ikke en kanonisk form: for eksempel, og er ekvivalent, og er begge i negasjon normal form. ${\ displaystyle a \ land (b \ lor \ lnot c)}$${\ displaystyle (a \ land b) \ lor (a \ land \ lnot c)}$

I klassisk logikk og mange modalogikker kan hver formel bringes inn i denne formen ved å erstatte implikasjoner og ekvivalenser med deres definisjoner, ved å bruke De Morgans lover for å skyve negasjonen innover og eliminere doble negasjoner. Denne prosessen kan vises med følgende omskrivingsregler ( Handbook of Automated Reasoning 1, s. 204):

${\ displaystyle {\ begin {align} 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 \ existerer xA & ~ \ til ~ \ forall x \ lnot A \\ \ lnot \ forall xA & ~ \ to ~ \ eksisterer x \ lnot A \ end {justert}}}$

[I disse reglene indikerer symbolet logisk implikasjon i formelen som blir skrevet om, og er omskrivingsoperasjonen.] ${\ displaystyle \ Rightarrow}$${\ displaystyle \ to}$

Transformasjon til negasjon normal form kan øke størrelsen på en formel bare lineært: antall forekomster av atomformler forblir den samme, det totale antallet forekomster av og er uendret, og antall forekomster av kan dobles. ${\ displaystyle \ land}$${\ displaystyle \ lor}$${\ displaystyle \ lnot}$

En formel i negasjon normalform kan settes i sterkere konjunktiv normalform eller disjunktiv normalform ved å bruke distribusjon . Gjentatt anvendelse av distributivitet kan eksponensielt øke størrelsen på en formel. I den klassiske proposisjonslogikken påvirker ikke transformasjon til negasjon normalform beregningsegenskapene: tilfredshetsproblemet fortsetter å være NP-komplett, og gyldighetsproblemet fortsetter å være co-NP-komplett. For formler i CNF er gyldighetsproblemet løst i polynomtid, og for formler i DNF er tilfredshetsproblemet løst i polynomtid.

Eksempler og moteksempler

Følgende formler er alle i normal form for negasjon:

${\ displaystyle {\ begin {justert} (A & \ vee B) \ wedge C \\ (A & \ wedge (\ lnot B \ vee C) \ wedge \ lnot C) \ vee D \\ A & \ vee \ lnot B \ \ A & \ wedge \ lnot B \ end {align}}}$

Det første eksemplet er også i konjunktiv normalform, og de to siste er i både konjunktiv normalform og disjunktiv normalform , men det andre eksemplet er i ingen av dem.

Følgende formler er ikke i normal form for negasjon:

${\ displaystyle {\ begin {align} A & \ Rightarrow B \\\ lnot (A & \ vee B) \\\ lnot (A & \ wedge B) \\\ lnot (A & \ vee \ lnot C) \ end {align} }}$

De tilsvarer imidlertid henholdsvis følgende formler i normal form for negasjon:

${\ displaystyle {\ begin {align} \ lnot A & \ vee B \\\ lnot A & \ wedge \ lnot B \\\ lnot A & \ vee \ lnot B \\\ lnot A & \ wedge C \ end {align}}}$

Referanser

• Alan JA Robinson og Andrei Voronkov, Håndbok for automatisert resonnement 1 : 203 ff (2001) ISBN  0444829490 .

Eksterne linker

• Java-applet for å konvertere logisk formel til Negation Normal Form, som viser lovene som brukes