2.1 Элементарная комбинаторная логика
Системы комбинаторов предназначены для выполнения тех же функций, что и системы λ-конверсии, но без использования связанных
переменных. Поэтому технические сложности, связанные с подстановкой и конгруэнтностью, исчезают.
2.1.1 Понятие комбинатора
Рассмотрим коммутативный закон сложения в арифметике:
∀x, y.x+y = y +x
Этот закон можно переписать без использования связанных перемен-
ных x и y, определив
∀x, y.A(x, y) = x+y
и введя оператор C:
∀f, x, y.(C(f))(x, y) = f(y, x).
Этот закон примет вид:
CA = A.
Оператор C может быть назван комбинатором.
Упражнение 1. Записать коммутативный закон умножения без ис-
пользования переменных. |