Naturlig fradrag

I matematisk logikk er naturlig deduksjon et formelt system der reglene for deduksjon fra bevis er nær naturlige måter å resonnere. Dette er et viktig trinn i bevisteoriens historie av flere grunner:

• I motsetning til systemer i Hilbert-stil basert på mer eller mindre ad hoc-lister over logiske aksiomer, er naturlig deduksjon basert på et systematisk symmetriprinsipp: for hver kontakt gir vi et par doble regler (introduksjon / eliminering);
• det førte til at Gentzen oppfant en annen veldig viktig formalisme i bevissteorien, enda mer “symmetrisk”: kalkulator av sekvenser  ;
• det tillot på 1960-tallet å identifisere den første forekomsten av Curry-Howard-isomorfismen .

Terminologien "naturlig deduksjon" ble foreslått av Gentzen med tanke på det uintuitive aspektet ved systems à la Hilbert .

Opprinnelsen til naturlig deduksjon

Det naturlige fradraget i sin nåværende form er et formelt system foreslått av Gerhard Gentzen i 1934.

Mange logikere, startende med Gottlob Frege og David Hilbert, men også Bertrand Russell og Alfred North Whitehead med deres Principia Mathematica , har utviklet logikk i en aksiomatisk form inspirert av den euklidiske metoden: logiske lover trekkes fra aksiomer i hovedsak å bruke modus ponens- regelen . Denne enkle metoden avslørte vanskeligheter knyttet til det faktum at resonnement under hypoteser, en vanlig praksis i matematikk, ikke er direkte representativ.

Gerhard Gentzen er den første som har utviklet formalismer som, ved delvis å forlate den euklidiske metoden, gir logikken tilbake karakteren av en naturlig vei, det vil si nærmere matematisk praksis. Gentzens hovedide var enkel: å erstatte de nødvendige, men unaturlige logiske aksiomene i Hilbert-stil-systemer med deduksjonsregler, slik som innføringen av pilen som formelt koder for "hypotesen" i løpet av en undersøkelse. På denne måten har Gentzen for første gang utviklet en veldig symmetrisk presentasjon av logikken der hver kobling er definert av et par doble regler: introduksjoner og elimineringer . Han utviklet også en formalisme der deduksjoner ikke er setningssekvenser, men trær (eller mer presist rettet asykliske grafer ). Denne metoden, som er veldig suggestiv for intuisjonen, har ført til at Gentzen har gjort noen store funn, men den undergraver den opprinnelige ideen, som var å gjengi naturlige former for resonnement. Fitch modifiserte Gentzens metode ved å introdusere fordypningsbasert notasjon for å representere trestrukturen til trekk. Denne representasjonen, som er både formell og mer naturlig, er imidlertid ikke den best egnede for å oppnå hovedresultatene av naturlig deduksjon som normalisering. Av denne grunn vil vi i denne artikkelen begrense oss til en presentasjon til Gentzen, den interesserte leseren kan henvise til artikkelen dedikert til stilen til Fitch .

På 1960-tallet fortsatte Dag Prawitz studien av naturlig deduksjon og demonstrerte en kutt eliminasjonssetning der .

Prinsippene for naturlig deduksjon

Regelkonsept

Naturlig fradrag er basert på slutningsregler som gjør det mulig å trekke setninger fra andre. For eksempel følgende regel, modus ponens, men som kalles eliminering av nedbøyningen i denne sammenhengen:

ss→qq{\ displaystyle {\ frac {p \ qquad p \ to q} {q}}}

tillater å utlede fra en demonstrasjon av og en demonstrasjon av . Formlene over linjen kalles premissene og formelen under linjen kalles konklusjonen . I eksemplet, og er premissene og er konklusjonen. q{\ displaystyle q}s{\ displaystyle p}s→q{\ displaystyle p \ til q}s{\ displaystyle p}s→q{\ displaystyle p \ til q}q{\ displaystyle q}

Begrepet bevis tre

