B,C,K,W系统

维基百科,自由的百科全书
跳转至: 导航搜索

1930年哈斯凱爾·加里在他的博士论文《Grundlagen der kombinatorischen Logik》中提议了一个組合子邏輯系統。它带有基本组合子BCKW(采用了现在的命名)。

定義[编辑]

  • B x y z = x(y z)
  • C x y z = x z y
  • K x y = x
  • W x y = x y y

直觉上,

  • B x y是函数复合x o y
  • C x y z交换参数y和z
  • K x y忽略第二个参数y
  • W x y复制参数y

在當代,只有兩個基本組合子KSSKI組合子演算成為了組合子邏輯的規范方式。B, CW可以使用SK表達為如下:

  • B = S (K S) K
  • C = S (S (K (S (K S) K)) S)(K K)
  • K = K
  • W = S SK (S K K))

在另一個方向上,SKI可以依據B,C,K,W定義為:

  • I = W K
  • K = K
  • S = B (B (B W) C) (B B)[1] = B (B B B W B) C

参见[编辑]

引用[编辑]

注釋[编辑]

  1. ^ Raymond Smullyan(1994)Diagonalization and Self-Reference. Oxford Univ. Press: 344, 3.6(d).

外部鏈接[编辑]