Kombinatorisk logik

Kombinatorisk logik er en gren af matematisk logik , der beskæftiger sig med grundlæggende (dvs. ikke behov for forklaring og ikke analyseret) begreber og metoder for formelle logiske systemer eller kalkuler [1] [2] . I diskret matematik er kombinatorisk logik tæt forbundet med lambdaregning , da den beskriver beregningsprocesser.

Siden deres begyndelse er kombinatorisk logik og lambda-regning blevet klassificeret som ikke-klassiske logikker . Pointen er, at kombinatorisk logik opstod i 1920'erne, og lambdaregning i 1940'erne som en gren af metamatematikken med et ret veldefineret formål - at give matematikken grundlag. Det betyder, at efter at have konstrueret den nødvendige "anvendte" matematiske teori - fagteorien - som afspejler processerne eller fænomenerne i det virkelige ydre miljø, kan man bruge den "rene" metateori som en skal til at afklare fagteoriens muligheder og egenskaber. . Det viste sig også hurtigt, at begge disse systemer kunne betragtes som programmeringssprog (se også kombinatorisk programmering ).

Til dato er begge disse sprog ikke kun blevet grundlaget for hele massen af forskning inden for datalogi , men er også meget brugt i programmeringsteori. Væksten i computerkraft har ført til automatisering af en betydelig del af teoretisk (logisk og matematisk) viden, og kombinatorisk logik, sammen med lambdaregning, anerkendes som grundlaget for ræsonnement i form af objekter. .

Grundlæggende begreber

I kombinatorisk logik er de grundlæggende begreber en et -steds funktion og operationen med at anvende en funktion til et argument ( applikation ). Begrebet en funktion tages som primært i forhold til begrebet en mængde . En funktion forstås på en generel måde og kan operere med objekter på samme niveau som argumenter og værdier. Da argumentet for en funktion kan være en funktion, kan en mangestedsfunktion reduceres til en etstedsfunktion [3] .

En kombinator er en funktion , der tilfredsstiller ligestillingen $f$

fg_{1}g_{2}\dots g_{n}=(\dots ((fg_{1})g_{2})\dots g_{n})=X,

hvor ( ) er nogle funktioner, X er et objekt konstrueret ud fra funktioner ved hjælp af applikation [3] . $g_1, g_2, \dots, g_n$ $n\geqslant 1$

Enhver kombinator kan udtrykkes som to kombinatorer S og K defineret af følgende ligheder [3] :

Sxyz=xz(yz)

( distributør ),

kxy=x

( angriber ).

Med et lambdaudtryk kan du altid bygge et anvendeligt udtryk . Dette kræver kun to kombinatorer: S og K . I form af lambda-udtryk: , . Det vil sige, at den kombinatoriske logik defineret på disse kombinatoriske objekter kan betragtes som en model af lambda-regningen [4] . $K = \lambda x.\lambda yx$ $S=\lambda f.\lambda g.\lambda x.fx(gx)$

Andre eksempler på kombinatorer (i notationen af lambda-regningen) er identitetsfunktionen , let udtrykt i form af S og K [4] :

I = \lambda xx = SKK

og fastpunktskombinatoren eller Y-kombinatoren :

Y=\lambda h.((\lambda xh(xx))(\lambda xh(xx))).

Historie

I 1920 blev kombinatorer som specielle matematiske entiteter [5] oprindeligt introduceret af M. Sheinfinkel [6] . Et par år senere blev de uafhængigt genopdaget af H. Curry [7] , som siden har gjort store fremskridt inden for kombinatorisk logik (selvom andre forskere, såsom Rosser, også har bidraget til dette arbejde på forskellige tidspunkter). Næsten på samme tid begyndte Church , Rosser og Kleene udviklingen af λ-konverteringen.

Siden 1970'erne er kombinatorer blevet brugt på tre hovedmåder: For det første til at bygge logiske systemer baseret på en abstrakt notation af en operation; for det andet i teorien om beviser som grundlag for registrering af konstruktive funktioner af forskellige typer; for det tredje i konstruktion og analyse af nogle programmeringssprog i datalogi .

Kategorisk kombinatorisk logik

Inden for rammerne af kombinatorisk logik bygges en særlig version af beregningsteorien, kaldet den kategoriske abstrakte maskine . Til dette introduceres et særligt fragment af kombinatorisk logik i betragtning - kategorisk kombinatorisk logik [8] . Det er repræsenteret af et sæt af kombinatorer, som hver har en uafhængig værdi som en instruktion af et programmeringssystem. Således er endnu en nyttig applikation indbygget i kombinatorisk logik - et programmeringssystem baseret på en kartesisk lukket kategori (fc). Dette giver dig mulighed for at gentænke forbindelsen mellem operatøren og den applikative programmeringsstil på et nyt niveau.

Illativ kombinatorisk logik

Ved at bruge begrebet objekter som abstrakte matematiske entiteter med visse substitutionsegenskaber er det muligt at bygge systemer med logisk ræsonnement . Den mest berømte blandt sådanne systemer er baseret på kombinatorer.

Logik baseret på kombinatorer, eller illativ kombinatorisk logik , er bygget ud fra teorien om kombinatorer eller lambdaregning, udvidet med yderligere konstanter - ekstra konstanter - sammen med de tilsvarende aksiomer og inferensregler, som giver et middel til deduktiv inferens.

Se også

Noter

↑ Udg. F. V. Konstantinova. Kombinatorisk logik // Philosophical Encyclopedia: i 5 bind . - M . : Sovjetisk encyklopædi, 1960-1970.
↑ Kondakov, 1971 .
↑ 1 2 3 MES, 1988 , s. 275-276.
↑ 1 2 Field, Harrison, 1993 , s. 291-293.
↑ Cardone F., Hindley J. R. History of lambda calculus and combinators ( arkiveret 10. oktober 2011 på Wayback Machine ), i Handbook of the History of Logic, bind 5, DM Gabbay og J. Woods (red) (Amsterdam: Elsevier Co. ., vises).
↑ Schonfinkel M. Uber die Baustein der mathematischen Logik. — Matematik. Annalen, bd. 92, 1924, s. 305-316.
↑ Curry H. B. Grundlagen der kombinatorischen Logik. American Journal of Mathematics, 52:509-536, 789-834, 1930.
↑ Curien P.-L. Kategorisk kombinatorisk logik. — LNCS, 194, 1985, s. 139-151.

Litteratur

Wolfenhagen VE Kombinatorisk logik i programmering. Beregninger med objekter i eksempler og opgaver. - 2. udg. - M . : AO Center YurInfoR, 2003. - 204 s. — ISBN 5-89158-101-9 .
Kondakov N. I. Logisk ordbog / Gorsky D. P. - M . : Nauka, 1971. - 656 s.
Field A., Harrison P. Funktionel programmering = Funktionel programmering. — M .: Mir, 1993. — 637 s. — ISBN 5-03-001870-0 .
Matematisk encyklopædisk ordbog / Yu. V. Prokhorov. - M . : Soviet Encyclopedia, 1988. - 847 s.
A. S. Kuzichev. Kombinatorisk logik // New Philosophical Encyclopedia : i 4 bind / prev. videnskabeligt udg. råd fra V. S. Stepin . — 2. udg., rettet. og yderligere - M . : Tanke , 2010. - 2816 s.

Ordbøger og encyklopædier	Stor russer
I bibliografiske kataloger	BNF : 119473722 GND : 4164750-6 J9U : 987007543265905171 LCCN : sh85028814 SUDOC : 027430677