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


ЛОГИКА КОМБИНАТОРНАЯ
ЛО́ГИКА КОМБИНАТО́РНАЯ
одно из направлений логики, занимающихся ее основаниями, т.е. такими осн. понятиями и методами, к-рые при построении формальных логич. систем или исчислений предполагаются обычно не нуждающимися в пояснениях (содержательно понятными) и не анализируются. Особое внимание уделяется при этом понятиям переменной, функции, множества, различению типов переменных (предметные, предикатные, пропозициональные и др.), правилу подстановки, логич. антиномиям.
В системах математической логики (призванных формализовать логич. выводы) правила вывода, хотя и формулируются содержательно, но, по идее, должны быть вполне доступны для одноактного автоматич. выполнения. Нек-рые из них, вроде известного 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.


.

Смотреть что такое "ЛОГИКА КОМБИНАТОРНАЯ" в других словарях:

  • логика комбинаторная — (от лат. combinare соединять, сочетать) одно из направлений в математической логике, занимающееся анализом понятий, которые в рамках классической математической логики принимаются без дальнейшего изучения (напр., понятия переменная , функция ,… …   Словарь терминов логики

  • КОМБИНАТОРНАЯ ЛОГИКА — см. Логика комбинаторная. Философская Энциклопедия. В 5 х т. М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960 1970. КОМБИНАТОРНАЯ ЛОГИКА …   Философская энциклопедия

  • Логика — Гр …   Википедия

  • Логика (философия) — Логика (др. греч. λογική «наука о рассуждении», «искусство рассуждения» от λόγος  «речь», «рассуждение»)  наука о формах, методах и законах интеллектуальной познавательной деятельности, формализуемых с помощью логического языка. Поскольку это… …   Википедия

  • Комбинаторная логика —         ветвь математической логики, изучающая комбинаторы и их свойства. В качестве основных понятий в К. л. выбираются функция и операция применения функции к аргументу (аппликация). Комбинаторами называют члены некоторого класса операций над… …   Большая советская энциклопедия

  • КОМБИНАТОРНАЯ ЛОГИКА — раздел логики, посвященный изучению и анализу таких понятий и методов, как переменная, функция, операция подстановки, классификация предметов по типам или категориям и другие. В качестве основных понятий в К. л. выбираются одноместная функция и… …   Математическая энциклопедия

  • Логика в информатике — Логика в информатике  это направления исследований и отраслей знания, где логика применяется в информатике и искусственном интеллекте. Логика очень эффективна в этих областях[1]. Содержание 1 Область применения …   Википедия

  • Логика в компьютерных науках — Логика в информатике это направления исследований и отрасли знания, где логика применяется в информатике и искусственном интеллекте. Логика оказалась гораздо более эффективной в информатике, чем это было в математике[1]. Включаются следующие… …   Википедия

  • комбинаторная логика — комбинационные логические схемы — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики Булева алгебра, элементы цифровой техники Синонимы комбинационные логические схемы EN combinational logic …   Справочник технического переводчика

  • Комбинаторная логика — направление математической логики, занимающееся фундаментальными  не нуждающимися в объяснении и не анализируемыми  понятиями и методами формальных логических систем или исчислений[1][2]. В дискретной математике тесно связана с λ… …   Википедия

Книги

Другие книги по запросу «ЛОГИКА КОМБИНАТОРНАЯ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.