Intuition d'une preuve

Publié le October 17, 2022
Tags: informatique, maths, preuve

Dans cet article nous allons nous intéresser à la notion de preuve en abordant la question sous l’angle de l’intuition.

Intuition

Le fait à prouver

Dans un premier temps, il est bon de s’intéresser à ce l’objet d’une preuve, le fait. Il est la chose que l’on doit prouver. Un fait peut être une assertion atomique. Par exemple

Il fait beau

ou alors être composé de sous-faits, comme par exemple

S’il fait beau alors j’irai jouer dehors.

Cette dernière forme est une implication, c’est à dire que la véracité du premier fait implique celle du second.

D’autres formes de faits sont possibles, comme la disjonction (AA ou BB) et la conjonction (AA et BB), mais ne seront pas utilisées dans la suite de cet article.

La preuve du fait

Étant donné un ensemble de faits supposés vrais (hypothèses), une preuve est une construction dont la présence justifie un fait.

Par exemple, dans l’élucidation d’une affaire judiciaire, le fait à prouver pourrait être

l’individu est passé par ici.

et la preuve serait le cheminement depuis les faits hypothèses jusqu’au fait à prouver.

Première preuve

La preuve la plus simple est le flagrant-délit, c’est à dire la constatation directe de la présence de l’individu par le responsable de l’ordre.

La construction de cette preuve est ici très simple car elle est uniquement la constatation d’un fait. De manière un peu plus formelle, la preuve est de la forme “Le fait AA est vrai car le fait AA est vrai”.

La première construction d’une preuve mise en évidence ici est l’axiome, ou le principe d’identité. Les preuves qui se réduisent à cette unique règle sont des tautologies.

Déduction

Au delà du niveau 0 de la preuve précédente, la construction de la preuve peut être étendue en utilisant des règles naturelles.

Par exemple, si d’une part connais le fait suivant

Si la lampe s’est allumée, alors l’individu est passé par ici

et si, d’autre part, je sais que le fait suivant est vrai

La lampe s’est allumée

alors je peux en déduire le fait suivant

L’individu est passé par ici.

On a présenté ici la règle basique de la déduction, ou encore modus ponens. Cette règle lie d’une part deux faits prémisses (les deux premiers) et un fait déduit.

Il est important de bien différencier le fait implication de la preuve par déduction. Effet, le fait

Si AA alors BB

est une simple phrase, sans valeur de vérité intrinsèque. De plus, AA et BB ne sont pas contraints. Ce fait est à différencier de la règle de déduction vue juste avant où sont mis en relations des faits prémisses avec un fait déduit.

Exemple

On va utiliser les deux règles présentées (axiome et modus ponens) pour construire la preuve du fait

L’éclairage public est éteint

en utilisant les trois hypothèses

S’il fait jour, alors l’éclairage public est éteint

Si le coq chante, alors il fait jour.

Le coq chante.

  1. Je pars de ce que je veux prouver : l’éclairage public est éteint
  2. En utilisant la règle du modus ponens, je réduis le fait que j’ai à prouver à deux sous-faits :
    • Il fait jour
    • S’il fait jour, alors l’éclairage public est éteint
  3. Le deuxième sous-fait est validé par la règle de l’axiome car il fait partie de mes hypothèses.
  4. En utilisant la règle du modus ponens, je réduis le premier sous-fait que j’ai à prouver à deux autres sous-faits :
    • Le coq chante
    • Si le coq chante, alors il fait jour
  5. Ces deux faits sont validés tous les deux par la règle de l’axiome car ces deux faits font partie de mes hypothèses

Conclusion

Une preuve est un assemblage construit à partir de règles permettant de composer des sous-preuves en une nouvelle preuve.

Ces règles sont ce qui défini la logique avec laquelle on veut travailler, leur définition est crucial dans l’expressivité de la logique.

Dans cette partie introductive, les notions on été abordées et utilisées de manière non rigoureuse. Cette formalisation sera l’objet d’un prochain article.