Laboratorul 4 - Programare Logică s, i Funct, ională

Seria 36
Martie 2025

În acest laborator vom continua să aplicăm algoritmul de unificare de la seminar, şi vom
ı̂nvăţa să utilizăm limbajul Prolog pentru probleme de căutare de soluţii.

1 Exerciţiul 1
O substituţie este o funcţie parţială de la variabile la termeni, adică σ : V → T rmL . Un unificator
pentru doi termeni t1 şi t2 este o substituţie θ astfel ı̂ncât θ(t1 ) = θ(t2 ). Un unificator ν pentru t1
şi t2 este un cel mai general unificator dacă pentru orice alt unificator ν ′ pentru t1 şi t2 , există o
substituţie µ astfel ı̂ncât ν ′ = ν; µ.
Algoritmul de unificare:

Lista soluţie Lista de rezolvat

S R
Iniţial ∅ t1 = t′1 , . . . , tn = t′n
SCOATE S R′ , t = t
S R′
DESCOMPUNE S R , f (t1 , . . . , tn ) = f (t′1 , . . . , t′n )
′

S R′ , t1 = t′1 , . . . tn = t′n
REZOLVĂ S R′ , x = t sau t = x, x nu apare ı̂n t
x = t, S[x ← t] R′ [x ← t]
Final S ∅

Algoritmul se termină normal dacă R = ∅ (ı̂n acest caz, ı̂n S are un unificator pentru termenii
din lista iniţială R).
Algoritmul este oprit cu concluzia inexistenţei unui unificator dacă:
1. În R există o ecuaţie de forma f (t1 , . . . , tn ) = g(t′1 , . . . , t′k ) cu f ̸= g. Simbolurile de constantă
se consideră simboluri de funcţie de aritate 0.
2. În R există o ecuaţie de forma x = t sau t = x şi variabila x apare ı̂n termenul t.

Fie limbajul de ordinul I L = (F, R, C, ari) unde F := {h, g, f, ∗, +, p}, C := {a, b, c}, iar
x, y, z, u, v ∈ V ar, descrise astfel:
• x, y, z, u, v ∈ V ar;
• a, b, c ∈ C(= F0 ); (doar informal! am stabilit la seminar că Fm are sens pentru m ≥ 1)

• h, g ∈ F1 ;
• f, ∗, + ∈ F2 ;
• p ∈ F3

unde Fm := {f ∈ F | ari(f ) = m}.

Decideţi dacă există unificatori pentru următorii termeni şi verificaţi că Prolog răspunde conform
rezultatului pe care l-aţi obţinut.
În Prolog, putem găsi unificatori prin apelarea predicatului
unify_with_occurs_check/2

1
Recomandare. Creaţi un fişier ı̂n care să definiţi un predicat cu nume mai simplu pentru unificare,
de exemplu
eq(X, Y) :- unify_with_occurs_check(X, Y).

Exemple:
?- eq(h(a, X), h(Y, b)).
X = b, Y = a

?- eq(A, f(A)).
false

De ce e false ı̂n al doilea caz?

Continuaţi cu exerciţiile:
1. f (h(a), g(x)) cu f (y, y);
2. p(a, x, g(x)) cu p(a, y, y);
3. p(x, y, z) cu p(u, f (v, v), u);

4. p(x, f (x, x)) cu f (g(y), f (z, g(a)));

5. x + (y ∗ y) cu (y ∗ y) + z;
6. f (g(x), x) cu f (y, y);
7. p(a, u, h(x)) cu p(y, f (y, z), z).

2
2 Exerciţiul 2
Fie următoarele şase cuvinte:
FLOWERS PROLOG ENTIRELY SCHOOL OREGANO SLEEP
Vom aşeza cuvintele ı̂n următorul puzzle:

(cinci cuvinte sunt pe orizontală, iar al şaselea este pe verticală).

Pentru rezolvare:
1. Implementaţi o bază de cunoştinţe, definită prin predicatul word/1.
2. Utilizaţi predicatul string chars/2, care primeşte un atom şi returnează lista caracterelor
conţinute ı̂n atomul respectiv.

3. Definiţi un predicat list pos/3 care primeşte o listă, un index şi returnează elementul de pe
indexul dat dacă acesta există, şi false altfel.
Veţi scrie un predicat principal
solution(W1, W2, W3, W4, W5, W6, L) :- ...

care se va asigura că cele şase cuvinte sunt cele din baza de cunoştinţe şi sunt mutual diferite, iar ı̂n
L va ı̂ntoarce o listă conţinând soluţia acestui puzzle.

3
3 Exerciţiul 3
Fie următoarea bază de cunoştinţe, formată prin intermediul predicatului connected/2:
connected(1,2).
connected(3,4).
connected(5,6).
connected(7,8).
connected(9,10).
connected(12,13).
connected(13,14).
connected(15,16).
connected(17,18).
connected(19,20).
connected(4,1).
connected(6,3).
connected(4,7).
connected(6,11).
connected(14,9).
connected(11,15).
connected(16,12).
connected(14,17).
connected(16,19).

1. Scrieţi un predicat path/2 care indică dacă dintr-un punct puteţi să ajungeţi ı̂ntr-un alt
punct (ı̂n mai mulţi paşi), legând conexiunile din baza de cunoştinţe. Drumurile se consideră
unidirecţionale (relaţia nu este simetrică).

Întrebări pentru verificare:

• puteţi ajunge din punctul 5 ı̂n punctul 10?

• ı̂n ce puncte puteţi să ajungeţi plecând din 1?

• din ce puncte puteţi să ajungeţi ı̂n punctul 13?
Testaţi programul pentru baza de cunoştinţe:

connected(1,2).
connected(2,1).
connected(1,3).
connected(3,4).

cu ı̂ntrebarea

?- path(1,4).
Observaţie. Dacă graful conţine cicluri, este posibil ca programul să nu ı̂şi termine execuţia.

2. Scrieţi un predicat care determină dacă există drumuri, evitând ciclurile din graf.

Hint. Utilizaţi un predicat auxiliar care reţine ı̂ntr-o listă punctele vizitate până ı̂n momentul
curent.