Korisnik:StasaRadosavljevic/Uvod u logičko programiranje

Logičko programiranje je paradigma programiranja koja koristi logiku za rešavanje problema. U ovom tipu programiranja, programer definiše pravila i činjenice, dok se odgovori na specifične probleme izvode pomoću logičkih dedukcija. Za razliku od proceduralnih ili objekno-orijentisanih jezika, gde se piše konkretan algoritam, logički programi definišu samo šta treba da bude tačno, a ne kako to postići.

Najpopularniji jezik za logičko programiranje je Prolog, koji koristi logičke izraze za rešavanje problema pomoću unifikacije i pravila zaključivanja.

Istorijat logičkog programiranja

Razvoj logičkog programiranja seže do fundamentalnih principa formalne logike i ranih radova iz oblasti veštačke inteligencije i računarskih nauka. Evo ključnih trenutaka u njegovom istorijskom razvoju:

Razvoj formalne logike
Osnove logičkog programiranja leže u formalnoj logici, oblasti koju su utemeljili matematičari poput Gottloba Fregea, Bertranda Russella i Alfreda North Whiteheada krajem 19. i početkom 20. veka. Njihov rad na simboličkoj logici, matematičkoj logici i logičkoj dedukciji postavio je temelje za računarsku logiku i automatsko zaključivanje.

Tarski i semantika logike
Poljski matematičar Alfred Tarski dao je doprinos razvoju formalne semantike za logiku 1930-ih godina. Njegova istraživanja o modelima, pojmu istine i formulaciji značenja logičkih izraza uticala su na kasniji razvoj logičkih jezika i teorije programiranja.

Automatsko zaključivanje i veštačka inteligencija
Tokom 1950-ih i 1960-ih godina, interes za automatsko zaključivanje i veštačku inteligenciju naglo je porastao. Matematičari i informatičari su istraživali mogućnosti računara da rešavaju probleme korišćenjem deduktivne logike. Ovi napori su doprineli nastanku disciplina kao što su ekspertni sistemi i algoritmi zasnovani na pretrazi.

Kreiranje Prologa (1972)
Logičko programiranje dobija praktičan oblik 1972. godine, kada Alain Colmerauer i njegov istraživački tim u Marseju razvijaju Prolog, prvi jezik za logičko programiranje. Prolog (skraćenica od "PROgrammation en LOGique") je zamišljen kao jezik za rešavanje složenih lingvističkih problema i bio je inspirisan radovima Roberta Kowalskog, jednog od pionira logičkog programiranja.

Japanski projekat za veštačku inteligenciju (1980-ih)
U periodu 1980-ih, japanska vlada pokrenula je projekat „Računari pete generacije“, sa ciljem razvoja naprednih računarskih sistema zasnovanih na logičkom programiranju i veštačkoj inteligenciji. Prolog je bio jezgro ovog projekta, čime je dodatno podstaknut interes za primenu logičkog programiranja u složenim ekspertizama.

Razvoj Datalog-a i drugih logičkih jezika
Od 1980-ih godina nadalje, razvijani su i drugi logički jezici, poput Datalog-a, koji su optimizovani za rad sa relacijama i rad sa bazama podataka. Logički jezici su prilagođavani i prošireni u oblasti rada sa bazama podataka i složenih upita.

Logičko programiranje danas
Danas, logičko programiranje ostaje relevantno u specifičnim oblastima kao što su semantički veb, baze podataka, analitika podataka i ekspertni sistemi. Prolog se i dalje koristi, dok su principi logičkog programiranja utkani u savremene sisteme za rad sa podacima, veštačku inteligenciju i mašinsko učenje.

Osnovni koncepti logičkog programiranja

Logičko programiranje zasniva se na nekoliko ključnih koncepata, koji uključuju:

Fakte (Facts): Činjenice predstavljaju osnovne istine u sistemu.
Pravila (Rules): Pravila povezuju fakte i omogućavaju složenije relacije između njih.
Upiti (Queries): Upiti su pitanja koja postavljamo na osnovu definisanih fakata i pravila.
Unifikacija (Unification): Unifikacija je proces povezivanja varijabli sa vrednostima tako da logički izraz postane tačan. To je osnovna metoda rešavanja u Prologu.

