En
logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un
algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction (voir
système à la Hilbert,
calcul des séquents,
déduction naturelle), sans autres axiomes que ceux de l'égalité. De façon équivalente par le
théorème de complétude, il s'agit de savoir si un énoncé est universellement valide, c’est-à-dire vrai dans tous les modèles (de l'égalité). Il s'agit de
décidabilité algorithmique. Dit autrement, la question est celle de la
décidabilité du calcul des prédicats égalitaire du premier ordre : l'ensemble des énoncés universellement valides du calcul des prédicats du premier ordre est-il décidable ?
Pour la suite, voir Wikipédia.org…
Free Download Now!
