Implication (logique)

La logique classique n'a que deux valeurs de vérité, « vrai » et « faux », que l'on représente par 1 et 0. Le connecteur « ⇒ » s'interprète alors par une application de l'ensemble {0,1}² sur {0,1}, soit une opération booléenne ayant la table de vérité suivante :

La proposition « p ⇒ q » (“p implique q”) est logiquement équivalente à « ¬p ∨ q » (“non(p) ou q”). On présente généralement cette propriété comme un théorème qui se démontre en remarquant que les tables de vérités de « p ⇒ q » et de « ¬p ∨ q » sont exactement les mêmes. Certains ouvrages de mathématique[5] utilisent aussi parfois cette propriété comme une définition de « p ⇒ q ». Il n'est pas rare que des objets mathématiques puissent avoir plusieurs définitions. Mais il y a généralement une définition plus classique ou plus conforme à l'histoire et la chronologie de l’apparition de ces objets dans le corpus correspondant, même si d'autres définitions sont parfois plus pratiques à manipuler. L'avantage de définir « p ⇒ q » = « ¬p ∨ q » est d'avoir une définition algébrique compacte, que l'on peut donc manipuler plus facilement dans des développements mathématiques qu'une table de vérité. Mais il est quand même préférable et plus conforme à la logique chronologique de définir cet opérateur binaire à partir de sa table de vérité tout comme ses homologues « ¬ » (non), « ∨ » (ou), et ∧ (et).

Ainsi, la proposition « p ⇒ q » est fausse exactement lorsque p est vraie et q fausse, raison pour laquelle elle peut aussi se lire « p seulement si q ». L’intérêt de cet opérateur binaire « ⇒ » est donc de ne pas accepter (Faux) dans le cas, et seulement celui-là, où l'on part d'une proposition P vraie et qu'on arrive à une proposition Q fausse. En effet, la plupart des démonstrations mathématiques partent d'hypothèses supposées vraies (y compris dans les raisonnements par l'absurde) et conduisent par des déductions successives à d'autres propositions qui permettent soit d'arriver à ce qu'on veut démontrer (CQFD), soit à une absurdité, ce qui prouve alors qu'une des hypothèses est fausse. Les trois autres cas sont autorisés (Vrai), même si certains peuvent paraitre contre-intuitifs. Mais cela est facile à comprendre, cf. les exemples ci-dessous. Il y a donc bien un lien entre cette opérateur binaire « ⇒ » en logique classique, et celui qu'on utilise dans le cadre de règles de déduction des développements mathématiques. Exemple :

• 2=2 ⇒ 2*0=2*0 : (exemple de Vrai ⇒ Vrai), cette implication est valide (Vraie) car on a le droit de multiplier les 2 membres par 0

• ${\displaystyle 2^{2}}$=${\displaystyle (-2)^{2}}$ ⇒ 2=-2 : (exemple de Vrai ⇒ Faux ), cette implication est invalide (Fausse) car en prenant la racine on doit écrire +/-

• 2=1 ⇒ 2*0=1*0 : (exemple de Faux ⇒ Vrai), cette implication est valide (Vraie) car on a le droit de multiplier les 2 membres par 0

• 2=1 ⇒ 2+1=1+1 : (exemple de Faux ⇒ Faux ), cette implication est valide (Vraie) car on a le droit d'ajouter 1 aux 2 membres

Le connecteur « implique » a donc une propriété qui le différencie d'un « donc » intuitif : d'après la table de vérité ci-dessus, si une proposition p est fausse, alors elle implique n'importe quelle autre proposition q, vraie ou fausse. Dans les exemples 3 et 4 ci-dessus on voit bien que des manipulations mathématiques licites (l'opérateur binaire « implique » est vrai, ainsi que la règle de déduction mathématique) conduit d'une proposition p fausse (2=1) à une proposition q vraie (0=0) ou fausse (3=2).

Les formules suivantes, constituées seulement de l'implication et de littéraux, sont des tautologies [cori_lascar_1 1] :

p ⇒ p

p a toujours la même valeur de vérité que p, donc cette implication est correcte. Elle est liée à la réflexivité de la déduction en logique classique.

p ⇒ (q ⇒ p)

