Математическая энциклопедия - комбинаторная логика

раздел логики, посвященный изучению и анализу таких понятий и методов, как переменная, функция, операция подстановки, классификация предметов по типам или категориям и другие.

В качестве основных понятий в К. л. выбираются одноместная функция и операция применения функции к аргументу (аппликация), при этом понятие функции рассматривается как первичное по отношению к понятию множества и обобщается таким образом, что функция может принимать объекты одного с ней уровня как в качестве аргументов, так и в качестве значений. В частности, аргументом функции f может служить сама эта функция. Поскольку функции могут выступать в качестве как аргументов, так и значений, понятие многоместной функции сводится к понятию одноместной функции. Результат аппликации функции f к аргументу хобозначают (fx). Для простоты часто скобки опускают, понимая при этом запись fx1x2...xn как (. . .((fx1)x2).. .хД). Функция f, удовлетворяющая равенству

где х 1, х 2, ... , х п,произвольные функции, a X объект, построенный из этих функций (быть может, не из всех) с помощью операции аппликации, наз. комбинатором (существование комбинаторов неявно постулируется). Всякий комбинатор может быть выражен через два комбинатора Sи К, удовлетворяющих следующим равенствам:

(здесь х, у, z - произвольные функции).

Одной из первых в К. л. была задача, к-рая состояла в сведении первичных логич. понятий к минимальному числу достаточно простых понятий. Была введена индивидуальная функция U, к-рая обобщала штрих Шеффера [если fи gодноместные пропозициональные функции, то Ufg интерпретируется как и было показано, что каждую формулу исчисления предикатов можно представить в виде комбинации из букв U, S, К (и скобок), откуда и название "К. л." [X. Карри (Н. Curry), 1930]. Переменные в таком представлении совсем не использовались, что позволило избавиться от переменной как исходного понятия (понятия индивидуальной константы, высказывания и пропозициональной функции при этом также элиминировались как исходные понятия). Однако, как показало дальнейшее развитие К. л., построение на такой основе логич. систем встретило значительные трудности. Первые логич. исчисления такого типа, предложенные А. Чёрчем (A. Church) и X. Карри, оказались противоречивыми (парадокс Клини-Россера, см. [4]). Чтобы избежать этого противоречия, К. л. приходится строить либо как обладающую очень бедными дедуктивными возможностями, либо как содержащую объекты разных категорий. Основное развитие К. л. пошло по второму пути.

Часть К. л., к-рая не имеет дела с "логикой", а интересуется только свойствами комбинаторов, наз. теорией комбинаторов. Показано, что эта теория непротиворечива. В результате формализации она принимает вид различных исчислений. Все они распадаются на два внешне различных класса: исчисления комбинаторов и l-исчисления.

Лит.:[1] Curry H., Fеуs R., Combinatory logic, v. 1, Amst., 1958; [2] Сurrу H., Hindley J., Seldin J., Combinatory logic, v. 2, Amst.L., 1972; [3] Сhurс h A., The calculi of lambda-conversion, Princeton, 1941; [4] Кleene S., Rosser J., "Ann. Math.", 1935, v. 36, p. 630-36; [5] Яновская С. А., Логика комбинаторная, в кн.: Философская энциклопедия, т. 3, М., 1964, с. 226-27; [6] Кузичев А. С, в сб.: История и методология естественных наук, в. 14, 1973, с. 131-41.

Л. В. Шабунин.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985