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

В 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: (BC) → ((АB) → (АC)),
AC: (А → (BC)) → (B → (АC)),
АК: А → (BА),
AW: (А → (АB)) → (АB).

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

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

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

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

Примечания

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

Рекомендации

  • Хендрик Питер Барендрегт (1984) Лямбда-исчисление, его синтаксис и семантика, Vol. 103 дюйм Исследования по логике и основам математики. Северная Голландия. ISBN  0-444-87508-5
  • Хаскелл Карри (1930) "Grundlagen der kombinatorischen Logik", Амер. J. Math. 52: 509–536; 789–834.
  • Карри, Хаскелл Б.; Хиндли, Дж. Роджер; Селдин, Джонатан П. (1972). Комбинаторная логика. Vol. II. Амстердам: Северная Голландия. ISBN  0-7204-2208-6.
  • Раймонд Смуллян (1994) Диагонализация и самооценка. Oxford Univ. Нажмите.

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