Logique Linéaire

Table des matières:

Logique Linéaire
Logique Linéaire

Vidéo: Logique Linéaire

Vidéo: Logique Linéaire
Vidéo: Jean-Yves Girard - Des règles de la logique à la logique des règles 2024, Mars
Anonim

Navigation d'entrée

  • Contenu de l'entrée
  • Bibliographie
  • Outils académiques
  • Aperçu du PDF des amis
  • Informations sur l'auteur et la citation
  • Retour au sommet

Logique linéaire

Publié pour la première fois le 6 septembre 2006; révision de fond ven 24 mai 2019

La logique linéaire est un raffinement de la logique classique et intuitionniste. Au lieu de mettre l'accent sur la vérité, comme dans la logique classique, ou la preuve, comme dans la logique intuitionniste, la logique linéaire met l'accent sur le rôle des formules en tant que ressources. Pour atteindre cet objectif, la logique linéaire ne permet pas aux règles structurelles habituelles de contraction et d'affaiblissement de s'appliquer à toutes les formules mais uniquement aux formules marquées avec certains modaux. La logique linéaire contient une négation totalement involutive tout en conservant une interprétation constructive forte. La logique linéaire fournit également de nouvelles perspectives sur la nature des preuves dans la logique classique et intuitionniste. Compte tenu de sa focalisation sur les ressources, la logique linéaire a trouvé de nombreuses applications en informatique.

  • 1. Introduction

    • 1.1 Un peu d'histoire
    • 1.2 Logique linéaire et informatique
  • 2. Systèmes de preuve

    • 2.1 Calcul séquentiel
    • 2.2 Recherche de preuves ciblée
    • 2.3 Filets de preuve
  • 3. Sémantique

    • 3.1 Sémantique de la prouvabilité
    • 3.2 Sémantique des preuves
  • 4. Complexité
  • 5. Impact de l'informatique

    • 5.1 Normalisation de la preuve
    • 5.2 Recherche de preuves
  • 6. Variations

    • 6.1 Différents traitements de la modalité
    • 6.2 Logique linéaire non commutative
    • 6.3 Traitement du comportement illimité
  • Bibliographie
  • Outils académiques
  • Autres ressources Internet
  • Entrées connexes

1. Introduction

1.1 Un peu d'histoire

La logique linéaire a été introduite par Jean-Yves Girard dans son ouvrage fondateur (Girard 1987). Si l'origine de la découverte de cette nouvelle logique vient d'une analyse sémantique des modèles du système F (ou polymorphe (lambda) - calcul), on peut voir tout le système de logique linéaire comme une tentative audacieuse de réconcilier le beauté et symétrie des systèmes pour la logique classique avec la recherche de preuves constructives qui ont conduit à la logique intuitionniste.

En effet, on pourrait présenter un fragment de logique linéaire, connu sous le nom de logique linéaire additive multiplicative (MALL), comme le résultat de deux observations simples.

  • Dans la présentation du calcul séquentiel de la logique classique, les règles des connecteurs «et» et «ou», ainsi que la règle de coupure et la règle d'implication peuvent être présentées de manière équivalente sous une forme additive (le contexte des prémisses est le même) ou une forme multiplicative (le contexte des prémisses est différent). Ces deux présentations sont équivalentes, en logique classique, du fait de la disponibilité de quelques règles dites «structurelles», à savoir la contraction et l'affaiblissement.
  • Les preuves non constructives que l'on peut effectuer en logique classique utilisent en fait, dans la présentation du calcul séquentiel, l'une ou l'autre de ces règles structurelles.

