Konjunktiv normal form - Conjunctive normal form

I boolsk logik är en formel i konjunktiv normal form ( CNF ) eller klausulär normal form om det är en konjunktion av en eller flera klausuler , där en klausul är en disjunktion av bokstavar ; i övrigt är det en produkt av summor eller ett OCH av OR . Som en kanonisk normal form är den användbar vid automatiserad satsprovning och kretsteori .

Alla konjunktioner av bokstäver och alla sammanslagningar av bokstäver finns i CNF, eftersom de kan ses som konjunktioner av en-bokstavsklausuler respektive konjunktioner av en enda klausul. Som i den disjunktiva normala formen (DNF) är de enda propositionella anslutningarna en formel i CNF kan innehålla är och , eller , och inte . Operatorn inte kan bara användas som en del av en bokstav, vilket innebär att den bara kan föregå en propositional variabel eller en predikatsymbol .

I automatiserad teorem som bevisar används ofta begreppet " klausulär normalform " i en smalare mening, vilket betyder en särskild representation av en CNF -formel som en uppsättning uppsättningar bokstavar.

Exempel och icke-exempel

Alla följande formler i variablerna och är i konjunktiv normal form:

För tydlighetens skull är de disjunktiva klausulerna skrivna inom parentes ovan. I disjunktiv normal form med parenteserade konjunktivklausuler är det sista fallet detsamma, men det näst sista är . Konstanterna sanna och falska betecknas med den tomma konjunkten och en klausul som består av den tomma disjunktionen, men skrivs normalt uttryckligen.

Följande formler är inte i konjunktiv normal form:

  • , eftersom ett ELLER är kapslat inom ett NOT
  • , eftersom ett OCH är kapslat inom ett OR

Varje formel kan skrivas på motsvarande sätt som en formel i konjunktiv normalform. De tre icke-exemplen i CNF är:

Konvertering till CNF

Varje propositionell formel kan omvandlas till en ekvivalent formel som finns i CNF. Denna transformation bygger på regler om logiska ekvivalenser : eliminering av dubbel negation , De Morgans lagar och distributiv lag .

Eftersom alla propositionella formler kan konverteras till en ekvivalent formel i konjunktiv normal form, är bevis ofta baserade på antagandet att alla formler är CNF. Men i vissa fall kan denna omvandling till CNF leda till en exponentiell explosion av formeln. Till exempel, översätter följande icke-CNF-formel till CNF ger en formel med klausuler:

I synnerhet är den genererade formeln:

Denna formel innehåller klausuler; varje klausul innehåller antingen eller för varje .

Det finns transformationer till CNF som undviker en exponentiell ökning i storlek genom att bevara tillfredsställelse snarare än likvärdighet . Dessa omvandlingar garanteras endast att linjärt öka formelns storlek, men introducera nya variabler. Exempelvis kan ovanstående formel omvandlas till CNF genom att lägga till variabler enligt följande:

En tolkning uppfyller denna formel endast om minst en av de nya variablerna är sant. Om den här variabeln är så är båda och sanna också. Det betyder att varje modell som uppfyller denna formel också uppfyller den ursprungliga. Å andra sidan uppfyller endast några av modellerna med den ursprungliga formeln denna: eftersom de inte nämns i den ursprungliga formeln är deras värden irrelevanta för att tillfredsställa den, vilket inte är fallet i den sista formeln. Detta innebär att den ursprungliga formeln och resultatet av översättningen är likvärdiga men inte likvärdiga .

En alternativ översättning, Tseitin -transformationen , inkluderar också klausulerna . Med dessa klausuler innebär formeln ; denna formel anses ofta vara "definiera" för att vara ett namn för .

Första ordningens logik

I första ordningens logik kan konjunktiv normal form tas vidare för att ge den klausulära normala formen av en logisk formel, som sedan kan användas för att utföra första ordningens upplösning . I upplösningsbaserad, automatisk teorem-bevisning, en CNF-formel

, med bokstäver, representeras vanligtvis som en uppsättning uppsättningar
.

Se nedan för ett exempel.

Beräkningskomplexitet

