Logique d'ordre supérieur

Les logiques d'ordre supérieur (en anglais, higher-order logic ou HOL) sont des logiques formelles permettant d'utiliser des variables qui réfèrent à des fonctions ou à des prédicats. Elles étendent le calcul des prédicats. Cela revient à dire que l'on considère les fonctions et prédicats comme des objets de base à part entière, au même titre que, par exemple, un nombre entier. On s'autorisera ainsi, d'une part, à quantifier les prédicats et les fonctions et, d'autre part, à donner des fonctions ou des prédicats en arguments à d'autres fonctions ou prédicats. On peut doter le système formel d'un mécanisme de typage qui restreint la nature des objets donnés en argument d'un prédicat ou d'une fonction. Un prédicat d'ordre supérieur est un prédicat qui prend comme argument un ou plusieurs autres prédicats. De manière générale, un prédicat d'ordre n prend comme argument un ou plusieurs prédicats d'ordre n-1, avec n > 1. Les mêmes définitions s'appliquent aux fonctions d'ordre supérieur. Les lambda-calculs typés, comme le calcul des constructions, mettent en œuvre de telles logiques. Un lien fort est tissé entre les mathématiques et l'informatique grâce à la correspondance de Curry-Howard qui associe un lambda-calcul (un modèle de calcul) à une logique. Cela conduit aux langages de programmation fonctionnelle. La logique du second ordre étend celle du premier ordre par l'ajout de variables relationnelles, qui peuvent donc être quantifiées. Par exemple, est une formule de la logique du second ordre. En particulier, la logique du second ordre permet de quantifier sur des fonctions (vues comme des cas particuliers de relations). L'axiome d'induction est un axiome du second ordre : La logique monadique du second ordre se restreint aux variables relationnelles unaires, qui sont en fait les ensembles. Elle permet d'avoir des résultats de décidabilité plus intéressants qu'au premier ordre : par exemple, la théorie monadique d'un ordinal dénombrable est décidable. Cette logique apparaît en algorithmique, par le biais du théorème de Courcelle.