Laboratorul 3 - Programare Logică s, i Funct, ională
Seria 36
Martie 2024
În acest laborator, vom implementa ı̂n Prolog formulele propoziţionale şi semantica lor.
Variabilele vor fi reprezentate de atomi ı̂n Prolog (dacă atom(X). este true, atunci X ∈ V ar).
Operatorii pe care ı̂i vom utiliza sunt ¬, ∧, ∨ şi →, pe care ı̂i vom implementa individual, spre
deosebire de seminar, iar ei vor fi reprezentaţi ı̂n Prolog prin non/1, and/2, or/2, respectiv imp/2.
Spre exemplu, formula logică p → (q ∨ r) va fi ı̂n reprezentarea noastră:
?- X = imp(p, or(q, r)).
Scopul laboratorului va fi determinarea algoritmică a faptului că o formulă este sau nu tautologie.
1 Exerciţiul 1
Definiţi un predicat vars/2 care este adevărat exact atunci când primul argument este o formulă,
iar al doilea argument este lista care reprezintă mulţimea variabilelor care apar ı̂n ea.
?- vars(imp(non(a), imp(a, b)), S).
S = [a, b]
Utilizaţi, pentru implementare, predicatul predefinit atom/1, respectiv predicatul union/3, care
calculează reuniunea a două liste, considerate ca fiind mulţimi.
2 Exerciţiul 2
Vom considera evaluările e : V ar → {0, 1} ca fiind reprezentate printr-o listă de perechi de forma
[(a, 1), (b, 0)] (ı̂n evaluarea curentă, e(a) = 1 şi e(b) = 0). Definii̧i un predicat val/3 astfel
ı̂ncât pentru orice variabilă V şi orice evaluare E să avem că val(V, E, A) este adevărat exact atunci
când A este E(V).
?- val(b, [(a, 1), (b, 0)], X).
X = 0
3 Exerciţiul 3
Definiţi predicate bnon/2, band/3, bor/3, bimp/3 care implementează operaţiile ¬, ∧, ∨, → pe
mulţimea {0, 1}.
?- band(1, 0, C).
C = 0
?- bimp(A, 0, 0).
A = 1
?- bimp(0, B, 0).
false
Puteţi defini unele operaţii ı̂n funcţie de altele.
1
4 Exerciţiul 4
Definiţi un predicat eval/3 astfel ı̂ncât pentru orice formulă X şi orice evaluare E, avem că pentru
orice A, eval(X, E, A) este adevărat exact atunci când A este E+ (X).
?- eval(imp(b,d), [(a, 1), (b, 0), (d, 1)], A).
A = 1
?- eval(imp(d,b), [(a, 1), (b, 0), (d, 1)], A).
A = 0
5 Exerciţiul 5
Definiţi un predicat evals/3 astfel ı̂ncât, pentru orice formulă X şi orice listă de evaluări Es, avem
că pentru orice As, evals(X, Es, As) este adevărat atunci când As este lista rezultatelor evaluării
lui X ı̂n fiecare dintre elementele lui Es.
?- evals(imp(d, b), [[(a, 1), (b, 0), (d, 1)], [(a, 1), (b, 1), (d, 0)]], As).
As = [0, 1]
6 Exerciţiul 6
Definiţi un predicat evs/2 astfel ı̂ncât, pentru orice listă de variabile S, avem că pentru orice Es,
evs(S, Es) este adevărat exact atunci când Es este lista evaluărilor definite pe S.
?- evs([c, b], Es).
Es = [[(c, 0), (b, 0)], [(c, 1), (b, 0)], [(c, 0), (b, 1)], [(c, 1), (b, 1)]]
7 Exerciţiul 7
Definiţi un predicat all evals/2 astfel ı̂ncât, pentru orice formulă X, avem că pentru orice As,
all evals(X, As) este adevărat exact atunci când As este lista rezultatelor evaluării lui X ı̂n fiecare
dintre elementele listei evaluărilor definite pe variabilele din X.
?- all_evals(imp(a, a), As).
As = [1, 1]
?- all_evals(imp(a, b), As).
As = [1, 0, 1, 1]
8 Exerciţiul 8
Definiţi un predicat taut/1 astfel ı̂ncât, pentru orice formulă X, avem că taut(X) este true exact
atunci când X este tautologie.
?- taut(imp(a, a)).
true
?- taut(imp(a, b)).
false