Donc, si nous voulons éliminer les preuves non constructives sans détruire la symétrie du calcul séquent, comme cela se fait dans la logique intuitionniste, nous pouvons essayer d'éliminer les règles de contraction et d'affaiblissement à la place. Ce faisant, on se retrouve avec deux versions différentes de chaque connectif: une version additive et une version multiplicative de conjonction et de disjonction. Ces différentes versions de la même connexion ne sont plus équivalentes. Ces nouveaux connecteurs sont & ("avec", additif et), (oplus) ("plus", additif ou, (otimes) ("tenseur", multiplicatif et) et (lpar) («Par», multiplicatif ou).

Cette duplication des connecteurs conduit en fait à une compréhension beaucoup plus claire du conflit entre logique classique et intuitionniste. Par exemple, la loi du milieu exclu ((A) ou non - (A)) est considérée comme valide dans le monde classique et absurde dans l'intuitionniste. Mais en logique linéaire, cette loi a deux lectures: la version additive ((A / oplus / neg A)) n'est pas prouvable et correspond à la lecture intuitionniste de la disjonction; la version multiplicative ((A / lpar / neg A)) est prouvable trivialement et correspond simplement à la tautologie ((A) implique (A)) qui est également parfaitement acceptable en logique intuitionniste.

Aussi, la propriété de disjonction, essentielle dans le constructivisme, est facilement établie pour la disjonction additive.

On trouve alors à l'intérieur de cette logique plus riche une manière de représenter à la fois les besoins de l'intuitionnisme et l'élégance de la logique classique: la négation est involutive, les suites sont symétriques et les connecteurs sont interdéfinissables. Comparez ces propriétés avec celles de la logique intuitionniste, où la négation n'est pas involutive, les suites ne sont pas symétriques et les connecteurs ne sont pas tous indéfinissables.

Remarquez cependant qu'une fois que l'on a éliminé la règle de contraction et d'affaiblissement, les formules ne se comportent plus comme des valeurs de vérité immuables: en effet, quand on a une preuve de (A / Rightarrow B) et une preuve de (A) en logique linéaire, en les composant nous les consommons réellement pour obtenir une preuve de (B), de sorte que (A / Rightarrow B) et (A) ne soient plus disponibles après la composition. Les formules logiques linéaires se comportent désormais davantage comme des ressources qui ne peuvent être utilisées qu'une seule fois.

Pour retrouver toute la puissance expressive de la logique intuitionniste et classique, il est alors nécessaire d'ajouter au fragment MALL deux modalités duales, généralement appelées exponentielles dans la littérature de logique linéaire. En particulier, l'exponentiel «bien sûr» (bang) permet d'appliquer la contraction et l'affaiblissement à la formule (bang B) dans le contexte séquentiel gauche tandis que l'exponentiel «pourquoi-pas» (quest) permet d'appliquer la contraction et l'affaiblissement à la formule (quest B) sur le contexte séquentiel de droite. Cela conduit à la logique linéaire propositionnelle complète et à une très belle connexion avec l'informatique.

Notez qu'en plus de MALL, il existe deux autres fragments largement utilisés de la logique linéaire: la logique linéaire multiplicative (MLL), qui est MALL sans les connecteurs additifs; et la logique linéaire exponentielle multiplicative (MELL), qui est la logique linéaire sans les connecteurs additifs.

Avant l'introduction de la logique linéaire en 1987, divers chercheurs avaient travaillé sur divers types de logiques sous-structurelles dans lesquelles toutes les règles structurelles de Gentzen (contraction, affaiblissement et échange) ne sont pas acceptées. Lambek a étudié un système de preuve de calcul séquentiel dans lequel aucune de ces règles structurelles n'était autorisée (Lambek 1958). D'autres exemples de telles logiques sont la logique pertinente (dans laquelle l'affaiblissement n'est pas accepté) (Avron 1988, Read 1988). et la logique affine (dans laquelle la contraction n'est pas acceptée) (Grishin 1981).

1.2 Logique linéaire et informatique

La théorie de la preuve se concentre sur les systèmes de preuve formels et de tels systèmes formels ont été développés pour le calcul intuitionniste des prédicats, le calcul classique des prédicats, l'arithmétique, les calculs d'ordre supérieur, entre autres. La logique intuitionniste et constructive a commencé lorsque les gens ont vu la possibilité de lire '(A / Rightarrow B)' comme 'si vous me donnez un (A), je vous donnerai un (B)', qui est un écart significatif par rapport à la lecture classique '(A) est faux ou (B) est vrai' '.

L'informatique, en revanche, se concentre sur les mécanismes de calcul: application de fonction, gestion des exceptions, invocation de méthode dans les langages orientés objet, affectation de variables et ensembles similaires de règles de construction de processus. Sauf que les mécanismes de ces processus doivent être explicités: une fonction de type (A / rightarrow B) donne un compte rendu formel de la façon de transformer un (A) en un (B).

A un moment donné, ces deux sens se sont rencontrés. HB Curry et W. Howard se sont rendu compte que l'ensemble des déductions intuitionnistes à implication uniquement était un langage fonctionnel de base appelé simplement (lambda) - calcul: le langage de programmation était une logique, la logique un langage de programmation. Cette réunion mémorable a été appelée «l'isomorphisme de Curry-Howard» (Howard 1980).

La logique linéaire fournit une autre torsion dans l'interprétation de l'implication '(A / Rightarrow B)': maintenant on peut la lire comme 'donnez-moi autant de (A) que je pourrais avoir besoin et je vous donnerai un (B) '. La notion de copie qui est si centrale dans l'idée de calcul est désormais intégrée à la logique.

