Logique minimale

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

En logique mathématique, la logique minimale, créée par Ingebrigt Johansson[1], est une variante de la logique classique qui en plus de ne pas inclure le tiers-exclu évite le principe d'explosion. Les trois logiques (logique minimale, logique intuitionniste et logique classique) diffèrent sur la façon de traiter la négation et la contradiction dans le calcul des propositions ou le calcul des prédicats. Dans une certaine mesure, la logique minimale n'aborde pas le concept de contradiction et représente une logique sans véritable négation.

Comparaison entre les diverses logiques[modifier | modifier le code]

On utilisera comme notation les symboles suivants : pour la disjonction, pour la conjonction, pour l'implication, pour la négation, pour l'équivalence.

Les règles communes[modifier | modifier le code]

Dans les trois logiques, on dispose des deux règles suivantes, relatives à la négation :

  • La règle d'élimination de la négation : si on a à la fois une proposition et sa négation , alors on a une contradiction, notée  ;
  • La règle d'introduction de la négation : si une proposition conduit à une contradiction, alors c'est que est valide. Cette règle peut d'ailleurs être prise comme définition de la négation : est un synonyme de .

Les différences[modifier | modifier le code]

Les trois logiques diffèrent sur les conséquences à tirer d'une contradiction.

  • La logique classique utilise le raisonnement par l'absurde et déduit de le fait que est valide. C'est en fait une règle d'élimination de la double négation, puisque est un synonyme de .
  • La logique intuitionniste déduit d'une contradiction n'importe quelle proposition : , ce qu'on résume par la formule ex falso sequitur quodlibet.
  • La logique minimale ne prévoit aucun traitement lié à .

Il en résulte que la logique minimale n'établit pas de différence entre la formule et n'importe quelle autre formule. Considérons par exemple une formule quelconque . Définissons comme synonyme de . On a alors :

  • Si on a à la fois et , alors on a . En effet, de et de , on peut déduire . C'est la règle du modus ponens ;
  • Si une proposition conduit à , alors on a et donc .

On voit donc que, si on n'attribue aucun rôle particulier à la contradiction, on peut faire jouer le rôle de cette contradiction à n'importe quelle formule , en définissant la négation comme étant , et qu'inversement, on peut supprimer toute référence à la négation en logique minimale.

Par souci de comparaison avec les autres logiques, nous continuerons néanmoins à utiliser les symboles et .

Exemples de formules valides en logique minimale[modifier | modifier le code]

Exemple 1 :

En effet, supposons qu'on ait (autrement dit, on a à la fois et ). Montrons que l'on a , autrement dit, montrons que l'hypothèse conduit à une contradiction. Distinguons les cas : soit on a qui est bien contradictoire avec l'hypothèse , ou bien on a qui est contradictoire avec . Dans tous les cas, on a une contradiction, CQFD.

Réciproquement, supposons que l'on ait et montrons que l'on a , autrement dit que conduit à une contradiction. Mais entraîne qui est contradictoire avec l'hypothèse. CQFD. On procède de même pour montrer .

Par contre, on a seulement , la réciproque étant seulement vraie en logique classique.

Exemple 2 :

Supposons qu'on ait . Alors l'hypothèse supplémentaire conduit à une contradiction. On a donc . CQFD

La réciproque est invalide en logique minimale et en logique intuitionniste. On dispose cependant de . En effet, supposons que . L'hypothèse supplémentaire entraîne qui est contradictoire avec , donc on a .

Exemple 3 : On peut montrer la validité en logique minimale de . Mais la réciproque est seulement valide en logique intuitionniste ou en logique classique.

Exemple 4 : En ce qui concerne la contraposition, on peut montrer qu'en logique minimale, on a , ainsi que et , mais on ne dispose pas de qui est une variante du raisonnement par l'absurde.

Exemples de formules invalides[modifier | modifier le code]

Exemple 1 : La formule est invalide en logique minimale. En effet, si elle était prouvable, alors on pourrait prouver également, en remplaçant par une proposition quelconque que , or cette dernière formule n'est pas même prouvable en logique classique, sans hypothèse supplémentaire sur .

Exemple 2 : La formule est valide en logique intuitionniste et en logique classique, mais pas en logique minimale. En effet, une preuve demanderait de supposer et d'en déduire , et donc de supposer et d'en déduire . L'utilisation de par disjonction des cas et de pour prouver demanderait de prouver que et prouvent , et que et prouvent . Mais la preuve de à partir de et n'existe pas en logique minimale. Elle existe en logique intuitionniste, puisque, de la contradiction , on peut déduire .

Logique minimale et logique classique[modifier | modifier le code]

La traduction de Gödel[modifier | modifier le code]

La logique minimale, amputée du traitement de la négation, semble bien pauvre devant la logique classique ou la logique intuitionniste. Elle n'en est cependant pas si éloignée. On montre en effet, que, pour toute formule A, il existe une formule A', équivalente à A en logique classique, telle que A est prouvable en logique classique si et seulement si A' est prouvable en logique minimale. A' est obtenue au moyen de la traduction de Gödel, définie inductivement comme suit :

pour toute formule atomique différente de

Autrement dit, la traduction de Gödel d'une formule consiste à rajouter des doubles négations devant les formules atomiques, les disjonctions et les quantificateurs existentiels. Cela signifie qu'en logique classique, il suffit de faire appel à des raisonnements par l'absurde seulement devant des formules atomiques, des disjonctions ou des quantificateurs existentiels.

Exemples[modifier | modifier le code]

Par exemple, le tiers exclu est un théorème de la logique classique, mais pas de la logique minimale. Par contre, la formule est valide en logique minimale. En effet, celle-ci est équivalente, en logique minimale, à ou à ou encore à , c'est-à-dire à qui est une formule valide.

Bibliographie[modifier | modifier le code]

  • René Davour, Karim Nour, Christophe Raffali, Introduction à la logique, Dunod (2001, 2003), (ISBN 2-10-006796-6)

Notes et références[modifier | modifier le code]

  1. Johansson, Ingebrigt, « Der Minimalkalkül, ein reduzierter intuitionistischer Formalismus », Compositio Mathematica, vol. 4,‎ (lire en ligne, consulté le 29 octobre 2018)