Logisk programmering: regler, fakta og negation (Prolog og LISP)

Introduktion til logisk programmering: regler, fakta og negation i Prolog og LISP – lær principper, eksempler og praksis for deklarative programmer.

Logisk programmering er at bruge matematisk logik til at skrive computerprogrammer. Der findes specialiserede programmeringssprog, hvor brugeren kan indtaste logiske udsagn direkte. Det mest kendte af disse sprog hedder sandsynligvis Prolog. Alonzo Church brugte en form for logisk programmering i det, der i dag er kendt som lambda calculus. Logisk programmering er også blevet anvendt i LISP.

Programmer består af et sæt regler og fakta. I de fleste tilfælde bruger logisk programmering det, der kaldes negation som fejl eller svag negation: Det betyder, at hvis det ikke er muligt at udlede en klausul p {\displaystyle p} af fakta og regler, vil systemet antage, at dens negation er sand.

Regler og fakta

I logisk programmering opdeles programmet typisk i fakta og regler:

• Fakta er grundlæggende atomare udsagn, f.eks. at en relation holder mellem to elementer (fx parent(alice, bob)).
• Regler er implikationer, der udleder nye fakta ud fra eksisterende (fx ancestor(X,Y) :- parent(X,Y). eller ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).).

Et simpelt eksempel i Prolog-stil:

% Fakta parent(alice, bob). parent(bob, charlie).  % Regler ancestor(X,Y) :- parent(X,Y). ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

Her kan en forespørgsel som ancestor(alice, charlie). udledes ved at kombinere fakta og regler gennem inferens.

Negation — svag negation (negation som fejl) og klassisk negation

Den type negation, som ofte omtales i Prolog og beslægtede sprog, kaldes negation som fejl (eng. "negation as failure"). Det bygger på en praktisk antagelse: hvis målet p ikke kan bevises ud fra de kendte fakta og regler, antager systemet, at ¬p er sandt. Denne tilgang hænger tæt sammen med closed-world assumption (CWA): alt, der ikke er kendt at være sandt, betragtes som falsk.

Dette adskiller sig fra klassisk/logisk negation, hvor man kun kan konkludere ¬p hvis der foreligger et bevis for ¬p under de logiske aksiomer. I klassisk logik betyder manglende bevis for p ikke automatisk bevis for ¬p.

Eksempel på negation som fejl i Prolog (ofte skrevet som \+ eller not):

% Fakta male(bob). female(alice).  % Spørgsmål ?- \+ male(alice).  % Svarer sandt, fordi 'male(alice)' ikke kan bevises ?- \+ male(bob).    % Svarer falsk, fordi 'male(bob)' kan bevises

Bemærk: negation som fejl kan føre til ikke-monoton adfærd — tilføjelse af nye fakta kan ændre tidligere konklusioner.

Unifikation, inferens og evalueringsstrategier

De centrale mekanismer i logisk programmering er:

• Unifikation: proces hvor variable matches med konkrete termer for at gøre to udtryk ens; grundlaget for argumentpassing i regler.
• SLD-resolution / backtracking: Prolog bruger en backtracking-baseret søgestrategi (ofte kaldet backward chaining) for at finde beviser for forespørgsler. Systemet forsøger at matche målet med et regelsæt og tilbagegår ved fejl til tidligere valgpunkter.
• Forward chaining: alternativ strategi hvor man anvender regler fremadrettet for at udlede alle mulige konsekvenser (bruges i andre systemer, fx produktsystemer).

Anvendelser og relation til LISP og lambda calculus

Logisk programmering bruges især inden for:

• Symbolsk kunstig intelligens og videnrepræsentation
• Regelbaserede systemer og ekspertssystemer
• Databasespørgsmål og forespørgselsoptimering (f.eks. Datalog)
• Naturlig sprogbehandling og planlægning

Historisk har Alonzo Church og lambda calculus bidraget til formelle grundlag for beregning og funktionel programmering. LISP har traditionelt været stærk til symbolmanipulation og har inspireret mange ideer i AI-forskning; selvom LISP ikke er et logikprogrammeringssprog per se, kan logiske teknikker og inferens implementeres i LISP (fx via biblioteker eller embedding af logikmotorer).

Begrænsninger og udvidelser

Praktiske begrænsninger ved klassiske logiske programmeringssprog inkluderer:

• Problemer med negation og ikke-monoton logik (negation som fejl kan være upræcis i åbne verdener).
• Søgeeksplosion ved store eller uendelige søgestier (backtracking kan være dyrt).
• Manglende indbygget håndtering af kontinuerlige værdier og numerisk beregning (dog løses det ofte ved integration med imperativ kode eller CLP — constraint logic programming).

For at håndtere disse udfordringer findes udvidelser og varianter som f.eks. constraint logic programming (CLP), probabilistiske extensions, og systemer der kombinerer logik med ontologier og description logics for mere robust videnrepræsentation.

Opsummering

Logisk programmering giver et deklarativt paradigme, hvor programmer beskrives gennem fakta og regler, og hvor inferensmaskinen søger efter beviser. Negation som fejl (svag negation) er et pragmatisk værktøj, der tilbyder en enkel måde at håndtere ukendte udsagn på ved at antage falskhed, hvis noget ikke kan bevises — men det har semantiske konsekvenser, især i systemer, hvor verden ikke er lukket eller fuldt kendt.

Spørgsmål og svar

Q: Hvad er logisk programmering?

Q: Hvad er nogle programmeringssprog, der bruger logisk programmering?

Q: Hvilken rolle spiller regler og fakta i logisk programmering?

Q: Hvad er negation som fiasko i logisk programmering?

Q: Hvad er svag negation i logisk programmering?

Q: Hvem brugte en form for logisk programmering i lambda calculus?

Q: Hvilket er det mest kendte programmeringssprog, der giver brugerne mulighed for direkte at indtaste logiske udsagn?

Søg efter bogstav