Ce nouveau point de vue ouvre de nouvelles possibilités, notamment:

  • de nouvelles formules exprimant des propriétés opérationnelles raffinées comme 'donnez-moi (A) une fois et je vous donnerai (B)'. Les applications ici vont de la programmation logique raffinée où la capacité de la logique linéaire à représenter des états est mise à profit (Hodas & Miller, 1994), à l'analyse de la logique classique et de ses interprétations informatiques (Abramsky 1993), à la spécification des mécanismes d'exception dans langages de programmation (Miller, 1996), à l'analyse de linéarité (Wadler, 1991).
  • de nouvelles règles exprimant des contraintes sur l'utilisation des copies aboutissant à un fragment de logique linéaire pour les calculs polytime pour ne citer que l'application la plus spectaculaire (Baillot & Terui, 2004, Baillot 2015).
  • nouvelles manières de représenter les preuves (Abramsky & Jagadeesan, 1994, Girard 1987).

2. Systèmes de preuve

Les connecteurs propositionnels de base de la logique linéaire sont divisés en connecteurs additifs et multiplicatifs. La conjonction classique et son identité, (wedge) et (top), se divisent en l'additif (amp) (avec) et (top) (top) et le multiplicatif (otimes) (tenseur) et 1 (un). De même, la disjonction classique et son identité, (vee) et (bot), se divisent en l'additif (oplus) (oplus) et 0 (zéro) et le multiplicatif (lpar) (par) et (bot) (en bas). La négation est généralement traitée de deux manières dans les présentations d'une logique linéaire. La négation peut être considérée comme un connectif propositionnel primitif sans aucune restriction sur ses occurrences dans les formules. Puisque des dualités de De Morgan existent entre la négation et tous les connecteurs propositionnels, exponentiels et quantificateurs,il est également possible de traiter la négation comme un symbole spécial qui n'apparaît qu'aux formules atomiques. Les implications sont aussi couramment introduites dans la logique linéaire via des définitions: l'implication linéaire (B / limp C) peut être définie comme (B ^ { bot} lpar C), tandis que l'implication intuitionniste (B / Rightarrow C) peut être défini comme (bang B / limp C). Les opérateurs (bang) et (quest) sont appelés différemment modaux ou exponentiels. Le terme «exponentiel» est particulièrement approprié car, suivant la relation habituelle entre exponentiation, addition et multiplication, la logique linéaire prend en charge les équivalences (bang (B / amp C) equiv (bang B / otimes / bang C)) et (quest (B / oplus C) equiv (quest B / lpar / quest C)), ainsi que les versions 0-aire de ces équivalences, à savoir, ((bang / top / equiv 1)) et ((quest 0 / equiv / bot)). Ici,nous utilisons l'équivalence binaire (B / equiv C) pour signifier que la formule ((B / limp C) amp (C / limp B)) est dérivable en logique linéaire.

2.1 Calcul séquentiel

Un calcul séquentiel bilatéral pour la logique linéaire est présenté dans la figure ci-dessous. Notez ici que la négation est traitée comme s'il s'agissait d'un autre connectif logique: c'est-à-dire que ses occurrences dans les formules ne sont pas limitées et qu'il existe des règles d'introduction à gauche et à droite pour la négation. Les côtés gauche et droit des séquences sont un ensemble de formules multiples: ainsi, l'ordre des formules dans ces contextes n'a pas d'importance, mais leur multiplicité importe.

