resoluutiosääntöjen

Resolutioreglerna är en samling regler inom formell logik och automatiserad resonemang som används för att bevisa att en mängd logiska klausuler är oförenlig. Principen bakom resolutioreglerna är att om en mängd klausuler är oförenlig, så kan man genom att upprepade gånger applicera resolutioregeln härleda en tom klausul, som representerar en motsägelse.

Resolutioregeln fungerar på disjunktioner av literaler. En literal är antingen ett predikat eller negationen av ett predikat. En klausul är en disjunktion av literaler, vilket innebär att minst en av literaler i klausulen måste vara sann för att klausulen ska vara sann. Till exempel är (A eller B) en klausul med literaler A och B.

Regeln säger att om vi har två klausuler som innehåller komplementära literaler, det vill säga en literal och dess negation (till exempel A i den ena klausulen och inte A i den andra), så kan vi härleda en ny klausul. Den nya klausulen bildas genom att ta alla literaler från båda de ursprungliga klausulerna, förutom de komplementära literaler som användes för att härleda den nya klausulen. Till exempel, från klausulerna (A eller B) och (inte A eller C) kan vi härleda klausulen (B eller C). Detta kallas en resolvent.

Genom att systematiskt tillämpa resolutioregeln på en uppsättning klausuler, och fortsätta att härleda nya resolventer, strävar man efter att nå en tom klausul (en klausul utan några literaler). Om den tomma klausulen kan härledas, bevisar det att den ursprungliga mängden klausuler är oförenlig. Detta är grunden för resolutionsmetoden inom automatiserad bevisföring.