Комбинаторная логика

ветвь математической логики, изучающая комбинаторы и их свойства. В качестве основных понятий в К. л. выбираются функция и операция применения функции к аргументу (аппликация). Комбинаторами называют члены некоторого класса операций над функциями, замкнутого относительно аппликации. Сформулированное в терминах К. л. понятие «комбинаторно определимой функции» явилось одним из первых способов уточнения понятия алгоритма. Начало К. л. положено работой советского математика М. И. Шейнфинкеля (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.

combinational [combinatorial\] logic

КОМБИНАТО́РНАЯ ЛО́ГИКА

см. Логика комбинаторная.

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

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

где х ₁, х ₂, ..., х _п,- произвольные функции, 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.

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

combinational [combinatorial] logic

* * *

combinational logic

logica combinatoria

комбіна́торна ло́гіка

комбіна́торна ло́гіка