Règles d'identité) frac {} {B / vdash B} / textit {init} qquad / frac { Delta_1 / vdash B, / Gamma_1 / qquad / Delta_2, B / vdash / Gamma_2} { Delta_1, / Delta_2 / vdash / Gamma_1, / Gamma_2} / textit {cut}) Règles de négation) frac { Delta / vdash B, / Gamma} { Delta, B ^ { perp} vdash / Gamma} (cdot) ^ { perp} L / qquad / frac { Delta, B / vdash / Gamma} { Delta / vdash B ^ { perp}, / Gamma} (cdot) ^ { perp} R) Règles multiplicatives) frac { Delta / vdash / Gamma} { Delta, / one / vdash / Gamma} / one L / qquad / frac {} { vdash / one} / one R)) frac { } { bot / vdash} / bot L / qquad / frac { Delta / vdash / Gamma} { Delta / vdash / bot, / Gamma} / bot R)) frac { Delta, B_1, B_2 / vdash / Gamma} { Delta, B_1 / ot B_2 / vdash / Gamma} / ot L / qquad / frac { Delta_1 / vdash B, / Gamma_1 / qquad / Delta_2 / vdash C, / Gamma_2} { Delta_1, / Delta_2 / vdash B / ot C, / Gamma_ {1}, / Gamma_ {2}} / ot R)) frac { Delta_1, B / vdash / Gamma_1 / qquad / Delta_2, C / vdash / Gamma_2} { Delta_1, / Delta_2, B / lpar C / vdash / Gamma_1, / Gamma_2} / lpar L / qquad / frac { Delta / vdash B, C, / Gamma} { Delta / vdash B / lpar C, / Gamma} / lpar R) Règles additives) frac {} { Delta, / zero / vdash / Gamma} / zero L / qquad / frac {} { Delta / vdash / top, / Gamma} / top R)) frac { Delta, B_i / vdash / Gamma} { Delta, B_1 / amp B_2 / vdash / Gamma} { amp} L (i = 1,2) qquad / frac { Delta / vdash B, / Gamma / qquad / Delta / vdash C, / Gamma} { Delta / vdash B / amp C, / Gamma} { amp} R)) frac { Delta, B / vdash / Gamma / qquad / Delta, C / vdash / Gamma} { Delta, B / oplus C / vdash / Gamma} { oplus} L / qquad / frac { Delta / vdash B_i, / Gamma} { Delta / vdash B_1 / oplus B_2, / Gamma} { oplus} R (i = 1,2)) Règles de quantification) frac { Delta, B [t / x] vdash / Gamma} { Delta, / forall xB / vdash / Gamma} / forall L / qquad / frac { Delta / vdash B [y / x], / Gamma} { Delta / vdash / forall xB, / Gamma} / forall R)) frac { Delta / vdash B [t / x], / Gamma} { Delta / vdash / exists xB / Gamma} / existe R / qquad / frac { Delta, B [y / x] vdash / Gamma} { Delta, / existe xB / vdash / Gamma} / existe L,) Règles exponentielles) frac { Delta / vdash / Gamma} { Delta, / bang B / vdash / Gamma} / bang W / quad / frac { Delta, / bang B, / bang B / vdash / Gamma} { Delta, / bang B / vdash / Gamma} / bang C / quad / frac { Delta, B / vdash / Gamma} { Delta, / bang B / vdash / Gamma} / bang D)) frac { Delta / vdash / Gamma} { Delta / vdash / quest B, / Gamma} / quest W / quad / frac { Delta / vdash / quest B, / quest B, / Gamma} { Delta / vdash / quête B, / Gamma} / quest C / quad / frac { Delta / vdash B, / Gamma} { Delta / vdash / quest B, / Gamma} / quest D)) frac { bang / Delta / vdash B, / quest / Gamma} { bang / Delta / vdash / bang B, / quest / Gamma} / bang R / quad / frac { bang / Delta, B / vdash / quest / Gamma} { bang / Delta, / quest B / vdash / quest / Gamma} / quest L)

Notez que les règles d'affaiblissement et de contraction ne sont disponibles que pour les formules marquées de l'exponentiel (bang) à gauche ou (quest) à droite du séquent. Les règles (quest) R et (bang) L sont souvent appelées règles de «déréliction». Les règles (quest) L et (bang) R sont souvent appelées règles de «promotion» et sont les mêmes que les règles de possibilité et de nécessité trouvées dans la logique modale S4 de Kripke. La condition habituelle pour les règles d'introduction (forall) - droite et (existe) - gauche est supposée: en particulier, la variable (y) ne doit pas être libre dans les formules de la séquence inférieure de celles-ci règles d'inférence. La quantification est ici supposée être du premier ordre: les versions d'ordre supérieur de la logique linéaire peuvent être écrites selon des lignes standard.

La règle de coupe peut être éliminée et l'exhaustivité est toujours maintenue. Dually, la règle init peut également être éliminée, sauf pour les occurrences de init impliquant des formules atomiques.

2.2 Des preuves ciblées

Un important théorème de forme normale pour la structure des preuves sans coupure a été fourni par Andreoli (1992). Il a classé une formule non atomique comme asynchrone si son connecteur logique de niveau supérieur est (top), &, (bot, / lpar), (quest) ou (forall) ou synchrone si son connecteur logique de niveau supérieur est (0, / oplus, 1, / otimes), (bang), ou (existe).

