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

Наиме­но­ва­ние:Комбинаторная логика (образовано от латинского слова: combinare — соединять, сочетать).
Опреде­ле­ние:Комбинаторная логика — это направление в основаниях логики и математики, занимающееся анализом понятий, которые в рамках классической математической логики принимаются без дальнейшего изучения.
Текст статьи: © Подготовка электронной публикации и общая редакция: © Центр гуманитарных технологий. Главный редактор: А. В. Агеев. Информация на этой странице периодически обновляется. Последняя редакция: 22.09.2025.

Комбинаторная логика — это направление в основаниях логики и математики, занимающееся анализом понятий, которые в рамках классической математической логики (см. Логика математическая) принимаются без дальнейшего изучения (например, понятия «переменная», «функция», «правила подстановки» и другие). В комбинаторной логике в качестве основных понятий выбираются: функция (оператор) и операция аппликации (application) — применение (приложение) функции f к аргументу g, пишут: (fg). Функции понимаются теоретико-операторно, бестипово, то есть допустимы: (gf), (gg), (g(ff)), (gg) (fg) и так далее. Выражение вида f(x₁, … xn), является лишь записью для (…(fx₁) x₂)xn). Тем самым многоместные функции сводятся к одноместным. Опуская скобки, пишут: fxx2 … xn вместо x₁, … xn можно поставить f, получая fff … f. Здесь n ≥ 0 (если n = 0, то f — нульместная функция).

Исходными объектами (сокращённо, по X. Карри, называемыми обами) в комбинаторной логике служат константы и переменные (множество переменных может быть пустым). Новые обы строятся из исходных и полученных ранее по правилу: если a и b — обы, то (ab) считается обом. Выделяются три константы, обозначающие индивидуальные функции (комбинаторы): два собственных комбинатора К и S, удовлетворяющих равенствам Kab = a и Sabc = ac (bc), где a, b и c — произвольные обы (скобки в обах восстанавливаются по ассоциации влево) и один дедуктивный комбинатор U как некоторый аналог формальной импликации или оператора функциональности. Эти три комбинатора позволяют заменить любое предложение логико-математических языков комбинацией (обом) из К, S и U и скобок, откуда и название «комбинаторная логика» (введённое Карри). Употребление же переменных вообще может быть исключено, что соответствует первоначальному замыслу М. И. Шейнфинкеля, X. Карри и А. Чёрча. К примеру, если A комбинатор такой, что Аху = x + y, а C комбинатор такой, что Cfxy = fyx [или в более обычных обозначениях: приложение комбинатора A к аргументам x, y даёт x + y; приложение комбинатора C к fxу) даёт f(yx)], то сумму y + x в этом случае можно выразить как САху. Тождество x + y = y + x выражается при этом в виде Аху = САху. И если [как это делается обычно в математике] трактовать тождественное равенство f(x₁, … xn) = g(x₁…, xn) как другое выражение для f = g (то есть считать, что функции f и g, относящие обе одни и те же объекты к одним и тем же значениям аргументов, отождествляются нами), то другим выражением для тождества x + y = y + x будет формула A = CA, не содержащая переменных.

Создателем комбинаторной логики является московский математик Моисей Ильич Шейнфинкель (1920). Он ввёл комбинаторы К, S и U, сформулировал и обосновал, используя указанные равенства для К и S, принцип комбинаторной полноты, более общий, чем канторовское неограниченное теоретико-множественное свёртывание. Шейнфинкель предложил один из первых способов уточнения интуитивного понятия алгоритма, определив по существу комбинаторные алгоритмы как вариант реализации вычислительной (алгоритмической) части дискретно-комбинаторной программы Г. В. Лейбница.

Независимо от Шейнфинкеля американские математики Карри и Чёрч получили аналогичные результаты. В их трудах комбинаторные алгоритмы представлены дедуктивно в виде доказуемо непротиворечивых исчислений негилбертовского типа. Таковы, в частности, ламбда-исчисления (λ-исчисления) Чёрча, эквивалентные чистой (без логических законов) комбинаторной логике Шейнфинкеля — Карри. Исчисления Шейнфинкеля — Чёрча — Карри оказались удачными теориями вычислений. Они дали толчок развитию теории рекурсий, различных видов алгоритмов, а в последнее время и информатики. Известны применения комбинаторной логики в теории доказательств, в семантике языков программирования, алгебре, топологии, теории категорий и других разделах современного знания.

Бестиповые исчисления Шейнфинкеля — Чёрча — Карри были введены прежде всего в расчёте на то, что их дедуктивные расширения станут основаниями математики и других наук. Пытаясь реализовать синтаксически дедуктивный комбинатор U, Карри и Чёрч построили также логико-математические исчисления гилбертовского типа, которые, однако, оказались противоречивыми: парадокс Клини — Россера (1936), парадокс Карри (1941). Следует отметить, что в парадоксе Карри из логических средств используются только имшшкативные, а правило modus ponens выступает как единственный логический источник противоречивости. Поскольку все известные дедуктивные системы гилбертовского типа либо бедны выразительными возможностями, либо противоречивы, обращаются к идее ступенчатых расширений. Ступенчатые системы комбинаторной логики строятся на основе комбинаторных алгоритмов путём последовательных расширений бестиповых непротиворечивых исчислений Шейнфинкеля — Чёрча — Карри, опираясь на принципы дедуктивной полноты — правила введения операторов (прежде всего логических) в сукцедент (в заключение выводимостей) и в антецедент (в посылки выводимостей).

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

