Quelle est la différence entre la déduction naturelle et le calcul des séquents ?

La déduction naturelle opère avec des formules dans un contexte d'hypothèses et utilise des règles d'élimination, correspondant étroitement à la preuve informelle. Le calcul des séquents travaille avec des implications explicites et remplace les règles d'élimination par des règles d'introduction gauche, un format qui rend transparents l'élimination des coupures (cut-elimination) et la propriété de sous-formule.

Pourquoi la normalisation est-elle importante ?

Une preuve normale ne contient pas de détours et possède la propriété de sous-formule, de sorte que chaque formule qu'elle contient est une sous-formule de la conclusion ou des prémisses. Cela contraint la forme des preuves, produit des résultats de cohérence et, via la correspondance preuves-programmes (proofs-as-programs), correspond à l'évaluation d'un programme à une valeur.

Déduction naturelle et calcul des séquents

La déduction naturelle et le calcul des séquents sont les deux systèmes formels de type Gentzen qui représentent les preuves au moyen de règles d'introduction et d'élimination pour les connecteurs logiques, constituant le mécanisme fondamental de la théorie structurelle de la preuve.

Trouver un sujet avec PaperMindBientôtFind papers & topics

Tools & resources

Télécharger les diapositives

Learn & explore

VidéoBientôt

Definition

La déduction naturelle dérive des formules à partir d'hypothèses en utilisant des règles d'introduction et d'élimination qui reflètent le raisonnement informel, tandis que le calcul des séquents manipule des séquents, des assertions selon lesquelles une liste de formules en implique une autre, par des règles agissant à gauche et à droite d'une implication.

Scope

Ce sujet aborde les règles de la déduction naturelle avec leurs paires d'introduction et d'élimination, la structure du calcul des séquents avec ses règles gauches et droites et ses règles structurelles, la normalisation pour la déduction naturelle, la relation entre les deux systèmes, et leurs variantes intuitionnistes et classiques.

Core questions

Comment les règles d'introduction et d'élimination confèrent-elles un sens aux connecteurs logiques ?
Qu'est-ce qu'un séquent et en quoi ses règles diffèrent-elles de celles de la déduction naturelle ?
Comment la normalisation simplifie-t-elle les preuves en déduction naturelle ?
Comment les versions classiques et intuitionnistes de ces calculs sont-elles liées ?

Key theories

Règles d'introduction et d'élimination: Chaque connecteur est régi par des règles qui l'introduisent et des règles qui l'exploitent, et leur harmonie, selon laquelle l'élimination récupère exactement ce que l'introduction a apporté, exprime la signification du connecteur.
Théorème de normalisation: Prawitz a montré que les preuves en déduction naturelle peuvent être réduites à une forme normale exempte de détours où une introduction est immédiatement annulée par une élimination, l'analogue en déduction naturelle de l'élimination des coupures (cut-elimination).
Correspondance des deux calculs: La déduction naturelle et le calcul des séquents prouvent les mêmes théorèmes et peuvent être traduits l'un dans l'autre, les règles gauches des séquents correspondant aux règles d'élimination de la déduction naturelle.

Clinical relevance

Ces calculs sont les formats standards pour l'étude structurelle des preuves : la déduction naturelle sous-tend la théorie des types et les assistants de preuve via la correspondance preuves-programmes (proofs-as-programs correspondence), tandis que le calcul des séquents, avec sa propriété de sous-formule après l'élimination des coupures (cut-elimination), est la base de la recherche de preuves automatisée et des tableaux analytiques.

History

Gentzen a introduit la déduction naturelle et le calcul des séquents en 1934 et 1935, développant le calcul des séquents pour obtenir son théorème d'élimination des coupures (cut-elimination) après avoir jugé la déduction naturelle plus difficile à analyser. Prawitz a relancé la déduction naturelle en 1965 avec une étude approfondie de la normalisation, et ces systèmes sont devenus centraux dans les développements ultérieurs de la correspondance preuves-programmes (proofs-as-programs).

Key figures

Gerhard Gentzen
Dag Prawitz
Stanislaw Jaskowski
Jan von Plato

Seminal works

troelstra2000
prawitz1965
negri2001

Frequently asked questions

Quelle est la différence entre la déduction naturelle et le calcul des séquents ?: La déduction naturelle opère avec des formules dans un contexte d'hypothèses et utilise des règles d'élimination, correspondant étroitement à la preuve informelle. Le calcul des séquents travaille avec des implications explicites et remplace les règles d'élimination par des règles d'introduction gauche, un format qui rend transparents l'élimination des coupures (cut-elimination) et la propriété de sous-formule.
Pourquoi la normalisation est-elle importante ?: Une preuve normale ne contient pas de détours et possède la propriété de sous-formule, de sorte que chaque formule qu'elle contient est une sous-formule de la conclusion ou des prémisses. Cela contraint la forme des preuves, produit des résultats de cohérence et, via la correspondance preuves-programmes (proofs-as-programs), correspond à l'évaluation d'un programme à une valeur.