logica computationala

Facultatea de Matematica si InformaticaSpecializarea Informatica

LOGICA COMPUTATIONALA

Note de seminar

Titular: Lector drd. Alexandrescu Adrian

Pag.1

Seminar 1 Calculul propoziltional

1. Sa se reprezinte sub forma unui arbore binar urmatoarele formule din calculul propozitional:p q ( r p)); (p q) ( p r)

Model de rezolvare:

2. Folosind metoda tabelelor de adevar, sa se determine interpretarile pentru care formulele date iau valoarea fals: (p q) (p r) ; (p q) q r)

Model de rezolvare:

P q r p p q p r (p q) (p r)A A A F F A AA A F F F A AA F A F F A AA F F F F A AF A A A A A AF A F A A F FF F A A F A AF F F A F F A

Formula (p q) (p r) ia valoarea fals doar pentru o singura interpretare I: I(p)=F, I(q)=A, I(r)=F.

3. Sa se realizeze un program care determina valorile unei formule din calculul propozitional, folosind metoda tabelelor de adevar.

Model de rezolvare: program in Visual Basic.

Const NPropozitii = 3

Pag.2

p

qr p

Const NFormule = 4Const NLinii = 2 ^ NPropozitiiConst NColoane = NPropozitii + NFormule

Dim t(1 To NLinii, 1 To NColoane) As Boolean

Dim p As Boolean, q As Boolean, r As Boolean

Function f1() As Boolean f1 = p or qEnd Function

Function f2() As Boolean f2 = not q or rEnd Function

Function f3() As Boolean f3 = not p or not rEnd Function

Sub GenereazaValori()Dim n As IntegerFor n = 1 To NLinii r = n Mod 2 q = (n \ 2) Mod 2 p = (n \ 4) Mod 2 t(n, 1) = p: t(n, 2) = q: t(n, 3) = r t(n, 4) = f1: t(n, 5) = f2: t(n, 6) = f3: t(n, 7) = f1 And f2 And f3Next

End Sub

Sub AfiseazaTabela()Dim i As Integer, j As Integer, text As Stringtext = ""For i = 1 To NLinii For j = 1 To NColoane text = text & t(i, j) & Chr(9) Next text = text & Chr(13)NextMsgBox text

End Sub

Pag.3

Sub main() GenereazaValori AfiseazaTabela

End Sub

Comentarii:

- numarul de variabile propozitionale si numarul de subformule se specifica prin constantele Npropozitii respectiv Nformule.

- subformulele se definesc prin functii booleene.

- formula considerata in acest program este (p q ) (q r ) (p r)

Pag.4

Seminar 2 Calculul propozitional 1. Sa se demonstreze ca urmatoarele formule sunt valide: (p p), (p p) si ( p p)

Indicatie de rezolvare: metoda tabelelor de adevar.

2. Sa se demonstreze ca urmatoarele formule sunt inconsistente: p p, p p, (q p) ( (p q)).

Indicatie de rezolvare: metoda tabelelor de adevar.

3. Sa se dea exemple de formule consistente, continand trei variabile propozitionale.

4. Folosind metoda tabelelor de adevar, sa se demonstreze ca formula p q ) este o consecinta logica a multimii { p r, q r } .

Model de rezolvare:

Construim o tabela de adevar cu 3 variabile p, q, r si cu 4 subformule r, p r, q r, p q.

p q r r

p r Q r p q

A A A F A A AA A F A A A AA F A F A A AA F F A A F AF A A F F A AF A F A A A AF F A F F A FF F F A A F F

Observam ca atunci cand formulele p r, q r iau ambele valoarea adevarat, formula p q ia deasemenea valoarea adevarat.

5. Folosind algoritmul lui Quine sa se demonstreze validitatea formulei

((p q) r) (p (q r))

Construim un arbore semantic corespunzator variabilelor: p, q, r.

1. Consideram cazul p=A (corespunzator arcului etichetat cu p). Prin eliminarea lui p, formula devine:

(q r) (q r), deoarece (p q) q iar (p (q r)) (q r)

Pag.5

1.1 Consideram cazul q=A (corespunzator arcului etichetat cu q). Formula devine:

r r , deoarece (q r) r . Se observa ca formula este valida

1.2 Consideram cazul q=F (corespunzator arcului etichetat cu q). Formula devine:

A ceea ce reprezinta o formula valida.

