Корисник:StasaRadosavljevic/Увод у логичко програмирање

Логичко програмирање је парадигма програмирања која користи логику за решавање проблема. У овом типу програмирања, програмер дефинише правила и чињенице, док се одговори на специфичне проблеме изводе помоћу логичких дедукција. За разлику од процедуралних или објекно-оријентисаних језика, где се пише конкретан алгоритам, логички програми дефинишу само шта треба да буде тачно, а не како то постићи.

Најпопуларнији језик за логичко програмирање је Пролог, који користи логичке изразе за решавање проблема помоћу унификације и правила закључивања.

Историјат логичког програмирања

Развој логичког програмирања сеже до фундаменталних принципа формалне логике и раних радова из области вештачке интелигенције и рачунарских наука. Ево кључних тренутака у његовом историјском развоју:

Развој формалне логике
Основе логичког програмирања леже у формалној логици, области коју су утемељили математичари попут Gottloba Фрегеа, Бертранда Russella и Alfreda North Whiteheada крајем 19. и почетком 20. века. Њихов рад на симболичкој логици, математичкој логици и логичкој дедукцији поставио је темеље за рачунарску логику и аутоматско закључивање.

Тарски и семантика логике
Пољски математичар Алфред Тарски дао је допринос развоју формалне семантике за логику 1930-их година. Његова истраживања о моделима, појму истине и формулацији значења логичких израза утицала су на каснији развој логичких језика и теорије програмирања.

Аутоматско закључивање и вештачка интелигенција
Током 1950-их и 1960-их година, интерес за аутоматско закључивање и вештачку интелигенцију нагло је порастао. Математичари и информатичари су истраживали могућности рачунара да решавају проблеме коришћењем дедуктивне логике. Ови напори су допринели настанку дисциплина као што су експертни системи и алгоритми засновани на претрази.

Креирање Пролога (1972)
Логичко програмирање добија практичан облик 1972. године, када Алаин Цолмерауер и његов истраживачки тим у Марсеју развијају Пролог, први језик за логичко програмирање. Пролог (скраћеница од "PROgrammation en LOGique") је замишљен као језик за решавање сложених лингвистичких проблема и био је инспирисан радовима Роберта Kowalskog, једног од пионира логичког програмирања.

Јапански пројекат за вештачку интелигенцију (1980-их)
У периоду 1980-их, јапанска влада покренула је пројекат „Рачунари пете генерације“, са циљем развоја напредних рачунарских система заснованих на логичком програмирању и вештачкој интелигенцији. Пролог је био језгро овог пројекта, чиме је додатно подстакнут интерес за примену логичког програмирања у сложеним експертизама.

Развој Даталог-а и других логичких језика
Од 1980-их година надаље, развијани су и други логички језици, попут Даталог-а, који су оптимизовани за рад са релацијама и рад са базама података. Логички језици су прилагођавани и проширени у области рада са базама података и сложених упита.

Логичко програмирање данас
Данас, логичко програмирање остаје релевантно у специфичним областима као што су семантички веб, базе података, аналитика података и експертни системи. Пролог се и даље користи, док су принципи логичког програмирања уткани у савремене системе за рад са подацима, вештачку интелигенцију и машинско учење.

Основни концепти логичког програмирања

Логичко програмирање заснива се на неколико кључних концепата, који укључују:

Факте (Facts): Чињенице представљају основне истине у систему.
Правила (Rules): Правила повезују факте и омогућавају сложеније релације између њих.
Упити (Queries): Упити су питања која постављамо на основу дефинисаних факата и правила.
Унификација (Unification): Унификација је процес повезивања варијабли са вредностима тако да логички израз постане тачан. То је основна метода решавања у Прологу.

Пролог – Језик логичког програмирања

Пролог (скраћено од „Programming in Logic“) је најчешће коришћен језик за логичко програмирање. Програми у Прологу састоје се од серија факата и правила, а Пролог користи те дефиниције за решавање проблема путем унификације и закључивања.

Пример:
covek(marko).
covek(petar).
smrtan(X) :- covek(X).

Овде дефинишемо два факта (covek(marko). и covek(petar).) и једно правило (smrtan(X) :- čovek(X).). Ако поставимо упит (?- smrtan(marko).), Пролог ће одговорити „да“, јер је марко човек, а сваки човек је смртан према правилу.

Закључивање у логичком програмирању

Закључивање у логичком програмирању може се остварити помоћу две главне методе:

Дедуктивно закључивање: Закључак се изводи из општих правила и специфичних факата. На пример, ако знамо да су сви људи смртни и да је Марко човек, онда можемо закључити да је Марко смртан.
Индуктивно закључивање: У неким напредним применама, попут вештачке интелигенције, могуће је закључивање на основу узорака или примера, али то није уобичајено у основном логичком програмирању.

Предности и изазови логичког програмирања

Предности:

Висок ниво апстракције – дефинише се шта, а не како.
Погодан за проблеме са сложеним релацијама и правилима.
Применљив у областима као што су вештачка интелигенција, системска логика и наука о подацима.

Изазови:

Тежак за учење за оне који су навикли на процедуралне или објектно-оријентисане језике.
Изазови у перформансама код сложених проблема.
Неопходно је разумевање логике и математике на вишем нивоу.

Пример кода

roditelj(petar, ana).
roditelj(marija, ana).
roditelj(petar, marko).
roditelj(marija, marko).
brat(X, Y) :- roditelj(Z, X), roditelj(Z, Y), X \= Y.

Овим кодом се дефинишу родитељски односи и правило за одређивање браће и сестара. Можемо поставити упит:
?- brat(marko, ana).
Пролог ће одговорити "не", јер Ана и Марко нису браћа, већ брат и сестра.

Задаци за вежбање

Дефинисање фамилијарних односа

Задатак: Прошири пример са породичним односима тако да додате правила за сестра, родитељ, деда, и баба.
Циљ: Дефинисати правила тако да могу препознати односе између различитих чланова породице, а затим тестирати са упитима попут ?- deda(petar, ana).

Бојење мапе

Задатак: Креирај програм у Прологу који решава проблем бојења мапе за четири регије, са правилом да ниједне две суседне регије не смеју бити исте боје.
Циљ: Поставити правила за бојење тако да се користе три боје (на пример: црвена, зелена, плава), и тестирати их упитом ?- bojenje(X, Y, Z, W).

Izvori

Colmerauer, A., & Roussel, P. - The Birth of Prolog у History of Programming Languages – II. ACM, Њујорк.
Овај рад нуди историјски приказ развоја језика Пролог, од Q-система до финалног дизајна 1972. године, уз фокус на примене у области природног језика и вештачке интелигенције.
Тафтс Универзитет - A View of the Origins and Development of Prolog.
Приказ са Тафтс универзитета који обухвата Колмераурове прве кораке у раду са вештачком интелигенцијом, као и развој језика кроз различите граматике и алгоритме за обраду природног језика. Доступно на њиховом сајту: Tufts University.
Википедија - Logic Programming и Prolog (Programming Language).
Википедија странице за основне појмове логичког програмирања и Пролога пружају прегледне информације о структури језика, основним концептима и историјским догађајима, као и о његовој примени у AI истраживањима. Доступно на Logic Programming - Wikipedia и Prolog - Wikipedia.
Kowalski, R. - Algorithm = Logic + Control из Communications of the ACM.
Рад Роберта Ковалског из 1979. године разматра основне принципе логичког програмирања, укључујући дистинкцију између логике и контроле у програмима, што је кључно за разумевање Пролога и логичког приступа решавању проблема.