Calcul des prédicats Article, Signification, Explication
Le calcul des prédicats du premier ordre ou logique du premier ordre, ou tout simplement calcul des prédicats est une logique formelle qui étend la logique propositionnelle. L'originalité de cette logique est l'introduction d'un ensemble de symboles appelés variables, d'un autre ensemble de symboles représentant des prédicats, ainsi que de deux symboles et appelés quantificateurs, permettant ainsi d'exprimer des propriétés telles que : «Pour tout X, P(X).».
Ici les variables représentent des valeurs d'un certain ensemble d'objets de base donné (par exemple, les entiers naturels), les quantifications de variables se rapportent donc uniquement à cet ensemble, et les prédicats représentent des relations n-aires sur cet ensemble.
On parle de logique du premier ordre par opposition aux logiques d'ordre supérieur, où l'on peut quantifier aussi bien les objets de l'ensemble de base que des prédicats ou des fonctions sur l'ensemble de base. Il s'ensuit que les prédicats représentent ainsi des relations entre tous ces objets.
On appellera termes les formules composées ainsi :
Les formules du calcul des prédicats du premier ordre sont les suivantes, et uniquement les suivantes (appelons F l'ensemble des formules):
Formation d'une formule du calcul des prédicats du premier ordre
On se donne :
On pourrait de contenter d'un seul quantificateur et de deux connecteurs logiques ¬ et sans perdre en expressivité.
Appelons T l'ensemble des termes.
Ce système très formel peut s'instancier, par exemple en l'arithmétique en prenant pour fonctions 0-aires les nombres (entiers par exemple) pour fonctions binaires les symboles des opérations « + » et « * » et comme prédicats binaires, les symboles « = » et « < ».
Formules closes, variables libres, variables liées