2. Consideram cazul p=F (corespunzator arcului etichetat cu p). Prin eliminarea lui p, formula devine:

((F q) r) (F (q r)) sau

(F r) (A) sau

A A, ceea ce rprezinta o formula valida.

Observatii: am construit un arbore semantic incomplet, corespunzator situatiei de mai jos.

Pag.6

q

p

q

p

Seminar 3 Calculul propozitional

1. Sa se demonstreze urmatoarele proprietati:

(X X) A(X X) F X X (X1 X2 … Xn) X1 X2 … Xn) (X1 X2 … Xn) X1 X2 … Xn)

simbolurile A şi F reprezintă valorile logice “adevărat” respectiv “fals”.

Indicatie: se porneste de la definitia relatiei de echivalenta logica “”.

2. Sa se aduca la forma conjunctiv normala, urmatoarele formule din calculul propozitional:

(p (q r)) ((p q) r)

((( p q) r) (p q)) ( p r)

((p q) r) (p (q r))

Indicatie: se aplica algoritmul de normalizare.

3. Sa se realizeze un program care sa preia dintr-un fisier text clauzele unei formule normalizate, sa codifice literalii si sa reprezinte formula printr-o matrice.

Dim fn(1 To 20) As String, nfn As Integer ' Clauze in format externDim dsim(1 To 10) As String, nsim As Integer ' Dictionar de

simboluriDim v(1 To 10) As Integer, nv As Integer ' Codificare clauza curentaDim fncod(1 To 20, 1 To 10) As Integer, nfncod As Integer ' Clauze in format codificat

Sub preluare_clauze() ' Preluare clauze din fisier text Open "d:\Logica\F.txt" For Input As 1 nfn = 0 Do Until EOF(1) nfn = nfn + 1 Input #1, fn(nfn) Loop Close 1

End Sub

Pag.7

Sub afiseaza_clauze() ' Afisare fn Dim t As String, i As Integer t = "" For i = 1 To nfn t = t & fn(i) & Chr(13) Next MsgBox t

End Sub

Sub conv_clauza(x As String) ' Conversia unei clauze x in format

'

intern: v,nv Do Until x = "" If Left(x, 1) >= "a" And Left(x, 1) <= "z" And Left(x, 1) <> "v" Then adauga_in_vector (intrare_literal(Left(x, 1))) ElseIf Left(x, 1) = "-" Then x = Mid(x, 2) If Left(x, 1) >= "a" And Left(x, 1) <= "z" And Left(x, 1) <> "v" Then adauga_in_vector (-intrare_literal(Left(x, 1))) Else MsgBox "Clauza eronata" Exit Do End If End If x = Mid(x, 2) Loop

End Sub

Function intrare_literal(x As String) As Integer ' Furnizeaza codul intern al unui literal

Dim i As Integer, este As Boolean ' pozitiv sau negativ este = False i = 1 Do While i <= nsim And Not este If dsim(i) = x Then este = True Else i = i + 1 End If Loop If este Then

Pag.8

intrare_literal = i Exit Function Else nsim = nsim + 1 dsim(nsim) = x intrare_literal = nsim End If

End Function

Sub adauga_in_vector(x As Integer) ' Adauga literalul x in vectorul v,nv nv = nv + 1 v(nv) = x

End Sub

Sub adauga_vector() ' Adauga vectorul v,nv in fncod,nfncod

Dim j As Integer nfncod = nfncod + 1 For j = 1 To nv fncod(nfncod, j) = v(j) Next

End Sub

Sub afiseaza_clauze_codificate() ' Afiseaza forma normala codificate:

' fncod,nfncodDim i As Integer, j As Integer, t As Stringt = "nr.linii=" & nfncod & Chr(13) & Chr(13)For i = 1 To nfncod

For j = 1 To 10 t = t & fncod(i, j) & Chr(9) Next t = t & Chr(13)

NextMsgBox t

End Sub

Sub main() ' Programul principal Dim i As Integer preluare_clauze afiseaza_clauze nsim = 0: nfncod = 0

Pag.9

init_fncod For i = 1 To nfn nv = 0 conv_clauza (fn(i)) adauga_vector Next afiseaza_clauze_codificate

End Sub

Observatii:

Daca vrem sa codificam clauzele pentru formula:

h ( h p q ) (p c ) (q c ) (c ) (h c )

fisierul text de intrare are urmatorul continut:

h-hvpvq-pvc-qvc-chvc

Se foloseste caracterul minus(-) pentru operatorul de negatie si caracterul v pentru disjunctie.

Pag.10


1. Folosind algoritmul lui Davis si Putnam, să se verifice inconsistenţa urmatoarelor mulţimi:

{p q, p r, q r, p}

{ p r t, q, r, t p r, t q, p q r}

Indicatie: se aplica algoritmul lui Davis si Putnam pentru cazul particular al unei clauze unitare.

2. Sa se extinda programul de codificare al unei formule reprezentata in forma conjunctiv normala, pentru implementarea algoritmului lui Davis si Putnam. Se va considera cazul particular in care exista clauze unitare.

Solutie:

Function exista_clauze_unitare_opuse() As Boolean ' Verifica daca exista clauze unitare opuse Dim i As Integer, j As Integer

For i = 1 To nfncod - 1 For j = i + 1 To nfncod If fncod(i, 1) = -fncod(j, 1) And fncod(i, 2) = 0 And fncod(j, 2) = 0 Then exista_clauze_unitare_opuse = True Exit Function End If Next Next exista_clauze_unitare_opuse = False

End Function

Function exista_clauza_unitara() As Integer ' Verifica daca exista o clauza unitara Dim i As Integer For i = 1 To nfncod If fncod(i, 2) = 0 Then exista_clauza_unitara = i: Exit Function End If Next exista_clauza_unitara = 0

End Function

Pag.11

Sub sterge_clauza(n As Integer) 'Eliminare clauza din fncod n=> nr.linie Dim i As Integer, j As Integer For i = n + 1 To nfncod For j = 1 To 10 fncod(i - 1, j) = fncod(i, j) Next Next nfncod = nfncod - 1

End Sub

Sub elimina_literal(n As Integer) 'Aplica un pas din algoritmul Davis & Putnam Dim i As Integer, j As Integer, p As Integer, k As Integer ' simplificat p = fncod(n, 1) 'p este Literalul Clauzei unitare sterge_clauza (n) ' Sterg clauza unitara For i = 1 To nfncod ' Caut clauzele care contin -p For j = 1 To 10 If fncod(i, j) = -p Then For k = j + 1 To 10 fncod(i, k - 1) = fncod(i, k) ' Elimin -p din clauza Next End If Next Next For i = 1 To nfncod ' Caut clauzele care contin p For j = 1 To 10 If fncod(i, j) = p Then sterge_clauza (i) ' Elimin clauza ce contine p Next Next End Sub

Function algoritm_DP_simplificat() As Integer Dim i As Integer Do If nfncod = 0 Then algoritm_DP_simplificat = 3 ' Multime consistenta

Pag.12

Exit Do End If If exista_clauze_unitare_opuse Then algoritm_DP_simplificat = 1 ' Multime inconsistenta Exit Do End If i = exista_clauza_unitara ' 0 nu exista <> 0 (nr.linie) exista If i = 0 Then algoritm_DP_simplificat = 2 ' nu se poate aplica algoritmul Exit Do End If elimina_literal (i) afiseaza_clauze_codificate LoopEnd Function

Function multime_valida()Dim i As Integer, j As Integer, k As IntegerDim validg As Boolean, valid As Boolean

validg = True

For i = 1 To nfncod valid = False For j = 1 To 9 For k = j + 1 To 10 If fncod(i, j) <> 0 And fncod(i, k) <> 0 And fncod(i, j) = -fncod(i, k) Then valid = True: Exit For End If Next If valid Then Exit For Next validg = validg And valid If Not validg Then Exit ForNext multime_valida = validg

End Function

Pag.13

Sub main() ' Programul principal Dim i As Integer preluare_clauze afiseaza_clauze nsim = 0: nfncod = 0 For i = 1 To nfn nv = 0 conv_clauza (fn(i)) adauga_vector Next afiseaza_clauze_codificate If nfncod = 0 Then MsgBox "Multimea este vida" Exit Sub End If If multime_valida Then MsgBox "Multimea este valida" Exit Sub End If Select Case algoritm_DP_simplificat Case 1 MsgBox "Multime inconsistenta" Case 2 MsgBox "Algoritmul nu se poate aplica" Case 3 MsgBox "Multime consistenta" Case Else MsgBox "Algoritmul a returnat un cod eronat" End Select End Sub

Pag.14


1. Sa se demonstreze inconsistenta urmatoarelor formule, folosind algoritmul de rezolutie.

S1 = { p q, p r, q r, p}.

S2 = { p r t, q, r, t p r, t q, p q r}

Model de rezolvare:

Vom considera multimea S1. Numerotam clauzele:

1. p q2. p r3. q r4. p

Extidem multimea de clauze cu noi clauze obtinute prin regula rezolutiei:

5. p r (1,3)6. q (1,4)7. p q (2,3)8. r (2,4)9. p (2,5)

Obtinerea clauzei Fals

10. F Clauze unitare opuse (4,9)

2. Sa se realizeze un program care verifica inconsistenta unei multimi de clauze, folosind algoritmul de rezolutie.

Indicatie: se va utiliza programul de codificare a clauzelor, preluate dintr-un fisier text.

3. Sa se realizeze un program care verifica daca o multime de caluze sunt clauze Horn.

Indicatie: se va utiliza programul de codificare a clauzelor, preluate dintr-un fisier text si se va verifica pentru fiecare clauza daca are cel mult un literal pozitiv.

Pag.15

Seminar 6 Calculul predicatelor

1. Prezentarea mediului de dezvoltare Turbo Prolog

2. Reprezentarea in limbajul Prolog a rationamentului:

Orice om este muritor ;Socrate este om;deci Socrate este muritor.

Model de rezolvare:

Predicatesom(symbol)muritor(symbol)

Clausesmuritor(X) :- om(X).om(socrate).

Goal: muritor(socrate)Yes

3.1 Sa se defineasca in limbajul Prolog predicatele: facultate(f), specializare(sp,f,n), inscris(st,sp,an) avand semnificatia:

f este denumirea unei facultati din universitatea Ovidius,

sp este denumirea unei specializari din cadrul facultatii f, cu n ani de studiu,

st este numele unui student inscris la specializarea sp in anul an.

3.2 Sa se descrie in limbajul Prolog faptul ca la toate specializarile de la facultatea de matematica se studiaza 3 ani.

3.3 Sa se descrie in calculul predicatelor si in Limbajul Prolog expresia: exista studenti inscrisi la facultatea de matematica si la facultatea de medicina ?

3.4 Sa se descrie in calculul predicatelor si in Limbajul Prolog expresia: este studentul Popescu Vasile in an terminal la facultatea de matematica ?

Pag.16

Seminar 7 Calculul relational

1. Definirea relatiilor intr-o baza de date Access.

2. Sa se defineasca relatia Studenti(Nume,DataNasterii,Media,Bursier) avand urmatoarele tuple:

Nume DataNasterii Media BursierPopescu Eugen 30.08.1985 9.30 AdevaratIonescu Marcel 15.06.1984 8.70 FalsBarbu Elena 11.05.1983 8.90 FalsPetrescu George 15.09.1982 9.50 AdevaratPopa Maria 16.10.1983 7.25 Fals

3. Sa se descrie in calculul relational orientat pe tuple si pe domenii urmatoarele cereri:

3.1 Care sunt studentii (Nume, Media) ce au media 8.

3.2 Care sunt studentii (Nume, DataNasterii, Media) nascuti inainte de 1.1.1984 cu media cuprinsa intre 8 si 9.

3.3 Care sunt nemele studentilor bursieri.

Model de rezolvare pt. 3.1:

Calculul relational pe tuple:

{ t | ( u ) student(u) u.media 8 t.nume = u.nume t.media = u.media }

Calculul relational pe domenii:

{ n,m | ( d ) ( b ) student(n,d,m,b) m 8 }

4. Fie baza de date universitara ce contine relatiile

Student (Nume, DataNasterii, Media, Bursier)Inscris(Nume,DenSectie,An)Sectie(DenSectie,DenFacultate,NrAni)

Sa se descrie in calculul relational orientat pe tuple si pe domenii urmatoarele cereri:

4.1 Care sunt sectiile de la facultatea de medicina si cati ani se studiaza la fiecare din ele.

Pag.17

4.2 Care sunt studentii (Nume, DenSectie, DenFacultate) din anii terminali.

4.3 Care sunt studentii (Nume) din anii 1 si 2.

Model de rezolvare pt. 4.2:

Calculul relational pe tuple:

{ t | ( i ) ( s) inscris(i) sectie(s) i.denSectie = s.denSectie i.an = s.nrAni t.nume=inscris.nume t.denSectie=inscris.denSectie t.denFacultate=s.denFacultate}

Calculul relational pe domenii:

{ n,ds,df | ( n ) inscris(n,ds,n) sectie(ds,df,n) }

Pag.18

Seminar 8 Limbajul QBE

1. Prezentarea obiectului query (modul design view) dintr-o baza de date Access.

2. Se da schema unei baze de date:

persoane(cnp, nume, localitate)auto(nr, marca, model, capacitate, data, proprietar)

continand date despre persoane si automobile:

cnp cod numeric personalnume nume persoanalocalitate localitatea de resedinta

nr numar de inmatricularemarca marca automobiluluimodel modelul automobiluluicapacitate capacitatea motorului (in cm3)data data inmatriculariiproprietar cnp-ul proprietarului

Sa se descrie in limbajul QBE urmatoarele cereri:

2.1 Care sunt persoanele (Nume, Cnp, Localitate) din Constanta sau Mangalia.

2.2 Care sunt persoanele (Nume, Cnp) din localitatea specificata de la tastatura in momentul executiei cererii (cerere parametrizata).

2.3 Care sunt automobilele (nr, marca, model, capacitate) din proprietatea persoanei al carui cnp este solicitat la momentul executiei, inmatriculate inainte de 1.1.2000.

2.4 Care sunt automobilele (nr, marca, model, capacitate) din baza de date precum si durata in ani de la inmatriculare .

2.5 Sa se afiseze toate persoanele (Nume, Localitate, Cnp) care detin in proprietate un automobil marca Audi inmatriculat in anul 2007.

2.6 Sa se afiseze numai persoanele (Nume, Cnp, Localitate) ce sunt proprietari de automobile.

2.7 Sa se afiseze toate persoanele din baza de date (Nume, Cnp, Localitate) iar pentru cele ce detin automobile sa se afiseze marca, model si numar de inmatriculare.

Pag.19

Model de rezolvare pt. 2.1: care sunt persoanele (Nume, Cnp, Localitate) din Constanta sau Mangalia.

Model de rezolvare pt. 2.2: care sunt persoanele (Nume, Cnp) din localitatea specificata de la tastatura in momentul executiei cererii (cerere parametrizata).

Pag.20

Model de rezolvare pt. 2.3: care sunt automobilele (nr, marca, model, capacitate) din proprietatea persoanei al carui cnp este solicitat la momentul executiei, inmatriculate inainte de 1.1.2000.

Model de rezolvare pt. 2.4: care sunt automobilele (nr, marca, model, capacitate) din baza de date precum si durata in ani de la inmatriculare .

Pag.21

Model de rezolvare pt. 2.5: sa se afiseze toate persoanele (Nume, Localitate, Cnp) care detin in proprietate un automobil marca Audi inmatriculat in anul 2007.

Pag.22

Model de rezolvare pt. 2.6: sa se afiseze numai persoanele (Nume, Cnp, Localitate) ce sunt proprietari de automobile.

Model de rezolvare pt. 2.7: Sa se afiseze toate persoanele din baza de date (Nume, Cnp, Localitate) iar pentru cele ce detin automobile sa se afiseze marca, model si numar de inmatriculare.

Pag.23

Pag.24

Seminar 9 Extensii ale calculului relational in limbajul QBE

1. Prezentarea obiectului query ce utilizeaza functii agregat.

2. Se da schema unei baze de date:

persoane(cnp, nume, localitate)auto(nr, marca, model, capacitate, data, proprietar, impozit)

continand date despre persoane si automobile (vezi seminar 8)

Sa se descrie in limbajul QBE urmatoarele cereri:

2.1 Care sunt persoanele (Nume, Cnp, Localitate) din baza de date si cate automobile au acestea in proprietate.

2.2 Care sunt persoanele (Nume, Cnp) ce detin automobile si care este totalul impozitelor platite de fiecare din aceste persoane.

2.3 Care este suma impozitelor platite de toti proprietarii de automobile din Constanta.

Model de rezolvare pt. 2.1: care sunt persoanele (Nume, Cnp, Localitate) din baza de date si cate automobile au acestea in proprietate.

Pag.25

Model de rezolvare pt. 2.2: care sunt persoanele (Nume, Cnp) ce detin automobile si care este totalul impozitelor platite de fiecare din aceste persoane.

Pag.26

Model de rezolvare pt. 2.3: care este totalul impozitelor platite de toti proprietarii de automobile din Constanta.

Pag.27

Seminar 10 Limbajul Prolog – Notiuni de baza

1. Acomodarea cu mediul de programare Turbo Prolog

2. Verificarea programelor prezentate la cursul 10.

3. Rezolvarea unor probleme cu notiunile din cursul 10.

3.1 Sa se descrie printr-un program prolog relatiile de subordonare directa intre angajatii unei organizatii.

3.2 Sa se construiasca expresii goal pentru a raspunde la urmatoarele cereri:

- care sunt subordonatii directi ai unei anumite persoane ;- este o anumita persoana subordonata direct unei alte persoane ;- care este “seful direct” al unei anumite persoane;

3.3 Sa se defineasca predicatul coleg(x,y) in care x si y reprezinta numele unor persoane. Acest predicat stabileste daca x si y au acelasi sef direct.


- este o anumita persoana coleg cu a alta persoana ?- care sunt colegii unei anumite persoana;

Model de rezolvare pentru 3.1:

predicates sd(symbol,symbol) /* sef direct */

clauses sd(a,b). sd(a,c). sd(a,d). sd(b,e). sd(b,f).

Pag.28

Observatie: relatiile din program corespund urmatoarei structuri ierarhice:

Model de rezolvare pentru 3.2: sa se construiasca expresii goal pentru a raspunde la urmatoarele cereri:

- care sunt subordonatii directi ai unei anumite persoane ;

Goal: sd(b,X)X=eX=f2 Solutions

- este o anumita persoana subordonata direct unei alte persoane ;

Goal: sd(a,d)Yes

Goal: sd(d,a)No

- care este “seful direct” al unei anumite persoane;

Goal: sd(X,c)X=a1 Solution

Model de rezolvare pentru 3.3: sa se defineasca predicatul coleg(x,y) in care x si y reprezinta numele unor persoane. Acest predicat stabileste daca x si y au acelasi sef direct.

predicates sd(symbol,symbol) /* sef direct */ coleg(symbol,symbol)clauses sd(a,b). sd(a,c).

Pag.29

a

b c d

e f

sd(a,d). sd(b,e). sd(b,f). coleg(X,Y):-sd(Z,X),sd(Z,Y),X <> Y.


- este o anumita persoana coleg cu a alta persoana ?

Goal: coleg(b,d)Yes

Goal: coleg(a,d)No

- care sunt colegii unei anumite persoana;

Goal: coleg(b,X)X=cX=d2 Solutions

Pag.30

Seminar 11 Limbajul Prolog – obiecte compuse, recursivitate



2.1 Sa se defineasca predicatul s(x,y) in care x si y reprezinta numele unor persoane. Acest predicat stabileste daca x este sef pentru y (vezi Seminarul 10).


- este o anumita persoana seful unei alte persoane ?- care sunt subordonatii unui anumit sef;

2.3 Sa se defineasca un predicat care calculeaza suma primelor N numere naturale

2.4 Sa se realizeze un program Prolog care sa reprezinte expresii aritmetice si sa calculeze valoarea lor. Expresiile contin constante reale si operatori aritmetici.


predicates sd(symbol,symbol) /* sef direct */ s(symbol,symbol) clauses sd(a,b). sd(a,c). sd(a,d). sd(b,e). sd(b,f). s(X,Y) :- sd(X,Y). s(X,Y) :- sd(X,Z),s(Z,Y).


- este o anumita persoana seful unei alte persoane ?

Goal: s(a,f)Yes

Goal: s(b,c)No

- care sunt subordonatii unui anumit sef;

Pag.31

Goal: s(a,X)X=bX=cX=dX=eX=f5 Solutions


predicates suma(integer,integer)

clauses suma(0,0). suma(N,S):-N1=N-1,suma(N1,S1),S=S1+N.


domains nod=op(symbol);ct(real) tree=t(nod,tree,tree);vid

predicates calcul(tree,real)

clauses calcul(t(ct(X),vid,vid),X). calcul(t(op(plus),T1,T2),R):-calcul(T1,R1),calcul(T2,R2),R=R1+R2. calcul(t(op(minus),T1,T2),R):-calcul(T1,R1),calcul(T2,R2),R=R1-R2. calcul(t(op(ori),T1,T2),R):-calcul(T1,R1),calcul(T2,R2),R=R1*R2. calcul(t(op(div),T1,T2),R):-calcul(T1,R1),calcul(T2,R2),R=R1/R2.

