Systém B, C, K, W. - B, C, K, W system - Wikipedia

The B, C, K, W systém je variantou kombinační logika který bere jako primitivní kombinátory B, C, K., a Ž. Tento systém objevil Haskell Curry ve své disertační práci Grundlagen der kombinatorischen Logik, jejíž výsledky uvádí Curry (1930).

Definice

Kombinátory jsou definovány takto:

• B x y z = X (y z)
• C x y z = x z y
• K. x y = X
• Ž x y = x y y

Intuitivně,

• B x y z je složení z argumenty X a y aplikován na argument z;
• C x y z zamění argumenty y a z;
• K. x y zahodí argument y;
• Ž x y duplikuje argument y.

Připojení k jiným kombinátorům

V posledních desetiletích SKI kombinátorový počet, pouze se dvěma primitivními kombinátory, K. a S, se stal kanonickým přístupem k kombinační logika. PŘED NAŠÍM LETOPOČTEM, a Ž lze vyjádřit pomocí S a K. jak následuje:

• B = S (K S) K.
• C = S (S (K. (S (K S) K.)) S) (K K.)
• K. = K.
• Ž = S S (S K.)

Když půjdeme opačným směrem, SKI lze definovat z hlediska B, C, K, W jako:

• Já = W K.
• K. = K.
• S = B (B (B W) C) (B B) = B (B W) (B B C).^[1]

Napojení na intuitivní logiku

Kombinátory B, C, K. a Ž odpovídají čtyřem známým axiómům sentenciální logika:

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

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

AK: A → (B → A),

AW: (A → (A → B)) → (A → B).

Aplikace funkcí odpovídá pravidlu modus ponens:

MP: z A a A → B usoudit B.

Axiomy AB, AC, AK a AWa pravidlo MP jsou kompletní pro implikační fragment souboru intuicionistická logika. Aby kombinatorická logika měla jako model:

• The implikační fragment z klasická logika, by vyžadovalo kombinační analog k zákon vyloučeného prostředku, např. Peirceův zákon;
• Kompletní klasická logika, by vyžadovalo kombinační analog k sentenciálnímu axiomu F → A.

Viz také

• Kombinovaná logika
• SKI kombinátorový počet
• Lambda kalkul
• Vysmívat ptáčka

Poznámky

Reference

• Hendrik Pieter Barendregt (1984) Lambda kalkul, jeho syntax a sémantika, Sv. 103 palců Studie v logice a základech matematiky. Severní Holandsko. ISBN  0-444-87508-5
• Haskell Curry (1930) „Grundlagen der kombinatorischen Logik,“ Amer. J. Math. 52: 509–536; 789–834.
• Curry, Haskell B.; Hindley, J. Roger; Seldin, Jonathan P. (1972). Kombinovaná logika. Sv. II. Amsterdam: Severní Holandsko. ISBN  0-7204-2208-6.
• Raymond Smullyan (1994) Diagonalizace a vlastní reference. Oxford Univ. Lis.

externí odkazy

• Keenan, David C. (2001) "Pitvat ptáčka. "
• Rathman, Chris, "Combinator Birds. "
• ""Drag 'n' Drop kombinátory (Java applet). "