Si p est vrai, q⇒ p est vrai aussi (c’est un des dits paradoxes de l'implication matérielle (en).)

(p ⇒ q) ⇒ ((q ⇒ r ) ⇒ (p ⇒ r ))

Cette formule est liée à la transitivité de la relation de déduction ; elle est équivalente à la tautologie [(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r ) par exportation (en).

(p ⇒ q) ⇒ (((p ⇒ r ) ⇒ q) ⇒ q)

Cette formule est une formulation sous forme purement implicative du fait qu’en logique des prédicats si p ⇒ q et si ¬p ⇒ q alors q est vraie dans tous les cas.

(¬p ⇒ p) ⇒ p

Cette tautologie conduit (par modus ponens) au raisonnement par l’absurde en logique classique.

¬p ⇒ (p ⇒ q)

Cette tautologie conduit (toujours par modus ponens) au principe d’explosion.

« p ⇒ q » équivaut à « ¬(p ∧ ¬q) » ainsi qu'à « (¬p) ∨ q ».

Ces deux formules pourraient être prises comme des définitions de l'implication. Essentiellement elles décrivent la table de vérité, la première donne le seul cas où « p ⇒ q » est fausse, la seconde les cas où « p ⇒ q » est vraie.

« p ⇒ q » équivaut à « ¬q ⇒ ¬p ».

Ces deux formules sont dites contraposées.

« p ⇒ (q ∧ r ) » équivaut à « (p ⇒ q) ∧ (p ⇒ r ) » et « p ⇒ (q ∨ r ) » à « (p ⇒ q) ∨ (p ⇒ r ) ».

Distributivité à gauche de l’implication par rapport à la conjonction et à la disjonction

« (p ∧ q) ⇒ r » équivaut à « (p ⇒ r ) ∨ (q ⇒ r ) » et « (p ∨ q) ⇒ r » à « (p ⇒ r ) ∧ (q ⇒ r ) ».

En revanche elle n'est distributive à droite ni par rapport à la conjonction ni par rapport à la disjonction : si le « ⇒ » est à droite, dans l'expression développée le « ∧ » se transforme en « ∨ » et vice-versa [cori_lascar_1 2].

Non associativité.

L'implication n'est pas associative, car « (p ⇒ q) ⇒ r » et « p ⇒ (q ⇒ r ) » ne prennent pas les mêmes valeurs pour toutes les distributions de valeurs de vérité, on s'en convaincra en donnant la valeur 0 à « p » et à « r » : la première expression vaut 0 et la seconde vaut 1.

L'implication (correspondant au « si …, alors … »), qui est un connecteur, se distingue de la relation de déduction (marquée par exemple par le mot « donc »). Cependant, le connecteur implication et la relation de déduction sont étroitement liées par les deux règles suivantes :

• Le modus ponens est la règle de déduction qui indique comment s'utilise une implication dans une démonstration ; elle s'énonce ainsi : de p et de p ⇒ q on déduit q[cori_lascar_1 3] ;
• Le lemme de déduction indique comment l'on démontre une implication : si de p on déduit q, alors on en déduit p ⇒ q.

Ces règles sont les deux règles fondamentales qui gouvernent l'implication. Adaptées à la déduction naturelle (il faut les préciser en indiquant en particulier le contexte des hypothèses), elles deviennent règle d’élimination (modus ponens) et règle d'introduction (lemme de déduction) de l'implication[6].

Ces deux règles sont suffisantes pour l'implication en logique intuitionniste.

En logique classique, il faut ajouter une forme de raisonnement par l'absurde. Par exemple il suffit d'ajouter comme axiome logique la loi de Peirce ((p ⇒ q) ⇒ p) ⇒ p, qui est purement implicationnelle.

Dans le cadre de l'interprétation de Brouwer-Heyting-Kolmogorov, qui est une interprétation en matière de preuves, une preuve de A ⇒ B est vue comme un procédé, une fonction en un sens effectif, qui transforme une preuve de A en une preuve de B. La réalisabilité est une contrepartie formelle de cette sémantique informelle.

En sémantique de Kripke, qui est une sémantique traditionnelle en matière de mondes possibles, avec une relation d'accessibilité qui dans le cas de la logique intuitionniste est sans cycle, on a A ⇒ B dans le monde m quand, à chaque fois que l'on a A dans un monde accessible à partir de m, on a aussi B.

Les logiques modales sont des extensions de la logique classique, et l'implication y possède alors la même interprétation. Cependant, les opérateurs modaux permettent de définir des formes plus fortes de l'implication.