goal X=t(op(plus), t(ct(10),vid,vid), t(op(ori), t(ct(20),vid,vid), t(ct(30),vid,vid) ) ),calcul(X,R),write("Rezultat=",R),nl.

Observatie: expresia considerata este 10 + 20 * 30

Pag.32

Seminar 12 Limbajul Prolog – liste



2.1 Sa se defineasca un predicat care obtine lista cuvintelor dintr-un text dat.

2.2 Sa se defineasca un predicat ce calculeaza valoarea unui polinom pentru un argument dat. Polinomul este specificat prin lista coeficientilor sai dati in ordinea inversa a gradului termenilor.

2.3 Sa se defineasca un predicat care inverseaza ordinea elementelor dintr-o lista.

2.4 Folosind predicatul de inversare lista sa se modifice programul 2.2 incat lista coeficientilor polinomului sa fie data in ordinea crescatoare a gradului termenilor.

2.5 Sa se defineasca un predicat pentru generarea permutarilor unei liste.


domains lista=string* predicates scan(string,lista)

clauses scan(S,[T|Tl]):-fronttoken(S,T,S1),!,scan(S1,Tl). scan(_,[]).

goal write("Text:"),readln(S),scan(S,L),write(L),nl.


domains polinom=real*

predicates val(polinom,real,real)

clauses val([],_,0):-!. val([H|T],X,V):-val(T,X,V1),V=V1*X+H.

goal

Pag.33

P=[1,2,3,4],X=2,val(P,X,V),write("Val=",V),nl.

Observatie: Polinomul dat este 4x3 + 3x2 + 2x + 1. Lista contine coeficientii in ordinea inversa a gradului termenilor.


Domains lista=symbol*

predicates adauga(lista,symbol,lista) inv(lista,lista)

clauses adauga([],X,[X]):-!. adauga([A|B],X,[A|C]):-adauga(B,X,C). inv([],[]):-!. inv([A|B],R):-inv(B,R1),adauga(R1,A,R). Goal L=[a,b,c,d],inv(L,L1),write(L1)


Domains lista=integer*

predicates ins(integer,lista,lista) perm(lista,lista)

clauses ins(X,L,[X|L]). ins(X,[H|L],[H|L1]):-ins(X,L,L1). perm([],[]):-!. perm([H|L],R):-perm(L,R1),ins(H,R1,R). goal L=[1,2,3],perm(L,L1),write(L1),nl,fail

Pag.34

Seminar 13 Limbajul Prolog – lucrul cu baze de date

1.1 Sa se realizeze un program prolog care sa permita lucrul cu o baza de date externa. Baza de date contine predicatul persoana avand 2 argumente: nume si varsta.

1.2 Sa se modifice programul 1.1 incat predicatul persoana sa aiba ca argument 2 un obiect compus pentru reprezentarea datei de nastere.

1.3 Sa se realizeze un program prolog care sa permita lucrul cu o baza de date externa ce

contine verbe si substantive. Programul va defini totodata un predicat pentru analiza morfologica a verbelor.


database persoana(symbol,integer)

predicates repeat operatie(symbol)

clauses repeat. repeat:-repeat.

operatie(add):-write("Nume:"),readln(N), write("Varsta:"),readint(V), asserta(persoana(N,V)),!. operatie(list):-persoana(X,Y),write(X," ",Y),nl,fail,!. operatie(end):-!. operatie("save"):-save(bd),!. operatie(load):-consult(bd),!.

goal repeat,write("operatie:"),readln(X),operatie(X),X="end".

Observatii:

1. Programul prevede patru operatii: load pentru incarcarea unei baze de date externe, save pentru salvarea bazei de date, add pentru adaugarea unei noi clauze, list pentru listarea bazei de date si end pentru terminarea programului.

2. Repeat este un predicat care intoarce intotdeauna valoarea adevarat. El este util pentru realizarea unor operatii repetitive prin backtracking.

Pag.35


domains persoana=integer numar=symbol cuvant=sub(string); ver(string,persoana,numar)database v(string) ve(string,string,persoana,numar) s(string)

predicates repeat operatie(symbol) sufix(string,string,string) analiza(string,cuvant)

clauses repeat. repeat:-repeat. sufix(C,T,RC):-concat(RC,T,C). analiza(X,ver(Inf,P,N)):-ve(Inf,X,P,N).

