Logique classique et principe du tiers-exclu

L'axiome du tiers-exclus

La différence entre ce que nous avons fait en Coq et votre cours de mathématiques classique est que Coq n'est pas équipé par défaut du principe du tiers exclu qui dit qu'une proposition est soit vraie, soit fausse. Donc, jusqu'à présent, nous n'avons pas pu faire de preuve par l'absurde, ni de raisonnement par contraposition.

Voici l'axiome du tiers-exclu :

Attention, un axiome n'est pas un théorème. En ajoutant un axiome on prend le risque énorme que la théorie devienne incohérente, c'est-à-dire permette de prouver False. Dans notre cas, un théorème difficile montre que si Coq est correct (c'est-à-dire ne permet pas de prouver False), alors il l'est encore avec le tiers exclu.

Conséquences en logique propositionnelle

Avec cet axiome, on peut prouver, par exemple, que le raisonnement par l'absurde est correct.

Remarquer destruct (classic P) as [HP | HnP.]. Ici, classic est un axiome qui prend une proposition en argument et (classic P) est une preuve de (P \/ ~P). Avec destruct, on peut donc la détruire et faire une preuve par cas.

Exercice :

En utilisant le tiers exclu ou l'une de ses conséquences, prouver le théorème suivant :

Remarque (voir les exercices à faire à la maison) :

  • les trois autres lois de de Morgan sont prouvables en logique intuitionniste.
  • celle-ci ne l'est pas, on a absolument besoin du tiers exclu.

Exercice :

En utilisant le tiers exclu ou l'une de ses conséquences, prouver le théorème suivant :

Exercice :

En utilisant le tiers exclu ou l'une de ses conséquences, prouver le théorème suivant :

Conséquences en calcul des prédicats

On va voir qu'en logique classique (comme dans vos cours de mathématique), la négation d'un "il existe" est un "pour tout" et la négation d'un "pour tout" est un "il existe".

Les deux prochains théorèmes n'ont pas besoin de l'axiome du tiers exclu.

Mais à partir d'ici, il y en a besoin. Remarquez que ce n'est pas toujours facile de deviner à quelle proposition il faut l'appliquer. Ici, il faut destruct (classic (P n)) pour raisonner par cas sur P n.