Lorsque nous considérons la recherche de preuves comme un modèle de calcul, nous pouvons voir les formules dans une séquence comme des «agents» qui peuvent agir indépendamment ou de concert avec d'autres dans leur environnement. Ici, les actions de ces agents sont déterminées en lisant la règle d'introduction pour eux de bas en haut. Si une formule asynchrone apparaît à droite d'un séquent, elle peut évoluer sans affecter la prouvabilité et sans interagir avec son contexte, c'est-à-dire que la règle d'introduction correspondante est inversible. Par exemple, l'agent ((B / lpar C)) devient (en appliquant la (lpar) - règle d'introduction à droite) les deux agents (B) et (C) (travaillant maintenant en parallèle). De même, l'agent ((B / amp C)) donne (en appliquant la règle d'introduction & -right) deux mondes identiques différents (séquents) sauf que (B) est dans l'un de ces mondes et (C) est dans l'autre.

D'un autre côté, si nous considérons une formule synchrone comme un agent dont l'évolution est déterminée par la règle d'introduction à droite correspondante, alors il est possible qu'une séquence prouvable évolue vers une séquence non prouvable (par exemple, en appliquant le (oplus) règle d'introduction à droite). De plus, les instances de telles règles d'inférence dépendent des détails du contexte de la formule. Par exemple, le succès de la règle d'introduction 1-droite nécessite que le contexte environnant soit vide et le succès de la règle d'introduction (otimes) - droite dépend de la façon dont le contexte environnant de l'agent est divisé en deux contextes. Ainsi, l'évolution de tels agents dépend de la «synchronisation» avec d'autres parties du contexte.

Considérons maintenant une présentation de calcul séquentiel unilatéral de la logique linéaire où les seules règles d'introduction sont des règles d'introduction à droite. Compte tenu de la classification ci-dessus des connecteurs, il est possible de montrer que la recherche de preuves peut être structurée dans les phases suivantes sans perte d'exhaustivité. La phase asynchrone se produit si une formule asynchrone est présente dans la séquence. Dans cette phase, les règles d'introduction de droite sont appliquées dans n'importe quel ordre jusqu'à ce qu'il n'y ait plus de formules asynchrones. Dans la phase synchrone, une formule synchrone est sélectionnée et devient le «focus» de cette phase: c'est-à-dire que des règles d'introduction à droite lui sont appliquées et à toute sous-formule synchrone qu'elle pourrait générer.

La figure suivante illustre la logique linéaire du système de preuve de focalisation. Remarquez que les deux phases sont représentées par des flèches différentes: la flèche vers le haut désigne la phase asynchrone et la flèche vers le bas la phase synchrone. De plus, les séquences sont divisées en trois zones (où les zones sont séparées par un point-virgule ou une flèche vers le haut ou vers le bas). En particulier, à gauche de la flèche vers le haut et la flèche vers le bas se trouvent les deux zones. La zone écrite comme (Psi) désigne un ensemble de formules qui peuvent être utilisées un nombre illimité de fois dans la preuve de cette séquence. La zone écrite comme (Delta) désigne un multiset de formules restreintes comme dans MALL. La zone à droite d'une flèche vers le haut est également un ensemble multiple de formules tandis que la zone à droite d'une flèche vers le bas est une formule unique. Il est possible d'imposer un ordre arbitraire sur les formules à droite de la flèche vers le haut puisque l'introduction de formules asynchrones peut se faire dans n'importe quel ordre. Les atomes reçoivent une polarité et dans la figure ci-dessous, (A) représente des atomes positifs et la négation de (A) représente des atomes négatifs. Les preuves construites par ces règles d'inférence sont appelées preuves focalisées. Le résultat dans Andreoli 1992 est que les preuves focalisées sont complètes pour la logique linéaire.

Phase asynchrone) frac { Up { Psi} { Delta} {L}} { Up { Psi} { Delta} { bot, L}}) bot] qquad / frac { Up { Psi, F} { Delta} {L}} { Up { Psi} { Delta} { quest F, L}}) quest])) frac {} { Up { Psi} { Delta} { top, L}}) top] qquad / frac { Up { Psi} { Delta} {F [y / x], L}} { Up { Psi} { Delta} { forall xF, L}}) forall])) frac { Up { Psi} { Delta} {F_1, F_2, L}} { Up { Psi} { Delta} {F_1 / lpar F_2, L}}) lpar] qquad / frac { Up { Psi} { Delta} {F_1, L} quad / Up { Psi} { Delta} {F_2, L}} { Up { Psi} { Delta} {F_1 / amp F_2, L}}) amp])) frac { Up { Psi} { Delta, F} {L}} { Up { Psi} { Delta} {F, L}} [R / Uparrow] / text {à condition que $ F $ ne soit pas asynchrone}) Phase synchrone) frac {} { Down { Psi} { cdot} { one}}) one] qquad / frac { Down { Psi} { Delta_1} {F_1} quad / Down { Psi} { Delta_2} {F_2}} { Down { Psi} { Delta_1, / Delta_2} {F_1 / ot F_2}}) ot] qquad / frac { Up { Psi} { cdot} {F}} { Down { Psi} { cdot} { bang F}}) bang])) frac { Down { Psi} { Delta} {F_i}} { Down { Psi} { Delta} {F_1 / oplus F_2}}) oplus_i] qquad / frac { Down { Psi} { Delta} {F [t / x]}} { Down { Psi} { Delta} { exists xF}}) exists])) frac { Up { Psi} { Delta} {F}} { Down { Psi} { Delta} {F}} [R / Downarrow] / text {à condition que $ F $ soit asynchrone ou un atome}) Identity and Decide Rules) frac {} { Down { Psi} {A} {A ^ { perp}}} [I_1] qquad / frac {} { Down { Psi, A} { cdot} {A ^ { perp}}} [I_2] / text {où} A / text {est un atome})) frac { Down { Psi} { Delta} {F}} { Up { Psi} { Delta, F} { cdot}} [D_1] qquad / frac { Down { Psi} { Delta} {F}} { Up { Psi, F} { Delta} { cdot}} [D_2] / text {où} F / text {est une formule positive})

