Kombinatorial məntiq

Kombinatorial məntiq — formal məntiqi sistemlərin və ya kalkulyasiyanın əsasları (yəni izah edilməli və təhlil edilməməsi lazım olmayan) ilə əlaqəli riyazi məntiqin bir istiqaməti^[1]^[2].

Diskret riyaziyyatda kombinatorial məntiq hesablama proseslərini izah etdiyi üçün lambda hesablanması ilə sıx əlaqəlidir. Yarandığı gündən bu yana kombinatorial məntiq və lambda hesablamaları qeyri-klassik məntiq kimi təsnif edilmişdir. Məsələ burasındadır ki, kombinatorial məntiq 1920-ci illərdə və lambda hesablamaları — 1940-cı illərdə kifayət qədər müəyyən edilmiş bir məqsədi olan metamatikanın bir qolu kimi — riyaziyyata əsas vermək üçün yaranmışdı. Bu o deməkdir ki, həqiqi xarici mühitdə baş verən prosesləri və hadisələri əks etdirən, tələb olunan "tətbiq olunan" riyazi nəzəriyyə — mövzu nəzəriyyəsi quraraq, "saf" metatoriyasını mövzu nəzəriyyəsindən imkanlarını və xüsusiyyətlərini müəyyənləşdirmək üçün bir qabıq kimi istifadə etmək olar. Tezliklə məlum oldu ki, bu sistemlərin hər ikisini proqramlaşdırma dilləri kimi qəbul etmək olar (bax kombinatorial proqramlaşdırma).

İndiyə qədər bu dillərin hər ikisi yalnız kompüter elmləri sahəsində bütün tədqiqat kütləsi üçün əsas olmur, həm də proqramlaşdırma nəzəriyyəsində geniş istifadə olunur. Kompüterlərin hesablama gücünün artması nəzəri (məntiqi və riyazi) biliklərin əhəmiyyətli bir hissəsinin avtomatlaşdırılmasına və lambda hesablamaları ilə birlikdə kombinatorial məntiq obyektlər baxımından düşüncə üçün əsas kimi qəbul edilir.

Əsas anlayış

Kombinatorial məntiqdə tək yerlik bir funksiya və bir funksiyanın bir arqumentə (tətbiqə) tətbiq olunması əsas anlayışlardır. Funksiya ümumiyyətlə başa düşülür və arqumentlər və dəyərlər kimi bərabər səviyyədə olan obyektlərləişləyə bilər. Bir funksiya dəlil bir funksiya ola bilər, çox yerlik funksiya təkə endirilə bilər^[3].

Kombinator bərabərliyi təmin edən $f$ funksiyasıdır:

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

,

$g_{1},g_{2},\dots ,g_{n}$ ( $n\geq 1$ )-nın bəzi funksiyaları, X — tətbiqi ilə funksiyalardan qurulmuş bir obyektdir^[3].

İstənilən kombinator aşağıdakı bərabərliklərlə təyin olunan iki kombinator S və K baxımından ifadə edilə bilər^[3]:

Sxyz=xz(yz)

(distribyutor)

Kxy=x

(tətil)

Bu lambda ifadəsini istifadə edərək həmişə tətbiqli bir ifadə qura bilərsiniz. Bunun üçün yalnız iki kombinator lazımdır: S və K. Lambda ifadələri şəklində: $K=\lambda x.\lambda y.x$ , $S=\lambda f.\lambda g.\lambda x.fx(gx)$ . Yəni bu kombinatorial obyektlərdə müəyyən edilmiş kombinatorial məntiq lambda hesablama modeli sayıla bilər^[4].

Kombinatorların digər nümunələri (lambda hesablama girişində) şəxsiyyət funksiyası kimi xidmət edə bilən, S və K baxımından asanlıqla ifadə olunur^[4]:

I=\lambda x.x=SKK

və sabit nöqtəli kombinator və ya Y —kombinator:

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

Tarixi

1920-ci ildə kombinatorlar xüsusi riyazi varlıqlar^[5] kimi əvvəlcə M. Şeyinfinkel tərəfindən təqdim edildi^[6]. Bir neçə il sonra, Harri Haskel^[7]tərəfindən müstəqil olaraq yenidən kəşf edildi, bunun sayəsində kombinatorial məntiqdə əsas irəliləyişlər edildi (baxmayaraq ki, Rosser kimi digər tədqiqatçılar da müxtəlif vaxtlarda bu işdə iştirak etmişdilər). Demək olar ki, eyni zamanda, Cyorç Alonzo, Rosser və Kline tərəfindən λ-dönüşümünün inkişafı başladı.

