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

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

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

С момента своего возникновения комбинаторная логика и лямбда-исчисление были отнесены к неклассическим логикам. Дело заключается в том, что комбинаторная логика возникла в 1920-х годах, а лямбда-исчисление — в 1940-х годах как ветвь метаматематики с достаточно очерченным предназначением — дать основания математике. Это означает, что сконструировав требуемую «прикладную» математическую теорию — предметную теорию, — которая отражает процессы или явления в реальной внешней среде, можно воспользоваться «чистой» метатеорией как оболочкой для выяснения возможностей и свойств предметной теории.

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

Изначальным назначением комбинаторной логики был именно анализ процесса подстановки. В качестве ее сущностей планировалось использовать объекты в виде комбинаций констант. Лямбда-исчислению отводилась роль средства уточнения представлений об алгоритме и вычислимости. Как следствие, комбинаторная логика дает в руки инструмент для анализа процесса подстановки. Через короткий промежуток времени оказалось, что обе эти системы можно рассматривать как языки программирования (см. также комбинаторное программирование).

В обеих системах исчисляются объекты, они являются исчислениями или языками высших порядков, то есть имеются средства описания отображений или операторов, которые определяются на отображениях или операторах, а в качестве результата вырабатывают также отображения или операторы. Самое существенное, что именно отображение считается объектом. В этом их принципиальное отличие от всего многообразия других систем, в которых первичной сущностью обычно считают представление о множестве и его элементах.

К настоящему времени оба эти языка не только стали основой для всей массы исследований в области компьютерных наук и компьютинга, но и широко используются в теории программирования. Развитие вычислительной мощности компьютеров привело к автоматизации значительной части теоретического — логического и математического, — знания, а комбинаторная логика вместе с лямбда-исчислением признаются основой для рассуждений в терминах объектов.

Содержание

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

В рамках комбинаторной логики строится специальный вариант теории вычислений, называемый категориальной абстрактной машиной. Для этого вводится в рассмотрение особый фрагмент комбинаторной логики — категориальная комбинаторная логика[3]. Она представлена набором комбинаторов, каждый из которых имеет самостоятельное значение как инструкция системы программирования. Тем самым в комбинаторную логику встраивается еще одно полезное приложение — система программирования, основанная на декартово замкнутой категории (д.з.к.). Это позволяет еще раз на новом уровне переосмыслить связь операторного и аппликативного стиля программирования.

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

Пользуясь представлениями об объектах как абстрактных математических сущностях, обладающих определенными подстановочными свойствами, можно строить системы логических рассуждений. Наиболее известная среди таких систем основана на комбинаторах.

Логика, основанная на комбинаторах, или иллативная комбинаторная логика, строится из теории комбинаторов или лямбда-исчисления, расширенного дополнительными константами — экстра-константами, — вместе с соответствующими аксиомами и правилами вывода, которые обеспечивают средства дедуктивного вывода.

Исторические комментарии

В 1920 году комбинаторы как специальные математические сущности[4] первоначально были установлены М. Шейнфинкелем[5]. Несколькими годами позже они независимо были переоткрыты Х.Карри[6], благодаря которому с тех пор были выполнены основные продвижения в комбинаторной логике (хотя другие исследователи, например, Россер, в различное время также участвовали в этой работе). Почти в то же самое время Черчем, Россером и Клини было начато развитие \lambda-конверсии. С 1970-х гг. комбинаторы использовались в трех главных аспектах: во-первых, для построения логических систем, основанных на абстрактной записи операции; во-вторых, в теории доказательств как основа записи конструктивных функций различного вида; в-третьих, при построении и анализе некоторых языков программирования в компьютерных науках.

Примечания

  1. Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960—1970.
  2. Кондаков, 1971
  3. Curien P.-L. Categorical combinatory logic. — LNCS, 194, 1985, pp.~139-151.
  4. Cardone F., Hindley J.R. History of lambda calculus and combinators, in Handbook of the History of Logic, Volume 5, D M Gabbay and J Woods (eds) (Amsterdam: Elsevier Co., to appear).
  5. Schonfinkel M. Uber die Baustein der mathematischen Logik. — Math. Annalen, vol. 92, 1924, pp.~305-316.
  6. Curry H.B. Grundlagen der kombinatorischen Logik. American Journal of Mathematics, 52:509–536, 789–834, 1930.

Литература

  • Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. — 2-е изд.. — М.: АО Центр ЮрИнфоР, 2003. — 204 с. — ISBN 5-89158-101-9
  • Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 1971. — 656 с.

См. также

Ссылки


Wikimedia Foundation. 2010.

Поможем решить контрольную работу

Полезное


Смотреть что такое "Комбинаторная логика" в других словарях:

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

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

  • комбинаторная логика — kombinatorinė logika statusas T sritis automatika atitikmenys: angl. combinational logic; combinatory logic; combinatorial logic vok. kombinatorische Logik, f; Schaltlogik, f rus. комбинаторная логика, f pranc. logique combinatoire, f …   Automatikos terminų žodynas

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

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

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

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

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

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

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

Книги

Другие книги по запросу «Комбинаторная логика» >>


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

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