Sistema B, C, K, W

El sistema B, C, K, W és una variant de llògica combinatòria que pren com a primitives als combinadores B, C, K, i W. Este sistema va ser propost originalment pel matemàtic nortamericà Haskell Curry en la seua tesis doctoral Grundlagen der kombinatorischen Logik (Fonaments de la llògica combinatòria).

Definició

Els combinadores es definixen com seguix:

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

De forma intuïtiva,

• B x i z és la composició dels arguments x i i aplicada a l'argument z;
• C x i z intercanvia els arguments i i z;
• K x i descarta l'argument i;
• W x i duplica l'argument i.

Conexió en atres combinadores

En les últimes décades, el càlcul combinatori SKI, en sol dos combinadores primitius, K i S, s'ha convertit en l'enfocament canònic de la llògica combinatòria. B, C i W poden expressar-se en térmens de S i K com seguix:

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

En l'atra direcció, SKI pot definir-se en térmens de B, C, K, W com:

• I = W K
• K = K
• S = B (B (B W) C) (B B) = B (B W) (B B C).

Vore també

• Llògica combinatòria
• Càlcul lambda

Bibliografia

• Hendrik Pieter Barendregt (1984) The Lambda Calculus, Its Syntax and Semantics, Vol. 103 in Studies in Logic and the Foundations of Mathematics. North-Holland. ISBN 0-444-87508-5
• Haskell Curry (1930) "Grundlagen der kombinatorischen Logik," Amer. J. Math. 52: 509–536; 789–834.
• (1972) Combinatory Logic (vol. Vol. II), Amsterdam: North Holland. ISBN 0-7204-2208-6.
• Raymond Smullyan (1994) Diagonalization and Self-Reference. Oxford Univ. Press.