Et bevis i naturlig fradrag er et prøvetre. Her er et prøvetre som trekker utsagnet om at bakken er glatt fra de tre hypotesene: (1) det regner , (2) hvis det regner er bakken våt og (3) hvis bakken er våt så er bakken glatt  :

det regnerdet regner→vått gulvvått gulvvått gulv→glatt gulvglatt gulv{\ displaystyle {\ frac {\ displaystyle {\ frac {{\ text {det regner}} \ qquad \ qquad {\ text {det regner}} \ til {\ text {våt bakke}}} {\ text {våt bakke }}} \ qquad \ qquad \ qquad {\ text {wet ground}} \ til {\ text {glatt bakken}}} {\ text {glatt bakken}}}}

Pilens eliminasjonsregel brukes der to ganger.

Hypotesekonsept

Naturlig deduksjon gjør resonnement under hypoteser. Et bevis på q under hypotesen p har formen:

⋮sq{\ displaystyle {\ frac {\ stackrel {\ displaystyle p} {\ vdots}} {q}}}

der vertikale ellipser representerer et tre for bevis på avslutning, og noen av bladene inkluderer hypotesen . q{\ displaystyle q}s{\ displaystyle p}

Konseptet med ulastet hypotese

Det er også regler der en hypotese blir lastet ut , dvs. hypotesen antas ikke lenger fra anvendelsen av regelen. For eksempel, fra et bevis på q under hypotesen p , kan vi konstruere et bevis på implikasjonen . Vi merker: s→q{\ displaystyle p \ til q}

q⋮[s]s→q{\ displaystyle {\ frac {\ stackrel {\ displaystyle [p]} {\ stackrel {\ vdots} {q}}} {p \ to q}}}

og parentesene betyr at hypotesen losses. Denne regelen kalt introduksjon av implikasjon er en internalisering av Hilbert-systemets deduksjonssats . [s]{\ displaystyle [p]}s{\ displaystyle p}

Begrepet introduksjonsregel og eliminasjonsregel

Regelen lyder: fra premiss p og premiss q konkluderer vi formelen ( p og q ). Det er en introduksjonsregel (her introduksjonsregelen til “og”) fordi koblingen “og” vises i konklusjonen. sqs∧q{\ displaystyle {\ frac {p \ qquad q} {p \ wedge q}}}s∧q{\ displaystyle p \ land q}

Regelen lyder: fra premissene konkluderer vi formelen p . Det er en eliminasjonsregel (her eliminasjonsregelen for "og") fordi koblingen "og" elimineres og ikke lenger er i konklusjonen. s∧qs{\ displaystyle {\ frac {p \ wedge q} {p}}}s∧q{\ displaystyle p \ land q}

Ulike presentasjoner av regler og demonstrasjoner

Det er flere presentasjoner av reglene og demonstrasjonene i naturlig fradrag.

• Den historiske presentasjonen “à la Prawitz” som et bevisstreet der hypotesene er på bladene; dette er den som brukes i denne artikkelen.

[s∧q]q(∧E)[s∧q]s(∧E)q∧s(∧Jeg)s∧q→q∧s(→Jeg){\ displaystyle {\ frac {\ displaystyle {\ frac {\ displaystyle {\ frac {[p \ wedge q]} {q}} {\ scriptstyle (\ wedge E)} \ qquad {\ frac {[p \ wedge q ]} {p}} {\ scriptstyle (\ wedge E)}} {q \ wedge p}} {\ scriptstyle (\ wedge I)}} {p \ wedge q \ rightarrow q \ wedge p}} {\ scriptstyle ( \ rightarrow I)}}

• En presentasjon der dommene er sekvenser av formen der de inneholder aktive hypoteser og er den demonstrerte formelen. Denne presentasjonen, selv om den er mindre intuitiv, er teknisk sett den mest egnede for å demonstrere egenskapene til naturlig deduksjon.Γ⊢φ{\ displaystyle \ Gamma \ vdash \ varphi}Γ{\ displaystyle \ Gamma}φ{\ displaystyle \ varphi}

