Règle d'introduction (logique)

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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üḧrung », qui veut précisément dire Introduction.

Présentation des règles[modifier | modifier le code]

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érale[modifier | modifier le code]

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 à droite[modifier | modifier le code]

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 à gauche[modifier | modifier le code]

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

Exemples de règles d'introduction en déduction naturelle[modifier | modifier le code]

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équents[modifier | modifier le code]

Pour la conjonction[modifier | modifier le code]

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 disjonction[modifier | modifier le code]

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

Pour l'implication[modifier | modifier le code]

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

Pour la négation[modifier | modifier le code]

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 quantificateurs[modifier | modifier le code]

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 aussi[modifier | modifier le code]

  • 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érences[modifier | modifier le code]

  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é