ЛОГИКА КОМБИНАТОРНАЯ
Logic, Combinatory
A branch in mathematical logic analyzing concepts which, within the framework of classical mathematical logic, are accepted without further study. Among them are the concepts: variable, function, rule of substitution, etc. In classical mathematical logic rules of two kinds are used. The first are formulated simply and are applied without any restrictions. Such, for instance, is the rule of modus ponens. It is formulated as follows: "Given A and A → B to infer B." This rule is accessible for a one-act automatic performance. Other rules (for example, the rule of substitution) are very intricately formulated and presuppose a number of restrictions and reservations (without which they cannot be applied purely formally).
One of the purposes of Combinatory Logic is to construct a formal system having no rules like the rule of substitution. The beginning of Combinatory Logic was laid by the Soviet mathematician M. I. Sheinfinkel (his main results were published in 1924). Independent of him, A. Church also constructed a lambda conversion calculus closely linked with Combinatory Logic. Important results were also obtained by the American logician H. Curry. Problems of Combinatory Logic are studied by J. B. Rosser, W. Craig, R. Feys, and others.
Комбинаторная логика
Ветвь математической логики, изучающая комбинаторы и их свойства. В качестве основных понятий в К. л. выбираются функция и операция применения функции к аргументу (аппликация). Комбинаторами называют члены некоторого класса операций над функциями, замкнутого относительно аппликации. Сформулированное в терминах К. л. понятие «комбинаторно определимой функции» явилось одним из первых способов уточнения понятия алгоритма. Начало К. л. положено работой советского математика М. И. Шейнфинкеля (1924), большая часть результатов принадлежит американскому логику Х. Карри. К. л. находит широкое применение в теории языков программирования.
Лит.: Яновская С. А., Логика комбинаторная, в кн.: Философская энциклопедия, т. 3, М., 1964; SchönfinkeI М., Über die Bausteine der mathema-tischen Logik, «Mathematische Annalen», 1924, Bd 92; Curry H. B., Feys R., Combinatory logic, Amst., 1958; Curry H. B., Recent advances in combinatory logic, «Bulletin de la Société mathématique de Belgique», 1968, t. 20, № 3.