s∧q⊢q(∧E)s∧q⊢s(∧E)s∧q⊢q∧s(∧Jeg)∅⊢s∧q→q∧s(→Jeg){\ displaystyle {\ frac {\ displaystyle {\ frac {\ displaystyle {\ frac {} {p \ land q \ vdash q}} {\ scriptstyle (\ wedge E)} \ qquad {\ frac {} {p \ land q \ vdash p}} {\ scriptstyle (\ wedge E)}} {p \ land q \ vdash q \ wedge p}} {\ scriptstyle (\ wedge I)}} {\ emptyset \ vdash p \ wedge q \ rightarrow q \ wedge p}} {\ scriptstyle (\ rightarrow I)}}

• Presentasjonen "à la Fitch" hvor en demonstrasjon hvor hver linje inneholder en nummerert dom. Vi trekker inn teksten hver gang vi legger inn en hypotese.

1 s∧q{\ displaystyle p \ land q} 2 s{\ displaystyle p} 3 q{\ displaystyle q} 4 q∧s{\ displaystyle q \ land p} 5 s∧q→q∧s{\ displaystyle p \ land q \ rightarrow q \ land p}

Naturlig deduksjon i proposisjonslogikk

Regler

Følgende tabell gir reglene for innføring og reglene for eliminering av kontakter →, ∧, ∨ og ⊥.

	Innledende regler	Avhendingsregler
og	(∧Jeg)sqs∧q{\ displaystyle (\ wedge \ mathrm {I}) \ quad {\ frac {p \ qquad q} {p \ wedge q}}}	(∧E)s∧qss∧qq{\ displaystyle (\ wedge \ mathrm {E}) \ quad {\ frac {p \ wedge q} {p}} \ qquad {\ frac {p \ wedge q} {q}}}
eller	(∨Jeg) ss∨q(∨Jeg) qs∨q{\ displaystyle {(\ vee \ mathrm {I})} ~ {\ frac {p} {p \ vee q}} \ qquad {(\ vee \ mathrm {I})} ~ {\ frac {q} {p \ vee q}} \ qquad}	(∨E) s∨q[s]⋮r[q]⋮rr{\ displaystyle {(\ vee \ mathrm {E})} ~ {\ frac {p \ vee q \ quad {\ begin {array} {c} [p] \\\ vdots \\ r \ end {array}} \ quad {\ begin {array} {c} [q] \\\ vdots \\ r \ end {array}}} {r}}}
involvert	(→Jeg)q⋮[s]s→q{\ displaystyle (\ to \ mathrm {I}) \ quad {\ frac {\ stackrel {\ displaystyle [p]} {\ stackrel {\ vdots} {q}}} {p \ to q}}}	(→E)ss→qq{\ displaystyle (\ to \ mathrm {E}) \ quad {\ frac {p \ qquad p \ to q} {q}}}
falsk	(⊥Jeg)s¬s⊥{\ displaystyle (\ bot \ mathrm {I}) \ quad {\ frac {p \ qquad \ lnot p} {\ bot}}}	(⊥E)⊥s{\ displaystyle (\ bot \ mathrm {E}) \ quad {\ frac {\ bot} {p}}}

Regelen om eliminering av ⊥ har det spesielle å innføre et forslag. Så ofte bruker vi betegnelsen ¬ p som en forkortelse av p → ⊥. Hvis vi har et bevis på p og et bevis på q , har vi et bevis på p ∧ q , dette er angitt av regelen (∧ I). Regelen (→ I) sier at hvis vi fra hypotesen p kan utlede q så kan vi utlede p → q , så blir hypotesen p fjernet fra settet med hypoteser, vi sier at den er losset . De to koblingseliminasjonsreglene connectectorur sier at hvis vi har et bevis på p ∧ q, har vi umiddelbart et bevis på p (første regel), og vi har også et bevis på q (andre regel). Regelen om eliminering av → er modus ponens kjent siden Aristoteles . Regelen (⊥ E) angir det faktum at fra det falske proposisjonen kan vi utlede ethvert annet forslag. Vi merker at regelen (⊥ E) er en eliminasjonsregel for kontakten ⊥.

