Vad om du kunde programmera genom att bara beskriva vad du vill ha gjort, istället för hur det ska göras? Det är tanken bakom logisk programmering. Istället för att skriva steg-för-steg instruktioner skriver du logiska regler och fakta, och låter datorn själv räkna ut hur målet ska uppnås. Prolog, det mest kända logiska programmeringsspråket, låter dig uttrycka kunskap som 'alla fåglar kan flyga' och 'Tweety är en fågel', och sedan automatiskt dra slutsatsen att 'Tweety kan flyga'.

Fördjupning

Logisk programmering baseras på första ordningens logik och använder horn-klausuler för kunskapsrepresentation. Prolog implementerar SLD-resolution (Selected Linear resolution for Definite clauses) med backtracking för att söka lösningar. Program består av fakta och regler, och queries utför logisk härledning. Unifiering är den centrala algoritmen för att matcha termer. Logisk programmering har tillämpningar inom AI, expertsystem och deklarativ problemlösning.

Horn-klausuler och Prolog-syntax

Horn-klausuler är specialfall av logiska klausuler med högst en positiv literal. De bildar grunden för logisk programmering.

Typer av Horn-klausuler

Fakta: P (definit klausul utan kropp)

Regler: P :- Q, R (implikation med konjunktiv kropp)

Mål: :- P, Q (query, negation av konjunktion)

Tomma klausulen: □ (motsägelse)

Prolog-program exempel

% Fakta

fågel(tweety).

fågel(polly).

% Regler

kan_flyga(X) :- fågel(X), \+ pingvin(X).

% Query

?- kan_flyga(tweety).

% Svar: Yes

SLD-resolution och backtracking

Prolog använder SLD-resolution för att systematiskt söka efter bevis genom att matcha mål med klausulhuvuden.

Resolutionsstrategi

Välj ett mål från mållistan

Hitta en klausul som kan unifieras med målet

Ersätt målet med klausulens kropp

Upprepa tills mållistan är tom (framgång) eller inga klausuler matchar (misslyckande)

Unifiering

Unifiering är processen att hitta substitutioner som gör två termer identiska.

Unifieringsexempel

f(X, a) och f(b, Y) unifieras med X=b, Y=a

Resultat: f(b, a)

g(X, X) och g(f(Y), Z) unifieras med X=f(Y), Z=f(Y)

occurs check: X får inte unifieras med term som innehåller X

Vanliga misstag

❌ Infinite rekursion utan basfall

Rekursiva regler måste ha basfall för att terminera

Exempel: ancestor(X,Y) :- ancestor(X,Z), ancestor(Z,Y). saknar basfall

Tillämpningar

Expertsystem

Representation av kunskapsbaserad expertis

Exempel: Medicinska diagnoser baserat på symptom och regler

Naturlig språkprocessning

Parsing och grammatikregler

Exempel: DCG (Definite Clause Grammars) för syntaxanalys

Övningar

1 Medel

Skriv Prolog-regler för släktskapsrelationer: förälder, farförälder, syskon

Tips

Använd grundfakta för förälder och definiera andra relationer rekursivt

Visa facit

1. förälder(adam, eva).
2. farförälder(X, Z) :- förälder(X, Y), förälder(Y, Z).
3. syskon(X, Y) :- förälder(Z, X), förälder(Z, Y), X \= Y.

Svar: Regler som bygger på grundrelationen förälder

Sammanfattning

Logisk programmering använder horn-klausuler och SLD-resolution för deklarativ problemlösning. Prolog implementerar denna paradigm med fakta, regler och queries. Unifiering matchar termer och backtracking utforskar sökrymden. Logisk programmering är kraftfullt för kunskapsrepresentation, expertsystem och symbolisk AI.