Prolog – Jezik logičkog programiranja

Prolog (skraćeno od „Programming in Logic“) je najčešće korišćen jezik za logičko programiranje. Programi u Prologu sastoje se od serija fakata i pravila, a Prolog koristi te definicije za rešavanje problema putem unifikacije i zaključivanja.

Primer:
covek(marko).
covek(petar).
smrtan(X) :- covek(X).

Ovde definišemo dva fakta (covek(marko). i covek(petar).) i jedno pravilo (smrtan(X) :- čovek(X).). Ako postavimo upit (?- smrtan(marko).), Prolog će odgovoriti „da“, jer je marko čovek, a svaki čovek je smrtan prema pravilu.

Zaključivanje u logičkom programiranju

Zaključivanje u logičkom programiranju može se ostvariti pomoću dve glavne metode:

Deduktivno zaključivanje: Zaključak se izvodi iz opštih pravila i specifičnih fakata. Na primer, ako znamo da su svi ljudi smrtni i da je Marko čovek, onda možemo zaključiti da je Marko smrtan.
Induktivno zaključivanje: U nekim naprednim primenama, poput veštačke inteligencije, moguće je zaključivanje na osnovu uzoraka ili primera, ali to nije uobičajeno u osnovnom logičkom programiranju.

Prednosti i izazovi logičkog programiranja

Prednosti:

Visok nivo apstrakcije – definiše se šta, a ne kako.
Pogodan za probleme sa složenim relacijama i pravilima.
Primenljiv u oblastima kao što su veštačka inteligencija, sistemska logika i nauka o podacima.

Izazovi:

Težak za učenje za one koji su navikli na proceduralne ili objektno-orijentisane jezike.
Izazovi u performansama kod složenih problema.
Neophodno je razumevanje logike i matematike na višem nivou.

Primer koda

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

Ovim kodom se definišu roditeljski odnosi i pravilo za određivanje braće i sestara. Možemo postaviti upit:
?- brat(marko, ana).
Prolog će odgovoriti "ne", jer Ana i Marko nisu braća, već brat i sestra.

Zadaci za vežbanje

Definisanje familijarnih odnosa

Zadatak: Proširi primer sa porodičnim odnosima tako da dodate pravila za sestra, roditelj, deda, i baba.
Cilj: Definisati pravila tako da mogu prepoznati odnose između različitih članova porodice, a zatim testirati sa upitima poput ?- deda(petar, ana).

Bojenje mape

Zadatak: Kreiraj program u Prologu koji rešava problem bojenja mape za četiri regije, sa pravilom da nijedne dve susedne regije ne smeju biti iste boje.
Cilj: Postaviti pravila za bojenje tako da se koriste tri boje (na primer: crvena, zelena, plava), i testirati ih upitom ?- bojenje(X, Y, Z, W).

Izvori

Colmerauer, A., & Roussel, P. - The Birth of Prolog u History of Programming Languages – II. ACM, Njujork.
Ovaj rad nudi istorijski prikaz razvoja jezika Prolog, od Q-sistema do finalnog dizajna 1972. godine, uz fokus na primene u oblasti prirodnog jezika i veštačke inteligencije.
Tafts Univerzitet - A View of the Origins and Development of Prolog.
Prikaz sa Tafts univerziteta koji obuhvata Kolmeraurove prve korake u radu sa veštačkom inteligencijom, kao i razvoj jezika kroz različite gramatike i algoritme za obradu prirodnog jezika. Dostupno na njihovom sajtu: Tufts University.
Vikipedija - Logic Programming i Prolog (Programming Language).
Vikipedija stranice za osnovne pojmove logičkog programiranja i Prologa pružaju pregledne informacije o strukturi jezika, osnovnim konceptima i istorijskim događajima, kao i o njegovoj primeni u AI istraživanjima. Dostupno na Logic Programming - Wikipedia i Prolog - Wikipedia.
Kowalski, R. - Algorithm = Logic + Control iz Communications of the ACM.
Rad Roberta Kovalskog iz 1979. godine razmatra osnovne principe logičkog programiranja, uključujući distinkciju između logike i kontrole u programima, što je ključno za razumevanje Prologa i logičkog pristupa rešavanju problema.