Opløsningsregel

Opløsningsreglen er en inferensregel , der stiger op til metoden til at bevise teoremer gennem søgen efter modsigelser; bruges i propositionel logik og første-ordens logik . Opløsningsreglen, der anvendes sekventielt for en liste over opløsningsmidler, giver os mulighed for at besvare spørgsmålet om, hvorvidt der er en modsigelse i det oprindelige sæt af logiske udtryk. Opløsningsreglen blev foreslået i 1930 i Jacques Herbrands doktorafhandling for at bevise sætninger i førsteordens formelle systemer. Reglen blev udviklet af John Alan Robinson i 1965.

Derivabilitetssikrede algoritmer bygget på basis af denne metode bruges i mange kunstige intelligenssystemer og er også grundlaget for Prolog logik-programmeringssproget . $A \vdash B$

Propositionsregning

Lad og være to sætninger i sætningsregningen , og lad , og , hvor er en sætningsvariabel, og og er alle sætninger (især måske tomme eller kun bestående af én bogstavelig). $C_{1}$ $C_{2}$ $C_{1}=P\lor C'_{1}$ ${\displaystyle C_{2}=\likke P\lor C'_{2))$ $P$ $C'_1$ $C'_2$

Inferensregel

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

kaldet opløsningsreglen . [en]

Sætningerne C 1 og C 2 kaldes opløselige (eller overordnede ), sætningen er opløselige , og formlerne og er modordre . Generelt tages der to udtryk i en opløsningsregel, og der genereres et nyt udtryk, der indeholder alle bogstaverne i de to oprindelige udtryk, undtagen to gensidigt omvendte bogstaver. ${\displaystyle C'_{1}\lor C'_{2))$ $P$ $\ ikke P$

Opløsningsmetode

Beviset for sætninger er reduceret til at bevise, at en eller anden formel (sætningens hypotese) er en logisk konsekvens af et sæt formler (antagelser). Det vil sige, at selve sætningen kan formuleres som følger: "hvis sandt, så sandt og ". $G$ ${\displaystyle F_{1},\dots ,F_{k))$ ${\displaystyle F_{1},\dots ,F_{k))$ $G$

For at bevise, at en formel er en logisk konsekvens af et sæt formler , anvendes opløsningsmetoden som følger. Først kompileres et sæt formler . Derefter reduceres hver af disse formler til CNF (konjunktion af disjunkter), og konjunktionstegnene er streget over i de resulterende formler. Det viser sig en masse disjunkter . Og endelig outputtet af en tom klausul fra . Hvis den tomme klausul er afledt af , så er formlen en logisk konsekvens af formlerne . Hvis # ikke kan udledes af, så er det ikke en logisk konsekvens af formler . Denne metode til at bevise teoremer kaldes oplø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))$

Overvej et eksempel på en metode til bevis ved opløsning. Lad os sige, at vi har følgende udsagn:

"Æblet er rødt og velduftende." "Hvis æblet er rødt, så er æblet lækkert."

Lad os bevise udsagnet "æblet er velsmagende". Lad os introducere et sæt formler, der beskriver simple udsagn, der svarer til ovenstående udsagn. Lade

X_{1}

- Rødt æble

X_{2}

- "Aromatisk æble",

X_3

- Lækkert æble.

Så kan selve udsagnene skrives i form af komplekse formler:

X_{1}\land X_{2}

- "Æblet er rødt og velduftende."

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

"Hvis æblet er rødt, så er æblet velsmagende."

Så udtrykkes det udsagn, der skal bevises, med formlen . $X_3$

Så lad os bevise, at det er en logisk konsekvens af og . Først sammensætter vi et sæt formler, hvor negationen af udsagnet bliver bevist; vi får $X_3$ $(X_{1}\land X_{2})$ $(X_{1}\to X_{3})$

\{(X_{1}\land X_{2}),(X_{1}\højrepil X_{3}),\neg X_{3}\}.

Nu bringer vi alle formlerne til konjunktiv normalform og krydser konjunktionerne ud. Vi får følgende sæt klausuler:

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

Dernæst leder vi efter udledningen af en tom klausul. Vi anvender opløsningsreglen på første og tredje klausul:

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

Vi anvender opløsningsreglen på fjerde og femte led:

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

Således udledes en tom klausul, derfor er udtrykket med negationen af udsagnet tilbagevist, derfor er selve udsagnet bevist.

Metodens fuldstændighed og kompakthed

Opløsningsreglen har fuldstændighedsegenskaben i den forstand, at den altid kan bruges til at udlede fra en tom klausul #, hvis det oprindelige sæt klausuler er inkonsistent. $S$ $S$

Afledningsforholdet (på grund af afledningens endelighed) er kompakt: hvis , Så er der en endelig delmængde af , sådan at . Derfor skal vi først bevise, at umulighedsforholdet er kompakt. $S\vdash\#$ $S' \subseteq S$ $S'\vdash\#$

Lemma. Hvis hver endelig delmængde har et tilfredsstillende estimat, så er der et tilfredsstillende estimat for hele sættet af klausuler . $S' \subseteq S$ $S$

Bevis. Antag, at der er klausuler, der bruger et tælleligt sæt af propositionelle variabler . Lad os bygge et uendeligt binært træ, hvor to kanter dukker op fra hvert toppunkt i en højde , mærket med bogstaver og hhv. Vi fjerner fra dette træ disse hjørner, bogstaverne langs stien, som danner et skøn, der modsiger mindst én disjunkt . $S$ $p_{1},\ldots ,p_{k},\ldots$ $k$ $\neg p_{k+1}$ $p_{k+1}$ $S$

Overvej for hver en finit delmængde bestående af klausuler, der ikke indeholder variabler . Ved lemmaets betingelse er der et sådant estimat af variablerne (eller en vej til toppunktet på niveau med det beskårede træ), at det opfylder alle disjunktioner fra . Det betyder, at det afkortede træ er uendeligt (det vil sige, at det indeholder et uendeligt antal hjørner). Ved Koenigs uendelige sti-lemma indeholder et beskåret træ en uendelig gren. Denne gren svarer til en evaluering af alle variabler , som gør alle klausuler fra . Hvilket var det, der krævedes. $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$

Fuldstændighedsteorem for opløsningsmetoden for propositionel logik

Sætning . Et sæt sætninger S er inkonsekvent, hvis og kun hvis der er en gendrivelse i S (eller fra S ).

Bevis. Nødvendigheden (rigtigheden af opløsningsmetoden) er indlysende, da den tomme klausul ikke kan være sand under nogen evaluering. Lad os give et bevis for tilstrækkelighed. Ved kompakthedslemmaet er det tilstrækkeligt at begrænse os til tilfældet med et begrænset antal propositionelle variable. Vi udfører induktion på antallet af propositionelle variable , der forekommer i mindst én klausul fra . Lad fuldstændighedssætningen være sand for , lad os bevise dens sandhed for . Med andre ord vil vi vise, at fra ethvert modstridende sæt af klausuler, hvori propositionelle variabler forekommer , kan en tom klausul udledes. $n$ $S$ $n=k$ $n=k+1$ $S$ $p_{1},\ldots ,p_{k+1}$

Lad os vælge en af de propositionelle variable, for eksempel . Lad os konstruere to sæt klausuler og . I sættet sætter vi de klausuler , hvorfra det bogstavelige ikke forekommer , og fra hver sådan sætning fjerner vi det bogstavelige (hvis det forekommer der). På samme måde indeholder sættet resten af sætninger , der ikke indeholder det bogstavelige efter fjernelsen af det bogstavelige (hvis det forekommer 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ævdes, at hvert af sættene af klausuler og er inkonsistente, det vil sige, at det ikke har et skøn, der opfylder alle klausulerne samtidigt. Dette er sandt, fordi man ud fra et estimat , der opfylder alle klausulerne i mængden samtidigt, kan konstruere et estimat , der opfylder alle klausulerne i sættet samtidigt . At denne evaluering opfylder alle de sætninger, der er udeladt i overgangen fra til , er indlysende, fordi disse klausuler indeholder det bogstavelige . De resterende klausuler er opfyldt under den antagelse, at evalueringen opfylder alle klausulerne i sættet , og dermed alle de udvidede klausuler (ved at tilføje den kasserede bogstavelige ). På samme måde kan man ud fra et estimat , der opfylder alle klausulerne i mængden samtidigt, konstruere et estimat , der opfylder alle klausulerne i sættet 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$

Ved antagelsen om induktion, fra modstridende sæt af klausuler og (da kun propositionelle variabler forekommer i hver af dem ), er der konklusioner af en tom klausul. Hvis vi gendanner den udeladte literal for sæt-klausulerne i hver forekomst af output fra en tom klausul, så får vi output fra en klausul bestående af en enkelt literal . På samme måde opnår vi udledningen af en tom klausul fra et inkonsistent sæt , udledningen af en disjunkt bestående af en enkelt bogstavelig . Det er tilbage at anvende opløsningsreglen én gang for at 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}$

Prædikatregning

Lad C 1 og C 2 være to sætninger i prædikatregningen.

Inferensregel

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

kaldes en opløsningsregel i prædikatregning, hvis der i sætningerne C 1 og C 2 er forenede modbogstaver P 1 og P 2 , det vil sige , og , og atomformlerne P 1 og P 2 er forenet med den mest almindelige unifier . ${\displaystyle C_{1}=P_{1}\lor C'_{1))$ $C_2 = \likke P_2 \eller C'_2$ $\sigma$

I dette tilfælde er opløsningen af sætningerne C 1 og C 2 den sætning , der opnås fra sætningen ved at anvende foreneren . [2] $(C'_{1}\lor C'_{2})\sigma$ ${\displaystyle C'_{1}\lor C'_{2))$ $\sigma$

Men på grund af uafgøreligheden af logikken i førsteordens prædikater for et tilfredsstillende (konsistent) sæt klausuler, kan en procedure baseret på opløsningsprincippet køre på ubestemt tid. Typisk bruges opløsning i logisk programmering i forbindelse med direkte eller omvendt ræsonnement. Den direkte metode (fra præmisserne) ud fra præmisserne A, B udleder konklusionen B (modus ponens-reglen). Den største ulempe ved den direkte metode til ræsonnement er dens mangel på retning: gentagne anvendelser af metoden fører normalt til en kraftig stigning i mellemkonklusioner, der ikke er relateret til målkonklusionen.

Den omvendte metode (fra målet) er rettet: fra den ønskede konklusion B og de samme præmisser udleder den en ny delmålskonklusion A. Hvert trin i konklusionen i dette tilfælde er altid forbundet med det oprindeligt fastsatte mål.

En væsentlig mangel ved opløsningsprincippet ligger i dannelsen på hvert trin i udledningen af et sæt opløsningsmidler - nye klausuler, hvoraf de fleste viser sig at være overflødige. I denne henseende er der udviklet forskellige modifikationer af opløsningsprincippet, der bruger mere effektive søgestrategier og forskellige begrænsninger på formen af indledende klausuler.

Litteratur

Chen Ch., Li R. Kapitel 5. Opløsningsmetode // Matematisk logik og automatisk sætningsbevis = Chin-Liang Chang; Richard Char-Tung Lee (1973). Symbolsk logik og mekanisk sætningsprøve. Akademisk presse. - M . : "Nauka" , 1983. - S. 358.
Guts A. K. Kapitel 1.3. Opløsningsmetode // Matematisk logik og teori om algoritmer. - Omsk: Heritage. Dialog-Sibirien, 2003. - S. 108.
Nilson N. J. Principper for kunstig intelligens. - M. , 1985.
Mendelson E. Introduktion til matematisk logik. - M. , 1984.
Russell S., Norvig P. Artificial Intelligence: a Modern Approach = Artificial Intelligence: a Modern Approach. - M. : Williams, 2006.

Opløsningsregel

Propositionsregning

Opløsningsmetode

Prædikatregning

Links

Litteratur