Des systèmes de preuve focalisés ont également été conçus pour les logiques classiques et intuitionnistes (Danos et al.1997; Laurent et al.2005; Liang & Miller 2009).

2.3 Filets de preuve

Les preuves présentées en utilisant le calcul séquentiel contiennent beaucoup de détails qui sont parfois inintéressants: considérez par exemple le nombre de façons inintéressantes de former une preuve de (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ { n-1} lpar A_n)) à partir d'une dérivation de (vdash / Gamma, A_1, A_2, / ldots, A_n). Ce fait désagréable découle de la nature séquentielle des preuves en calcul séquentiel: si nous voulons appliquer un ensemble (S) de (n) règles à différentes parties d'un séquent, nous ne pouvons pas les appliquer en une seule étape, même si ils n'interfèrent pas les uns avec les autres! Il faut les séquentialiser, c'est-à-dire choisir un ordre linéaire sur (S) et appliquer les règles en (n) étapes, selon cet ordre.

Une question naturelle se pose: «Y a-t-il une représentation des preuves qui fait abstraction de détails aussi inintéressants?». Une question similaire trouve une réponse positive dans le cas du calcul séquentiel intuitionniste au moyen de ce que l'on appelle la déduction naturelle, qui a, via la correspondance Curry-Howard, un lien fort avec le dispositif de calcul connu sous le nom de (lambda) - calcul.

Pour la logique linéaire, cette représentation succincte des preuves est donnée par des réseaux de preuves, des structures de type graphe qui jouissent de propriétés particulièrement bonnes pour le fragment MLL de la logique. La première étape vers cette représentation est de convertir tout le système de calcul séquentiel, en utilisant l'involutivité de la négation, en un système unilatéral, où les suites sont de la forme (vdash / Gamma). En conséquence, le nombre de règles est réduit car nous n'avons pas de règles d'introduction à gauche, mais nous gardons le même pouvoir expressif, car la prouvabilité reste la même.

À chaque preuve de calcul séquentiel dans MLL, on peut associer inductivement un réseau de preuve aux mêmes conclusions comme suit:

  • A une preuve réduite à la règle de l'axiome, on associe un lien axiome.

    Filet Axiom
    Filet Axiom
  • Pour une preuve obtenue en appliquant la règle de coupe à deux preuves, nous construisons d'abord inductivement les filets de preuve associés à ces deux preuves, puis nous les combinons à l'aide d'un lien de coupe.

    Coupe du filet
    Coupe du filet
  • Pour une preuve obtenue en appliquant la règle des tenseurs à deux preuves, nous construisons d'abord inductivement les réseaux de preuves associés à ces deux preuves, puis nous les combinons à l'aide d'un lien tenseur.

    Construction du filet de tension
    Construction du filet de tension
  • Pour une preuve obtenue en appliquant la règle par à une preuve, construisez d'abord inductivement le réseau de preuve associé à cette preuve, puis nous ajoutons un «lien par».

    Construction par filet
    Construction par filet

Tout cela peut être correctement formalisé à l'aide d'hypergraphes (les formules sont des nœuds et les «liens» sont des hyperedges orientés avec des hypothèses et des conclusions), et nous pouvons définir formellement comme un réseau de preuve un hypergraphe construit de manière inductive à partir d'un calcul séquentiel dérivé de MLL. Notez qu'il existe de nombreux hypergraphes qui ne sont pas des réseaux de preuve.

Maintenant, si vous regardez le réseau de preuve construit à partir des dérivations de (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ {n-1} lpar A_n)) obtenues à partir de (vdash / Gamma, A_1, A_2, / ldots, A_n), vous verrez que toute trace de l'ordre d'application des règles a disparu. En un sens, les réseaux de preuve sont une classe d'équivalence de dérivations séquentielles de calcul par rapport à l'ordre de dérivation des règles dont l'application commute.

Supposons que quelqu'un vienne maintenant à vous avec un énorme hypergraphe construit avec des liens axiome, cut, par et tensoriel, en prétendant qu'il s'agit en fait d'une représentation de la preuve d'un problème mathématique ouvert de longue date. Comment pouvez-vous vérifier qu'il s'agit en fait d'une représentation d'une preuve, et pas seulement d'une structure aléatoire?

