Ouvrir le menu principal

Règle d'introduction (logique)

Les règles d'introduction des connecteurs (disjonction, conjonction, implication, négation, etc.) sont des règles d'inférence que l'on trouve dans le calcul des séquents et la déduction naturelle. Elles jouent un rôle fondamental dans la description de ces systèmes, car elles permettent d'expliquer comment les connecteurs sont « introduits » dans le cours d'une démonstration. En dehors des règles structurelles, le calcul des séquents ne contient que des règles d'introduction et aucune règle d'élimination.

Les règles d'introduction ont été présentées pour la première fois par Gentzen en 1934 dans son article fondateur Recherches sur la déduction logique[1] sous le nom allemand « Einführung », qui veut précisément dire introduction.

Présentation des règlesModifier

Un séquent Γ ⊢ Δ est une expression logique qui se lit « du multiensemble Γ de formules on déduit le multiensemble Δ de formules ». rappelons qu'une règle d'inférence explique comment d'une famille de séquents (les prémisses) on peut déduire un séquent (la conclusion). Les règles d'introduction ont pour but de « complexifier » les formules de base, pour démontrer les propositions les plus générales.

Forme généraleModifier

Soit un connecteur ★, une règle d'introduction de ★ se présente sous la forme suivante. C'est en particulier la forme qu'elle a en (déduction naturelle):

 

Les points   représentent une ou plusieurs démonstrations de propositions et ces propositions sont, soit A, soit B et ne sont pas, a priori, la proposition A ★ B, qui doit être « introduite ».

Introduction à droiteModifier

En calcul des séquents, on peut introduire le nouveau connecteur, soit à droite, soit à gauche du symbole ⊢. Par exemple, étant donné un connecteur ★, la règle d'inférence d'introduction à droite de ★ a la forme

 

où les antécédents de la règle sont constitués de séquents qui contiennent les propositions de Γ et de Δ ainsi que la proposition A et la proposition B.

Introduction à gaucheModifier

En calcul des séquents, l'introduction à gauche se présente ainsi:

 

Exemples de règles d'introduction en déduction naturelleModifier

 

Ces règles ont toutes une justification par une proposition logique valide, ainsi l'introduction du ∧ se justifie par la proposition  , tandis que les introduction du ∨ se justifient par les propositions   et  .

Exemples de règles d'introduction en calcul des séquentsModifier

Pour la conjonctionModifier

 

Autrement dit la conjonction a une règle d'introduction à droite et deux règles d'introduction à gauche. La première règle pourrait se lire si « de Γ je déduis Δ ou A » et « de Γ je déduis Δ ou B » alors « de Γ je déduis Δ ou A v B ». La deuxième règle pourrait se lire si « de Γ ou A je déduis Δ » alors « de Γ ou A ∧ B je déduis Δ »

Pour la disjonctionModifier

 

La disjonction a deux règles d'introduction à droite et une règle d'introduction à gauche.

Pour l'implicationModifier

 

L'implication a une règle d'introduction à droite et une règle d'introduction à gauche.

Pour la négationModifier

   

Une proposition dans une partie du séquent correspond à la même proposition niée dans l'autre partie du séquent.

Règle d'introduction de quantificateursModifier

Au-delà des connecteurs, il y a aussi des règles d'introduction pour les quantificateurs. Ainsi, pour l'introduction du quantificateur universel on a la règle:

 

Voir aussiModifier

  • Jean-Yves Girard, Le Point aveugle, Tome I, chapitre 3 : « Les séquents classiques : LK », pp. 45-74. Éd. Hermann, mai 2006
  • René David, Karim Nour, Christophe Raffali, Introduction à la logique, théorie de la démonstration 2001, Dunod, (ISBN 2100067966), chap. 5
  • Stephen Cole Kleene, Mathematical logic, Dover, — Réimpression Dover reprint, 2001, (ISBN 0-486-42533-9). Traduction française, Logique mathématique, Armand Colin, 1971 ou Gabay 1987 (ISBN 2-87647-005-5).
  • René Lalement, Logique, réduction, résolution, Masson,

RéférencesModifier

  1. Gerhard Gentzen (trad. R. Feys et J. Ladrière), Recherches sur la déduction logique [« Untersuchungen über das logische schließen »], Presses Universitaires de France, , p. 4-5.
    Traduit et commenté