Reduksjon til det absurde

(RPÅPÅ)⊥⋮[¬s]s{\ displaystyle \ qquad \ qquad (RAA) \ quad {\ frac {\ stackrel {\ displaystyle [\ neg p]} {\ stackrel {\ vdots} {\ perp}}} {p}}}

Regelen (RAA) er resonnementet fra det absurde , det er denne regelen som gir naturlig fradrag sin ikke- intuisjonistiske (dvs. "  klassiske  ") karakter. I dette tilfellet blir hypotesen ¬ p losset. Regelen (RAA) er ikke en eliminasjonsregel, langt mindre en introduksjonsregel, så vi ser at denne regelen skaper en skjevhet i innledningselimineringens regelmessighet av det naturlige intuisjonistiske deduksjonen, noe som gjør det veldig vanskelig å demonstrere normaliseringsteoremet  ; det er sannsynlig at det var dette som førte til at Gentzen utviklet kalkulatoren av sekvenser .

Artikkelen som beregner proposisjoner gir en variant av naturlig deduksjon med spesifikke, såkalte “naturlige” sekvenser, der hypotesene holdes som en kontekst og der hypotesene ikke trenger å lastes ut, men forsvinner fra konteksten.

Demonstrasjonseksempler

• Her er et bevis i naturlig deduksjon av formelen p ∧ q → q ∧ p  :

[s∧q]q(∧E)[s∧q]s(∧E)q∧s(∧Jeg)s∧q→q∧s(→Jeg){\ displaystyle {\ frac {\ displaystyle {\ frac {\ displaystyle {\ frac {[p \ wedge q]} {q}} {\ scriptstyle (\ wedge E)} \ qquad {\ frac {[p \ wedge q ]} {p}} {\ scriptstyle (\ wedge E)}} {q \ wedge p}} {\ scriptstyle (\ wedge I)}} {p \ wedge q \ rightarrow q \ wedge p}} {\ scriptstyle ( \ rightarrow I)}} Hypotesen p ∧ q lastes ut av regelen .→Jeg{\ displaystyle \ rightarrow I}

• Her er et bevis på naturlig deduksjon av formelen ((p → ⊥) → ⊥) → p  :

[(s→⊥)→⊥][s→⊥]⊥(→E)s(RPÅPÅ)((s→⊥)→⊥)→s(→Jeg){\ displaystyle {\ frac {\ displaystyle {\ frac {\ displaystyle {\ frac {[(p \ rightarrow \ bot) \ rightarrow \ bot] \ qquad [p \ rightarrow \ bot]} {\ bot}} {\ scriptstyle (\ rightarrow E)}} {p}} {\ scriptstyle (RAA)}} {((p \ rightarrow \ bot) \ rightarrow \ bot) \ rightarrow p}} {\ scriptstyle (\ rightarrow I)}} Hypotesen blir lettet av resonnementsregelen av det absurde (RAA). Hypotesen blir lastet av innledningsregelen (→ I).s→⊥{\ displaystyle p \ rightarrow \ bot}(s→⊥)→⊥{\ displaystyle (p \ rightarrow \ bot) \ rightarrow \ bot}

Naturlig fradrag i første ordens logikk