Effectuer ce contrôle d'exactitude est un défi qui revient à reconstruire un historique de construction séquentiel de votre structure, correspondant à une dérivation en calcul séquentiel, et semble au premier abord un problème très complexe: le premier critère d'exactitude pour les réseaux de preuve MLL, appelé le «long voyage critère », et présent dans l'article original de Girard, est exponentiel, ainsi que le critère ACC (Acyclic connected) de Danos et Regnier (1989) trouvé plus tard. Néanmoins, il existe un critère beaucoup plus efficace, connu sous le nom de Contractibilité, dû à Danos et Regnier, qui a été plus récemment reformulé comme le critère d'analyse graphique élégant suivant par Guerrini, Martini et Masini: un hypergraphe est un réseau de preuve si et seulement si il se réduit au nœud singleton «net» via les règles de réduction de graphe suivantes

Analyse de graphes pour la reconnaissance de réseau de preuve MLL
Analyse de graphes pour la reconnaissance de réseau de preuve MLL

Effectuer cette vérification naïvement peut prendre un temps quadratique (chaque application d'une règle peut nécessiter une recherche complète du graphe pour trouver le redex, et nous devons effectuer autant d'étapes qu'il y a d'hyperliens dans le graphe). Des algorithmes de temps linéaire ont été donnés par Guerrini (2011) et par Murawski et Ong (2006).

Un autre style de critère de correction pour les réseaux de preuve MLL est donné par Retoré (2003) dans lequel un algorithme quadratique est donné pour MLL.

Sur les filets d'épreuve, on peut effectuer l'élimination des coupures de manière particulièrement propre: du fait de leur nature parallèle, les coupes peuvent être éliminées localement via deux règles de simplification:

  • Déplacement Axiom:

    Mouvement axiome
    Mouvement axiome
  • Mouvement multiplicatif:

    Mouvement multiplic-t.webp
    Mouvement multiplic-t.webp

Ce sont en fait des règles de calcul sur des réseaux de preuve, et les critères d'exactitude permettent de vérifier facilement qu'une telle règle préserve l'exactitude, et par conséquent, la réduction d'un filet de preuve provient toujours d'une preuve de calcul séquentiel du même séquent.

Par conséquent, l'élimination des coupures dans les réseaux de preuve MLL peut être effectuée en temps linéaire et donne un résultat d'élimination des coupures simple et élégant pour l'ensemble des MLL.

L'approche des filets de preuve peut être étendue à de plus grands sous-ensembles de logique linéaire, mais alors il est moins clair comment obtenir les mêmes résultats élégants que pour MLL: le système original proposé dans Girard 1987 fonctionne pour MELL, par exemple, en associant aux quatre exponentielle règle les constructions hypergraphiques suivantes:

  • Contraction

    Construction de contraction
    Construction de contraction
  • Affaiblissement

    Construction affaiblie
    Construction affaiblie
  • Abandon

    Construction d'abandon
    Construction d'abandon
  • Promotion, qui introduit la notion de «boîte», une marque de séquentialisation autour d'un morceau d'un réseau de preuves matérialisé dans les images des graphes par le rectangle dessiné autour du réseau de preuves de conclusions (A) et (quest / Gamma).

    Construction de promotion
    Construction de promotion

Bien que ces constructions et les réductions de graphes associées présentent une similitude frappante avec (lambda) - calcul avec substitutions explicites, comme l'ont remarqué pour la première fois Di Cosmo & Kesner (1997), elles sont trop similaires aux règles de calcul séquentiel correspondantes: l'effet de parallélisation si élégant pour MLL ne porte pas correctement ici, et les règles de réduction de graphe impliquent des boîtes et ne sont pas locales.

Pour retrouver un système satisfaisant, de nombreuses propositions ont été faites, à commencer par celle de Danos & Regnier (1995) mais nous voulons évoquer ici l'approche très élégante de Guerrini, Martini et Masini (Guerrini et al.2003), qui montre bien la connexion entre les systèmes de preuve à deux niveaux pour la logique modale, les réseaux de preuve appropriés pour MELL et la réduction optimale dans le (lambda) - calcul.

Un article récent de Heijltjes et Houston (2016) a montré qu'il ne peut y avoir de notion satisfaisante de filets de preuve pour MLL si les unités sont également autorisées.

Il est possible de fournir un traitement canonique des connecteurs additifs, même avec une quantification du premier ordre (Heijltjes et al.2018). Les réseaux de preuve pour les formules contenant à la fois des connecteurs multiplicatifs et additifs ont diverses présentations techniques, dont aucune ne semble canonique et satisfaisante. Leur traitement dans des systèmes de preuve de type proof-net est actuellement un sujet de recherche active. En particulier, voir (Hughes et van Glabbeek 2005) et (Hughes et Heijltjes 2016).

3. Sémantique

