Система B, C, K, W - B, C, K, W system

В B, C, K, W система является вариантом комбинаторная логика который принимает за примитивы комбинаторы B, C, K, и W. Эта система была открыта Хаскелл Карри в его докторской диссертации Grundlagen der kombinatorischen Logik, результаты которого изложены в Curry (1930).

Определение

Комбинаторы определяются следующим образом:

B x y z = Икс (у г)
C x y z = х г у
K х у = Икс
W х у = x y y

Интуитивно

B x y z это сочинение из аргументы Икс и у применительно к аргументу z;
C x y z меняет местами аргументы у и z;
K х у отвергает аргумент у;
W х у дублирует аргумент у.

Подключение к другим комбинаторам

В последние десятилетия Расчет комбинатора SKI, с двумя примитивными комбинаторами, K и S, стало каноническим подходом к комбинаторная логика. ДО Н.Э, и W можно выразить через S и K следующее:

B = S (K S) K
C = S (S (K (S (K S) K)) S) (К К)
K = K
W = SS (S K)

С другой стороны, SKI можно определить в терминах B, C, K, W как:

я = Вт К
K = K
S = B (B (B W) C) (B B) = B (B W) (Б Б В).^[1]

Связь с интуиционистской логикой

Комбинаторы B, C, K и W соответствуют четырем хорошо известным аксиомам сентенциальная логика:

AB: (B → C) → ((А → B) → (А → C)),

AC: (А → (B → C)) → (B → (А → C)),

АК: А → (B → А),

AW: (А → (А → B)) → (А → B).

Применение функции соответствует правилу modus ponens:

Депутат: из А и А → B сделать вывод B.

Аксиомы AB, AC, АК и AW, и правило Депутат завершены для имплицитного фрагмента интуиционистская логика. Для того, чтобы комбинаторная логика была моделью:

В имплицитный фрагмент из классическая логика, потребует комбинаторного аналога закон исключенного среднего, например, Закон Пирса;
Полная классическая логика, потребует комбинаторного аналога сентенциальной аксиомы F → А.

Смотрите также

Примечания

^ Раймонд Смуллян (1994) Диагонализация и самоотношение. Oxford Univ. Нажмите: 344, 3.6 (d) и 3.7.

внешняя ссылка

Кинан, Дэвид С. (2001) "Рассекать пересмешника. "
Ратман, Крис "Комбинатор Птицы. "
""Комбинаторы перетаскивания и перетаскивания (Java-апплет). "

[1] Раймонд Смуллян (1994) Диагонализация и самоотношение. Oxford Univ. Нажмите: 344, 3.6 (d) и 3.7.

[1]