analiza(X,ver(Inf,1,sg)):-v(Inf),sufix(Inf,"a",X). analiza(X,ver(Inf,2,sg)):-v(Inf),sufix(Inf,"a",R),sufix(X,"i",R). analiza(X,ver(X,3,sg)):-v(X),sufix(X,"a",_). analiza(X,ver(X,3,pl)):-v(X),sufix(X,"a",_). analiza(X,ver(Inf,1,pl)):-v(Inf),sufix(Inf,"a",R),sufix(X,"am",R). analiza(X,ver(Inf,2,pl)):-v(Inf),sufix(Inf,"a",R),sufix(X,"ati",R). analiza(X,sub(X)):-s(X). operatie(v):-write("Infinitiv:"), readln(I), assertz(v(I)). operatie(ve):-write("Infinitiv:"),readln(I), write("Flexiune:"),readln(F), write("Persoana:"),readint(P), write("Numar:"),readln(N),assertz(ve(I,F,P,N)). operatie(s):-write("Forma de baza:"),readln(B), assertz(s(B)). operatie(lv):-v(I),write("a ",I),nl. operatie(lve):-ve(I,F,P,N), write("a ",I," ",F," ",P," ",N),nl. operatie(ls):-s(B),write(B),nl. operatie(l):-operatie(lv);operatie(lve);operatie(ls). operatie(a):-write("Cuvant:"),readln(C), analiza(C,C1),write(C1),nl.

Pag.36

operatie(end). operatie("save"):-save(bd). operatie(load):-consult(bd). operatie(dv):-write("Verb:"),readln(X),retract(v(X)).

goal repeat,write("operatie:"),readln(X),operatie(X),X="end".

Observatii:

1. Predicatul analiza stabileste pentru fiecare forma flexionata, forma de infinitiv, numarul si persoana pentru verbele terminate la infinitiv in a.

2. Programul prevede definirea exceptiilor pentru verbele neregulate.

3. Predicatul sufix permite varificarea faptului ca un cuvant (argumentul 1) are o anumita terminatie (argumentul 2), furnizandu-ne si radacina cuvantului (argumentul 3).

Pag.37

Seminar 14 Limbajul Prolog – prelucrare simbolica

1.1 Sa se verifice programul Prolog prezentat in cursul 14 pentru analiza unei expresii ce contine variabile, constante operatori aritmetici si functiile: sinus, cosinus, logaritm.

1.2.Sa se realizeze un program Prolog care defineste regulile de derivare pentru expresii de

tipul celor de la 1.1. Model de rezolvare pentru 1.2:

Domains

exp=var(symbol);ct(real);plus(exp,exp);minus(exp,exp);mult(exp,exp); div(exp,exp);ln(exp);sin(exp);cos(exp);pow(exp,exp)

predicates

d(exp,string,exp)

clauses

d(ct(_),_,ct(0)):-!. d(var(X),X,ct(1)):-!. d(var(_),_,ct(0)):-!. d(plus(U,V),X,plus(U1,V1)):-d(U,X,U1),d(V,X,V1). d(minus(U,V),X,minus(U1,V1)):-d(U,X,U1),d(V,X,V1). d(mult(U,V),X,plus(mult(U1,V),mult(U,V1))):-d(U,X,U1),d(V,X,V1). d(pow(U,ct(N)),X,mult(mult(ct(N),pow(U,ct(N1))),U1)):-d(U,X,U1),N1=N-1.

d(div(U,V),X,div(minus(mult(U1,V),mult(U,V1)),pow(U,ct(2)))):- d(U,X,U1),d(V,X,V1).

d(ln(U),X,div(U1,U)):-d(U,X,U1). d(sin(U),X,mult(cos(U),U1)):-d(U,X,U1). d(cos(U),X,mult(ct(-1),mult(sin(U),U1))):-d(U,X,U1). goal E=plus(pow(var(x),ct(3)),ct(1)),d(E,V,E1),write(E1).

Pag.38

Observatii:

1. Expresia E data spre derivare este x3 + 1.

2. Predicatul pentru derivare este d si are 3 argumente. Primul argument este expresia ce trebuie derivata, argumentul 2 este varaibila in raport cu care se face derivarea, iar argumentul 3 reprezinta expresia rezultata in urma derivarii.

Pag.39

logica computationala

Documents