Среди всех двухярусных систем выделяется A-система со всеми логическими операторами и оператором λ. Её правила объединяют два яруса в формальное исчисление (в соответствии с программой Гилберта), для которого доказываются теоремы о полноте (в смысле К. Гёделя, ср. его теоремы 1931 года о неполноте известных исчислений гилбертовского типа) и непротиворечивости (в классическом секвенциальном смысле). Эти правила выражаются следующим образом:

λ*:(ГΘ, a)(a → b)
ГΘ, a
λ*:(b → a)(a, ГΘ)
b, ГΘ
λ*:(ГΘ, a)(a → b)
ГΘ, b

Где a и b — обы, Г, Θ — это наборы обов, → и ⇒ — это символы секвенций первого и второго ярусов, алгоритмической (вычислительной) и дедуктивной (генценовской) соответственно. Говорят, что об a конвертируется в об b, если секвенция ab выводима в чистой комбинаторной логике (в исчислении Шейнфинкеля — Чёрча — Карри).

Все элементы языка теории множеств записываются как обы комбинаторной логики с точностью до конвертируемости. Так, атомарная формула ba представляется обом ba, по формуле C и переменной x строится новый терм (новое множество) как об λ хС, отражая тем самым исходный принцип Кантора: неограниченное образование новых множеств.

В классе всех выводов A-системы выделяется подкласс M всех выводов, в которых применения структурных и логических правил второго яруса ограничены описанными элементами теории множеств. В основе M лежат два принципа, характеризующие канторовскую («наивную») теорию множеств: неограниченное теоретико-множественное свёртывание и классическая логика предикатов первого порядка без ограничений, соответствующие двум ярусам A-системы. Класс M выступает как вариант непротиворечивой формализации канторовской теории множеств.

Широко известный парадокс Рассела (1902) отражается в классе M в виде выводов двух дедуктивных секвенций ⇒ D) и ⇒ ⌉D, где ⌉ — знак отрицания, a D — об: ∃λу П λx = (xy) (⌉(xx), представляющий частный случай известной схемы теоретико-множественного свёртывания, записанной на языке комбинаторной логики.

Библиография

  • Барендрегт Х. Ламбда-исчисление. Его синтаксис и семантика. — М., 1985.
  • Кузичев А. С. Об одной арифметически непротиворечивой λ-теории. — «Zeitschrift für Math. Logik und Grundlagen der Mathematik», 1983, Bd 29, H. 5.
  • Кузичев А. С. Вариант формализации канторовской теории множеств. — Доклады Российской Академии наук, 1999, том 369, № 6.
  • Кузичев А. С. Решение проблемы Гилберта по Колмогорову. — Доклады Российской Академии наук, 2000, том 371, № 3.
  • Кузичева З. А., Кузичевв А. С. Системы с бесконечной логикой и неограниченным принципом свёртывания. К 150-летию со дня рождения Г. Кантора. — В книге: Бесконечность в математике: философские и исторические аспекты. — М., 1997.
  • Яновская С. Л. Логика комбинаторная. — В книге: Философская энциклопедия. Том 3. — М., 1964.
  • Barendregt H. The Lambda Calculus: Its Syntax and Semantics, Amsterdam: 2ⁿᵈ edn, 1984.
  • Curry H. Functionality in Combinatory Logic. — Proceedings of the National Academy of Sciences of the USA, 20: 584–90, 1934.
  • Curry H., Feys R. Combinatory Logic, Vol. 1. — Amsterdam, 1958.
  • Hindley J., Seldin J. Introduction to Combinators and λ-Calculus. — London Mathematical Society Student Texts № 1. — Cambridge, 1986.
  • Kleene S., Rosser J. The Inconsistency of Certain Formal Logics. — Annals of Mathematics, 36: 630–6, 1935.
  • Rezus A. A Bibliography of Lambda-Calculi. Combinatory Logics and Related Topics. — Amsterdam, 1982.
  • Schönfmkel M. Über die Bausteine der Mathematischen Logik. — Math. Annalen, 1924, Bd 92.
  • Scott D. Data Types as Lattices. — SIAM Journal of Computing, 5: 522–87, 1976.
  • Seldin J. P., Hindley J. R. (eds.). Το Η. Β. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism. — L., 1980.
  • Sheffer H. M. A Set of Five Independent Postulates for Boolean Algebras, With Application To Logical Constants. — Transactions of the American Mathematical Society, 14: 481–8, 1913.
  • Stenlund, S. Combinators, λ-Terms and Proof Theory. — Dordrecht, 1972.
Выходные сведенияА. С. Кузичев. — Логика комбинаторная / Гума­нитар­ный портал: [Элект­рон­ный ресурс] // Центр гума­нитар­ных техно­логий, 2002–2025 (после­дняя редак­ция: 22.09.2025). URL: https://gtmarket.ru/concepts/7060

Логика: понятия и концепции

Базисные концепты

Новые концепты

ПорталГуманитарное пространство в рамках одного ресурса: гума­ни­тар­ные и соци­аль­ные науки, рынки гума­ни­тар­ных зна­ний, методов и техно­ло­гий, обще­ст­вен­ное раз­ви­тие, госу­дар­ст­вен­ные и кор­пора­тив­ные стра­тегии, управ­ле­ние, обра­зо­ва­ние, инсти­туты. Гума­нитар­ная биб­лио­тека, иссле­до­ва­ния и ана­ли­тика, рей­тинги и прог­нозы, тео­рии и кон­цеп­ции. Всё для изу­че­ния и про­ек­тиро­ва­ния гума­нитар­ного развития.