La recherche de preuve est l'exploration systématique de l'espace des dérivations possibles afin de localiser une preuve valide d'une assertion spécifiée, en utilisant algorithmes, stratégies et limites de ressources.

Principe

Organiser l'exploration avec des stratégies de recherche (profondeur, largeur, meilleur d'abord, enchaînement en arrière ciblé, enchaînement en avant), des heuristiques et de l'élagage tout en équilibrant complétude, correction et contraintes de ressources.

Démonstration

Effectuer une recherche enchaînée en arrière limitée en profondeur dans un calcul de séquents pour trouver une dérivation d'un but, ou faire une recherche basée sur la résolution avec unification et heuristiques de sélection de clauses pour réfuter la négation de la conjecture.

Mauvaise application

Appliquer une recherche exhaustive sans élagage ni heuristiques conduit à une explosion combinatoire ; employer des heuristiques biaisant la recherche peut sacrifier la complétude et manquer des preuves existantes.

Conséquence

Une recherche de preuve efficace localise des preuves ou des réfutations certifiables, renseigne sur la complexité et fournit la base des démonstrateurs automatiques et de la sélection de tactiques en environnements interactifs.

Inversion

L'inverse est la recherche ciblée de modèles ou de contre-exemples (réfutation par contre-modèles) ou le recours uniquement à l'intuition humaine pour construire une preuve sans exploration systématique.

Limite

La recherche de preuve se réfère à l'exploration syntaxique des dérivations et inclut procédures complètes et incomplètes ; elle exclut les méthodes purement sémantiques qui ne parcourent pas l'espace des dérivations syntaxiques sauf si elles sont formulées comme recherche.

Tension sémantique

Il existe une tension entre la recherche en arrière dirigée par l'objectif (qui se focalise sur la conclusion) et la saturation en avant (qui dérive largement des conséquences) ; chacune présente des compromis en applicabilité et performance.

Synthèse

La recherche de preuve est le parcours algorithmique guidé par des stratégies de l'espace des dérivations qui applique règles d'inférence, heuristiques et gestion de ressources pour découvrir une dérivation valide ou une réfutation d'une assertion cible.