Editor:

John Val

Bron: Learn Prolog Now!

Op zoek naar het bewijs

In het vorige hoofdstuk hebben we geleerd wat unificatie is. In dit hoofdstuk leer je hoe Prolog in een kennisbank op zoek gaat naar de antwoorden op een gestelde vraag. Een kijkje onder de motorkap. Dit hebben we ook al een beetje gezien in les 2. Het is nuttig om te begrijpen wat Prolog doet. Als je Prolog programma's schrijft is de volgorde van het plaatsen van vragen namelijk belangrijk. We beginnen weer met een simpel voorbeeld en wel de volgende kennisbank:

Stellen we nu de vraag

Dan is er maar één antwoord namelijk Y=b. Waarom? ( Antwoord :
Regel k(X) :- f(X), g(X), h(X). zegt dat k(X) geldt als zowel f(X) , g(X) en h(X) waar zijn. De kennisbank vertelt alleen wat over f,g en h in combinatie met a en b. Dus X kan alleen de 'zinvolle' waarden a, b of leeg aannemen. Je ziet nu dat alleen de waarde X=b in f,g en h tot een waarheid leiden. ). Hoe komt Prolog tot dat antwoord?

Prolog leest de kennisbank en probeert k(Y) te unificeren met een feit of de kop (head) van een regel. Deze zoektocht gaat van boven naar beneden en voert de unificatie, indien mogelijk, uit op de eerste geschikte plek. Hier is er maar één mogelijke plek. k(Y) moet unificeren met k(X), de kop van de regel k(X) :- f(X), g(X), h(X).. Op basis van regel 3 in het unificatie proces kan deze actie worden ondernomen, functor en ariteit kloppen. Nu moet ook Y nog met X unificeren.

Wanneer Prolog een variabele in een vraag unificeert met een variabele in een feit of een regel, dan maakt het een nieuwe variabele aan ( bijvoorbeeld _G34 ) om de gedeelde variabelen (X en Y) te representeren. Onze oorspronkelijk vraag wordt dan:

en Prolog weet

Wat hebben we nu? De oorspronkelijke vraag leest als volgt: "Ik wil een individu vinden dat eigenschap k heeft". De regel k zegt: "een individu heeft eigenschap k als het de eigenschappen f, g en h heeft". Dus als Prolog zo'n individu kan vinden dan kan de oorspronkelijke vraag positief worden beantwoord. De oorspronkelijke vraag wordt nu door Prolog omgezet in de volgende lijst van doelen:

Onze discussie over het proces om de vraag te beantwoorden kunnen we ook op een elegante en beknopte manier grafisch weergeven. Zie het diagram hiernaast. Alles in een rechthoek is of een vraag of een doel. Voor onze vraag is ons oorspronkelijke doel k(Y) te bewijzen, dit is in de bovenste gele rechthoek weergegeven. Toen we k(Y) unificeerden met de regel k(X) in de kennisbank, zijn de variabelen X,Y en _G34 gedeelde variabelen geworden. Ons nieuwe doel is de lijst met vragen

ofwel er moet worden bewezen dat deze allen gelden. Deze staat nu in de tweede rechthoek.

Als er een lijst van doelen moet worden beantwoord doet Prolog dit één voor één en wel van links naar rechts. Het meest linkse doel is f(_G34) dat te lezen is als: "Ik wil een individu met eigenschap f ". Kan dit doel worden behaald? Prolog begint de zoektocht weer van bovenaf naar beneden en vindt in dit geval dat f(_G34) unificeert met het feit f(a) waarmee de zoektocht eindigt en _G34 de waarde a krijgt. Deze waarde heeft _G34 ook in het unificeren van de overige twee doelen ofwel De grafische representatie is hier links weergeven:

Het feit g(a) is aanwezig in de kennisbank waardoor het doel g(a) in de vraag is behaald. Blijft alleen nog over Helaas is er geen manier om dit laatste doel te bereiken. De enige informatie in de kennisbank is h(b) en dit unificeert niet met h(a).

Hoe nu verder? Wel, Prolog besluit dat er een fout is gemaakt, en gaat op zoek naar een stap waar nog een andere mogelijkheid tot unificatie is met een feit of een regel. Prolog beweegt zich daartoe in omgekeerde richting door de grafische representatie. Er is niets anders te unificeren met g(a), dus weer een stap terug. Er is nu wel een andere keuze te maken f(_G34) unificeert na f(a) ook met f(b) (De volgende in de lijst van f feiten). Een punt in het pad van beslissingen waar er meerdere mogelijkheden zijn noemt men een keuzepunt (choice point). Prolog houdt bij waar het keuzepunten is tegengekomen, zodat bij een doodlopend pad Prolog terugkeert naar het laatst gepasseerde keuzepunt om daar een nieuw pad te proberen. Dit belangrijke proces in Prolog in de zoektocht naar bewijs noemt men backtracking (terugkeren)