En viktig uppsättning problem i beräkningskomplexitet innefattar att hitta tilldelningar till variablerna i en boolsk formel uttryckt i konjunktiv normalform, så att formeln är sann. Den k -SAT problem är problemet med att finna en tillfredsställande tilldelning till en boolesk formel uttryckt i CNF där varje disjunktion innehåller högst k variabler. 3-SAT är NP-komplett (som alla andra k- SAT-problem med k > 2) medan 2-SAT är känt för att ha lösningar under polynomtid . Som en konsekvens är uppgiften att omvandla en formel till en DNF , bevara tillfredsställelsen, NP-hård ; dually , omvandling till CNF, bevara giltigheten , är också NP-svårt; därför är ekvivalensbevarande omvandling till DNF eller CNF återigen NP-hård.

Typiska problem i detta fall innefattar formler i "3CNF": konjunktiv normalform med högst tre variabler per konjunkt. Exempel på sådana formler som påträffas i praktiken kan vara mycket stora, till exempel med 100 000 variabler och 1 000 000 konjunktioner.

En formel i CNF kan konverteras till en equisatisfiable formel i " k CNF" (för k ≥3) genom att ersätta varje konjunkt med mer än k variabler med två konjunkt och med Z en ny variabel, och upprepa så ofta som behövs.

Konvertering från första ordningens logik

För att konvertera första ordningens logik till CNF:

  1. Konvertera till negation normal form .
    1. Eliminera konsekvenser och likvärdigheter: byt upprepade gånger mot ; ersätt med . Så småningom kommer detta att eliminera alla förekomster av och .
    2. Flytta NOTs inåt genom att upprepade gånger tillämpa De Morgans lag . Specifikt, ersätt med ; ersätt med ; och ersätt med ; ersätt med ; med . Efter det kan a bara inträffa omedelbart före en predikatsymbol.
  2. Standardisera variabler
    1. För meningar som använder samma variabelnamn två gånger, ändra namnet på en av variablerna. Detta undviker förvirring senare när man släpper kvantifierare. Till exempel byter namn till .
  3. Skolemize uttalandet
    1. Flytta kvantifierare utåt: byt upprepade gånger mot ; ersätt med ; ersätt med ; ersätt med . Dessa ersättningar bevarar likvärdighet, eftersom det föregående steget för standardiserad standardisering säkerställde att det inte sker i . Efter dessa ersättningar kan en kvantifierare förekommer endast i den inledande prefixet formeln, men aldrig i en , eller .
    2. Upprepa upprepade gånger med , var är en ny -ary -funktionssymbol, en så kallad " Skolem -funktion ". Detta är det enda steget som bara bevarar tillfredsställelse snarare än likvärdighet. Det eliminerar alla existentiella kvantifierare.
  4. Släpp alla universella kvantifierare.
  5. Fördela ORs inåt över AND: ersätt upprepade gånger med .

Som ett exempel omvandlas formeln som säger "Alla som älskar alla djur, i sin tur älskade av någon" till CNF (och därefter till klausulform i sista raden) enligt följande (markerar ersättningsregel återlöser in ):

senast 1.1
senast 1.1
med 1.2
med 1.2
med 1.2
med 2
senast 3.1
senast 3.1
med 3.2
med 4
med 5
( klausulrepresentation )

Informellt sett kan Skolem -funktionen anses vara att ge den som är älskad, medan den ger det djur (om något) som inte älskar. Den 3: e sista raden underifrån lyder då som " älskar inte djuret , annars älskas det av " .

Den 2: a sista raden ovanifrån , är CNF.

Anteckningar

  1. ^ Peter B. Andrews, En introduktion till matematisk logik och typteori , 2013, ISBN  9401599343 , s. 48
  2. ^ a b Artificiell intelligens: En modern metod Arkiverad 2017-08-31 på Wayback Machine [1995 ...] Russell och Norvig
  3. ^ Tseitin (1968)
  4. ^ Jackson och Sheridan (2004)
  5. ^ eftersom ett sätt att kontrollera en CNF för tillfredsställelse är att konvertera den till en DNF , vars tillfredsställelse kan kontrolleras i linjär tid

Se även

Referenser

externa länkar