Når det gjelder syntaks, viser vi til artikkelen beregningen predikat . Notasjonen betegner formelen der alle de frie forekomster av variabelen i erstattes av forekomster av begrepet , etter mulig omdøping av forekomsten av relaterte variabler som vises gratis i . For eksempel, hvis er formelen , betegner ikke notasjonen formelen , men formelen (vi har passet på å gi nytt navn til variabelen for å unngå fenomenet kjent som variabel fangst). Følgende tabell gir reglene for naturlig deduksjon for de universelle og eksistensielle kvantifiseringsmengdene: F[t/x]{\ displaystyle F [t / x]}F{\ displaystyle F}x{\ displaystyle x}F{\ displaystyle F} t{\ displaystyle t}F{\ displaystyle F}t{\ displaystyle t}F{\ displaystyle F}∃y,y=x{\ displaystyle \ eksisterer y, y = x}P[y+1/x]{\ displaystyle P [y + 1 / x]}∃y,y=y+1{\ displaystyle \ eksisterer y, y = y + 1}∃y′,y′=y+1{\ displaystyle \ eksisterer y ', y' = y + 1}y{\ displaystyle y}y′{\ displaystyle y '}

	Innledende regler	Avhendingsregler
for alt	F∀xF(∀Jeg){\ displaystyle {\ frac {F} {\ forall xF}} {\ scriptstyle (\ forall I)}} forutsatt at variabelen ikke vises i noen av de ulastede forutsetningene. x{\ displaystyle x}	∀xFF[t/x](∀E){\ displaystyle {\ frac {\ forall xF} {F [t / x]}} {\ scriptstyle (\ forall E)}}
det finnes	F[t/x]∃xF(∃Jeg){\ displaystyle {\ frac {F [t / x]} {\ eksisterer xF}} {\ scriptstyle (\ eksisterer jeg)}}	∃xF[F]⋮qq(∃E){\ displaystyle {\ frac {\ existerer xF \ quad {\ begin {array} {c} [F] \\\ vdots \\ q \ end {array}}} {q}} {\ scriptstyle (\ exist E) }} forutsatt at variabelen x ikke vises i konklusjonen q eller i noen av de ulastede hypotesene; denne regelen avlaster hypotesenF{\ displaystyle F}

Legg merke til analogien som ikke er tilfeldig mellom reglene for kontakten og kvantisatoren , på den ene siden, og kontakten og kvantisereren, på den annen side. ∧{\ displaystyle \ wedge}∀{\ displaystyle \ forall}∨{\ displaystyle \ vee}∃{\ displaystyle \ eksisterer}

Kutt i naturlig fradrag

Symmetriene uttrykt gjennom intro / elimin-dualiteten tillater å definere det grunnleggende konseptet i teorien om bevis for kutt , som man også kaller redex i sammenheng med det naturlige deduksjonen. Et kutt er en rekke av en introduksjonsregel etterfulgt av en eliminasjonsregel som gjelder den samme kontakten, så det er ett kutt per kontakt.

Kuttene tilsvarer bruken av en teorem i løpet av et bevis; forestill deg for eksempel at vi søker å bevise en eiendom og at vi har en teorem som fastslår at vi vil bli redusert til å bevise eiendommen og ved å eliminere implikasjonen (modus ponens) for å utlede den etterspurte eiendommen . Formelt vil vi konstruere følgende trekk: q{\ displaystyle q}s→q{\ displaystyle p \ rightarrow q}s{\ displaystyle p}q{\ displaystyle q}

⋮s→q⋮sq{\ displaystyle {\ frac {\ displaystyle {\ frac {\ vdots} {\ displaystyle p \ rightarrow q}} \ quad {\ frac {\ vdots} {\ displaystyle p}}} {\ displaystyle q}}}

hvor til venstre er fradraget for teoremet og til høyre et fradrag fra proposisjonen . Nå hvis vi vurderer fradraget for teoremet, er det en god sjanse for at det er av formen: s{\ displaystyle p}

⋮[s]qs→q{\ displaystyle {\ frac {\ frac {\ stackrel {\ displaystyle [p]} {\ vdots}} {\ displaystyle q}} {\ displaystyle p \ rightarrow q}}}

Den mest naturlige måten å demonstrere det på er å stille hypotesen , utlede og konkludere ved hjelp av regelen om innføring av implikasjonen som avlaster hypotesen . Hvis vi kommer tilbake til fradraget ovenfra, kan vi se at det i dette tilfellet er av skjemaet: s→q{\ displaystyle p \ rightarrow q}s{\ displaystyle p}q{\ displaystyle q}s{\ displaystyle p}q{\ displaystyle q}

⋮[s]qs→q⋮sq{\ displaystyle {\ frac {{\ frac {\ frac {\ stackrel {\ displaystyle [p]} {\ vdots}} {\ displaystyle q}} {\ displaystyle p \ rightarrow q}} \ quad {\ frac {\ vdots} {\ displaystyle p}}} {\ displaystyle q}}}

som får et kutt til å vises på formelen . s→q{\ displaystyle p \ rightarrow q}

Klippet er derfor det mønsteret som er mest brukt når vi formaliserer matematisk resonnement, i en slik grad at Gentzen vil gjøre det til en egen regel for beregning av sekvenser . Det var i denne siste formalismen (og dette er utvilsomt grunnen til at han introduserte den) at han var i stand til å demonstrere sin teorem om eliminering av kutt, noe som etablerte muligheten for å assosiere med noe fradrag for en eiendom under et endelig sett med hypoteser , .. . ,, et normalt trekk , det vil si uten kutt, av den samme proposisjonen under de samme hypotesene. s{\ displaystyle p}s1{\ displaystyle p_ {1}}sk{\ displaystyle p_ {k}}

På grunn av tilstedeværelsen av den absurde reduksjonsregelen som, som vi har sett, verken er en eliminasjonsregel eller en introduksjonsregel, er denne setningen ikke lett å demonstrere ved naturlig deduksjon, det var imidlertid for intuisjonistisk logikk , det vil si å si i delsystemet uten det absurde, av Dag Prawitz . Den fradrag normaliseringsprosedyre definert ved Prawitz er ved opprinnelsen til mange utviklingen, spesielt oppdagelsen av den dype analogi mellom prøve trær av naturlig trekk og maskinskrevne lambda-betingelser som uttrykkes av bevis / program korrespondanse .

Andre logikker

Det finnes systemer for naturlig deduksjon for modalogikk .

Referanser

1. Howard, W., Formlene - as - typer begrepet konstruksjon , i Essays på Combinatory Logic, Lambda Kalkulus, og formalisme , Seldin, JP og Hindley, JR ed,. Academic Press (1980), s. 479--490.
2. (de) Gerhard Gentzen , “  Untersuchungen über das logische Schließen. I  ” , Mathematische Zeitschrift , vol.  39, n o  1,1 st desember 1935, s.  176–210 ( ISSN  1432-1823 , DOI  10.1007 / BF01201353 , leses online , åpnes 4. mars 2019 )
3. The fradrag teoremet seirer denne feilen, men på bekostning av en eksplosjon i størrelsen på fradragene
4. Vanligvis aksiomer og som tjener til å bevise deduksjonssatsen .K{\ displaystyle K}S{\ displaystyle S}
5. Spesielt sin Hauptsatz som resulterer i sammenheng med logikk.
6. (in) Dag Prawitz , Natural deduction: A proof-theoretical study , Mineola, New York, Dover Publications,2006( 1 st  ed. 1965), 113  s. ( ISBN  978-0-486-44655-4 , les online )
7. "  Logikkurs på ENS Lyon  " .

Se også

Bibliografi

• (in) Stanislaw Jaśkowski. Om reglene for antagelser i formell logikk , 1934.
• Gerhard Gentzen ( overs.  R. Feys og J. Ladrière), Forskning om logisk deduksjon [“Untersuchungen über das logische schließen”], Presses Universitaires de France,1955
• (av) Gerhard Gentzen. Untersuchungen über das logische Schliessen . Mathematische Zeitschrift, v. 39, 1934-35. (Engelsk oversettelse Investigations into Logical Deduction , i ME Szabo (red.), The Collected Works of Gerhard Gentzen , Amsterdam, Nord-Holland, 1969.)
• ( fr ) Dag Prawitz. Naturlig fradrag . Almqvist & Wiksell, Stockholm, 1965.
• (en) Dirk van Dalen, Logic and Structure , Springer Verlag, 1994.
• (en) Pelletier, Jeff, " A History of Natural Deduction and Elementary Logic Textbooks. "

Relaterte artikler

• Innledende regel (logikk)
• Eliminasjonsregel (logikk)

Ekstern lenke

• Michel Lévy Prouveur  : En online demonstrator av formler
• Naturlige deduksjonsøvelser , et verktøy utviklet hos ENS Rennes

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">