Kombinatorická logika

Kombinatorická logika  je odvětví matematické logiky , které se zabývá základními (to znamená, že nepotřebují vysvětlení a nejsou analyzovány) koncepty a metodami formálních logických systémů nebo kalkulů [1] [2] . V diskrétní matematice je kombinatorická logika blízko příbuzná počtu lambda , protože popisuje výpočetní procesy.

Od svého vzniku jsou kombinatorická logika a lambda počet klasifikovány jako neklasické logiky . Jde o to, že kombinatorická logika vznikla ve 20. letech a lambda kalkul ve 40. letech jako odvětví metamatematiky s poměrně přesně definovaným účelem – dát matematice základy. To znamená, že po vybudování požadované "aplikované" matematické teorie - předmětové teorie - která odráží procesy nebo jevy v reálném vnějším prostředí, lze použít "čistou" metateorii jako skořápku k objasnění možností a vlastností předmětové teorie. . Brzy se také ukázalo, že oba tyto systémy lze považovat za programovací jazyky (viz také kombinatorické programování ).

K dnešnímu dni se oba tyto jazyky nejen staly základem pro celou masu výzkumu v oblasti informatiky , ale jsou také široce používány v teorii programování. Růst výpočetního výkonu počítačů vedl k automatizaci významné části teoretických (logických a matematických) znalostí a kombinatorická logika spolu s lambda kalkulem je uznávána jako základ pro uvažování z hlediska objektů. .

Základní pojmy

V kombinační logice jsou základními pojmy jednomístná funkce a operace aplikace funkce na argument ( application ). Pojem funkce je brán jako primární ve vztahu k pojmu množina . Funkce je chápána obecně a může pracovat s objekty stejné úrovně jako argumenty a hodnoty. Protože argumentem funkce může být funkce, lze vícemístnou funkci redukovat na funkci s jedním místem [3] .

Kombinátor je funkce , která splňuje rovnost

kde ( ) jsou nějaké funkce, X  je objekt vytvořený z funkcí pomocí aplikace [3] .

Libovolný kombinátor lze vyjádřit pomocí dvou kombinátorů S a K definovaných následujícími rovnostmi [3] :

Vzhledem k výrazu lambda můžete vždy vytvořit aplikační výraz . To vyžaduje pouze dva kombinátory: S a K . Ve formě lambda výrazů: , . To znamená, že kombinatorickou logiku definovanou na těchto kombinatorických objektech lze považovat za model lambda počtu [4] .

Další příklady kombinátorů (v zápisu lambda kalkulu) jsou funkce identity , snadno vyjádřené pomocí S a K [4] :

a kombinátor s pevnou čárkou nebo Y-kombinátor :

Historie

V roce 1920 byly kombinátory jako speciální matematické entity [5] původně představeny M. Sheinfinkelem [6] . O pár let později je nezávisle znovu objevil H. Curry [7] , který od té doby udělal velké pokroky v kombinatorické logice (ačkoli k této práci v různých dobách přispěli i jiní badatelé, jako Rosser). Téměř ve stejnou dobu zahájili Church , Rosser a Kleene vývoj konverze λ.

Od 70. let 20. století se kombinátory používají třemi hlavními způsoby: zaprvé k sestavení logických systémů založených na abstraktním zápisu operace; za druhé v teorii důkazů jako základu pro záznam konstruktivních funkcí různého typu; za třetí, při konstrukci a analýze některých programovacích jazyků v informatice .

Kategorická kombinatorická logika

V rámci kombinatorické logiky je vybudována speciální verze teorie počítání, nazývaná kategorický abstraktní stroj . K tomu je v úvahu uveden speciální fragment kombinatorické logiky - kategorická kombinatorická logika [8] . Je reprezentován sadou kombinátorů, z nichž každý má nezávislou hodnotu jako instrukce programovacího systému. Do kombinatorické logiky je tedy zabudována ještě jedna užitečná aplikace – programovací systém založený na kartézské uzavřené kategorii (fc). To vám umožní znovu promyslet spojení mezi operátorem a aplikačním programovacím stylem na nové úrovni.

Illativní kombinatorická logika

Pomocí konceptu objektů jako abstraktních matematických entit s určitými substitučními vlastnostmi je možné budovat systémy logického uvažování . Nejznámější z těchto systémů je založen na kombinátorech.

Logika založená na kombinátorech nebo illativní kombinatorická logika je postavena na teorii kombinátorů nebo lambda počtu, rozšířené o další konstanty - zvláštní konstanty - spolu s odpovídajícími axiomy a pravidly inference, které poskytují prostředky k deduktivnímu závěru.

Viz také

• Aplikační výpočetní systémy
• Funkcionální programování
• Typovaný lambda kalkul
• SKI kalkul

Poznámky

1. ↑ Ed. F. V. Konstantinová. Kombinatorická logika // Filosofická encyklopedie: v 5 svazcích . - M  .: Sovětská encyklopedie, 1960-1970.
2. ↑ Kondakov, 1971 .
3. ↑ 1 2 3 MES, 1988 , str. 275-276.
4. ↑ 1 2 Field, Harrison, 1993 , str. 291-293.
5. ↑ Cardone F., Hindley J. R. Historie lambda kalkulu a kombinátorů ( Archivováno 10. října 2011 na Wayback Machine ), v Handbook of the History of Logic, Volume 5, DM Gabbay and J. Woods (eds) (Amsterdam: Elsevier Co ., objevit se).
6. ↑ Schonfinkel M. Uber die Baustein der mathematischen Logik. — Matematika. Annalen, sv. 92, 1924, str. 305-316.
7. ↑ Curry H. B. Grundlagen der kombinatorischen Logik. American Journal of Mathematics, 52:509-536, 789-834, 1930.
8. ↑ Curien P.-L. Kategorická kombinatorická logika. — LNCS, 194, 1985, s. 139-151.

Literatura

• Wolfenhagen VE Kombinatorická logika v programování. Výpočty s objekty v příkladech a úlohách. - 2. vyd. - M. : AO Center YurInfoR, 2003. - 204 s. — ISBN 5-89158-101-9 .
• Kondakov N. I. Logický slovník / Gorsky D. P. - M . : Nauka, 1971. - 656 s.
• Field A., Harrison P. Funkční programování = Funkční programování. — M .: Mir, 1993. — 637 s. — ISBN 5-03-001870-0 .
• Matematický encyklopedický slovník / Yu. V. Prochorov. - M. : Sovětská encyklopedie, 1988. - 847 s.
• A. S. Kuzichev. Kombinatorická logika  // Nová filozofická encyklopedie  : ve 4 svazcích  / předchozí. vědecky vyd. rada V. S. Stepina . — 2. vyd., opraveno. a doplňkové - M .  : Myšlenka , 2010. - 2816 s.

Slovníky a encyklopedie	Velký Rus
V bibliografických katalozích	BNF : 119473722 GND : 4164750-6 J9U : 987007543265905171 LCCN : sh85028814 SUDOC : 027430677