L'approche de la sémantique de la logique linéaire se fait généralement selon deux voies différentes. Premièrement, il existe diverses structures sémantiques disponibles qui peuvent être utilisées pour mapper des formules à des dénotations dans de telles structures. Cette approche peut être utilisée pour établir la justesse et l'exhaustivité de divers fragments de logique linéaire. Une approche sémantique plus nouvelle de la logique linéaire implique de donner directement une sémantique aux preuves. Nous décrivons brièvement ces deux approches et fournissons quelques liens vers la littérature.

3.1 Sémantique de la prouvabilité

Une approche pour tenter une sémantique solide et complète pour des fragments de logique linéaire associe à une formule l'ensemble de tous les contextes qui peuvent être utilisés pour prouver cette formule. Bien entendu, une telle collection peut avoir besoin d'être plus abstraite et de recevoir diverses propriétés de fermeture. La sémantique de phase de Girard (1987) fournit une telle sémantique: certaines utilisations de cette sémantique ont été faites en informatique pour fournir des contre-exemples et comme un outil qui peut aider à établir qu'un système concurrent donné ne peut pas évoluer vers un autre avec certaines propriétés (Fages et al.2001). De même, la sémantique de type Kripke a été fournie dans Allwein & Dunn 1993 et Hodas & Miller 1994. Les quantales, certains types de structures algébriques partiellement ordonnées, ont également été utilisées pour fournir des modèles sémantiques précoces pour des parties de la logique linéaire (Yetter 1990).

3.2 Sémantique des preuves

Dans l'analogie des formules-comme-types qui est si populaire et féconde en informatique théorique, un système logique est mis en correspondance avec un dispositif de calcul typé (comme typé (lambda) - calcul), en associant à chaque preuve de cette formule un programme ayant cette formule comme type. Par exemple, une preuve de la tautologie (A / Rightarrow A) correspond au programme fun ((x: A).x: A / rightarrow A), la fonction d'identité sur les objets de type (A). C'est pourquoi, dans les systèmes logiques constructifs (comme la logique intuitionniste et l'arithmétique), et dans la logique linéaire, tant d'importance est attachée aux preuves, au point que la construction et l'étude de modèles de preuves suscitent beaucoup plus d'attention que la construction et l'étude de modèles. de la prouvabilité: nous ne sommes pas satisfaits de savoir qu'une formule est prouvable,nous voulons vraiment connaître le contenu informatique de sa preuve.

De nombreux modèles de preuves logiques linéaires ont été proposés; nous considérons que, à ce jour, la construction la plus simple et la plus intuitive est celle basée sur la soi-disant «sémantique relationnelle» ou «sémantique à la Kripke», où les formules sont interprétées comme des multisets, les séquences unilatérales sont interprétées comme des tuples de multisets, et les preuves sont interprétées comme des relations sur l'interprétation des séquences. Si l'on veut donner une sémantique purement théorique des ensembles, sans recourir à des multisets, il est possible de le faire au moyen d'espaces de cohérence, ensembles dotés d'une relation de cohérence particulière, comme le montre à l'origine Girard 1987. Il existe des catégories théoriques intéressantes. modèles de logique linéaire, tels que les catégories * autonomes (Barr 1991) et les hypercohérences (Ehrhard 1993).

Une autre approche de la sémantique des preuves est donnée par la Géométrie de l'Interaction de Girard, qui nous permet d'obtenir une caractérisation entièrement algébrique des preuves. A chaque réseau de preuve, on peut associer une matrice de permutation partielle (sigma) correspondant aux liens coupés, et une matrice propre (M) expressions correspondantes construites à partir d'une certaine algèbre dynamique, qui décrivent les chemins possibles à l'intérieur du filet de preuve. Il est alors possible de décrire complètement le réseau de preuve via la formule d'exécution

) mathrm {EX} (sigma, M) = (1- / sigma ^ 2) left (sum_i M (sigma M) right) (1- / sigma ^ 2))

qui, dans le cas MLL, est un invariant du processus de normalisation. Une bonne connexion aux résultats provenant de alt="sep man icon" /> Comment citer cette entrée.

icône de l'homme Sep
icône de l'homme Sep

Prévisualisez la version PDF de cette entrée aux Amis de la société SEP.

icône inpho
icône inpho

Recherchez cette rubrique d'entrée sur le projet d'ontologie de la philosophie Internet (InPhO).

icône de papiers phil
icône de papiers phil

Bibliographie améliorée pour cette entrée chez PhilPapers, avec des liens vers sa base de données.

Autres ressources Internet

  • La bibliographie de la logique linéaire (jusqu'en 1998).
  • Vincent Danos et Roberto Di Cosmo. Le guide de la logique linéaire. Notes de cours. (1992).

Recommandé: