Upplösningsregel

Upplösningsregeln är en inferensregel , som går upp till metoden att bevisa satser genom sökandet efter motsägelser; används i propositionell logik och första ordningens logik . Resolutionsregeln, som tillämpas sekventiellt för en lista med resolventer, tillåter oss att svara på frågan om det finns en motsägelse i den ursprungliga uppsättningen av logiska uttryck. Resolutionsregeln föreslogs 1930 i Jacques Herbrands doktorsavhandling för att bevisa teorem i första ordningens formella system. Regeln utvecklades av John Alan Robinson 1965.

Derivabilitetssäkra algoritmer byggda på basis av denna metod används i många artificiella intelligenssystem och är också grunden för programmeringsspråket Prolog logik . $A \vdash B$

Propositionskalkyl

Låta och vara två meningar i satskalkylen , och låt , och , där är en satsvariabel, och och är alla meningar (i synnerhet kanske tomma eller består av endast en bokstavlig). $C_{1}$ $C_{2}$ $C_{1}=P\lor C'_{1}$ $C_{2}=\lnot P\lor C'_{2}$ $P$ $C'_1$ $C'_2$

Slutledningsregel

{\frac {C_{1},C_{2}}{C'_{1}\lor C'_{2}}}

kallad resolutionsregeln . [ett]

Meningarna C 1 och C 2 kallas resolvable (eller parent ), meningen är resolvent , och formlerna och är kontra bokstavliga. I allmänhet tas två uttryck i en upplösningsregel och ett nytt uttryck genereras som innehåller alla bokstaver i de två ursprungliga uttrycken, förutom två ömsesidigt omvända bokstaver. ${\displaystyle C'_{1}\lor C'_{2))$ $P$ $\linte P$

Upplösningsmetod

Beviset för satser reduceras till att bevisa att någon formel (satsens hypotes) är en logisk konsekvens av en uppsättning formler (antaganden). Det vill säga att själva satsen kan formuleras på följande sätt: "om sant, då sant och ". $G$ ${\displaystyle F_{1},\dots ,F_{k))$ ${\displaystyle F_{1},\dots ,F_{k))$ $G$

För att bevisa att en formel är en logisk konsekvens av en uppsättning formler tillämpas upplösningsmetoden enligt följande. Först kompileras en uppsättning formler . Sedan reduceras var och en av dessa formler till CNF (konjunktion av disjunkter) och konjunktionstecknen är överstrukna i de resulterande formlerna. Det visar sig en hel del disjunkter . Och slutligen utmatningen av en tom klausul från . Om den tomma satsen härleds från , är formeln en logisk konsekvens av formlerna . Om # inte kan härledas från, så är det inte en logisk konsekvens av formler . Denna metod för att bevisa teorem kallas upplösningsmetoden . $G$ ${\displaystyle F_{1},\dots ,F_{k))$ ${\displaystyle \{F_{1},\dots ,F_{k},\neg G\))$ $S$ $S$ $S$ $G$ ${\displaystyle F_{1},\dots ,F_{k))$ $S$ $G$ ${\displaystyle F_{1},\dots ,F_{k))$

Betrakta ett exempel på en proof by resolution-metod. Låt oss säga att vi har följande uttalanden:

"Äpplet är rött och doftande." "Om äpplet är rött, då är äpplet gott."

Låt oss bevisa påståendet "äpplet är gott". Låt oss introducera en uppsättning formler som beskriver enkla påståenden som motsvarar ovanstående påståenden. Låta

X_{1}

- Rött äpple

X_{2}

- "Aromatiskt äpple",

X_3

- Läckert äpple.

Sedan kan själva påståendena skrivas i form av komplexa formler:

X_{1}\land X_{2}

- "Äpplet är rött och doftande."

{\displaystyle X_{1}\rightarrow X_{3))

"Om äpplet är rött, då är äpplet gott."

Sedan uttrycks det påstående som ska bevisas med formeln . $X_3$

Så låt oss bevisa att det är en logisk konsekvens av och . Först sammanställer vi en uppsättning formler med negationen av påståendet som bevisas; vi får $X_3$ $(X_{1}\land X_{2})$ $(X_{1}\to X_{3})$

\{(X_{1}\land X_{2}),(X_{1}\högerpil X_{3}),\neg X_{3}\}.

Nu tar vi alla formlerna till konjunktiv normalform och stryker över konjunktionerna. Vi får följande uppsättning klausuler:

\{X_{1},X_{2},(\neg X_{1}\vee X_{3}),\neg X_{3}\}.

Därefter letar vi efter härledningen av en tom klausul. Vi tillämpar resolutionsregeln på första och tredje stycket:

\{X_{1},X_{2},(\neg X_{1}\vee X_{3}),\neg X_{3},X_{3}\}.

Vi tillämpar resolutionsregeln på fjärde och femte stycket:

\{X_{1},X_{2},(\neg X_{1}\vee X_{3}),\neg X_{3},X_{3},\#\}.

Således härleds en tom sats, därav uttrycket med negationen av påståendet vederläggs, därför bevisas själva påståendet.

Metodens fullständighet och kompakthet

Resolutionsregeln har fullständighetsegenskapen i den meningen att den alltid kan användas för att härleda från en tom sats # om den ursprungliga uppsättningen satser är inkonsekvent. $S$ $S$

Härledningsrelationen (på grund av härledningens ändlighet) är kompakt: om , Då finns det en ändlig delmängd av , så att . Därför måste vi först bevisa att omöjlighetsrelationen är kompakt. $S\vdash\#$ $S' \subseteq S$ $S'\vdash\#$

Lemma. Om varje finit delmängd har en tillfredsställande uppskattning, så finns det en tillfredsställande uppskattning för hela uppsättningen av klausuler . $S' \subseteq S$ $S$

Bevis. Antag att det finns satser som använder en räknebar uppsättning propositionsvariabler . Låt oss bygga ett oändligt binärt träd, där två kanter kommer ut från varje vertex på en höjd , märkta med bokstaver och respektive. Vi tar bort från detta träd dessa hörn, bokstavstexterna längs vägen till vilka bildar en uppskattning som motsäger åtminstone en disjunkt . $S$ $p_{1},\ldots ,p_{k},\ldots$ $k$ $\neg p_{k+1}$ $p_{k+1}$ $S$

För varje , överväg en finit delmängd som består av satser som inte innehåller variabler . Enligt villkoret för lemma finns det en sådan uppskattning av variablerna (eller en väg till vertex i nivå med det beskurna trädet) att den uppfyller alla disjunktioner från . Det betyder att det avkortade trädet är oändligt (det vill säga det innehåller ett oändligt antal hörn). Vid Koenigs oändliga väglemma innehåller ett beskuret träd en oändlig gren. Denna gren motsvarar en utvärdering av alla variabler , vilket gör alla satser från . Vilket var det som krävdes. $k$ $S_{k}\subseteq S$ $p_{k+1}, p_{k+2}, \ldots$ ${\displaystyle p_{1},\ldots ,p_{k))$ $k+1$ $S_k$ $p_{1},\ldots ,p_{k},\ldots$ $S$

Fullständighetsteorem för upplösningsmetoden för propositionell logik

Teorem . En uppsättning satser S är inkonsekvent om och endast om det finns ett vederläggande i S (eller från S ).

Bevis. Nödvändigheten (riktigheten av upplösningsmetoden) är uppenbar, eftersom den tomma klausulen inte kan vara sann under någon utvärdering. Låt oss ge ett bevis på tillräcklighet. Med kompakthetslemmat räcker det att begränsa oss till fallet med ett ändligt antal propositionella variabler. Vi utför induktion på antalet propositionsvariabler som förekommer i minst en sats från . Låt fullständighetssatsen vara sann för , låt oss bevisa dess sanning för . Med andra ord kommer vi att visa att från varje motsägelsefull uppsättning satser där propositionsvariabler förekommer kan en tom sats härledas. $n$ $S$ $n=k$ $n=k+1$ $S$ $p_{1},\ldots ,p_{k+1}$

Låt oss välja någon av propositionsvariablerna, till exempel . Låt oss konstruera två uppsättningar satser och . I uppsättningen lägger vi de satserna där bokstaven inte förekommer , och från varje sådan sats tar vi bort den bokstavliga (om den förekommer där). På samma sätt innehåller uppsättningen resten av satser som inte innehåller bokstaven efter borttagningen av bokstavlig (om den förekommer i dem). $k+1$ $p_{k+1}$ $S$ ${\displaystyle S_{k+1}^{+))$ $S_{k+1}^{-}$ ${\displaystyle S_{k+1}^{+))$ $S$ $\neg p_{k+1}$ $p_{k+1}$ $S_{k+1}^{-}$ $S$ $p_{k+1}$ $\neg p_{k+1}$

Det hävdas att var och en av uppsättningarna av klausuler och är inkonsekvent, det vill säga att den inte har en uppskattning som uppfyller alla klausuler samtidigt. Detta är sant eftersom man från en uppskattning som uppfyller alla satser i mängden samtidigt kan konstruera en uppskattning som uppfyller alla klausuler i mängden samtidigt . Att denna utvärdering uppfyller alla satser som utelämnats i övergången från till är uppenbart, eftersom dessa satser innehåller den bokstavliga . De återstående satserna är uppfyllda under antagandet att utvärderingen uppfyller alla klausuler i uppsättningen , och därmed alla de utökade satserna (genom att lägga till den bortkastade bokstavliga ). På liknande sätt, från en uppskattning som uppfyller alla klausuler i mängden samtidigt, kan man konstruera en uppskattning som uppfyller alla klausuler i mängden samtidigt . ${\displaystyle S_{k+1}^{+))$ $S_{k+1}^{-}$ ${\displaystyle \rho ^{+))$ ${\displaystyle S_{k+1}^{+))$ $\rho ^{+}\cup [\rho (p_{k+1})=0]$ $S$ $S$ ${\displaystyle S_{k+1}^{+))$ $\neg p_{k+1}$ $S$ ${\displaystyle \rho ^{+))$ ${\displaystyle S_{k+1}^{+))$ $p_{k+1}$ $\rho ^{-}$ $S_{k+1}^{-}$ $\rho ^{-}\cup [\rho (p_{k+1})=1]$ $S$

Genom antagandet om induktion, från motsägelsefulla uppsättningar av satser och (eftersom endast propositionsvariabler förekommer i var och en av dem ), finns det slutsatser av en tom sats. Om vi återställer den utelämnade literalen för setsatserna i varje förekomst av utdata från en tom sats, får vi utgången av en sats som består av en enda bokstavlig . På liknande sätt, från härledningen av en tom sats från en inkonsekvent mängd , får vi härledningen av en disjunkt som består av en enda bokstavlig . Det återstår att tillämpa resolutionsregeln en gång för att få en tom klausul. Q.E.D. ${\displaystyle S_{k+1}^{+))$ $S_{k+1}^{-}$ $k$ ${\displaystyle p_{1},\ldots ,p_{k))$ $p_{k+1}$ ${\displaystyle S_{k+1}^{+))$ $p_{k+1}$ $S_{k+1}^{-}$ $\neg p_{k+1}$

Predikatkalkyl

Låt C 1 och C 2 vara två meningar i predikatkalkylen.

Slutledningsregel

{\frac {C_{1},C_{2}}{(C'_{1}\lor C'_{2})\sigma }}R

kallas upplösningsregel i predikatkalkyl om det i meningarna C 1 och C 2 finns förenade motbokstaver P 1 och P 2 , det vill säga , och , och atomformlerna P 1 och P 2 är förenade av den vanligaste förenaren . $C_{1}=P_{1}\lor C'_{1}$ $C_2 = \linte P_2 \eller C'_2$ $\sigma$

I det här fallet är upplösningen av meningarna C 1 och C 2 meningen som erhålls från meningen genom att använda förenaren . [2] $(C'_{1}\lor C'_{2})\sigma$ ${\displaystyle C'_{1}\lor C'_{2))$ $\sigma$

Men på grund av att logiken i första ordningens predikat för en tillfredsställande (konsekvent) uppsättning klausuler är obestämd, kan en procedur baserad på upplösningsprincipen köras på obestämd tid. Vanligtvis används upplösning i logisk programmering i samband med direkta eller omvända resonemang. Den direkta metoden (från premisserna) från premisserna A, B härleder slutsatsen B (modus ponensregeln). Den största nackdelen med den direkta resonemangsmetoden är dess brist på riktning: upprepade tillämpningar av metoden leder vanligtvis till en kraftig ökning av mellanslutsatser som inte är relaterade till målslutsatsen.

Den omvända metoden (från målet) är riktad: från den önskade slutsatsen B och samma premisser härleder den en ny delmålsslutsats A. Varje steg i slutsatsen i detta fall är alltid associerat med det ursprungligen uppsatta målet.

En betydande brist i upplösningsprincipen ligger i bildandet vid varje steg av härledningen av en uppsättning resolvent - nya klausuler, av vilka de flesta visar sig vara överflödiga. I detta avseende har olika modifieringar av resolutionsprincipen utvecklats som använder effektivare sökstrategier och olika restriktioner för formen av initiala klausuler.

Länkar

↑ Chen Ch., Li R. Matematisk logik och automatisk satsbevisning , sid. 77.
↑ Chen Ch., Li R. Matematisk logik och automatisk satsbevisning , sid. 85.

Litteratur

Chen Ch., Li R. Kapitel 5. Upplösningsmetod // Matematisk logik och automatisk satsbevisande = Chin-Liang Chang; Richard Char-Tung Lee (1973). Symbolisk logik och mekanisk satsbevisning. Akademisk press. - M . : "Nauka" , 1983. - S. 358.
Guts A. K. Kapitel 1.3. Upplösningsmetod // Matematisk logik och algoritmteori. - Omsk: Arv. Dialog-Sibirien, 2003. - S. 108.
Nilson N. J. Principer för artificiell intelligens. - M. , 1985.
Mendelson E. Introduktion till matematisk logik. - M. , 1984.
Russell S., Norvig P. Artificial Intelligence: a Modern Approach = Artificial Intelligence: a Modern Approach. — M .: Williams, 2006.