Une procédure qui crée des instances ground de formules quantifiées ou de règles schématiques en substituant des termes aux variables afin de permettre l'application de raisonnements propositionnels ou de procédures de décision au niveau ground.

Principe

Générer un ensemble représentatif et sonore de substitutions (instances) de sorte que les questions de validité ou de satisfiabilité concernant des formules quantifiées puissent être réduites aux questions correspondantes sur les formules ground produites, tout en équilibrant complétude et contraintes de ressources.

Démonstration

Dans un solveur SMT, instancier des contraintes universelles quantifiées avec des termes ground trouvés lors de la recherche (E‑matching) pour produire des clauses ground traitées par le moteur SAT/théorie ground ; en preuve automatique, effectuer une expansion de Herbrand pour réduire l'implication du premier ordre à des vérifications de clauses ground dans un cadre borné.

Mauvaise application

Une instanciation complète aveugle sur des domaines de termes larges ou infinis menant à une explosion combinatoire et à la non‑termination, ou une instanciation non sonore qui utilise des substitutions illégales (par ex. violant les tris ou la portée) produisant des conclusions incorrectes.

Conséquence

Gérée avec sonorité et des heuristiques adaptées (par ex. appariement par motifs, triggers, ou contrôles d'équité), la mécanisme d'instanciation permet de réduire efficacement le raisonnement quantifié aux solveurs ground, élargissant l'applicabilité des outils automatiques de raisonnement.

Inversion

Laisser les quantificateurs implicites et s'appuyer uniquement sur le raisonnement schématique ou d'ordre supérieur sans créer d'instances ground, ce qui peut éviter l'explosion mais risquer de manquer l'occasion d'exploiter des moteurs propositionnels/ground efficaces.

Limite

La terminaison et la complétude dépendent du langage de termes, des triggers/heuristiques et de la finitude du domaine de termes ; pour de nombreuses théories, une instanciation complète est indécidable ou impraticable, de sorte que heuristiques et incomplétude sont inévitables en pratique.

Tension sémantique

Entre instanciation avide (qui peut être complète dans des domaines finis mais explosive) et instanciation paresseuse/ciblée (scalable mais potentiellement incomplète), et entre triggers syntactiques et pertinence sémantique.

Synthèse

Un mécanisme d'instanciation produit systématiquement des instances ground à partir d'énoncés quantifiés pour permettre aux solveurs ground d'opérer ; les conceptions pratiques équilibrent sonorité, couverture et limites de ressources via des heuristiques qui échangent complétude contre évolutivité tout en cherchant à préserver autant que possible la puissance déductive.