Оглавление
Переписка Карри и Говарда
-
Основы соответствия Карри-Говарда
- Соответствие Карри-Говарда связывает логические формулы с типами и доказательствами в лямбда-исчислении.
- Оно позволяет выразить логические утверждения через лямбда-термины и доказать их эквивалентность.
-
Связь с интуиционистской логикой
- Интуиционистская логика использует конструктивные методы доказательства, в отличие от классической логики.
- Соответствие Карри-Говарда позволяет выразить интуиционистские доказательства в терминах лямбда-терминов.
-
Связь с типизированным лямбда-исчислением
- Типизированное лямбда-исчисление расширяет лямбда-исчисление, добавляя типы к лямбда-термам.
- Соответствие Карри-Говарда связывает типы в типизированном лямбда-исчислении с логическими формулами.
-
Примеры соответствия Карри-Говарда
- Комбинатор тождеств в лямбда-исчислении соответствует доказательству α → α в интуиционистской логике.
- Комбинатор композиции в лямбда-исчислении соответствует доказательству (β → α) → (γ → β) → γ → α в интуиционистской логике.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.