Pour les articles homonymes, voir combinatoire (homonymie).
Cet article traite de la logique combinatoire, au sens qu'a ce mot en logique mathématique et en informatique théorique. Il ne doit pas être confondu avec ce que l'on appelle logique combinatoire en électronique numérique.
En logique mathématique, la logique combinatoire est une théorie logique[1] introduite par Moses Schönfinkel[2] en 1920 lors d'une conférence[Laquelle ?] et développée dès 1929 par Haskell Brooks Curry[3] pour supprimer le besoin de variables en mathématiques, pour formaliser rigoureusement la notion de fonction et pour minimiser le nombre d'opérateurs nécessaires pour définir le calcul des prédicats à la suite de Henry M. Sheffer. Plus récemment, elle a été utilisée en informatique comme modèle théorique de calcul et comme base pour la conception de langages de programmation fonctionnels.
Le concept de base de la logique combinatoire est celui de combinateur qui est une fonction d'ordre supérieur ; elle utilise uniquement l'application de fonctions et éventuellement d'autres combinateurs pour définir de nouvelles fonctions d'ordre supérieur. Chaque combinateur simplement typable est une démonstration à la Hilbert en logique intuitionniste et vice-versa [4]. On appelle ceci la correspondance de Curry-Howard
- Katalin Bimbó, The Stanford Encyclopedia of Philosophy, Metaphysics Research Lab, Stanford University, (lire en ligne)
- Moses Schönfinkel "Über die Bausteine der mathematischen Logik", Mathematische Annalen 92, p. 305-316. Traduit en français par Geneviève Vandevelde : Moses Schönfinkel, « Sur les éléments de construction de la logique mathématique », Mathématiques et sciences humaines, vol. 112, , p. 5-26 (lire en ligne) et traduit en anglais dans Moses Schönfinkel (trad. Stefan Bauer-Mengelberg), « On the building blocks of mathematical logic », dans Jean van Heijenoort, A Source Book in Mathematical Logic, 1879-1931, Harvard Univ. Press, (lire en ligne), p. 355-66.
- H. B. Curry, « Grundlagen der Kombinatorischen Logik », American Journal of Mathematics, vol. 52, no 3, , p. 509–536 (DOI 10.2307/2370619, lire en ligne, consulté le )
- H. Curry, J. R. Hindley et J. P. Seldin, Combinatory Logic II. North-Holland, 1972.