Laten we verder gaan met ons voorbeeld. Prolog backtracks (keert terug) naar het laatste keuzepunt, daar waar de lijst van doelen gelijk was aan

Prolog moet vanaf hier het beslissingspad opnieuw beginnen en zoals eerder vermeld is de de unificatie van f(_G34) met de eerstvolgende optie voor f na f(a) en dat is f(b). f(_G34) unificeert met f(b) door _G34 de waarde b te geven. Wat weer leidt tot de nieuwe doelvraag: Er is weer unificatie van g(b) in de vraag met het feit g(b) in de kennisbank. Dus Prolog gaat verder met en er nu wel een unificatie van h(b) uit de vraag met het feit h(b) in de kennisbank. Prolog is nu aangekomen bij een lege lijst van doelen. Dit betekent dat aan alles wat nodig was in de bewijsvoering van ons oorspronkelijke doel (?- K(Y) ) is voldaan. De vraag is dus positief te beantwoorden als Y de waarde b krijgt.

Is er nog een ander antwoord mogelijk? Als je het voorbeeld naspeelt in Swish verschijnt er geen Next knop. Na het positieve resultaat doet Prolog alsnog een backtracking en heeft nu geen andere mogelijkheden bij de keuzepunten h(b) , g(b) , f(_G34) en k(Y). Voeg eens f(c),g(c) en h(c) toe aan de kennisbank. Wat ervaar je nu?

De grafische weergave rechts bevat alle genomen stappen. De gestreepte pijlen zijn de stappen in het backtracking proces. Naast de andere pijlen staan waar mogelijk de waarde voor de variabelen die gekozen worden in het vervolg van de zoektocht naar een bewijs.

Je ziet in de weergave rechts dat het diagram de vorm van een boom heeft; in les 2 hebben we al een aantal traces gezien die overeenkomstig zijn met deze boom weergave. De knopen in de boom zijn de vragen die ter plekke moeten worden beantwoord, langs de takken (de pijlen) staat waar mogelijk de waarde voor de variabelen die het eerstvolgende doel unificeert. De gestippelde (opgaande) pijlen tonen het backtracking proces. Alleen takken (en de waarden van de variabelen ernaast) die eindigen met een lege vraag beantwoorden de oorspronkelijke vraag positief.

Nog een voorbeeld van een kennisbank:

We stellen nu de vraag: Hoe gaat Prolog hier mee om? Hieronder zie je de boom weergave van de zoektocht naar een positief antwoord.

Er is slechts één mogelijkheid om jaloers(X,Y) te unificeren met de kennisbank namelijk met de regel

De lijst van te behalen doelen is nu: Nu moet houdVan(_G4,_G6) worden geünificeerd met de kennisbank en de eerste gegadigde is houdVan(vincent,mia). Maar Prolog weet hier ook al dat er een tweede mogelijkheid is namelijk houdVan(marcellus,mia). We hebben hier dus een keuzepunt. De linker tak wordt de eerste keuze. Dus _G4=vincent en _G6=mia, waarna de vraag moet worden beantwoord. De eerste mogelijkheid waarmee deze vraag unificeert is weer houdVan(vincent,mia) en er is ook weer de tweede mogelijkheid houdVan(marcellus,mia). Weer een keuzepunt! De linkerkant heeft geeft _G5=vincent. De vraag unificeert met de kennisbank en dus is dit een pad met een positief antwoord. Backtracking levert dan één niveau hoger de keuze _G5=marcellus, ook weer valide. Weer één stap omhoog levert geen nieuwe keuze, een tweede stap wel. De rechter tak begint met de tweede keuze houdVan(marcellus,mia) dus _G4=marcellus en _G6=mia. Ook in die tak volgen weer twee valide keuzes.

Er zijn dus vier oplossingen voor de vraag jaloers(X,Y).

1. X = _G4 = vincent en Y = _G5 = vincent
2. X = _G4 = vincent en Y = _G5 = marcellus
3. X = _G4 = marcellus en Y = _G5 = vincent
4. X = _G4 = marcellus en Y = _G5 = marcellus

Zorg dat je dit voorbeeld goed bestudeert en nog belangrijker begrijpt.