Oppløsningsregel

I matematisk logikk , den oppløsning regelen eller prinsippet om oppløsning av Robinson er en regel av slutning logikk som generaliserer de Modus ponens . Denne regelen brukes hovedsakelig i automatiske proof-systemer , det er grunnlaget for det logiske programmeringsspråket Prolog .

I proposisjonslogikk

Modus ponens-regelen er skrevet og lyder: fra p og "p innebærer q", utleder jeg q. Vi kan omskrive implikasjonen "p innebærer q" som "p er falsk eller q er sant". Dermed er modus ponens-regelen skrevet . ${\ displaystyle {\ frac {p \ qquad p \ rightarrow q} {q}}}$ ${\ displaystyle {\ frac {p \ qquad (\ lnot p \ lor q)} {q}}}$

Oppløsningsregelen, den generaliserer modus ponens-regelen fordi den gjelder alle klausuler . En klausul er en formel som er en adskillelse (en "eller") av bokstavelige (en atom proposisjon eller en atom proposition foran en negasjon). For eksempel er en klausul med to bokstaver ("ikke p" og "q"). I proposisjonslogikk er resolusjonsregelen skrevet: ${\ displaystyle (\ lnot p \ lor q)}$

${\ displaystyle {\ frac {(p \ lor L_ {1} \ lor \ dots L_ {n}) \ qquad (\ lnot p \ lor M_ {1} \ lor \ dots \ lor M_ {k})} {( L_ {1} \ lor \ dots L_ {n} \ lor M_ {1} \ lor \ dots \ lor M_ {k})}}}$

Med andre ord, gitt to klausuler, og vi utleder . Den utledede formelen, dvs. kalles løseren på og . Selvfølgelig er regelapplikasjonen gitt til permutasjon nær bokstavene. ${\ displaystyle (p \ lor L_ {1} \ lor \ ldots \ lor L_ {n})}$ ${\ displaystyle (\ lnot p \ lor M_ {1} \ lor \ ldots \ lor M_ {k})}$ ${\ displaystyle (L_ {1} \ lor \ dots L_ {n} \ lor M_ {1} \ lor \ dots \ lor M_ {k})}$ ${\ displaystyle (L_ {1} \ lor \ dots L_ {n} \ lor M_ {1} \ lor \ dots \ lor M_ {k})}$ ${\ displaystyle (p \ lor L_ {1} \ lor \ ldots \ lor L_ {n})}$ ${\ displaystyle (\ lnot p \ lor M_ {1} \ lor \ ldots \ lor M_ {k})}$

Eksempler

For eksempel :

${\ displaystyle {\ frac {(a \ lor \ lnot b \ lor \ lnot c) \ qquad (b \ lor e \ lor \ lnot f)} {(a \ lor \ lnot c \ lor e \ lor \ lnot f)}}}$

${\ displaystyle {\ frac {p \ qquad \ lnot p} {\ bot}}}$ hvor betegner motsetningen (tom ledd). ${\ displaystyle {\ bot}}$

I predikatlogikk

I predikatlogikk er atomformler av formen hvor er et predikatsymbol, og det er begreper som består av konstanter, variabler og funksjonssymboler. Oppløsningsregelen i predikatlogikk er lik oppløsningsregelen i proposisjonslogikk, men atomformlene som deles av to ledd, må ikke være identiske, men ikke kan omformuleres . To atomformler er unifiserbare hvis det er en substitusjon av variablene med termer som gjør de to formlene identiske (se forening ). For eksempel : ${\ displaystyle P (t_ {1}, \ ldots, t_ {n})}$ $P$ $t_i$

${\ displaystyle {\ frac {P (a) \ qquad (\ lnot P (x) \ lor Q (x))} {Q (a)}}}$

er en anvendelse av oppløsningsregelen i predikatlogikk. Den lyder: fra "P (a)" og fra "(for alle x) ikke P (x) eller Q (x)", utleder jeg "Q (a)". Her er atomformelen og atomformelen unifiserbar med substitusjon . Mer generelt er regelen for å løse predikatlogikk: ${\ displaystyle P (a)}$ $P (x)$ ${\ displaystyle x \ mapsto a}$

${\ displaystyle {\ frac {(A \ lor L_ {1} \ lor \ dots L_ {n}) \ qquad (\ lnot B \ lor M_ {1} \ lor \ dots \ lor M_ {k})} {( L_ {1} [\ sigma] \ lor \ dots L_ {n} [\ sigma] \ lor M_ {1} [\ sigma] \ lor \ dots \ lor M_ {k} [\ sigma])}}}$

hvor er en hovedforener av atomformler og . $\ sigma$ $PÅ$ $B$

Oppløsningen kan utføres på to bokstaver hvis de forholder seg til identiske atomformler eller til uforenkelige formler .

For eksempel atomformler

${\ displaystyle P (x, a, y)}$ og hvor a og c er konstanter, ${\ displaystyle P (c, a, z)}$

er uforenlige med erstatning . På den andre siden ${\ displaystyle x \ til c, y \ til z}$

${\ displaystyle P (x, a, y)}$ og der a, b og c er konstanter, ${\ displaystyle P (c, b, z)}$

kan ikke forenes fordi konstantene ikke kan erstattes.

Eksempel

${\ displaystyle C_ {1} = \ lnot P (x) \ lor \ lnot Q (y) \ lor R (x, y)}$

${\ displaystyle C_ {2} = Q (a)}$

${\ displaystyle C_ {3} = P (b)}$

Erstatningen gjør det mulig å bruke oppløsningen på Q, mellom og , som produserer ${\ displaystyle y \ to a}$ $C_1$ $C_2$

${\ displaystyle C_ {R} = \ lnot P (x) \ l R (x, a)}$

Erstatningen gjør det mulig å bruke oppløsningen på P, mellom og å produsere ${\ displaystyle x \ to b}$ $C_ {3}$ $C_R$

${\ displaystyle C_ {S} = R (b, a)}$

Løsning og bevis ved tilbakevisning

Generelt brukes oppløsningsprinsippet for å utføre bevis ved motbevisning. For å bevise at formelen er en logisk konsekvens av formlene, viser vi at settet er inkonsekvent. $f$ ${\ displaystyle f_ {1}, \ ldots, f_ {n}}$ ${\ displaystyle \ {f_ {1}, \ ldots, f_ {n}, \ lnot f \}}$

I praksis er det nødvendig å begynne med å sette alle formlene i klausulær form, for at man må sette dem i pre-appendiksform (alle kvantifiseringsmidler i begynnelsen) og deretter skolemize dem .

For å vise at et sett med klausuler er inkonsekvent, er det nødvendig å lykkes med å generere den tomme klausulen ved å bruke oppløsningsregelen så mange ganger som nødvendig.

Eksempel

Vi vil vise at de tre formlene

${\ displaystyle \ forall x \ ((S (x) \ lor T (x)) \ til P (x))}$ ,
${\ displaystyle \ forall x \ (S (x) \ lor R (x))}$ ,
${\ displaystyle \ lnot R (a)}$

resulterer i formelen . ${\ displaystyle P (a)}$

Den første formelen tilsvarer og produserer derfor de to leddene ${\ displaystyle (\ forall x \ (S (x) \ to P (x)) \ land (\ forall x \ (T (x) \ to P (x))}$

${\ displaystyle C_ {1} = \ lnot S (x) \ l P (x)}$

${\ displaystyle C_ {2} = \ lnot T (x) \ l P (x)}$

Den andre formelen gir straks klausulen

${\ displaystyle C_ {3} = S (x) \ lor R (x)}$

og den tredje

${\ displaystyle C_ {4} = \ lnot R (a)}$ .

Negasjonen av ønsket konsekvens gir

${\ displaystyle C_ {5} = \ lnot P (a)}$

Ved vedtak om av og med en produserer $R$ $C_ {3}$ $C_ {4}$ $x \ til en$

${\ displaystyle C_ {6} = S (a)}$

Ved beslutning om de og vi produserer $S$ $C_1$ $C_ {6}$

${\ displaystyle C_ {7} = P (a)}$

Til slutt og gi den tomme klausulen. $C_ {5}$ $C_ {7}$

Regelhåndhevelsesstrategi

Prinsippet om at oppløsningen er fullført, hvis settet med klausuler som er vurdert er inkonsekvent, klarer vi alltid å generere den tomme klausulen. På den annen side, fordi konsistensproblemet (tilfredshet) ikke kan avgjøres i predikatlogikk, er det ingen metode for å fortelle oss hvilke oppløsninger vi skal gjennomføre og i hvilken rekkefølge å komme til den tomme klausulen.

Man kan lett finne eksempler der man "synker" ned i generasjonen av et uendelig antall klausuler uten å nå den tomme klausulen, mens man ville ha oppnådd den ved å ta de riktige valgene.

Forskjellige strategier er utviklet for å lede prosessen. Prolog- systemet er for eksempel basert på rekkefølgen som ledd er skrevet i og rekkefølgen på bokstavene i ledd. Andre systemer, som CyC , bruker en avskjæringsstrategi (avhengig av ressursene som forbrukes) for å unngå å generere uendelige grener.

Bevis på minimumslengder

Haken demonstrerte at enhver motbevisning av prinsippet om skuffer med n sokker (på engelsk, dette er pigeonhole-prinsippet ) er minst 2 n / 10 i lengde .

Eksterne linker

Øvelser for å manipulere oppløsningsregelen , et verktøy utviklet hos ENS Rennes

Referanser

(en) Robinson JA, en maskinorientert logikk basert på resolusjonsprinsippet , J. Assoc. Beregn. Mach. 12, 23-41, 1965.
(en) Kowalski, R., Logic for Problem Solving , Nord-Holland, Elsevier, 1979.
(fr) Benzaken, C., Formelle systemer: innføring i logikk og språkteori , Masson, Paris, 1991.
(en) Bundy, A., The Computer Modelling of Mathematical Reasoning , Academic Press, London, 1983.
(en) Huth, M., Ryan, M. Logic in Computer Science , Cambridge University Press, 2004.