Uppgift 1 (4 poäng)

Använd Robinsons unifieringsalgoritm för att bestämma mgu till följande mängd. För att få full poäng måste alla steg i algoritmen redovisas utförligt.

 

{p( f(y), y, x), p(x, w, f(z)), p(x, f(a), x) }

Uppgift 2 (4 poäng)

Bevisa följande: Låt {l} S vara en enhetsklausul och S’ den mängd som man får om man från S tar bort alla klausuler som innehåller l och sedan tar bort lc från alla klausuler som är kvar. Då gäller att S S’, dvs S är satisfierbar omm S’ är satisfierbar.

Uppgift 3 (4 poäng)

Definiera negation by failure (not) i Prolog och förklara hur det fungerar. Ge ett exempel i Prolog där not inte fungerar som tänkt.

Uppgift 4 (6 poäng (1 + 1 + 2 + 2))

  1. Hitta alla interpretationer (tolkningar) som satisfierar (p q) (r q)
  2. Använd sanningstabell för att avgöra om formeln är valid, satisfierbar eller en motsägelse.
    (p q) r p
  3. Bestäm med hjälp av semantiska tablåer om formeln är valid, satisfierbar eller en motsägelse.
    x y(p(x, y) ( y p(y, x) r(y)))
  4. Bestäm med hjälp av semantiska tablåer om formeln är valid, satisfierbar eller en motsägelse.
    (((p q) p) p)

Uppgift 5 (6 poäng)

Skriv ett program tvaGanger(Lista1, Lista2) i Prolog som är sant om varje element i Lista1 förekommer minst två gånger i Lista2. Ordningen mellan elementen spelar ingen roll.

Exempel: tvaGanger([a, c], [c, a, a, a, b, c, d]).

yes

TIPS: Det blir mycket enklare att lösa uppgiften om ni använder er av hjälppredikat. Ett hjälppredikat kan tex ta ett element och kolla om elementet är medlem i en lista… Ni måste naturligtvis definiera alla hjälppredikat ni använder.

Uppgift 6 (8 poäng (2 + 2 + 4))

  1. Visa genom att ge ett motexempel att substitutionskomposition inte är kommutativ. Dvs visa att SIGMA inte är lika med SIGMA .
  2. Hur kan man använda en beslutsprocedur för satisfierbarhet för att visa validitet hos en formel?
  3. Vad innebär det att en formel är på PCNF-form? Hur går man tillväga för att omvandla en godtycklig formel till PCNF. Ge gärna ett exempel.

Uppgift 7 (8 poäng (4+2+2))

Givet är följande meningar:

 

En ros som är vattnad är inte törstig.

Blomma_A står i solen och är törstig.

Den som står i skuggan och inte är törstig är en fikus.

Den som står i solen står inte i skuggan och tvärtom.

Den som både är vattnad och törstig står i solen.

Blomma_B står i skuggan och är vattnad.

Ingen är både en fikus och en ros.

Blomma_C är törstig och inte vattnad.

 

  1. Transformera dessa meningar till uttryck i första ordningens predikatlogik. Använd dig av predikaten ros/1, fikus/1, vattnad/1, törstig/1 och står_i/2.
  2. Transformera uttrycken till klausalform förberedda för resolution.
  3. Visa med hjälp av resolution att det finns någon av blommorna som är en fikus.