1970-ci illərdən bəri kombinatorlar üç əsas cəhətdən istifadə edilmişdir:birincisi, bir əməliyyatın mücərrəd qeydinə əsaslanan məntiqi sistemlərin qurulması üçün;ikincisi, dəlil nəzəriyyəsində müxtəlif növ konstruktiv funksiyaların qeyd edilməsi üçün əsas kimi; üçüncüsü, kompüter elmində müəyyən proqramlaşdırma dillərinin qurulması və təhlilində.

Kateqoriyalı kombinatorial məntiq

Kombinatorial məntiq çərçivəsində, kateqoriyalı mücərrəd maşın adlanan hesablama nəzəriyyəsinin xüsusi bir versiyası qurulur. Bunun üçün kombinatorial məntiqin xüsusi bir parçası təqdim olunur — kateqoriyalı kombinatorial məntiq^[8]. Hər biri bir proqramlaşdırma sisteminin göstərişi olaraq müstəqil məna daşıyan kombinator dəsti ilə təmsil olunur. Beləliklə, başqa bir faydalı tətbiq kombinatorial məntiqə — bir Kartesian qapalı kateqoriyaya əsaslanan proqramlaşdırma sisteminə daxil edilmişdir. Bu, operator və tətbiqetmə proqramlaşdırma tərzi arasındakı əlaqəni yeni bir səviyyədə yenidən düşünməyə imkan verir.

Təsviri kombinatorial məntiq

Müəyyən permutasiya xüsusiyyətlərinə malik olan mücərrəd riyazi varlıqlar kimi obyektlərin anlayışlarından istifadə edərək məntiqi əsaslandırma sistemi qura bilərik. Belə sistemlər arasında ən məşhurları kombinatorlara əsaslanır.

Kombinatorial məntiq, ya da illatativ kombinatorial məntiq, detektiv təsir bağışlayan bir vasitə təmin edən uyğun aksiomalar və infer qaydaları ilə birlikdə əlavə sabitlər — ekstra-sabitlər tərəfindən uzadılmış kombinatorların və ya lambda hesabmalarının nəzəriyyəsindən qurulmuşdur.

Həmçinin bax

İstinadlar

↑ "Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960—1970". 2019-12-16 tarixində arxivləşdirilib. İstifadə tarixi: 2019-12-16.
↑ Кондаков, 1971
↑ ¹ ² ³ МЭС, 1988
↑ ¹ ² Филд, Харрисон, 1993
↑ Cardone F., Hindley J. R. History of lambda calculus and combinators Arxivləşdirilib 2011-10-10 at the Wayback Machine, in Handbook of the History of Logic, Volume 5, D M Gabbay and J Woods (eds) (Amsterdam: Elsevier Co., to appear).
↑ Schonfinkel M. Uber die Baustein der mathematischen Logik. — Math. Annalen, vol. 92, 1924, pp.~305–316.
↑ Curry H. B. Grundlagen der kombinatorischen Logik. American Journal of Mathematics, 52:509–536, 789–834, 1930.
↑ Curien P.-L. Categorical combinatory logic. — LNCS, 194, 1985, pp.~139–151.

Ədəbiyyat

Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах (2-е изд.). М.: АО Центр ЮрИнфоР. 2003. ISBN 5-89158-101-9.
Кондаков Н. И. Логический словарь. М.: Наука. Горский Д. П. 1971.
Филд А., Харрисон П. Функциональное программирование. М.: Мир. 1993 [Functional Programming]. ISBN 5-03-001870-0.
Математический энциклопедический словарь. М.: Советская энциклопедия. Ю. В. Прохоров. 1988.

Xarici keçidlər

[1] "Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960—1970". 2019-12-16 tarixində arxivləşdirilib. İstifadə tarixi: 2019-12-16.

[FOOTNOTEКондаков1971-2] Кондаков, 1971

[FOOTNOTEМЭС1988-3] ¹ ² ³ МЭС, 1988

[FOOTNOTEФилд,_Харрисон1993-4] ¹ ² Филд, Харрисон, 1993

[5] Cardone F., Hindley J. R. History of lambda calculus and combinators Arxivləşdirilib 2011-10-10 at the Wayback Machine, in Handbook of the History of Logic, Volume 5, D M Gabbay and J Woods (eds) (Amsterdam: Elsevier Co., to appear).

[6] Schonfinkel M. Uber die Baustein der mathematischen Logik. — Math. Annalen, vol. 92, 1924, pp.~305–316.

[7] Curry H. B. Grundlagen der kombinatorischen Logik. American Journal of Mathematics, 52:509–536, 789–834, 1930.

[8] Curien P.-L. Categorical combinatory logic. — LNCS, 194, 1985, pp.~139–151.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]