Classe de Bernays-Schönfinkel
From Wikipedia, the free encyclopedia
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?En logique mathématique, la classe de Bernays-Schönfinkel (parfois appelée la classe de Bernays-Schönfinkel-Ramsey) est le fragment syntaxique de la logique du premier ordre des formules dont la forme prénexe est de la forme et qui ne contiennent pas de symboles de fonctions[1],[2]. Elle est nommée d'après ses créateurs, Paul Bernays et Moses Schönfinkel (avec l'apport aussi de Frank Ramsey).
Le problème de la satisfiabilité est décidable et NEXPTIME-complet[3].
Cette classe de formules s'appelle parfois effectively propositional (EPR)[4] car elle peut être effectivement traduite en logique propositionnelle en instanciant les variables universelles par des termes clos.
