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

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

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

В системах математической логики (призванных формализовать логич. выводы) правила вывода, хотя и формулируются содержательно, но, по идее, должны быть вполне доступны для одноактного автоматич. выполнения. Нек-рые из них, вроде известного modus ponens, позволяющего из выведенных уже формул А и (A ⊃ B) вывести формулу В, представляются непосредственно удовлетво-ряющими этому требованию. В др. случаях, прежде всего для правила подстановки (особенно на место предикатных переменных), формулировка правила настолько сложна (требует введения ряда новых терминов, проверки выполнения или невыполнения трудно формулируемых условий), что даже квалифицированному специалисту бывает нелегко решить вопрос о ее корректности. Выполнить такое правило поэтому во многих случаях отнюдь не просто. В Л. к. правило подстановки сводится к цепочке правил, не более сложных, чем modus ponens. Анализ выявляет трудности и в др. упомянутых выше понятиях, формализацией (или устранением) к-рых и занимается Л. к.

История Л. к. начинается с труда сов. математика М. И. Шейнфинкеля "О кирпичах матем. логики" [(М. Schönfinkel, Über die Bausteine der mathematischen Logik, "Math. Ann.", 1924, Bd 92); краткое пояснение смысла исходных функций Шейнфинкеля имеется в статье С. А. Яновской "Основания математики и математическая логика" (см. сб. "Математика в СССР за тридцать лет 1917–1947", 1948, с. 31–33) ], положившего в основу логики нек-рые три индивидуальные функции С, S, U (рассматриваемые как особые предметы, отличные от значений функций) и одну операцию: приложения функции к аргументу (к-рым может быть и функция), обозначаемую только тем, что знак аргумента ставится непосредственно за знаком функции. Функции от n аргументов (n-местные функции) сводятся Шейнфинкелем к функциям от одного аргумента (к одноместным функциям). Задание же последних не предполагает у него (в отличие от того, как это принято в т.н. классич. математике) предварит, задания множеств значений аргументов и значений функции. Понятие функции оказывается, т.о., независимым от понятия множества, с к-рым связаны большие трудности (см. Парадокс). Шейнфинкель полагал, что введенных им функций С, S, U достаточно для представления любых выражений математич. логики (в т.ч. и содержащих кванторы "все" и "существует") в виде слов в алфавите, состоящем только из трех латинских букв С, S, U и скобок. Выражения логики должны были сводиться, т.о., к комбинациям (с повторениями) из букв С, S, U (и скобок), откуда и название "Л. к." (предложенное в 1930 X. Кёрри). Употребление же переменных должно было быть вообще исключено из логики.

Чтобы показать на простом примере, как это делается, рассмотрим комбинатор А такой, что Аху=х+у, и комбинатор С такой, что Cfxy=fyx; [приложение комбинатора А к аргументам х, у дает х+у; приложение комбинатора С к f(х, у) дает f(y, x) – в более обычных обозначениях ]. Сумму у +х в таком случае можно выразить как С Аху. Тождество х+у = у+х выражается при этом в виде Аху=САху. И если (как это делается обычно в математике) трактовать тождественное равенство f(х1, хп) = g(x1,..., хп) как другое выражение для того, что f=g (т.е. считать, что функции f и g, относящие обе одни и те же объекты к одним и тем же значениям аргументов, отождествляются нами), то другим выражением для тождества х+у=у+х будет А=CA – формула, не содержащая переменных.

Как показало дальнейшее развитие идей Шейнфинкеля, их осуществление – в применении к той части Л. к., к-рая призвана была заменить уже и оперирование с кванторами, – оказалось отнюдь не столь простым, как это представлялось их автору, и потребовало дальнейших исследований. Среди последних выделяются прежде всего работы Кёрри. Первые работы Кёрри по Л. к. появились в 1929–30. В них он пользовался системой исходных функций ("комбинаторов"), отличной от введенной Шейнфинкелем, а также разработал технику вывода для Л. к., к-рой не было у Шейнфинкеля. Непротиворечивость той части системы Л. к., в к-рой еще нет аналога для кванторов (т.н. "чистой" Л. к.), также была доказана в этих работах Кёрри. В это же время Чёрчем было разработано его исчисление λ-конверсии, в к-ром были получены первые в истории науки доказательства неразрешимости нек-рых массовых проблем (см. Алгоритм, Разрешения проблемы). В диссертации "Математическая логика без переменных" (J. В. Rosser, A mathematical logic without variables, 1935) амер. математик Россер показал эквивалентность Л. к. и исчисления λ-конверсии. В том же 1935 Клини и Россер обнаружили противоречие в первоначальной системе Чёрча, к-рое, т.о., оказалось имеющим место и в применении к Л. к.: не к "чистой", а к "заключительной" (illative), включающей импликацию и аналоги для кванторов. Чтобы избежать этого противоречия, "заключительную" Л. к. приходится строить либо как неклассическую, либо как содержащую предметы разных (не сводимых друг к другу) категорий (что и было сделано Кёрри). В логику приходится, т.о., включать нек-рые сведения о предметах (о существовании разных категорий предметов и, следовательно, о нек-рых специфич. свойствах их), к-рые естественно относить уже к области онтологии или еще более конкретных наук, изучающих специфицированные предметы. В развитии Л. к., т.о., полностью подтверждаются принципы, ясные с т. зр. материалистич. диалектики: о неотделимости логики от онтологии, о роли противоречия в развитии науки, о способах "снятия" противоречия с помощью большей конкретизации исследуемых предметов и др.

Поскольку в Л. к. исходным является понятие функции, а не множества, естественно, встает задача построить теорию множеств, исходя из Л. к. Такие попытки предприняли Кёрри в 1934 (опубликовано только резюме его работы) и Коген (1955), в работе к-рого (она посвящена обоснованию средствами Л. к. системы аксиом Гёделя для теории множеств) нем. математик Титгемейер обнаружил, однако, противоречие, свидетельствующее о том, что попытка Когена не удалась. В 1952 Кёрри предложил использовать Л. к. при составлении программ для вычислит. машин.

Лит.: Curry H., An analysis of logical substitution, "Amer. J. Math.", 1929, v. 51, p. 363–84; его же, Grundlagen der kombinatorischen Logik, там же, 1930, v. 52, p. 509–36; 789–834; его же, Foundations of the theory of abstract sets from the standpoint of combinatory logic, "Bull. Amer. Math. Soc.", 1934, v. 40, No 9, p. 654; eго же, The logic of program composition, в кн.: Applications scientifiques de la logique mathématique. Actes du 2-е colloque international de logique mathématique, Paris, 22–30 aôut 1952, P. – Louvain, 1954, p. 97–102; Кleene S. С. and Rosser J. В., The inconsistency of certain formal logics, "Annales Mathem.", 1935, v. 36, ser. 2, p. 630–36; Cogan E. J., A formalization of the theory of sets from the point of view of combinatory logic, "Z. math. Logik und Grundlagen Math.", 1955, Bd 1, H. 3, S. 198–240; Curry H. and Feys R., Combinatory logic, v. 1, Amst., 1958 (имеется библиогр.); Titgemeyer R., Über einen Widerspruch in Cogans Darstellung der Mengenlehre, "Z. math. Logik und Grundl. Math.", 1961, Bd 7, H. 3.

С. Яновская. Москва.

Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960—1970.