Tentamen i Logikprogrammering

Observera att uppgifterna inte är ordnade efter svårighetsgrad. Läs igenom tentan och börja med de uppgifter Du tycker ser lättast ut. Maximalt kan Du få 20 poäng. För betyget godkänd krävs minst 10 poäng. För betyget väl godkänd krävs minst 15 poäng.

Följande systempredikat får användas i samtliga Prologuppgifter var/1, nonvar/1, =.., !, name/2, read/1, write/1, fail/O, bag_of/3, set_of/3, not/1, arg/3, functor/3, constant/1, compound/1 samt standardoperatorer (+ - mm). Andra predikat som du vill använda måste du skriva själv.

Skriv en lösning per sida och numrera i höger kant.

1. a) I den abstrakta interpretatorn som beskriver logikprogrammeringens semantik görs två indeterministiska val. Vilka är dessa? (2p)
b) Hur har man i Prolog valt att implementera denna indeterminism? (1p)

2. Ange MGU (mest generella unfierare) till följande termer:

a)	abc(X,[1,2,3,X])	abc(apa, Y)
b)	bbb(g(X),h(X),u(Y))	bbb(g([]),h([l | Xs]),u(a))
c)	mnl(dvl(4))	mnl(dvl(4))
d)	[a(X)]	[Y | Ys] (2p)

3. Hur definieras (för logikprogram) termerna
a) korrekt program.
b) fullständigt program.
c) Ge ett programexempel som belyser ovanstående egenskaper. (3p)

4. a) Föreslå en representation (i Prolog) för prioritetsköer och ange vilka operationer som skall finnas på dessa köer. (1p)
b) Implementera de predikat som behövs för att realisera de operationer på prioritetsköer du har föreslagit ovan. (2p)

5. Skriv ett predikat tolist(Term, List) som givet en term genererar en lista av alla konstanter som termen är uppbyggd av, dvs även funktorn. Ex. tolist(a(b(c,d,X)), [a, b ,c, d]). Notera att predikatet inte skall ta med eventuella variabler. (2p)

6. Vad innebär termen CWA (closed world assumption) och i vilket sammanhang används det? (2p)

7.p(X, Y) :- q(X, a), !.
p(a, b).
p(X, Y) :- q(X, Y).
q(a, b).
q(a, c) :- !.

Ange alla lösningar (med värden för X,Y,Z) som Prolog ger till frågan

| ?­ p(X,Y), q(X, Z).

för ovanstående program (ange lösningarna i samma ordning som Prolog). (2p)

8. Anta en representation för generella träd (träd där varje nod har ett godtyckligt antal barn) och skriv ett predikat rowtrav(Tree, List)där List innehåller nodettiketterna från Tree i den ordning som fås om Tree traverseras radvis, dvs först kommer rotnoden, sedan noderna på djupet 1 (från vänster till höger) osv. (3p)

Umeå universitet, inst f. datavetenskap

Christer Ericson, ankn 6794

Logik med tillämpningar, tentamen 1994-10­26

Inga hjälpmedel är tillåtna.

Börja varje uppgift på nytt blad och skriv endast på en sida på varje blad. För full poäng, redovisa alltid hur du kommit fram till ditt svar.

Uppgifterna är slumpmässigt ordnade. Det totala antalet poäng är 21.

For betygen 3, 4 och 5 krävs 10, 13 respektive 16 poäng. For betygen G och VG krävs 10 respektive 15 poäng.

Uppgift 1 (2 poäng) Avgör huruvida dessa logiska konsekvenser är korrekta.

1. { (p q) r, r }p
2. ((p (p p)) p)

Uppgift 2 (2 poäng) For nedanstående formler, visa med semantiska tablåer om de är valida, satisfierbara eller motsägelser.

1. (p q) ( p r)
2. xp(x) xp(x)

Uppgift 3 (2 poäng) Konvertera följande formel till klausulform:

xy (p (x,y) yq (y,x) r (y) )

Uppgift 4 (2 poäng) Givet formeln E och substitutionerna och , bestäm formlerna E och E samt substitutionskompositionen .

E = p(x, y) q(y, z) r(f(x),a)

={x y, y f(x), z f(w)}

={x a, y f(a), w y, z b}

Uppgift 5 (2 poäng) Uttryck följande meningar i första ordningens predikatlogik. använd dig av predikaten kan/2, gör/2 samt tycker_om/2.

1. Den som kan något gör det, den som inte kan något undervisar. (G B Shaw)
2. Ingen som kan logik tycker om någon som inte kan logik. (C Ericson)

Uppgift 6 (2 poäng) Använd Robinsons unifieringsalgoritm for att bestämma mgu till följande mängd. Redovisa utförligt alla steg i algoritmen.

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

Uppgift 7 (3 poäng) Givet följande meningar:

En datavetare som spelar spel kan inte programmera.

Den som dricker Cola och inte kan programmera är matematiker.
Den som dricker julmust dricker inte Cola, och tvärtom.
Den som både spelar spel och kan programmera dricker julmust.
Ingen är både matematiker och datavetare.
Roger spelar spel och dricker Cola.
Olof kan programmera men spelar inte spel.
Jan dricker julmust och kan programmera.

1. Transformera dessa meningar till uttryck i första ordningens predikatlogik. Använd dig av predikaten kan_programmera/1, spelar_spel/l samt dricker/2.
   
2. Visa med resolution att det finns någon som är matematiker.

Uppgift 8 (2 poäng) (Lemma 2.10.5) Antag att en literal l, men inte dess komplement l^c, förekommer i en klausulmängd S. Låt Sí beteckna den klausulmängd vi erhåller genom att ur S ta bort alla klausuler som innehåller l. Visa att S Sí, dvs att S är satisfierbar omm Sí är satisfierbar.

Uppgift 9 (1 poäng) Låt P vara logikprogrammet nedan. Ge både herbranduniversum, U(P), och herbrandbas, B(P), för P.

natural_number(0).

natural_number(s(X)) natural_number(X).

Uppgift 10 (1 poäng) (Definition 2.5.4) Ge en formell definition av vad som ska gälla för att en algoritm P ska vara en beslutsprocedur för en klass formler U.

Uppgift 11 (1 poäng) Använd sanningstabell for att avgöra om den satslogiska formeln nedan är valid, satisfierbar eller en motsägelse.

(p q) r p

Uppgift 12 (1 poäng) Finn en modell for klausulmängden