slide-uri logica

233
CURS 1-2 Sunt, în anul universitar 2010-2011, semestrul I, 16 săptămâni de şcoală; săptămânile a 8-a şi a 16-a sunt destinate lucrărilor de evaluare În consecinŃă, vom avea 14 cursuri şi 14 seminarii (teoretic) Un curs a fost pierdut deoarece a coincis cu deschiderea oficială a anului universitar Rămân deci 13 cursuri şi 14 seminarii (teoretic, pentru că vom avea tot 13 seminarii) În perioada 4-9 octombrie 2010 suntem în săptămâna a doua cu primul curs şi al doilea seminar, dar acesta ar putea fi considerat şi el primul (Ńinând cont de faptul că trebuie să reprezinte primul curs) INFORMAłI-VĂ LA TIMP (pagini web…)

Upload: avadanei-cosmin

Post on 29-Jun-2015

223 views

Category:

Documents


1 download

TRANSCRIPT

Page 1: slide-uri logica

CURS 1-2• Sunt, în anul universitar 2010-2011, semestrul I, 16

săptămâni de şcoală; săptămânile a 8-a şi a 16-a sunt destinate lucrărilor de evaluare

• În consecinŃă, vom avea 14 cursuri şi 14 seminarii (teoretic)

• Un curs a fost pierdut deoarece a coincis cu deschiderea oficială a anului universitar

• Rămân deci 13 cursuri şi 14 seminarii (teoretic, pentru că vom avea tot 13 seminarii)

• În perioada 4-9 octombrie 2010 suntem în săptămâna a doua cu primul curs şi al doilea seminar, dar acesta ar putea fi considerat şi el primul (Ńinând cont de faptul cătrebuie să reprezinte primul curs)

• INFORMAłI-VĂ LA TIMP (pagini web…)

Page 2: slide-uri logica

DE CE LOGICA ?

• Introducere

Page 3: slide-uri logica

LOGICA PENTRU INFORMATICĂ

Facultatea de InformaticăUniversitatea „Al.I.Cuza” Iaşi

(http://www.info.uaic.ro)

Page 4: slide-uri logica

Profesori 1

• Prof. Dr. Cristian Masalagiu (Titular curs) [email protected]://profs.info.uaic.ro/~masalagiu

Page 5: slide-uri logica

Profesori 2

• Asist. drd. Cosmin Vârlan (seminar)[email protected]://profs.info.uaic.ro/~vcosmin

Page 6: slide-uri logica

Profesori 3

• Drd. Vasile Alaiba (seminar)[email protected]://profs.info.uaic.ro/~alaiba

Page 7: slide-uri logica

Profesori 4

• Marius Barat (seminar)[email protected]://students.info.uaic.ro/~marius.barat

Page 8: slide-uri logica

Orar 1 (http://www.info.uaic.ro/~orar):

• Curs: Luni 10.00 - 12.00 semianul A (C2)

Luni 12.00 – 14.00 semianul B (C2)

Page 9: slide-uri logica

Orar 2 (http://www.info.uaic.ro/~orar)

• Seminarii (ştiŃi cu cine, cf. ORAR):Luni: 10.00 – 12.00 : B6 (C903)

Miercuri: 08.00 – 10.00 : A1 (C112)

08.00 – 10.00 : B4 (C903)

18.00 – 20.00 : B8 (C903)

Joi: 08.00 – 10.00 : A2 (C901)

08.00 – 10.00 : 1X (C903)

10.00 – 12.00 : A3 (C112)

10.00 – 12.00 : B5 (C903)

10.00 – 12.00 : B7 (C909)

Page 10: slide-uri logica

Orar 3 (http://www.info.uaic.ro/~orar)

• Seminarii:Joi: 12.00 – 14.00 : A5 (C903)

14.00 – 16.00 : A6 (C903)

16.00 – 18.00 : 1X (C903)

Vineri: 08.00 – 10.00 : B1 (C901)

10.00 – 12.00 : B2 (C901)

14.00 – 16.00 : A4 (C909)

16.00 – 18.00 : A7 (C909)

18.00 – 20.00 : B3 (C909)

Page 11: slide-uri logica

Orar 4 (http://www.info.uaic.ro/~orar)

• Ore de consultaŃii– C.Masalagiu, V.Alaiba, M.Barat:

Miercuri: 10.00 – 12.00 Cabinet – C305

– C.Varlan:

Miercuri: 18.00 – 20.00 Cabinet – C211

Page 12: slide-uri logica

CerinŃe 1

http://www.info.uaic.ro -> Membri-> Personal Academic (pentru a cunoaşte şi alŃi profesori

şi a naviga către paginile noastre)

http://www.info.uaic.ro -> StudenŃi-> Regulamente

http://profs.info.uaic.ro/~masalagiu/-> SecŃiunea „Logic”

Page 13: slide-uri logica

CerinŃe 2

• Nota finală se obŃine în urma acumulăriiunui număr de puncte (maxim 100) şi înurma aplicării unui algoritm de tip Gauss (conform regulamentului în vigoare)

Page 14: slide-uri logica

CerinŃe 3

• 60 din cele 100 de puncte se pot obŃine la cele două lucrări din săptămânile 8 respectiv 16

• 40 de puncte se pot obŃine în urmaactivităŃii la seminar din timpul semestrului

• UrmăriŃi paginile web!

Page 15: slide-uri logica

CerinŃe 4

• Sunt necesare un minim de 30 de punctepentru a promova

• A se consulta (deja menŃionat) măcar pagina http://profs.info.uaic.ro/~masalagiu(„Logic”)

Page 16: slide-uri logica

CerinŃe 5• Bibliografie „scrisă” minimală:

Masalagiu, C. - Fundamentele logice ale Informaticii , Editura Universitatii „Al. I. Cuza”, Iasi, 2004, ISBN 973-703-015-X.

Masalagiu, C. - Introducere în programarea logicasi limbajele de programare logica , Ed. Universitatii„Al. I. Cuza”, Iasi, 1996.

Cazacu, C., Slabu, V. - Logica matematica , EdituraStefan Lupascu, Iasi, 1999, ISBN 973-99044-0-8.

Page 17: slide-uri logica

CerinŃe 6

• Bibliografie principală:Masalagiu, C. - Fundamentele logice ale Informaticii , Editura Universitatii "Al. I. Cuza", Iasi, 2004, ISBN 973-703-015-X.

http://profs.info.uaic.ro/~masalagiu(În secŃiunea „Logic” - Bibliografie de bază;linkurile pot fi accesate doar din cadrul FII)

A se învăŃa şi după carte, nu numai după slide-uri !!!

Page 18: slide-uri logica

Capitolele tematice• (unele nu vor fi prezentate chiar în această

ordine)• Logica în Informatică• Algebre booleene• Logica propoziŃională• Logica cu predicate de ordinul I • Sisteme deductive şi teorii logice• Introducere în Programarea logică• OBDD-uri şi Verificare

Page 19: slide-uri logica

Realitate•Realitate: obiecte şi fenomene aflate în rela Ńii de interdependen Ńă•RelaŃiile (legăturile) se reflectă, în procesul gândirii umane, prin afirma Ńii (judecăŃi)

Page 20: slide-uri logica

Logica (intuitiv) 1

• Logica (în sens filozofic) este ştiinŃa regulilor generale ale gândirii, cu accent pe aspectele exacte şi de natură structurală ale acesteia

• Alte „definiŃii” – după cum urmează

Page 21: slide-uri logica

Logica (intuitiv) 2

• Logica studiază modul de alcătuire a raŃionamentelor corecte, prin care, pornind de la afirmaŃii iniŃiale(presupuse a fi adevărate) se obŃin (utilizând reguli de inferenŃă) afirmaŃii noi (de asemenea adevărate)

Page 22: slide-uri logica

AfirmaŃii

• O afirma Ńie este adevărată dacă reflectă în mod adecvat realitatea şi falsă în caz contrar

• Este acceptat faptul că valorile de adevăr ataşate unei afirmaŃii pot avea o natură subiectivă şi, în consecinŃă, pot fi şi altceva decât cele standard (adevărat şi fals); dar asta…în „alte logici”

• De exemplu: necunoscut, posibil adevărat, adevărat din când în când, etc.

Page 23: slide-uri logica

Logica clasică• Logica clasic ă (aristotelic ă, bivalent ă)

foloseşte doar afirmaŃii cărora li se poate asocia în mod unic o valoare de adevăr standard (independentă de context, moment de timp, etc.) şi se bazează în esenŃă pe principiul tertium non datur (terŃiul exclus: dacă o afirmaŃie nu este adevărată, atunci ea este cu certitudine falsă şi reciproc)

• Un alt principiu este cel al extensionalităŃii(adevărul unei formule…)

• Există şi logici neclasice (exemple)

Page 24: slide-uri logica

Idei suplimentare 1• Logica matematic ă, formal ă

(simbolic ă), preia problemele logicii filozofice şi le cercetează folosind mijloace matematice specifice, punându-se bază pe rigurozitate şi claritate în detrimentul nuanŃelor sau intuiŃiei

Page 25: slide-uri logica

Idei suplimentare 2

• Aplicarea acesteia în Informatic ă necesită însă o anumită adaptare, atât a modului de prezentare a conceptelor (terminologiei) cât şi a metodelor de demonstraŃie, accentul căzând pe constructivism(algoritmic ă)

Page 26: slide-uri logica

Despre CURS• Structura Cursului; sugestii privind examinarea• DificultăŃi de învăŃare (sunt şi avantaje…)• Paradoxuri, greşeli frecvente, exemple• Sferă, conŃinut, gen proxim, diferenŃă specifică• Silogisme, axiome, teoreme, reguli de inferenŃă,

raŃionamente, exemple• Axiome adevărate şi reguli de inferenŃă

corecte (sound) – pot exista raŃionamente corecte, dardacă se „pleacă” cu premize false…(vezi şi „paradoxuri”)

• Sintaxă + semantică – Logica este un limbaj de programare: formulă + valoare de adevăr (execuŃie = evaluare)

• Nr. de pagină s-ar putea să nu coincidă cu ceea ce aveŃivoi pe site (eu mă refer la cartea publicată)

Page 27: slide-uri logica

MulŃimi 1• Clasa funcŃiilor booleene (intuitiv)• NotaŃii• Din manualele de matematică de liceu

sunt bine cunoscute cel puŃin două modalităŃi de a prezenta o mulŃime:

-Prin enumerarea elementelor sale : N = {0, 1, 2, ...} este mulŃimea numerelor naturale

Page 28: slide-uri logica

MulŃimi 2

-Prin specificarea unei propriet ăŃi caracteristice :A = {x ∈ R | x2 + 9x – 8 = 0}, este mulŃimea rădăcinilor reale ale unei ecuaŃii polinomiale de gradul al II-lea-Mai avem o posibilitate, bazată peconstructivism:

Page 29: slide-uri logica

MulŃimi 3 (Peano)• Baza. 0 ∈ N (zero este număr

natural)• Pas constructiv (structural ). Dacă

n ∈ N, atunci s(n) ∈ N (dacă n este număr natural, atunci succesorul său imediat este număr natural)

• Nimic altceva nu mai este num ăr natural

Page 30: slide-uri logica

MulŃimi 4

• Un prim avantaj este acela că se poate folosi aceeaşi metodă pentru a introduce alte definiŃii, care sunt legate de mulŃimea respectivă în totalitatea ei. Putem da astfel o definiŃie constructivă (recursivă) a adunării numerelor naturale:-Baza. x + 0 = x, pentru fiecare x ∈ N (a aduna 0 la orice număr natural înseamnă a-l lăsa neschimbat)-Pas constructiv . x + s(y) = s(x + y), pentru fiecare x, y ∈ N (dacă ştim să calculăm x + y şi cunoaştem succesorul imediat al numărului natural y, atunci ştim să calculăm şi suma x + s(y); mai exact, aceasta coincide cu succesorul imediat al numărului care reprezintă suma x + y) -Nimic altceva…

Page 31: slide-uri logica

MulŃimi 5

• Un al doilea, şi cel mai important, avantaj este posibilitatea folosirii în demonstraŃii a Principiului induc Ńiei structurale :-Fie A o mulŃime definită constructiv,

A’ ⊆ A mulŃimea elementelor ini Ńiale (definite prin pasul Baza al definiŃiei) şi P o “afirmaŃie” care trebuie demonstrată pentru toate elementele lui A-Acceptăm că P(a) este adevărată pentru fiecare a ∈ A dacă şi numai dacă:

Page 32: slide-uri logica

MulŃimi 6

• 1 (Baza – elemente iniŃiale). Arătăm că P(a) este adevărată pentru fiecare a ∈ A’

• 2 (Pas inductiv – elemente noi din elemente vechi):-Fie orice b ∈ A, element nou obŃinut din elementele deja “construite” a1, a2, ... , an, cu ajutorul “operatorului” f (vom conveni să scriem acest lucru prin b = f(a1, a2, ... , an), deşi relaŃia dintre elementele “vechi”şi cele “noi” nu este întotdeauna de natură funcŃională) şi presupunem că este adevărată P(ai) pentru fiecare i ∈ {1, 2, ..., n}-Arătăm că este adevărată P(b)

• Probleme seminar: http://profs.info.uaic.ro/~masalagiu/pub/Seminar1.pdf

Page 33: slide-uri logica

Algebre booleene 1• Se numeşte algebr ă boolean ă un 4-uplu M,

M = <M, ⊥, ∇, ~ >, format din orice mulŃime nevidă M (suportul algebrei) două operaŃii binare ⊥, ∇ : M × M → M şi o operaŃie unară ~ : M → M, care satisfac condiŃiile (legile):

• 1) x ⊥ y = y ⊥ x comutativitate(a lui ⊥)

• 2) (x ⊥ y) ⊥ z = x ⊥ (y ⊥ z)asociativitate (a lui ⊥)

• 3) x ⊥ (y ∇ z) = (x ⊥ y) ∇ (x ⊥ z) distributivitate (a lui ⊥ faŃă de ∇)

• 4) (x ⊥ y) ∇ y = y absorbŃie• 5) (x ⊥ (~x)) ∇ y = y legea contradicŃiei

Page 34: slide-uri logica

Algebre booleene 2

şi respectiv

• 1’) x ∇ y = y ∇ xcomutativitate (a lui ∇)

• 2’) (x ∇ y) ∇ z = x ∇ (y ∇ z)asociativitate (a lui ∇)

• 3’) x ∇ (y ⊥ z) = (x ∇ y) ⊥ (x ∇ z)distributivitate (a lui ∇ faŃă de ⊥)

• 4’) (x ∇ y) ⊥ y = y absorbŃie• 5’) (x ∇ (~x)) ⊥ y = y legea tautologiei

Page 35: slide-uri logica

Algebre booleene 3• Dualitate; principiul dualităŃii• NotaŃii (reamintit: M – B, 2V; ⊥ - •, ∩; ∇ - +, U;

~ - ¯ , CV)• Reprezentare (tabele „de adevăr”, standard)• FuncŃii importante (0, 1, 2 argumente): 0, 1, c0,

c1, 1B, ¯ , +, •, ⊕⊕⊕⊕, | . • Numărul de funcŃii din FB-uri• Reprezentarea „numerică” a tabelelor „standard”• Alte considerente algebrice (latici…)• Alte „legi” (Tabelul 1.1 – pag.30 – cartea

tipărită)

Page 36: slide-uri logica

CURS 3

• Reprezentarea funcŃiilor booleene• Forme normale• Clase speciale de funcŃii booleene• Sintaxa LP

Page 37: slide-uri logica

Reprezentarea funcŃiilorbooleene 1

• NotaŃii: x1 = x şi x0 = • Indicii (superiori) precedenŃi nu se supun

principiului dualităŃii (de exemplu, nu este adevărat că (x1 = x) coincide cu (x0 = x ))

• Dacă xi, αi ∈ B atunci, direct din notaŃiile de mai sus, rezultă că:

• (x0)α = (xα)0 precum şi (xα = 1 dacă şi numai dacă x = α)

x

Page 38: slide-uri logica

Reprezentarea funcŃiilorbooleene 2

• Teorem ă (de descompunere, în sumă de „termeni”). Pentru fiecare n ∈ N*, f ∈ FB(n) şi fiecare k ∈ [n], avem:

oricare ar fi x1, x2, ... , xn ∈ B (demonstraŃie)• EnunŃaŃi teorema duală

Page 39: slide-uri logica

Reprezentarea funcŃiilorbooleene 3

• Defini Ńie. Fie n ∈ N* şi x1, x2, ... , xn ∈ Bvariabile (booleene) distincte. NotămmulŃimea (lista!) acestora cu X = {x1, x2, ... , xn}. Se numeşte termen (n-ar, peste X) orice produs

unde 0 ≤ k ≤ n, α1, α2, ... ,αk ∈ B şi 1≤ i1<i2 < ... < ik ≤ n

Page 40: slide-uri logica

Reprezentarea funcŃiilor booleene4

• Termenul generat pentru k=0 este 1 (prin convenŃie). Pentru k = n obŃinem aşa-numiŃii termeni maximali (maxtermeni) , adică acei termeni în care fiecare dintre variabilele considerate apare o dată şi numai o dată (barată sau nebarată), în ordinea precizată

• Exemple• Numărul de termeni şi maxtermeni distincŃi• Dual: factori şi maxfactori

Page 41: slide-uri logica

Forme normale 1• Defini Ńie.

-Se numeşte formă normală disjunctivă (n-ară, n ∈ N*), sau (n-)FND pe scurt, orice sumă (finită) de termeni n-ari distincŃi -Se numeşte formă normală disjunctivă perfectă (n-ară, n ∈ N*), sau (n-)FNDP pe scurt, orice sumă de maxtermeni n-ari distincŃi

• Facem abstracŃie de ordinea (max)termenilor dintr-o sumă, mai exact, considerând oricare dou ă sume care difer ă doar prin ordinea termenilor, le vom privi ca fiind identice- Vor exista astfel forme normale disjunctive n-are având k termeni, 0 ≤ k ≤ 3n (prin convenŃie, pentru k = 0, unica formă care este acceptată şi este şi perfectă, se notează tot cu 0)-Care va fi numărul total al (n -)FND – urilor? Dar cel al(n-)FNDP–urilor ?

Page 42: slide-uri logica

Forme normale 2

• Teorem ă. Orice funcŃie booleană f se poate „reprezenta” în mod unic ca o FNDP:

(demonstraŃie)• Mai spunem că expresia din

membrul drept al reprezentării este (o) FND(P) pentru f

Page 43: slide-uri logica

Forme normale 3• Prin dualizare, folosind noŃiunile de (n-)factor peste X şi

maxfactor (n-ar, peste X) , putem defini noŃiunea de formă normală conjunctivă (n-ară) ((n-)FNC, adică orice produs de factori dictincŃi) şi respectiv formă normală conjunctivă (n-ară) perfectă ((n-)FNCP, adică orice produs de maxfactori distincŃi)

• ConvenŃie: două produse nu vor fi considerate distincte dacă diferă doar prin ordinea componentelor

• EnunŃaŃi duala teoremei anterioare, pentru FNCP• Care va fi numărul total al (n -)FNC – urilor? Dar cel al

(n-)FNCP–urilor ?

Page 44: slide-uri logica

Clase speciale de funcŃii booleene 1

• Criteriul „numărul total de apariŃii ale variabilelor în reprezentarea unei funcŃii” (apariŃia unei aceleiaşi variabile pe poziŃii diferite se numără distinct) poate genera alte forme normale

• Folosind această „măsură” (pe care o vom nota cu n(φ)), putem numi formă normală disjunctivă minimală (FNDM) pentru f ∈ FB orice FND φ’, astfel încât:n(φ’) = min {n(φ) | φ este FND pentru f}

• Dată o funcŃie booleană f ∈ FB, se poate pune problema determin ării tuturor FNDM pentru f , sau a uneia standard (algoritmul lui Quine)

Page 45: slide-uri logica

Clase speciale de funcŃii booleene 2

• Similar, putem reduce în anumite cazuri timpul de procesare a unor texte (expresii, formule etc.) prin găsirea unui num ăr minim de opera Ńii booleene convenabile , cu ajutorul cărora să se „reprezinte” orice funcŃie booleană

Page 46: slide-uri logica

Clase speciale de funcŃii booleene 3

• Defini Ńie. -Clasa funcŃiilor booleene elementare este:

E = { | n ∈ N*, 1 ≤ p ≤ n, : Bn → B,(x1, x2, ... , xp, ... , xn) = xp}

(proiecŃii)-Fie n ∈ N*, t un număr natural, f, h1, h2, ... , ht ∈ FB(n) şi g ∈ FB(t).

npi

npi

npi

Page 47: slide-uri logica

Clase speciale de funcŃii booleene 3

Spunem că f se obŃine din g, h1, h2, ... , ht prin superpozi Ńie dacă pentru fiecare x = <x1, x2, ... , xn> avem:

f(x) = g(h1(x), h2(x), ... , ht(x))

-Fie M ⊆ FB. Se numeşte M-şir orice secvenŃă (listă) finită f0, f1, ... , fr de funcŃii booleene în care fiecare fi este fie din E U M, fie se obŃine prin superpoziŃie din alte funcŃii, aflate în aceeaşi listă dar înaintea lui fi

Page 48: slide-uri logica

Clase speciale de funcŃii booleene 4

• Alte notaŃii …• MulŃimi închise, închideri• DefiniŃii alternative• Rezultate importante• Exemple: T0, T1, Aut , Mon , Lin• MulŃimi complete, precomplete, baze• Alte rezultate şi exemple

Page 49: slide-uri logica

Final FB

• Index recapitulativ• ExerciŃii suplimentare• Alte comentarii (ce a fost, ce va fi în Curs)

Page 50: slide-uri logica

LP - Sintaxa 1• Logica propoziŃională, d.p.d.v. sintactic, este o mulŃime

de „formule” (propoziŃionale), notată LP • Defini Ńie (constructiv ă):

-Fie o mulŃime numărabilă de variabile propoziŃionale(formule elementare, formule atomice pozitive, atomi pozitivi), A = {A1, A2, … }. Fie, de asemenea, C = {, ∨, ∧} mulŃimea conectorilor/conectivelor logici/logice: non (nega Ńia), sau (disjunc Ńia), respectiv şi (conjunc Ńia) şi P = { ( , ) } mulŃimea parantezelor(rotunde). Formulele (elementele lui LP) vor fi “cuvinte”(expresii bine formate) peste alfabetul L = A U C U P

Page 51: slide-uri logica

LP - Sintaxa 2

-Baza (formulele elementare sunt formule):A ⊆ LP-Pas constructiv (obŃinere formule noi din formule vechi):(i) Dacă F ∈ LP atunci ( F) ∈ LP(ii) Dacă F1, F2 ∈ LP atunci ( F1 ∨ F2 ) ∈ LP(iii) Dacă F1, F2 ∈ LP atunci ( F1 ∧ F2 ) ∈ LP(iv) Dacă F ∈ LP atunci (F) ∈ LP(v) Nimic altceva nu mai este formulă

Page 52: slide-uri logica

CURS 4

• Sintaxa LP• Semantica LP

Page 53: slide-uri logica

LP - Sintaxa 3

• Arbori, subformule

• (( F) ∨ G) se va nota cu (F → G) • Pentru ((( F) ∨ G) ∧ (( G) ∨ F)) folosim (F ↔ G)

sau ((F → G) ∧ (G → F))

• Fi este o prescurtare pentru F1 ∧ F2 ∧ ... ∧ Fn

• Fi este prescurtarea lui F1 ∨ F2 ∨ ... ∨ Fn

• Comentarii asupra noilor simboluri

∧n

i= 1

∨n

i= 1

Page 54: slide-uri logica

LP - Sintaxa 4

• Vom numi literal o variabilă propoziŃională sau negaŃia sa. A ∈ A se va numi literal pozitiv iar orice element de forma A, A ∈ A va fi un literal negativ (vom nota

= { A1, A2, … }). Dacă L este un literal, atunci complementarul său, va nota literalul A, dacă L = A ∈ A şi respectiv literalul A dacă L = A

• Se numeşte clauz ă orice disjuncŃie (finită) de literali. Se numeşte clauz ă Horn o clauză care are cel mult un literal pozitiv. O clauz ă pozitiv ă este o clauză care conŃine doar literali pozitivi, iar o clauz ă negativ ă va conŃine doar literali negativi. O clauz ă Horn pozitiv ă va conŃine exact un literal pozitiv (dar, posibil, şi literali negativi)

LA

Page 55: slide-uri logica

LP – Semantica 1• Semantica (înŃelesul) unei formule

propoziŃionale este, conform principiilor logicii aristotelice, o valoare de adevăr (a(=0) sau f (=0)), obŃinută în mod determinist, care este independentă de context. Notând de la început pe a cu 1 şi pe f cu 0, astfel încât să putem “lucra” cu algebra booleană B = < B, •, +, ¯ >, noŃiunea principală este cea de asignare(interpretare , structur ă)

• Defini Ńie. Orice funcŃie S, S : A → B se numeşte asignare

Page 56: slide-uri logica

LP – Semantica 2• Teorem ă (de extensie) . Pentru fiecare asignare S

există o unică extensie a acesteia, S’ : LP → B (numită tot structur ă sau interpretare ), care satisface:(i) S’(A) = S(A), pentru fiecare A ∈ A(ii) S’(( F)) = pentru fiecare F ∈ LP(iii) S’((F1 ∧ F2) ) = S’(F1) • S’(F2), pentru fiecare F1, F2 ∈ LP.(iv) S’((F1 ∨ F2) ) = S’(F1) + S’(F2), pentru fiecare F1, F2 ∈ LP(v) S’((F)) = S(F), pentru fiecare F ∈ LP(demonstraŃie)

S'(F)

Page 57: slide-uri logica

LP – Semantica 3• Defini Ńie (folosim tot S în loc de S’) .

-O formulă F ∈ LP se numeşte satisfiabil ă dacă există măcar o structură S (completă) pentru care formula este adevărată (S(F) = 1). Se mai spune în acest caz că S este model pentru F (simbolic, se mai scrie S ╞ F)

-O formulă este valid ă (tautologie) dacă orice structură este model pentru ea-O formulă este nesatisfiabil ă (contradic Ńie) dacă este falsă în orice structură (S(F) = 0, pentru fiecare S, sau S |≠ F, pentru fiecare S)

Page 58: slide-uri logica

LP – Semantica 4

• Teorem ă. O formulă F ∈ LP este validă dacă şi numai dacă ( F) este contradicŃie(demonstraŃie)

• Clasa tuturor formulelor propoziŃionale LPeste astfel partiŃionată în trei mulŃiminevide şi disjuncte: tautologii (formulevalide), formule satisfiabile dar nevalide, contradicŃii (formule nevalide); desen

Page 59: slide-uri logica

LP – Semantica 5• Defini Ńie.

-Două formule F1, F2 ∈ LP se numesc tare echivalente dacă pentru fiecare structură S ele au aceeaşi valoare de adevăr, adică S(F1) = S(F2) (simbolic, vom scrie F1 ≡ F2)-F1 şi F2 se numesc slab echivalente dacă F1 satisfiabilă implică F2 satisfiabilă şi reciproc (vom scrie F1 ≡s F2, ceea ce înseamnă că dacă există S1 astfel încât S1(F1) = 1, atunci există S2 astfel încâtS2 (F2) = 1 şi reciproc)

Page 60: slide-uri logica

LP – Semantica 6

-O formulă F ∈ LP este consecin Ńă semantic ă dintr-o mulŃime de formule G ⊆ LP, dacă: pentru fiecare structură corectă S (aceasta înseamnă …), dacă Ssatisface G (adică avem S(G) = 1 pentru fiecare G ∈ G) atunci S satisface F(simbolic, vom scrie G╞ F)

Page 61: slide-uri logica

LP – Semantica 7

• Teorem ă. Fie G ∈ LP şi

G = { G1, G2, …, Gn } ⊆ LP. Următoarele afirmaŃii sunt echivalente:

• (i) G este consecinŃă semantică din G• (ii) ( Gi ) → G este tautologie

• (iii) ( Gi ) ∧ G este contradicŃie

• (demonstraŃie)

∧n

i=1

∧n

i= 1

Page 62: slide-uri logica

LP – Semantica 8• Teorem ă. Sunt adevărate următoarele echivalenŃe (tari,

pentru oricare F, G, H ∈ LP):(a) F ∧ F ≡ F (a’) F ∨ F ≡ F (idempotenŃă)(b) F ∧ G ≡ G ∧ F (b’) F ∨ G ≡ G∨ F (comutativitate)(c) ( F ∧ G ) ∧ H ≡ F ∧ ( G ∧ H ) (c’) (F ∨ G) ∨ H ≡ F ∨ (G ∨ H) (asociativitate)(d) F ∧ ( G ∨ H ) ≡ (F ∧ G) ∨ (F ∧ H) (d’) F ∨ ( G ∧ H ) ≡ (F ∨ G) ∧ (F ∨ H) (distributivitate)(e) F ∧ ( F ∨ G ) ≡ F (e’) F ∨ ( F ∧ G ) ≡ F (absorbŃie)

Page 63: slide-uri logica

LP – Semantica 9(f) F ≡ F (legea dublei negaŃii)(g) ( F ∧ G ) ≡ F ∨ G (g’) ( F ∨ G ) ≡ F ∧ G (legile lui deMorgan)(h) F ∨ G ≡ F (h’) F ∧ G ≡ G (legile validităŃii, adevărate doar

dacă F este tautologie)(i) F ∧ G ≡ F (i’) F ∨ G ≡ G (legile contradicŃiei, adevărate doar

dacă F este contradicŃie)• Generalizări pentru mai multe formule

Page 64: slide-uri logica

LP – Semantica 10

• Teorem ă (de substitu Ńie). Fie H ∈ LP, oarecare. Fie orice F, G ∈ LP astfel încît F este o subformulă a lui H şi G este tare echivalentă cu F. Fie H’ formula obŃinută din H prin înlocuirea (unei apariŃii fixate a) lui F cu G. Atunci H ≡ H’ (demonstraŃie)

Page 65: slide-uri logica

LP – Forme normale 1

• Spre deosebire de cazul funcŃiilor booleene, studiemformele normale conjunctive şi formele normale disjunctive simultan (pentru început)

• Defini Ńie. O formulă F ∈ LP se află în form ă normal ă conjunctiv ă (FNC, pe scurt) dacă este o conjuncŃie de disjuncŃii de literali, adică o conjuncŃie de clauze:

Similar, F ∈ LP este în form ă normal ă disjunctiv ă (FND, pe scurt), dacă este o disjuncŃie de conjuncŃii de literali:

În cele de mai sus Li,j ∈ A U A

= ∧ ∨inm

i, ji=1 j=1F ( L )

= ∨ ∧inm

i , ji = 1 j = 1F ( L )

Page 66: slide-uri logica

LP – Forme normale 2• Teorem ă. Pentru fiecare formulă F ∈ LP

există cel puŃin două formule F1, F2 ∈ LP, F1 aflată în FNC şi F2 aflată în FND, astfel încât F ≡ F1 şi F ≡ F2 (se mai spune că F1 şi F2 sunt o FNC, respectiv o FND, pentru F) (demonstraŃie)

Page 67: slide-uri logica

LP – Forme normale 3

• Conform teoremei anterioare, precum şi datorită comutativităŃii şi idempotenŃei disjuncŃiei, comutativităŃii şi idempotenŃei conjuncŃiei (repetarea unui element, fie el literal sau clauză, este nefolositoare din punctul de vedere al (ne)satisfiabilităŃii unei formule), este justificată scrierea ca mul Ńimi a formulelor aflate în FNC

• Astfel, dacă F este în FNC, vom mai scrie F = {C1, C2, ... , Cm} (nu uităm totuşi că virgula aici provine dintr-o conjuncŃie, Ci fiind clauze)

L

Page 68: slide-uri logica

LP – Forme normale 4

• Fiecare clauză Ci poate fi la rândul ei reprezentată ca o mulŃime, Ci = {Li,1, Li,2,…. Li,ki }, Li,j fiind literali

• Mai mult, dacă avem F ∈ LP reprezentată ca mulŃime (de clauze) sau ca mulŃime de mulŃimi (de literali) şi ne interesează doar studiul (ne)satisfiabilităŃii ei, putem elimina clauzele C care conŃină atât L cât şi , deoarece L ∨ ≡ 1, 1 ∨ C ≡ 1 şi deci aceste clauze sunt tautologii (notate generic cu 1). Tautologiile componente nu au nici o semnificaŃie pentru stabilirea valorii semantice a unei formule F aflate în FNC (1 ∧ C ≡ C)

LL

Page 69: slide-uri logica

CURS 5

• Formule Horn• RezoluŃie

Page 70: slide-uri logica

Decidabilitate în LP• Teorem ă (decidabilitatea SAT) .

Satisfiabilitatea (validitatea, nesatisfiabilitatea) formulelor LP este decidabilă în timp exponenŃial(demonstraŃie)

• Alte comentarii, etc.

Page 71: slide-uri logica

Formule Horn în LP - 1• O clauză Horn este o disjuncŃie de literali care conŃine

cel mult un literal pozitiv• Defini Ńie. O formul ă Horn este o formulă aflată în FNC,

clauzele componente fiind (toate) clauze Horn • Vom numi (tot) formulă Horn (şi) o formulă care este

(tare) echivalentă cu o formulă având forma considerată în definiŃia precedentă. Se poate arăta că există formule propoziŃionale care nu sunt tare echivalente cu nici o formulă Horn, apariŃia a măcar doi literali pozitivi distincŃi într-o clauză fiind decisivă

• Formele posibile pentru o formulă Horn sunt (variabilele propoziŃionale care apar sunt elemente ale lui A):(i) C = A1 ∨ A2 ∨ …… ∨ Ak, k ≥ 1, k ∈ N şi(ii) C = A1 ∨ A2 ∨ …… ∨ Ak ∨ B, k ∈ N

Page 72: slide-uri logica

Formule Horn în LP - 2• În afară de reprezentarea ca mulŃimi, clauzele Horn pot fi

reprezentate şi sub aşa-numita form ă implica Ńional ă. Vom distinge cazurile (reamintim că 0 şi 1 denotă orice contradicŃie respectiv orice tautologie; ≜ - “egal” princonvenŃie):-C = A ∈ A (nici un literal negativ, un literal pozitiv). Acest lucru se mai poate scrie sub forma C ≜ 1 → A, ceea ce se justifică prin aceea că 1 → A ≜ 1 ∨ A ≡ 0 ∨ A ≡ A

-C = A1 ∨ A2 ∨ …… ∨ Ak (nici un literal pozitiv, măcar un literal negativ). Vom scrie C ≜ A1 ∧ A2 ∧ A3… …… ∧ Ak → 0 (folosim din nou definiŃia implicaŃiei şi faptul că 0 ∨ A ≡ A)

Page 73: slide-uri logica

Formule Horn în LP - 3

-C = A1 ∨ A2 ∨ …… ∨ Ak ∨ B (exact un literal pozitiv, măcar un literal negativ). Atunci C≜A1 ∧ A2 ∧ A3 … ∧ Ak→B, direct din definiŃia implicaŃiei-C ≜ □ (nici un literal negativ, nici un literal pozitiv)

• Din motive tehnice vom folosi şi această clauz ă vid ă (în reprezentarea clauzelor cu mulŃimi vom folosi pentru □ simbolul Ø, al mulŃimii vide). Prin convenŃie, □ este o clauză de orice tip (inclusiv o clauză Horn), dar nesatisfiabilă

Page 74: slide-uri logica

Formule Horn în LP - 4• Teorem ă. Satisfiabilitatea formulelor Horn este

decidabilă în timp liniar.DemonstraŃia se bazează pe următorul algoritm:

Algoritm HornIntrare : Orice formulă Horn, F, reprezentată ca mulŃime de clauze, clauzele componente fiind clauze Horn diferite de clauza vidă şi scrise sub formă implicaŃionalăIeşire : „DA”, în cazul în care formula F este satisfiabilă(furnizându-se şi o asignare S care este model pentru F) şi „NU” în caz contrar (F nu este satisfiabilă)

Page 75: slide-uri logica

Formule Horn în LP – 5• Metod ă (de marcare):

Pasul 1 . i := 0Pasul 2 .

Cât_timp ((există în F o clauză C de forma A1 ∧ A2 ∧ A3 …… ∧ Ak → B, cu A1, A2, A3, ... , Ak marcaŃi şi B nemarcat sau de forma A1 ∧ A2 ∧ A3 …… ∧ Ak → 0, cu A1, A2, A3, ... , Ak marcaŃi) şi (i = 0)) execut ă

Pasul 3 . Alege un asemenea C ca mai sus.Pasul 4 . Dacă ( C = A1 ∧ A2 ∧ A3 …… ∧ Ak → B )

atunciPasul 5 . Marchează B peste tot în F

altfelPasul 6 . i := 1

Sf_DacăSf_Cât_timp

Page 76: slide-uri logica

Formule Horn în LP - 6

Pasul 7 . Dacă ( i = 0 )

atunciPasul 8 . Scrie „DA”.

Pasul 9 . Scrie S, cu S(A) = 1 dacă şi numai dacă A apare în F şi

este marcat.

altfelPasul 10 . Scrie „NU”

Sf_Dacă

Page 77: slide-uri logica

Formule Horn în LP - 7• Arătăm mai întâi că algoritmul se termin ă pentru fiecare

intrare . Să precizăm că acŃiunea de marcare o privim iniŃialîn sensul că toate variabilele se presupun a fi nemarcate-Dacă F conŃine clauze de forma 1 → B (care se consideră a fi de fapt de formaA1 ∧ A2 ∧ A3 …… ∧ Ak → B, cu A1, A2, A3, ... , Ak marcaŃi şi B nemarcat), se procedează conform Algoritmului, adică se marchează toate apariŃiile lui B în F şi se trece la pasul următor. Mai departe, la fiecare execuŃie a corpului buclei(Paşii 3. şi 4.), fie se marchează o variabilă propoziŃională nouă (nemarcată încă), fie se iese din execuŃia buclei. Pentru că numărul de variabile peste care este construită formula F este finit, terminarea algoritmului este evidentă. Dacă nu există deloc clauze de tipul 1 → B, algoritmul se termină fără nici o execuŃie a corpului buclei, cu răspunsul „DA” (formula este satisfiabilă) şi cu asignarea S, în care S(A) = 0 pentru fiecare A (care apare în F)

Page 78: slide-uri logica

Formule Horn în LP - 8

• Arătăm în continuare că algoritmul este corect . Aceasta înseamnă că ieşirea algoritmului satisface ceea ce am dorit, adică răspunsul „DA”/S corespunde faptului că formula F furnizată la intrare este satisfiabilă (şi S atenŃie...F) iar răspunsul „NU” corespunde faptului că F este nesatisfiabilă. Vom separa cazurile:

Page 79: slide-uri logica

Formule Horn în LP - 9• Cazul a). La terminarea execuŃiei se

obŃine „DA” şi F nu conŃine clauze C de tipul 1 → B

• Cazul b). La terminare se obŃine „DA” iar F conŃine şi clauze C = 1 → B. Atunci bucla se termină după un anumit număr de execuŃii ale corpului său, valoarea lui i este 0 şi F conŃine în final clauze C având marcate anumite variabile

Page 80: slide-uri logica

Formule Horn în LP - 10• Cazul c) Algoritmul se termină cu i = 1 şi

răspunsul „NU”. Acest lucru înseamnă că există în F o clauză C = A1 ∧ A2 ∧ A3 …… ∧ Ak → 0 cu toŃi Ai, i ∈ [k] marcaŃi (obligatoriu, în F există şi clauze de forma 1 → B, B marcat), de unde rezultă că semantica lui C în asignarea furnizată de algoritm este de forma 1 → 0 şi prin urmare S(C) = 0, de unde S(F) = 0. Acest lucru nu înseamn ă însă că F este nesatisfiabil ă. Pentru a trage această concluzie trebuie să arătăm că pentru nici o altă asignare, ea nu poate fi model pentru F

Page 81: slide-uri logica

Formule Horn în LP - 11

Să presupunem (RA) că există o asignare S’ (diferită de S, furnizată de algoritm) astfel încât S’(F) = 1. Să observăm, pentru început, că toate variabilele care au fost marcate în algoritm (deci cele care au primit valoarea de adevăr 1 în S), trebuie să primească valoarea 1 în oricare S’ cu S’(F) = 1. Altfel spus, asignarea S conŃine cel mai mic număr posibil de valori 1 (atribuite evident variabilelor marcate) astfel încît formula să aibă şanse să fie satisfiabilă. Într-adevăr, pentru fiecare S’ cu S’(F) = 1, trebuie să avem S’(C) = 1 pentru fiecare clauză C din F

• Să ne ocupăm puŃin de momentul în care se marchează o variabilă B, ordonând clauzele din F de forma C = A1 ∧ A2 ∧ A3 … ∧ Ak → B (k ≥ 1) după numărul de variabile din antecedent (chiar în algoritm, selecŃia unei clauze „pentru marcare” se poate face după un asemenea criteriu):

Page 82: slide-uri logica

Formule Horn în LP - 12• Clauze C de tipul 1 → B ≡ B (nici o variabilă în antecedent, B

nemarcat). De la acestea începe procesul de marcare. Din faptul că S’(C) trebuie să fie egal cu 1, este clar că trebuie pus S’(B) = 1 (B se şi marchează, deci S(B) = 1)

• Clauze C de forma A → B ≡ A ∨ B (o variabilă în antecedent; A este marcat, B nemarcat). A nu putea fi marcat decât dacă a apărut deja ca un consecvent într-o clauză de tipul anterior, sau în una de acelaşi tip cu aceasta şi care are antecedentul marcat. Prin urmare, în orice S’ cu S’(C) = 1, trebuie oricum să avem S’(A) = 1, deci S’( A) = 0 şi atunci S’(B) = 1 (consecinŃa este că B se

marchează, deci şi S(B) = 1)• Continuăm raŃionamentul cu C = A1 ∧ A2 → B (două variabile

în antecedent; ambele variabile marcate; B este, încă, nemarcat) şi ajungem din nou la concluzia că pentru fiecare S’, pentru a avea S’(C) = 1, trebuie să avem S’(B) = 1, precum şi S(B) = 1

Page 83: slide-uri logica

Formule Horn în LP - 13• Revenind, am arătat că pentru fiecare S’ astfel încât

S’(F) = 1, trebuie să avem şi S’(A) = 1 pentru fiecare A marcat de către algoritm, adică pentru fiecare A care satisface S(A) = 1 (procesul descris mai sus se continuă pentru oricâte variabile prezente în antecedent, iar numărul acestora este finit). Prin urmare, avem şi S’(C) = 0, de unde rezultă că S’(F) = 0, ceea ce este absurd

• Să arătăm în final că algoritmul Horn are timp de execu Ńie liniar . Faptul că t(n) ∈ O(f(n)), unde f(n) = a•n + b (a, b ∈ N*), rezultă imediat din faptul că la fiecare execuŃie a corpuluibuclei se marchează o nouă variabilă. Desigur că, pentru a obŃine în mod real acest lucru, algoritmul trebuie detaliat, în sensul că, de exemplu, în Paşii de tip 3 (de alegere a unei clauze corespunzătoare C), selecŃia variabilei de marcat trebuie făcută prin parcurgerea de un număr fix de ori (independent de numărul de execuŃii) a listei variabilelor peste care este construită F

Page 84: slide-uri logica

RezoluŃie în LP - 1• Fără a restrânge generalitatea, putem presupune că

lucrăm cu formule din LP aflate în FNC, reprezentate sub formă de mulŃimi (finite) de clauze, iar clauzele ca mulŃimi (finite) de literali

• Defini Ńie (rezolvent) . Fie clauzele C1, C2 , R. Spunem că R este rezolventul lui C 1, C2 (sau că C1, C2 se rezolvă în R, sau că R se ob Ńine prin rezolu Ńie într-un pas din C1, C2), pe scurt, R = ResL(C1, C2), dacă şi numai dacă există un literal L ∈ C1 astfel încât ∈ C2 şi R = (C1 \ {L}) U (C2 \ { })

• Vom putea reprezenta acest lucru şi grafic, prin arborele de rezoluŃie:

L

1c 2c∨

L

R

L

L

L

Page 85: slide-uri logica

RezoluŃie în LP - 2

• Rezolventul a două clauze este tot o clauză. Mai mult, rezolventul a două clauze Horn este tot o clauză Horn. Clauza vidă (□) poate fi obŃinută prin rezoluŃie din două clauze de forma C1 = {A} şi C2 = {A}. În definiŃia anterioară putem considera că C1 şi C2 sunt diferite între ele. Dacă ele ar coincide, atunci

C1 = C2 = C = … ∨ L∨…∨ ∨ … ≡ 1, adică acele clauze sunt tautologii, detectabile sintactic (în acest caz nu ne mai interesează alte metode formale de studiere a satisfiabilităŃii lor)

L

Page 86: slide-uri logica

RezoluŃie în LP - 3

• Teorem ă (lema rezolu Ńiei) . Fie oricare formulă F ∈ LP (aflată în FNC şi reprezentată ca mulŃime de clauze) şi R un rezolvent pentru C1, C2 ∈ F. Atunci F este tare echivalentă cu F U {R} (demonstraŃie)

• În teorema anterioară am fi putut considera, în loc de F, o mulŃime oarecare de clauze, chiar infinită (vezi Teorema de compactitate )

Page 87: slide-uri logica

RezoluŃie în LP - 4• Defini Ńie. Fie F o mulŃime oarecare de

clauze din LP şi C o clauză. Spunem că lista C’1, C’2 , … , C’m este o demonstra Ńie prin rezolu Ńie (în mai mul Ńi paşi) a lui C pornind cu F dacă sunt satisfăcute condiŃiile:

(i) Pentru fiecare i ∈ [m], fie C’i ∈ F, fie C’ieste obŃinut prin rezoluŃie într-un pas din C’j, C’k, cu j, k < i(ii) C = C’m

Page 88: slide-uri logica

RezoluŃie în LP - 5• În condiŃiile definiŃiei se mai spune că C este

demonstrabil ă prin rezolu Ńie (pornind cu F sau în ipotezele date de F ). Mai mult, pentru a spune acest lucru, este suficient ca F să fie inserat ă (prezentă) într-o demonstraŃie şi nu să fie neapărat ultimul element al acesteia. Intuitiv, o demonstraŃie prin rezoluŃie în mai mulŃi paşi înseamnă o succesiune finită de rezoluŃii într-un pas, care poate fi reprezentată şi grafic, printr-un arbore, sau chiar ca un graf oarecare (dacă nu folosim noduri diferite pentru apariŃiile distincte ale unei aceleiaşi clauze)

Page 89: slide-uri logica

RezoluŃie în LP - 6

• În particular, dacă C este clauza vidă, atunci demonstraŃia respectivă se numeşte şi respingere . Numărul de pa şi dintr-o demonstraŃie este dat de numărul de clauze obŃinute prin rezoluŃie într-un pas (din clauze anterioare). Acesta poate fi considerat ca fiind o măsură a „mărimii” (lungimii) demonstraŃiei. O altă măsură pentru o demonstraŃie reprezentată ca text poate fi chiar lungimea listei (numărul total de clauze sau chiar numărul total de clauze distincte). Dacă reprezentăm o demonstraŃie ca un arbore, putem folosi şi măsuri specifice, cum ar fi adâncimea arborelui, numărul de nivele, etc.

Page 90: slide-uri logica

RezoluŃie în LP - 7• Defini Ńie (mul Ńimea rezolven Ńilor unei mul Ńimi de

clauze) . Fie F o mulŃime de clauze din LP (nu neapărat finită). Notăm succesiv:-Res(F) = F U {R | există C1, C2 ∈ F astfel încât R = Res(C1, C2)}

-Res(n+1)(F) = Res(Res(n)(F)), n ∈ N-Prin Res(0)(F) vom înŃelege F şi atunci vom putea pune şi Res(1)(F) = Res(F)

-Res*(F) = (F). • Res(n)(F) se va numi mul Ńimea rezolven Ńilor lui F

ob Ńinu Ńi în cel mult n pa şi, iar Res*(F) mul Ńimea (tuturor) rezolven Ńilor lui F (alternativ – definiŃii recursive)

Page 91: slide-uri logica

RezoluŃie în LP - 8

• Direct din definiŃie rezultă că:

F = Res(0)(F) ⊆ Res(1)(F) ⊆ ... ⊆ Res(n)(F) ⊆ ... ⊆ … ⊆ Res*(F)

• Putem da atunci şi o definiŃie structurală a lui Res*(F). Vom nota astfel cu Resc mulŃimea definită prin:

Baza. F ⊆ RescPas constructiv : Dacă C1, C2 ∈ Resc şi

C = Res(C1, C2), atunci C ∈ Resc

Page 92: slide-uri logica

RezoluŃie în LP - 9

• Teorem ă. Pentru fiecare F ∈ LP, avem Res*(F) = Resc(demonstraŃie)Vom putea astfel folosi ambele notaŃii (definiŃii) pentru mulŃimea rezolvenŃilorunei mulŃimi de clauze

Page 93: slide-uri logica

RezoluŃie în LP - 10• Teorem ă. Fie F o mulŃime de clauze din

LP (nu neapărat finită). O clauză C ∈ LPse poate demonstra prin rezoluŃie pornind cu clauzele lui F dacă şi numai dacă există k ∈ N, asfel încât C ∈ Res(k)(F)(demonstraŃie)

Page 94: slide-uri logica

RezoluŃie în LP - 11• În cele de mai sus am folosit în majoritatea

cazurilor termenul mulŃimea de clauze F şi nu formula F (aflată în FNC). Deşi pe noi ne interesează doar formulele (care pot fi privite ca mulŃimi finite de clauze în cazul în care ne interesează doar satisfiabilitatea lor), aproape toate rezultatele sunt valabile şi pentru mulŃimi infinite (num ărabile ) de formule (clauze)

• Teorema următoare stabileşte o legătură importantă, privind satisfiabilitatea, între mulŃimile infinite şi cele finite de formule oarecare din LP

Page 95: slide-uri logica

RezoluŃie în LP - 12

• Teorem ă (de compactitate, pentru LP). Fie M o mulŃime infinită (numărabilă) de formule din LP. Atunci M este satisfiabilă dacă şi numai dacă fiecare submulŃime finit ă a sa este satisfiabilă (demonstraŃie)

• Teorem ă. Fie F ∈ LP, aflată în FNC şi reprezentată ca mulŃime (finită) de clauze. Atunci Res*(F) este finită (demonstraŃie)

Page 96: slide-uri logica

RezoluŃie în LP - 13

• Teorem ă (teorema rezolu Ńiei pentru calculul propozi Ńional) . Fie F o mulŃime oarecare de clauze din calculul propoziŃional. Atunci F este nesatisfiabilă dacă şi numai dacă � ∈ Res*(F)(demonstraŃie)

• Corectitudine şi completitudine (demonstraŃie)

Page 97: slide-uri logica

CURS 6

• Rafinări ale rezoluŃiei şi „complemente”• Teorii logice, sisteme de demonstraŃie

Page 98: slide-uri logica

Rafinări ale rezoluŃiei - 1• Rafin ările rezolu Ńiei sunt metode prin care se

urmăreşte obŃinerea clauzei vide (dacă acest lucru este posibil) într-un număr cât mai mic de paşi de rezoluŃie. Pornind cu formula F = {C1, C2, … , Cn} (aflată în FNC şi scrisă ca o mulŃime de clauze, la rândul lor clauzele fiind scrise ca mulŃimi de literali), se poate construi efectiv mulŃimea Res*(F), care poate fi reprezentată (fiind finită), după cum deja ştim, ca un graf neorientat (nodurile sunt rezolvenŃii succesivi, inclusiv clauzele iniŃiale, iar muchiile sunt introduse prin rezoluŃiile într-un pas aplicate). Practic, acest graf ar trebui să cumuleze toateposibilele demonstraŃii prin rezoluŃie care pornesc cu clauzele lui F (reamintim că anumiŃi rezolvenŃi sunt totuşi excluşi, deoarece reprezintă tautologii)

Page 99: slide-uri logica

Rafinări ale rezoluŃiei - 2

• Teorema rezolu Ńiei sugerează creareamai întâi a acestui graf de rezolu Ńie totalşi apoi parcurgerea lui pentru a vedea dacă � este (eticheta unui) nod în graf. Este suficient, de asemenea, să găsim o respingere în loc de a crea şi apoi parcurge întregul graf. Rafinările se împart în două mari categorii: strategii şi restric Ńii

Page 100: slide-uri logica

Rafinări ale rezoluŃiei - 3• Strategiile nu restrâng, în general, spaŃiul de căutare (adică

graful total) dar folosesc anumite informaŃii suplimentare despre clauze, astfel încât să crească şansele pentru selectarea rapidă a unei demonstraŃii căutate, adică a unui „cel mai scurt drum” pornind de la frunze (elementele lui F), către o rădăcină (clauza vidă). Astfel, cel puŃin la modul ideal, graful total nu se construieşte în întregime, ci doar acele porŃiuni din el (cât mai puŃine şi cât mai mici), care este posibil să „conŃină” măcar o respingere. Cel mai cunoscut exemplu este strategia unitar ă, în care se recomand ă ca la fiecare pas al rezoluŃiei măcar una dintre clauze să conŃină un singur literal (dacă însă nu mai poate fi aleasă nici o asemenea clauză unitară, se con-tinuă procesul de obŃinere de noi rezolvenŃi în mod obişnuit). Prin urmare, strategiile nu distrug completitudinea rezoluŃiei (dacă o formulă este nesatisfiabilă, atunci se poate demonstra acest lucru prin rezoluŃie, găsindu-se o respingere), dar, în cel mai rău caz, este posibil să nu conducă la nici o economie de timp

Page 101: slide-uri logica

Rafinări ale rezoluŃiei - 4

• Pe de altă parte, restric Ńiile distrug în multe situaŃii completitudinea rezoluŃiei (există formule nesatisfiabile pentru care nu se pot găsi respingeri, în situaŃia în care paşii de rezoluŃie sunt supuşi unor condiŃii prea restrictive), deoarece spaŃiul de căutare este practic micşorat într-un mod, să-i spunem, abuziv. Astfel, o anumită restricŃie poate interzice total folosirea (într-un pas de rezoluŃie) a unor clauze având o anumită formă sintactică. RestricŃiile rămân însă complete pentru anumite subclase de formule propoziŃionale. Există mai multe exemple importante de restricŃii

• Exemple absolut necesare (rezoluŃia pozitivă, SLD, etc.)

Page 102: slide-uri logica

Teorii logice, sisteme de demonstraŃie, (O)BDD

• Teorie logic ă: mulŃime de formule închisă la consecinŃă semantică

• Sistem de demonstra Ńie: axiome + reguli de inferenŃă

• Teorem ă de corectitudine şi completitudine

• Alte modalităŃi de reprezentare ale funcŃiilor booleene

Page 103: slide-uri logica

Teorii logice - 1

• Teorie logic ă - concept semantic pentru definirea şi tratarea global ă a unei mul Ńimi de „formule ”: TE

• O teorie logic ă este o (sub)clasă de formule închis ă la consecin Ńă semantic ă

• Cu alte cuvinte, o mulŃime TE de formule este teorie logică dacă pentru fiecare submulŃime

T ⊆ TE şi fiecare (altă) formulă G care este consecinŃă semantică din T, avem şi G ∈ TE

Page 104: slide-uri logica

Teorii logice - 2

• Exemple imediate de teorii logice sunt clasele formulelor valide (din LP, LP1, LP1= , etc.) NotaŃie pt. consecin Ńăsemantic ă: IIII ╞ F

Page 105: slide-uri logica

Sisteme deductive - 1

• Sistem deductiv (de deduc Ńie, de demonstra Ńie, inferen Ńial ) - concept sintacticpentru definirea şi tratarea global ă a unei mul Ńimi de „formule ”: SD

• Se numeşte sistem deductiv în FORM - mulŃimea (meta)formulelor - un cuplu SD = <AAAA, RRRR> unde- AAAA ⊆ FORM este o mulŃime de axiome iar ---- RRRR ⊆ FORM+ × CCCC o mulŃime de reguli de inferen Ńă (de deduc Ńie, de demonstra Ńie)

Page 106: slide-uri logica

Sisteme deductive – 2

• În cele de mai sus, FORM+ denotă mulŃimea relaŃiilor de oricâte argumente (cel puŃin unul) peste FORM, iar CCCCreprezintă o mulŃime de condiŃii de aplicabilitate. Fiecare regulă de inferenŃă r ∈ RRRR , are astfel aspectulr = < < G1, G2, … , Gn, G>, c>, unde n ∈ N, iar G1, G2, … , Gn ∈ FORM; c ∈ CCCC

• G1, G2, … , Gn sunt ipotezele (premizele) regulii, G reprezintă concluzia (consecinŃa) iar c desemnează cazurile (modalităŃile) în care regula poate fi aplicată. Vom scrie chiar r = < < {G1, G2, … , Gn}, G>, c> deoarece ordinea ipotezelor nu este esenŃială

Page 107: slide-uri logica

Sisteme deductive - 3• O regulă r = < < {G1, G2, … , Gn}, G>, c> va fi

scrisă şi ca:

• În cazul în care n = 0 şi c lipseşte, r poate fi identificată ca fiind o axiomă, după cum rezultă din definiŃia care urmează. Câteodată, alături de c, sunt explicitate separat şi restricŃiile sintactice locale asupra (formei) (meta)formulelor

1 2 nG , G , . . . . , G, c

G

Page 108: slide-uri logica

Sisteme deductive - 4

• Defini Ńie (demonstra Ńie, deduc Ńie sintactic ă,raŃionament) . Fie un sistem deductiv SD = <AAAA, RRRR> în FORM. Se numeşte demonstraŃie (pentru F m, pornind cu AAAA) în SD o listă de (meta)formule (DDDD) : F1, F2, … , Fmastfel încât pentru fiecare i ∈ [m], fie Fi ∈ AAAA, fie Fi este obŃinut din Fj1, Fj2, … , Fjm folosind o regulă r = < < {Fj1, Fj2, … , Fjm}, Fi>, c> ∈ RRRR, unde j1, j2, ... , jm < i

• Prin urmare, fiecare element al listei (DDDD) este fie o axiomă, fie este concluzia unei reguli de inferenŃă ale cărei ipoteze sunt elemente anterioare din listă

Page 109: slide-uri logica

Sisteme deductive - 5

• Este un sistem deductiv standard, finit specificat, care generează, după cum vom vedea din anumite teoreme ulterioare, întreaga clasă (şi numai pe aceasta ) a formulelor valide din LP1 (sistemul a fost introdus pentru prima dată de către A. Church în 1954)

• „Variantă” LP:• Axiome (AAAASD3). Pentru fiecare F, G, H ∈ LP,

avem:1. F → (G → F)2. (F → (G → H)) → ((F → G) → (F → H))3. ( F → G) → (( F → G) → F)

Page 110: slide-uri logica

Sisteme deductive - 6• Să remarcăm faptul că LP trebuie considerată

ca fiind construită peste alfabetul care conŃine drept conectori doar pe şi → (de exemplu,

A ∨ B va reprezenta A → B etc.)• Reguli de inferen Ńă (RRRRSD3). Există doar restricŃii

de natură sintactică (lipsind condiŃiile de aplicabilitate). Prima şi ultima schemă de regulă este deja amintită, şi anume modus ponens (pe scurt, (MP)):

Page 111: slide-uri logica

Sisteme deductive - 7

• Exemplu: să se arate că în SD3 se poate „genera” teorema (seminar…) T = (A → A)

• Precizăm încă de pe acum că axiomele ar trebui să fie formule valide (în sensul noŃiunii de adevăr adoptate) iar regulile de inferenŃă – corecte. De asemenea, axiomele suplimentare (aici nu există) –(măcar) satisfiabile

Page 112: slide-uri logica

CURS 7• Alte modalităŃi de reprezentare ale

funcŃiilor booleene: (O)BDD

Page 113: slide-uri logica

(O)BDD - 1

• Ştim ce înseamnă funcŃii booleene şi reprezentarea lor cu ajutorul tabelelor de adevăr sau cu expresii (FNCP, de exemplu)

• O altă reprezentare a elementelor din FB se bazează pe diagramele de decizie binare (BDD)

• Alegerea celei mai „convenabile” reprezentări depinde de context

• Tot ceea ce putem menŃiona în acest moment este că în anumite cazuri o BDD poate fi mai „compactă” decât o tabelă de adevăr pentru o aceeaşi funcŃie (din cauza anumitor redundanŃe care pot fi exploatate)

Page 114: slide-uri logica

(O)BDD - 2

• Defini Ńie (diagram ă de decizie binar ă). Se numeşte diagramă de decizie binară (BDD pe scurt) peste X = {x1, x2, … , xn} un graf orientat, aciclic, etichetat (pe noduri şi pe arce) în care:-există o unică rădăcină (nod în care nu intră nici un arc)-frunzele (nodurile din care nu iese nici un arc) sunt etichetate cu 0 sau 1, iar celelalte noduri (inclusiv rădăcina) sunt etichetate cu elemente din X (se permit etichetări multiple, adică noduri diferite pot avea aceeaşi etichetă)-fiecare nod care nu este frunză are exact doi succesori imediaŃi, arcele care îi leagă fiind etichetate cu 0 respectiv 1 O subBDD (într-o BDD dată) este un subgraf generat de un nod fixat împreună cu toŃi succesorii săi

Page 115: slide-uri logica

(O)BDD - 3

• De obicei, într-un desen care reprezintă o BDD, frunzele pot fi identificate (şi) prin pătrate (nu cercuri, ca restul nodurilor), orientarea arcelor este implicită („de sus în jos”), arcele etichetate 0 sunt linii punctate(„stânga”), iar cele etichetate 1 sunt linii continue („dreapta”)

• În exemplele care urmează grafurile suntchiar arbori

Page 116: slide-uri logica

(O)BDD - 4

• (I) D0, D1 (peste ∅), Dx (peste X = {x}):

• (II) O BDD peste X = {x, y}

Page 117: slide-uri logica

(O)BDD - 5

• Observa Ńie. Orice BDD peste X = {x1,x2,… ,xn} defineşte/reprezintă/calculează o unică funcŃie booleană f ∈ FB(n). Astfel, pentru α1,α2,…,αn∈B (considerate ca fiind valori asignate corespunzător „variabilelor” din X) se „porneşte” cu rădăcina (unică) şi se „parcurge” un drum (unic) în graf „până” la o frunză (să spunem, etichetată cu β ∈ B)

• La fiecare pas, plecând din nodul curent, se alege acel arc (prin urmare şi noul nod curent) căruia i se ataşează valoarea 0 sau 1 conform valorii α deja atribuite nodului curent x (în asignarea aleasă). Valoarea asignată lui βeste chiar f(<α1, α2, … , αn>)

Page 118: slide-uri logica

(O)BDD - 6

• În acest mod, BDD-ul din exemplul anterior reprezintă funcŃiaf(x, y) = x(bară) • y(bară)

• Este clar că putem proceda şi invers, adică pornind cu orice funcŃie f ∈ FB(n) dată printr-un tabel de adevăr, construim (măcar) un arbore (BDD) binar, complet şi având n nivele, notate 0 - rădăcina, 1, … , n-1 – frunzele(alternativ, având adâncimea n) care „calculează” f, în modul următor:

Page 119: slide-uri logica

(O)BDD - 7• se ordonează mulŃimea de variabile cu ajutorul căreia

este exprimată funcŃia, să zicem X = {x1, x2, … , xn}, sub forma <xk,1, xk,2, … , xk,n>, <k,1; k,2; … ; k,n> fiind o permutare pentru <1, 2, … , n>

• nodurile interioare (care nu sunt frunze) situate pe nivelul i -1 sunt etichetate (toate ) cu xk,i (i ∈ [n]); rădăcina este etichetată cu xk,1 fiind (singurul nod de) pe nivelul 0

• cele două arce care ies din fiecare nod sunt etichetate cu 0 şi respectiv 1

• frunzele sunt etichetate cu 0 sau 1 conform tabelei de adevăr pentru f (drumul de la rădăcină la frunza corespunzătoare furnizează exact linia care trebuie aleasă din tabelă: eticheta fiecărui arc de pe drum reprezintă valoarea atribuită variabilei care este eticheta nodului din care iese arcul)

Page 120: slide-uri logica

(O)BDD - 8

• Exemplu. Fie f ∈ FB(3) dată prin f(a, b, c) = (a ∨ b) ∧ (a ∨ b ∨ c), deci exprimată cu ajutorul lui X = {a, b, c}, <a, b, c> fiind şi ordinea impusă asupra variabilelor. Tabela sa de adevăr este (de făcut voi…)

• BDD-ul care calculează f după algoritmul sugerat anterior este (de verificat):

Page 121: slide-uri logica

(O)BDD - 9

Page 122: slide-uri logica

(O)BDD - 10• După cum se observă imediat, construirea unui BDD care

calculează o funcŃie dată nu este un proces cu rezultat unic, fiind suficient să schimbăm ordinea

• Impunerea unei ordini asupra etichetelor nodurilor este însă şi un prim pas spre găsirea unor forme normale pentru BDD-uri

• Un alt aspect care trebuie avut în vedere pentru atingerea acestui scop este acela că reprezentarea ca arbore a unei BDD nu este deloc mai eficientă/compactă decât o tabelă de adevăr (nici decât, de exemplu, o FNC(P)): dacă f ∈ FB(n), atunci tabela sa de adevăr va avea 2n linii iar în reprezentarea BDD sugerată de noi (ca arbore, în care fiecare nivel este „destinat” unei variabile şi pe fiecare drum de la rădăcină la o frunză apar toate variabilele exact o dată) vor fi exact 2n+1 – 1 noduri

• Putem compacta o BDD dacă îi aplicăm următoarele procedee de reducere/optimizare (în cele de mai jos, când ne referim la nodul n, m, etc. nu ne referim la eticheta din X):

Page 123: slide-uri logica

(O)BDD - 11C1 (înlăturarea frunzelor duplicat) . Dacă o BDD conŃine mai mult de o frunză

etichetată cu 0, atunci:-păstrăm una dintre ele-ştergem celelalte frunze etichetate cu 0, împreună cu arcele aferente, care de fapt se “redirecŃionează” spre singura 0-frunză rămasă (fiecare păstrându-şi nodul sursă)-se procedează în mod similar cu 1-frunzele. Admitem şi înlăturarea unei frunze dacă, în final, ea nu are nici un arc incident cu ea

C2 (eliminarea „testelor” redundante) . Dacă în BDD există un nod (interior) n pentru care atât 0-arcul cât şi 1-arcul au ca destinaŃie acelaşi nod m (lucru care se poate întâmpla doar dacă s-a efectuat măcar un pas de tip C1), atunci nodul n se elimină (împreună cu arcele sale care punctează spre m), iar arcele care înainte punctau spre n sunt “redirecŃionate” spre m

C3 (eliminarea nodurilor duplicat care nu sunt frun ze). Dacă în BDD există două noduri interioare distincte, să zicem n şi m, care sunt rădăcinile a două subBDD -uri identice (fiind identice, n şi m sunt şi pe acelaşi nivel), atunci se elimină unul dintre ele, să zicem m (împreună cu arcele care-l au ca sursă), iar arcele care punctau spre m se “redirecŃionează” spre n

Page 124: slide-uri logica

(O)BDD - 12

• Exemplu. Plecând de la BDD-ul din ultimul exemplu obŃinem succesiv (mai întâi sunt transformări de tip C1, apoi de tip C3 şi, în sfârşit, de tip C2)

Page 125: slide-uri logica

(O)BDD - 13

Page 126: slide-uri logica

(O)BDD - 14

Page 127: slide-uri logica

(O)BDD - 15

Page 128: slide-uri logica

(O)BDD - 16

• Ultima BDD este maximal redusă• Desigur că ordinea în care se efectuează

eliminările de tipul C1-C3 poate influenŃa aspectul structural al unei BDD şi pot exista mai multe transformări distincte care să fie simultan admise pentru o aceeaşi structuri

• În schimb, nici o transformare nu modifică funcŃia booleană calculată

Page 129: slide-uri logica

(O)BDD – 16 bis

• Concluzionând, BDD-urile pot fi uneori „convenabil de compacte”. Mai mult, putem reformula anumite definiŃii ale funcŃiilor booleene pentru noua reprezentare, căpătând, de exemplu, idei noi pentru rezolvarea problemei SAT

Page 130: slide-uri logica

CURS 8

• O nouă logică: LP1 – Sintaxa

Page 131: slide-uri logica

LP1 – Sintaxa 1• Pentru a construi mulŃimea de formule a

logicii cu predicate de ordinul I, LP1, vom porni cu următoarele mulŃimi de simboluri:-X = {x1, x2, …}: o mulŃime cel mult numărabilă de variabile func Ńionale sau, pe scurt, variabile-PPPP = {P0, P1, …}: o mulŃime cel mult numărabilă de simboluri predicative (sau predicate , sau rela Ńii ), cu arităŃi. La rândul său, fiecare Pi este o mulŃime cel mult numărabilă de predicate de aritate i (i ∈ N). Elementele lui P0 se mai numesc şi variabile predicative

Page 132: slide-uri logica

LP1 – Sintaxa 2

-FFFF = {F0, F1, ...}: o mulŃime cel mult numărabilă de simboluri func Ńionale (sau func Ńii ) cu arităŃi, fiecare Fi fiind o mulŃime cel mult numărabilă de func Ńii de aritatei (i ∈ N). Elementele lui F0 se numesc şi constante (func Ńionale)-C1C1C1C1 = {, ∨, ∧}: o mulŃime de conectori logici (conective logice) , la care se pot adăuga, opŃional, şi alte simboluri cum ar fi →, ↔ etc.-C2C2C2C2 = {(∀x) | x ∈ X} U {(∃ x) | x ∈ X}: o mulŃime de cuantificatori (cuantori) , universali , respectiv existen Ńiali ((∀x) se citeşte “pentru fiecare x”, sau “pentru oricare (orice) x”, iar (∃ x) – “există x”, “există măcar un x” etc.)

Page 133: slide-uri logica

LP1 – Sintaxa 3• Ca şi în cazul LP, vom porni cu alfabetul

total, adică reuniunea mulŃimilor precedente, împreună cu parantezele rotunde şi virgula (pe scurt, P):Alf = X U (Pi ) U (Fi ) U C1C1C1C1 U C2C2C2C2 U P

• MulŃimile U Pi şi U Fi vor fi notate tot cu P ,

respectiv F, atunci când nu există confuzii

Page 134: slide-uri logica

LP1 – Sintaxa 4• Defini Ńie (sintaxa LP1) . Fie Alf alfabetul fixat anterior.

Atunci mulŃimea formulelor calculului cu predicate de ordinul I , LP1Alf , este dată constructiv prin:-Baza. Se defineşte mulŃimea formulelor atomice , notată cu At , prin:(i) Po ⊆ At (variabilele predicative sunt formule atomice)(ii) Pentru fiecare n ∈ N*, pentru fiecare P ∈ Pn, pentru fiecare t1, t2, …, tn ∈ T, avem P(t1, t2, ……, tn) ∈ At(iii) Nimic altceva nu mai este formulă atomică

-În cele de mai sus, T denotă mulŃimea termilor(func Ńionali) , care este la rândul ei definită constructiv astfel:

Page 135: slide-uri logica

LP1 – Sintaxa 5-Baza. X ⊆ T şi F0 ⊆ T (variabilele şi constantele

sunt termi; se mai numesc şi elementari)-Pas constructiv . Pentru fiecare n ∈ N*, pentru

fiecare f ∈ Fn, pentru fiecare t1, t2, … , t n ∈ T, avem f(t1, t2, ……, tn) ∈ T

• Concluzionăm această etapă a definiŃiei prin: At ⊆ LP1(formulele atomice sunt formule)-Pas constructiv . Continuăm definirea lui LP1Alf cu partea “formule noi din formule vechi”:(i) Dacă F ∈ LP1 atunci ( F) ∈ LP1(ii) Dacă F1, F2 ∈ LP1 atunci ( F1 ∧ F2 ), ( F1 ∨ F2 ) ∈ LP1 (dacă dorim, putem introduce şi (F1 → F2), ( F1 ↔ F2 ) ∈LP1 etc.)(iii) Dacă F ∈ LP1 atunci (∀x)(F) ∈ LP1 (punem şi (∃ x)(F) ∈ LP1), pentru fiecare x ∈ X (iv) Dacă F ∈ LP1 atunci (F) ∈ LP1-Nimic altceva nu mai este formulă

Page 136: slide-uri logica

LP1 – Sintaxa 6• Similar cu cazul LP, se definesc constructiv subf(F),

mulŃimea subformulelor formulei F şi Arb(F), arborele ataşat lui F (cuantorii sunt operatori de aritate 1). Singura subformulă a unei formule atomice este ea însăşi şi Arb(F) va fi constituit în acest caz dintr-un simplu nod. Un term poate fi, la rândul său, privit ca un arbore (ca de altfel şi orice formulă atomică), astfel încât arborele unei formule poate fi „detaliat”, dacă înlocuim fiecare nod corespunzător unui termcu arborele ataşat acestuia (similar pentru o subformulă atomică)

• Din motive tehnice, toate simbolurile care apar suntconsiderate a fi diferite (nu admitem „overloading”)

Page 137: slide-uri logica

LP1 – Sintaxa 7• Defini Ńie (apari Ńii libere şi legate ale

variabilelor) . Fie F ∈ LP1 şi x ∈ X, astfel încât x apare în F, la o poziŃie oarecare j (în sens textual, stânga/ dreapta, ca literă într-un cuvânt, apariŃia menŃionată nefiind parte a numelui unui cuantificator (∀x) sau (∃x)). ApariŃia fixată a lui x se numeşte legat ă dacă este într-o parte (subformulă) G a unei (alte) subformule a lui F de forma G1 = (∀x)(G) (sau (∃x)(G)). În restul cazurilor, apariŃia considerată se numeşte liber ă

Page 138: slide-uri logica

LP1 – Sintaxa 8

• Orice apariŃie a unei variabile într-o formulă poate fi definită formal într-un mod simplu (structural). Vom nota, pentru fiecare F ∈ LP1, cu free(F) - mulŃimea variabilelor care au apariŃii libere în F, şi cu leg(F) - mulŃimea variabilelor care au apariŃii legate în F. Desigur că, pentru fiecare x ∈ X, este posibil ca x să nu apară în F, să aibă doar apariŃii libere, doar apariŃii legate sau şi apariŃii libere, şi apariŃii legate. Putem nota cu var(F) = free(F) U leg(F). O situaŃie nenaturală din punct de vedere semantic, dar posibilă sintactic, este aceea în care o variabilă x nu apare de loc în F (în sensul considerat), dar este prezent ca nume al unui cuantificator. Vom conveni să notăm mulŃimea acestor variabile cu restvar(F) şi să includem şi această mulŃime în var(F)

Page 139: slide-uri logica

LP1 – Sintaxa 9• Defini Ńie (închideri) . O formulă F ∈ LP1 se numeşte

închis ă dacă nu conŃine apariŃii libere de variabile (altfel spus, free(F) = Ø). Pentru formula F, se numeşte închiderea sa universal ă formula (∀x1)((∀x2)( …((∀xk)(F)) ... ) (notată, pentru simplitate şi cu (∀∗)(F) sau chiar (∀F)), unde {x1, x2, … , xk} = free(F). Analog (înlocuind ∀ cu ∃) se defineşte (notează) închiderea existen Ńială a lui F. Se va numi matricea lui F (notată F*) acea formulă obŃinută din F prin ştergerea (sintactică, textuală) a tuturor cuantificatorilor (∀x) şi (∃x). O formulă care nu este închisă se numeşte deschis ă (o formulă în care var(F) = Ø se consideră a fi închisă)

• Defini Ńie (substitu Ńii) . Prin substitu Ńie vom înŃelege o secvenŃă finită de elemente de tipul [x/t] (numite şi substitu Ńii elementare ), unde x ∈ X, t ∈ T

Page 140: slide-uri logica

LP1 – Sintaxa 10• O substituŃie va avea astfel forma

s = [x1/t1]•[x2/t2]• … •[xn/tn] fiind practic un cuvânt peste alfabetul S = {[x/t] | x ∈ X, t ∈ T}, adică un element al lui S* (monoidul liber generat de S). O substitu Ńie s (ca mai sus) se aplic ă unei formule F , rezultând o formulă G, notată (F)s, care se obŃine din F prin înlocuirea fiecărei apariŃii libere a variabilei x1 cu termul t1, apoi a fiecărei apariŃii libere a variabilei x2 cu t2 etc. De obicei, se utilizează doar substitu Ńii permise pentru o formulă F ∈ LP1 dată. SubstituŃia elementară [x/t] este permisă pentru F (sau, F accept ă [x/t]) dacă t nu conŃine variabile (libere) care au apariŃii legate în F (s de mai sus va fi permisă pentru F dacă va fi permisă pentru fiecare componentă a sa, [xi/ti], i ∈ [n])

Page 141: slide-uri logica

LP1 – Sintaxa 11

• Ordinea (fixată deja prin modul de scriere) aplicării substituŃiilor elementare dintr-o substituŃie s este esenŃială în majoritatea cazurilor. O substituŃie s este normalizat ă (pentru F) dacă ordinea de aplicare a substituŃiilor elementare componente nu contează. Mai precis, s este normalizată dacă avem (F)s = (F)s’, pentru fiecare s’ care este obŃinută din s printr-o permutare a componentelor acesteia. Substitu Ńia vid ă (ca element neutru al lui S*), notată [ ], nu face desigur nici o transformare în formula F căreia îi este aplicată, adică avem (F)[ ] = F

• Dacă atunci s şi s’ se mai numesc şi echivalente

Page 142: slide-uri logica

LP1 – Sintaxa 12• Păstrăm notaŃiile, convenŃiile, rezultatele,

conceptele din LP, dacă nu precizăm altfel(ex.: literal = o formulă atomică sau negaŃia acesteia, clauză, clauză Horn, formă normală)

• RenunŃare la paranteze, priorităŃi ale operatorilor(cea mai “mare”: cuantificatorii, restul se păstrează), domeniul sintactic al unui operator

• Defini Ńie. Un term care nu conŃine variabile se numeşte term de bază. Analog, vom avea formule de baz ă, substitu Ńii de baz ă, etc.

Page 143: slide-uri logica

LP1 – Semantica 1

• ÎnŃelesul (semantica) unei formule F ∈ LP1 va fi, la fel ca în logica propoziŃională, o valoare de adevăr 0, 1 ∈ B, valoare obŃinută într-un mod extensional. Elementul principal în definirea semanticii va rămâne noŃiunea de structură

Page 144: slide-uri logica

LP1 – Semantica 2

• Defini Ńie. Se numeşte structur ă un cuplu S = <UUUUS, IIIIS> în care UUUUS este o mulŃime nevid ă numită univers , iar IIIISeste o funcŃie (numită şi interpretare ) IIIIS : X U FFFF U PPPP →UUUUS U [UUUUS*→ B] U [UUUUS* → UUUUS], care satisface condiŃiile:-Dacă x ∈ X, atunci IIIIS(x) ∈ UUUUS

-Dacă P ∈ Pn, atunci IIIIS(P) : → B-Dacă F ∈ Fn, atunci IIIIS(F) : → UUUUS

• [C → D] desemnează mulŃimea tuturor funcŃiilor totale având domeniul C şi codomeniul D, iar [C* → D] denotă mulŃimea tuturor funcŃiilor de oricâte argumente (inclusiv 0) peste C, cu valori în D

UnS

UnS

Page 145: slide-uri logica

LP1 – Semantica 3

• Prin urmare, interpretarea (semantica) unei variabile în structura S este un element din univers, interpretarea unui simbol predicativ n-ar este o func Ńie de la la {0, 1} (sau, uneori, mul Ńimea elementelor din pentru care valoarea în cauz ă este 1 ), iar semantica unui simbol func Ńional de aritate n este o func Ńie de la la U S. Pentru simplificarea exprimării, vom renunŃa la indici dacă nu există confuzii şi vom nota pe IIIIS tot cu S . Similar cu cazul logicii propoziŃionale, orice structură va putea fi unic extinsă astfel încât să fie definită pentru toate elementele lui LP1

UnS

UnS

UnS

Page 146: slide-uri logica

LP1 – Semantica 4• Defini Ńie. Pentru fiecare structură S = <UUUUS, IIIIS>,

vom numi extensia sa imediat ă func Ńia S’ : X U FFFF U PPPP U T U LP1 → UUUUS U [UUUUS* → UUUUS] U

[UUUUS* → B] U B, dată constructiv în continuare. Pentru început, vom pune S’(a) = S(a) (= IIIIS(a)), pentru fiecare a ∈ X U FFFF U PPPP, ceea ce înseamnă că S’ s-a definit, în particular, şipentru fiecare term elementar. Fie acum orice t ∈ T, adică orice n ∈ N*, orice t1, t2, … , tn ∈ T şi orice f ∈ Fn, astfel încât t = f(t1, t2, …, tn). Atunci S’(t) = S(f)(S’(t1), S’(t2), ... , S’(tn)) (∈ UUUUS). Am încheiat astfel procesul de definire al lui S’ pe XU FFFF U PPPP U T şi rămâne să definim S’ pe LP1. Vom face acest lucru în mod constructiv:

Page 147: slide-uri logica

LP1 – Semantica 5-Baza. Fie F = A ∈ At . În această situaŃie avem fie A = P ∈ P0 fieA = P(t1, t2, …, tn), n ∈ N*, t1, t2 , ……, tn ∈ T. În primul caz S’ este deja definită (S’(P) = S(P) ∈ B), iar în al doilea caz punem desigurS’ (P) = S(P)(S’ (t1), S’ (t2), ... , S’ (tn)) ∈ B (paranteze <>…)-Pas constructiv . Vom avea de considerat cazurile: (i) F = ( F1 ). Atunci S’(F) = (ii) F = (F1 ∧ F2). Atunci S’(F) = S’(F1) • S’(F2)(iii) F = (F1 ∨ F2). Atunci S’ (F) = S’(F1) + S’(F2)(iv) F = (∀x)(G). Atunci S’(F) = 1 dacă şi numai dacă pentru fiecare u ∈ UUUUS avem S’[x/u](G) = 1 unde S’[x/u] este o interpretare care coincide în totalitate cu S’ exceptând faptul că S’(x) = u (v) F = (∃x)(G). Atunci S’(F) = 1 dacă şi numai dacă există (măcar) un element u ∈ UUUUS astfel încât S’[x/u](G) = 1

• Alte notaŃii, observaŃii (F “la” S; LP1 “cu” egal, etc.; LP2;LP ⊆ LP1)

S'(F)

Page 148: slide-uri logica

LP1 – Semantica 6• Defini Ńie (universuri şi structuri Herbrand) .

Fie F ∈ LP1. Se numeşte univers Herbrand(ataşat lui F), mulŃimea D(F) definită prin:-Baza. În D(F) se pun toate elementele din F0care apar în F. Dacă F nu conŃine nici o constantă, atunci se pune for Ńat în D(F) un element oarecare din F0 (numele rezervat standard, de obicei, este a)-Pas constructiv . Fie orice n ∈ N*, orice f ∈ Fncare apare în F şi termii oarecare t1, t2, ... , tn ∈ D(F). Atunci f(t1, t2, ... , tn) ∈ D(F)-Nimic altceva nu mai este în D(F)

Page 149: slide-uri logica

LP1 – Semantica 7

• O structur ă Herbrand (pentru F) este o structură (corectă pentru F), H = <UUUUH, IIIIH>, în care UUUUH = D(F), iar IIIIH satisface condiŃia că “interpretează fiecare term prin el însuşi”. Mai exact, H(f(t1, t2, ... , tn)) = fH(<t1H, t2H, ... , tnH >) == f(t1H, t2H, ... , tnH), pentru fiecare n ∈ N şi fiecare t = f(t1, t2, ... , tn) ∈ T

Page 150: slide-uri logica

LP1 – Semantica 8• Se poate spune că D(F) este mulŃimea termilor de bază

construiŃi cu simboluri din F. Într-o structură Herbrand, dacă f ∈ F0 atunci H(f) = f şi în consecinŃă dacă t este un term de bază avem şi tH = t. Interpretarea unei variabile este cea uzuală (xH ∈ D(F) pentru fiecare x ∈ X), la fel ca şi interpretarea simbolurilor predicative (ele vor fi funcŃii oarecare peste D(F) cu valori în B). A nu se confunda f H(<t1

H, t2H, ... , tn

H >), care denot ă aplicarea efectiv ă a func Ńiei f H : D(F)n →→→→ D(F) n-uplului<t1

H, t2H, ... , tn

H>, cu f(t 1H, t2

H, ... , tnH) (valoarea

aplic ării anterioare), care este un term fără variabile apar Ńinând lui D( F), adic ă, în ultim ă instan Ńă, un şir de caractere . Dacă există o structură Herbrand care este model pentru o formulă F, atunci spunem şi că Fadmite model Herbrand

Page 151: slide-uri logica

LP1 – Semantica 9• Teorem ă (de extensie) . Pentru fiecare structură

S = <UUUUS, IIIIS>, extensia sa imediată S’ este funcŃie şi este unica funcŃie având domeniul X U P U T U F U LP1 şi codomeniul UUUUS U [UUUUS* → UUUUS] U [UUUUS* → B] U B unde S’ extinde S şi satisface condiŃiile: (i) S’(( F)) = S’(F) (bara…), pentru fiecare F ∈ LP1(ii) S’((F1 ∧ F2)) = S’(F1) • S’(F2), pentru fiecare

F1, F2 ∈ LP1(iii) S’((F1∨ F2)) = S’(F1) + S’(F2), pentru fiecare

F1, F2 ∈ LP1(iv) S’((∀x)(G)) = 1 dacă şi numai dacă pentru fiecare u ∈ UUUUS avem S’ [x/u](G) = 1 unde S’ [x/u] este o interpretare care coincide cu S’ exceptând faptul că S’(x) = u (pentru fiecare x ∈ X şi fiecare G ∈ LP1)

Page 152: slide-uri logica

LP1 – Semantica 10

• Mai sus putem adăuga (conform presupunerilor de până acum) şi (v) S’((∃x)(G)) = 1 dacă şi numai dacă există (măcar) un element u ∈ UUUUS astfel încât S’[x/u](G) = 1 (pentru fiecare x ∈ X şi fiecare G ∈ LP1)

• RelaŃia S’((F)) = S’(F) o putem considera ca fiind adevărată chiar prin convenŃie(demonstraŃie similară cu LP)

Page 153: slide-uri logica

CURS 9

• Forme normale

Page 154: slide-uri logica

LP1 – Forme normale 1• Teorem ă (de substitu Ńie). Fie H ∈ LP1, oarecare. Fie

orice F, G ∈ LP1 astfel încât F este o subformulă a lui H şi G este tare echivalentă cu F. Fie H’ formula obŃinută din H prin înlocuirea (unei apariŃii fixate a) lui F cu G. atunci H ≡ H’(demonstraŃie)

• EchivalenŃele deja cunoscute din LP pot fi completate cu altele, care se referă la cuantori:Teorem ă. Pentru fiecare F, G ∈ LP1 şi fiecare x, y ∈ X, sunt adevărate următoarele echivalenŃe:1. (∀x)F ≡ (∃x)( F)

(∃x)F ≡ (∀x)( F)

Page 155: slide-uri logica

LP1 – Forme normale 22. Dacă x nu apare liber în G, atunci:

(∀x)(F ∧ G) ≡ (∀x)(F) ∧ G(∀x)(F ∨ G) ≡ (∀x)(F) ∨ G(∃x)(F ∧ G) ≡ (∃x)(F) ∧ G(∃x)(F ∨ G) ≡ (∃x)(F) ∨ G

3. (∀x)(F) ∧ (∀x)(G) ≡ (∀x)(F ∧ G)(∃x)(F) ∨ (∃x)(G) ≡ (∃x)(F ∨ G)

4. (∀x)(∀y)F ≡ (∀y)(∀x)F(∃x)(∃y)F ≡ (∃y)(∃x)F

5. Dacă x nu apare liber în F, atunci:(∀x)F ≡ F(∃x)F ≡ F

(demonstraŃie)

Page 156: slide-uri logica

LP1 – Forme normale 3• Ca o consecinŃă a teoremei anterioare rezultă că sunt

adevărate şi echivalenŃele (∀x)(∀x)F ≡ (∀x)F şi (∃x)(∃x)F ≡ (∃x)F (chiar şi variantele (∃x)(∀x)F ≡ (∀x)F, respectiv (∀x)(∃x)F ≡ (∃x)F), care se pot generaliza pentru oricâte apariŃii ale cuantorilor (F ar putea conŃine la rândul ei cuantificatori). Se poate arăta însă că nu sunt adev ărate echivalenŃele (mai exact, există x ∈ X, există F, G ∈ LP1 astfel încât, mai jos, formulele din membrul stâng nu sunt echivalente cu cele corespunzătoare din membrul drept):(∀x)F ∨ (∀x)G ≡ (∀x)(F ∨ G) (∃x)F ∧ (∃x)G ≡ (∃x)(F ∧ G)

• Nici echivalenŃa (∀x)(∃y)F ≡ (∃y)(∀x)F nu este adevărată pentru fiecare formulă F

Page 157: slide-uri logica

LP1 – Forme normale 4• Teorem ă (lema de transla Ńie). Fie F ∈ LP1,

x ∈ X , t ∈ T un term de bază şi S orice structură corectă pentru formulele care apar. Atunci:

S((F)[x/t]) = S[x/S(t)] (F) (demonstraŃie)

• Teorem ă (lema de redenumire a variabilelor legate) . Fie F = (○x)G , ○ ∈ {∀, ∃}, o formulă oarecare din LP1. Fie y o variabilă nouă (în sensul că ea nu apare în G). Atunci :

F ≡ (○y)(G[x/y])(demonstraŃie)

Page 158: slide-uri logica

LP1 – Forme normale 5• Defini Ńie (forma normal ă rectificat ă). O

formulă F ∈ LP1 se numeşte rectificată (sau se află în formă normală rectificată, pe scurt FNR)dacă nu conŃine variabile care apar atât libere, cât şi legate şi nu are cuantificatori care să lege aceeaşi variabilă, dar pe poziŃii diferite în formulă (indiferent dacă este vorba de cuantificatori existenŃiali sau universali)

• Teorem ă. Pentru orice formulă din F ∈ LP1, există o formulă rectificată F’ ∈ LP1, astfel încât F’≡ F(demonstraŃie)

Page 159: slide-uri logica

LP1 – Forme normale 6

• Defini Ńie (forma normal ă prenex) . O formulă F ∈ LP1 este în formă normală prenex (FNP, pe scurt) dacă F = (○1y1) …(○nyn)G, unde n ∈ N, ○i ∈ {∃, ∀} (i ∈[n]), iar y1, … , yn sunt toate variabilele distincte care apar (liber) în G. În plus, G nu mai conŃine cuantificatori

• În cele de mai sus, cazul n = 0 se referă la absenŃa cuantificatorilor ([0] = Ø)

• Teorem ă. Pentru fiecare formulă F ∈ LP1, există o formulă F’ ∈ LP1, care este în FNP şi este tare echivalentă cu F (demonstraŃie)

Page 160: slide-uri logica

LP1 – Forme normale 7• Am arătat că pentru fiecare formulă din LP1, există o altă

formulă din LP1, care este tare echivalentă cu ea şi care este în FNP rectificată (pe scurt, FNPR). Putem presupune şi că nu există în această formulă cuantificatori care să lege variabile care nu apar în ea şi nici cuantificatori (relativ la o aceeaşi variabilă) cu apariŃii multiple. Cu alte cuvinte, din punctul de vedere al satisfiabilităŃii, ne putem limita la studiul formulelor din LP1 de forma F = (○1y1) … (○kyk)F’, unde free(F’) = {y1, y2, … , yk}, iar F’ este chiar matricea lui F, nemaiconŃinând alŃi cuantori (○1, ○2, …, ○k ∈ {∀, ∃}). Prin urmare (o formulă este satisfiabilă dacă şi numai dacă închiderea sa existenŃială este satisfiabilă), pentru testarea satisfiabilităŃii unei formule din LP1 putem să ne limităm la clasa de formule având aspectul sintactic F = (○1y1)(○2y2) … (○kyk)F*, unde F* este matricea lui F iar leg(F) = var(F) = free(F*) = {y1, y2, … yk}. Această formulă este şi închisă, neconŃinând apariŃii libere de variabile

Page 161: slide-uri logica

LP1 – Forme normale 8• Defini Ńie (forma normal ă Skolem) . O formulă F ∈ LP1

este în formă normală Skolem (FNS, pe scurt), dacă are aspectul F = (∀x1) … (∀xk)G unde G nu mai conŃine cuantificatori (este chiar matricea lui F), iar x1, x2, … , xksunt variabile distincte şi reprezintă exact variabilele care apar în G (free(G) = {x1, x2, … , xk}). F este în form ă normal ă Skolem clauzal ă (FNSC, pe scurt), dacă este în FNS şi matricea sa este în FNC (forma normală conjuctivă) într-un sens similar cu LP (literalii reprezentând acum formule atomice din LP1 sau negaŃii ale lor)

• Teorem ă. Pentru fiecare formulă F din LP1, există o altă formulă F’∈ LP1, care este în FNSC şi care este slab echivalentă cu eaDemonstra Ńie. Vom prezenta un algoritm prin care formula F’ va fi construită efectiv din formula F

Page 162: slide-uri logica

CURS 10

• Continuare forme normale• Decidabilitate şi rezoluŃie de bază în LP1

(LP1=)

Page 163: slide-uri logica

LP1 – Forme normale 9Algoritm Skolem

• Intrare : F ∈ LP1. Fără a restrânge generalitatea, putem presupune că F este în FNPR, închisă

• Ieşire : F’ ∈ LP1, aflată în FNS (şi închisă), slab echivalentă cu F

• Metod ă:• Pasul 1 . F’ : = F• Pasul 2 . Cât_timp (există cuantificatori existenŃiali în F’)

execut ă2.1. Alege un asemenea

cuantificator şi elimină-l2.2. Transformă formula F’

Sf_Cât_timp

Page 164: slide-uri logica

LP1 – Forme normale 10• Comentarii legate de demonstra Ńie. Orice formulă

intermediară prelucrată de algoritm are forma F’ = (∀y1) … (∀yn)(∃z)G, unde G poate să conŃină şi alŃi cuantificatori (am pus în evidenŃă primul cuantificator existenŃial, alegerea fiind acum deterministă dacă ne gândim că parcurgem formula simbol cu simbol, de la stânga la dreapta). Atunci, în urma Paşilor 2.1 şi 2.2, F’ va căpăta formaF’ = (∀y1) …(∀yn)((G)[z/f(y1, … , yn)]) unde f este un simbol funcŃional nou (în sensul că el nu mai apare în formulele considerate – atenŃie la cardinalităŃi), f ∈ Fn. Să notăm cuH ≜ (∀y1) … (∀yk)(∃z)G, formula de tip F’ existentă înainte de execuŃia unui pas al algoritmului precedent şi cuH’ ≜ (∀y1) … (∀yk)(G)[z/f (y1, y2, … yk)] formula rezultată după execuŃie

• Este suficient să arătăm că H este slab echivalentă cu H’

Page 165: slide-uri logica

LP1 – Forme normale 11

• Putem sintetiza rezultatele obŃinute până în prezent în:Teorem ă. Pentru fiecare formulă F ∈ LP1, există o formulă F’ ∈ LP1 astfel încât F’ ≡s F, F’ fiind în FNSC închisă (F’ = (∀y1) … (∀yn)F*, {y1, … , yn} = free(F*), F*este matricea lui F şi este în formă normală conjunctivă)

• Exemple, exerciŃii

Page 166: slide-uri logica

Decidabilitate şi rezolu Ńie de bază în LP1 (LP1 =) 1

• Teorem ă. Fie F o formulă din calculul cu predicate de ordinul I fără egalitate, închisă şi aflată în FNS. Atunci F este satisfiabilă dacă şi numai dacă F admite un model Herbrand(demonstraŃie)

Page 167: slide-uri logica

Decidabilitate şi rezoluŃie de bazăîn LP1 (LP1=) 2

• Teorem ă (Löwenheim – Skolem) . Fiecare formulă satisfiabilă din LP1 admite model cel mult numărabil (demonstraŃie)

• Defini Ńie (extensia Herbrand) . Pentru fiecare formulă F închisă, aflată în FNS, F = (∀y1) … (∀yn)F*, {y1, … , yn} = free(F*), F* fiind matricea lui F, extensia sa Herbrand este mulŃimeaE(F) = {(F*)[y1/t1]•[y2/t2]• … •[yn/tn] |

t1, t2, …, tn ∈ D(F)}

Page 168: slide-uri logica

Decidabilitate şi rezoluŃie de bazăîn LP1 (LP1=) 3

• Dacă F este în FNSC (F are forma de mai sus, în plus F* fiind în FNC, F* = C1 ∧ C2 ∧ …… ∧ Ck, C1, C2, ... , Ck reprezentând clauze, adică literali din LP1), mulŃimea se numeşte extensia Herbrand generalizată (notată E’(F))

• Extensia Herbrand generalizată a unei formule este obŃinută practic prin considerarea tuturor instanŃelor clauzelor care compun matricea sa (formula fiind deja în FNSC şi considerată în reprezentarea cu mulŃimi), instanŃe obŃinute prin aplicarea tuturor substituŃiilor posibile cu termi de bază din D(F)

Page 169: slide-uri logica

CURS 11

• RezoluŃie de bază

Page 170: slide-uri logica

Decidabilitate şi rezoluŃie de bazăîn LP1 (LP1=) 4

• Teorem ă (Church) . Problema validităŃii pentru logica cu predicate de ordinul I (fără egalitate) este nedecidabilă, dar semidecidabilă(demonstraŃie)

• Teorem ă (Gödel-Herbrand-Skolem) . O formulă F ∈ LP1 este satisfiabilă dacă şi numai dacă E(F) este satisfiabilă(demonstraŃie)

• Teorem ă (teorema lui Herbrand; teorema de compactitate pentru LP1) . O formulă F ∈ LP1 este nesatisfiabilă dacă şi numai dacă există o submulŃime finită a lui E’(F) care să fie nesatisfiabilă(demonstraŃie)

Page 171: slide-uri logica

Decidabilitate şi rezoluŃie de bazăîn LP1 (LP1=) 5

• În acest moment putem spune că procedura următoare (intitulată şi Procedura lui Gilmore ) poate fi folosită pentru testarea nesatisfiabilităŃii oricărei formule din LP1. Pasul 1 este un algoritm în sine, formula găsită la sfârşitul execuŃiei sale fiind slab echivalentă cu formula iniŃială şi având aspectul F = (∀*)F*, unde F* = C1 ∧ C2 ∧ … ∧ Ck. Extensia Herbrand generalizată E’(F) “rezultată” în urma aplicării Pasului 2 trebuie interpretată ca fiind o listă de clauze din LP. Datorită faptului că E’(F) nu este recursivă ci doar recursiv enumerabilă, Pasul 2 reprezintă un semialgoritm. După cum se observă, nici n-ar fi nevoie de obŃinerea acestei liste dintr-o dată. Este nevoie doar de a putea selecta câte un nou element din ea „atunci când este necesar”, conform Pasului 3.3.2 , care ar putea fi reformulat prin ObŃine un nou element din E’(F)

Page 172: slide-uri logica

Decidabilitate şi rezoluŃie de bazăîn LP1 (LP1=) 6

• Practic, pornind de la ordinea pe D(F) deja sugerată (bazată pe lungimea termilor), se poate defini o ordine totală şi pe E’(F) (acest lucru nu ar implica decât o simplă extensie a unei relaŃii de ordine definită pe o mulŃime „suport” la un produs cartezian al acelei mulŃimi cu ea însăşi, de oricâte ori). De fapt, doar Pasul 3 , şi numai el, este semialgoritmulcunoscut în literatura de specialitate ca Procedura lui Gilmore (sau Procedura rezolu Ńiei de baz ă). Aceasta nu se termină în cazul în care F este satisfiabilă şi conŃine măcar un simbol funcŃional de aritate cel puŃin 1

Page 173: slide-uri logica

Decidabilitate şi rezoluŃie de bazăîn LP1 (LP1=) 7

Semialgoritmul lui Gilmore(Procedura rezolu Ńiei de baz ă)

• Intrare : Orice formulă F ∈ LP1• Ieşire : „DA”, doar dacă F este nesatisfiabilă• Metod ă:

Pasul 1 . Se transformă F într-o formulă aflată în FNSC (închisă), succesiv, prin rectificare (redenumire), găsirea FNP (FNPR), obŃinerea închiderii existenŃiale, obŃinerea FNS şi apoi FNSC, formula rezultat notându-se, pentru simplitate, tot cu F

Pasul 2 . Se „obŃine” E’(F) = {G1, G2, ... , Gn, ... }

Page 174: slide-uri logica

Decidabilitate şi rezoluŃie de bazăîn LP1 (LP1=) 8

Pasul 3.3.1. M := Ø3.2. i := 03.3. Repetă

3.3.1. i := i + 13.3.2. Alege Gi ∈ E’(F)3.3.3. M := M U {Gi}3.3.4. M’ := Res*(M)

Până_când (� ∈ M’)Pasul 4 . Tipăreşte „DA”

Page 175: slide-uri logica

Decidabilitate şi rezoluŃie de bazăîn LP1 (LP1=) 9

• Trebuie însă să arătăm că (semi)algoritmul precedent „face ceea ce dorim”. Să precizăm de la bun început că vom lua în considerare doar formule F ∈ LP1 pentru care E’(F) este infinită. În caz contrar, rezultatele obŃinute până în prezent ne „spun” că F poate fi privită ca o formulă din LP, nemaifiind necesară o tratare a acesteia în noul context

• Teorem ă. Procedura rezoluŃiei de bază pentru LP1 este corectă(demonstraŃie)

Page 176: slide-uri logica

Decidabilitate şi rezoluŃie de bazăîn LP1 (LP1=) 10

• Teorem ă (a rezolu Ńiei de baz ă). Fie F ∈ LP1 şi E’(F’) extensia Herbrand generalizată a unei formule F’, slab echivalente cu F şi aflată în FNSC (închisă). Atunci F este nesatisfiabilă dacă şi numai dacă există o demonstraŃie prin rezoluŃie (în sensul logicii propoziŃionale) a lui �, pornind cu (o parte finită din) elementele lui E’(F’)(demonstraŃie)

• Exemple, exerciŃii, comentarii

Page 177: slide-uri logica

CURS 12

• RezoluŃie pură

Page 178: slide-uri logica

LP1 – RezoluŃie pură 1

• Rezolu Ńia specific ă (numită şi pur ă) pentru LP1, deşi diferită de rezoluŃia de bază, păstrează ideea principală a rezoluŃiei din LP şi anume că la fiecare pas de rezolu Ńie se aleg dou ă clauze şi se ob Ńine o alt ă clauz ă (rezolvent), eliminând anumi Ńi literali prin „reducere” cu nega Ńiile lor

• Eliminările devin mai complicate, iar „esenŃa” lor este (sub)procedura de unificare

Page 179: slide-uri logica

LP1 – RezoluŃie pură 2

• A unifica două sau mai multe formule atomice din LP1 înseamnă a găsi o substituŃie pentru variabilele care intervin în acele formule (substituŃia nefiind neapărat elementară sau de bază) astfel încât în urma aplicării substituŃiei formulele atomice respective să coincidă (textual, ca şiruri de caractere)

• ObŃinerea unui rezolvent nu va însemna numai o simplă reducere a unui literal cu complementarulsău, ci şi o „identificare” prealabilă a unor literali

Page 180: slide-uri logica

LP1 – RezoluŃie pură 3• Unificarea se „face” cu ajutorul Algoritmului lui

J. Robinson• Exemplu .Fie:F = (∀x)(∀y)((P(x) ∨ P(f(c)) ∨ Q(y)) ∧ P(y) ∧

(P(g(b, x)) ∨ Q(b))), unde- C1 = P(x) ∨ P(f(c)) ∨ Q(y)- C2 = P(y)- C3 = P(g(b, x)) ∨ Q(b)

F* = {C1, C2, C3} = {{ P(x), P(f(c)), Q(y)}, {P(y)}, { P(g(b, x)), Q(b)}}

Considerăm pe rând următoarele cupluri de clauze:

Page 181: slide-uri logica

LP1 – RezoluŃie pură 4-C1 şi C2. Din motive tehnice, nu trebuie să existe

variabile comune în clauzele considerate în momentul în care încercăm să aplicăm un pas al rezoluŃiei pure

Facem substituŃia de redenumire [y/z] în C2, găsind C’2 = {P(z)}

Prin [x/z], unificăm mulŃimea {P(x), P(z)} (acest din urmă literal fiind complementarul celui conŃinut de C’2), găsind Res(C1, C’2) = { P(f(c)), Q(y)} = C4

-C4 şi C2. Redenumim în C2 şi lucrăm tot cu C’2. Aplicând [z/f(c)], vom unifica mulŃimea { P(f(c)), P(z)}, găsind Res(C4, C’2) = = {Q(y)} = C5

Page 182: slide-uri logica

LP1 – RezoluŃie pură 5-C3 şi C2. Nu mai avem nevoie de redenumiri,

putând unifica { P(g(b, x)), P(y)}, prin substitutia s = [y/g(b, x)]. Găsim Res(C3,C2) = { Q(b))} = C6

-C5 şi C6. Nu avem nevoie de redenumiri si vomunifica { Q(y), Q(b)} prin s = [y/b] şi obŃinem în final � Res(C5, C6)

• Astfel, am găsit o respingere utilizând rezoluŃia pură, pornind cu clauzele lui F, adică demonstraŃia(DDDD) : C1, C2, C4, C5, C3, C6, �

Page 183: slide-uri logica

LP1 – RezoluŃie pură 6• Defini Ńie (unificare) . Fie LLLL = {L1, L2, ... , Lk} o

mulŃime finită, nevidă, de literali din LP1. Ea se numeşte unificabil ă dacă există o substituŃie s astfel încât card((LLLL)s) = 1. În acest caz, s se numeşte unificator pentru LLLL. O substituŃie s se numeşte cel mai general unificator (m.g.u. ) pentru o mulŃime unificabilă LLLL dacă orice alt unificator s’ se „obŃine” din s, adică pentru fiecare unificator s’ există o substituŃie sub astfel încât s’ = s • sub

• Să presupunem acum că avem două clauze distincte din LP1 (nu neapărat clauze Horn şi conŃinând eventual şi variabile). Ideea rezoluŃiei pure se bazează pe faptul că putem unifica „cât mai mulŃi” literali din cele două clauze şi apoi îi putem elimina, într-un mod similar cu rezoluŃia propoziŃională

Page 184: slide-uri logica

LP1 – RezoluŃie pură 7• Defini Ńie (rezolu Ńia pur ă într-un pas, în LP1) .

Fie C1, C2 şi R clauze în LP1, C1 ≠ C2. R se numeşte rezolvent (pur) pentru C1 şi C2, obŃinut într-un pas , dacă sunt îndeplinite condiŃiile:(i) Există substituŃiile de redenumire s1 şi s2astfel încât (C1)s1 şi (C2)s2 nu au variabile comune(ii) Există literalii L1, L2, ... , Lm ∈ (C1)s1şi L’1, L’2, ... , L’n ∈ (C2)s2 astfel încât mulŃimeaLLLL = {L1, L2, ... , Lm (barate), L’1, L’2, ... , L’n} este unificabilă. Fie sub un cel mai general unificator pentru LLLL(iii) R = (((C1)s1 \ {L1, L2, ... , Lm}) U ((C2)s2 \ {L’1, L’2, ... , L’n}))sub

1L

Page 185: slide-uri logica

LP1 – RezoluŃie pură 8• Deoarece nu există pericol de confuzii, vom folosi

aceleaşi notaŃii pentru rezoluŃia pură ca si cele adoptate pentru rezoluŃia propoziŃională (ceea ce se schimbă este practic doar definiŃia rezolvenŃilor obŃinuŃi într-un pas)

• Teorem ă (Julia Robinson) . Orice mulŃime LLLL, finită, nevidă, unificabilă, de literali din LP1, admite un cel mai general unificator. Problema testării faptului că o mulŃime de literali este unificabilă, precum şi găsirea unui cel mai general unificator, sunt decidabile (vezi algoritmul de mai jos)

• Există astfel o metodă relativ simplă pentru unificarea unei mulŃimi date de literali. Ideea este de a identifica porŃiuni de text, având un format special. Acest lucru nu se poate face decât prin intermediul variabilelor, folosind substituŃiile. În plus, „apelurile” recursive, de genul „x este înlocuit cu t, care conŃine x”, sunt interzise (altfel ar fi necesară o procedură de tip occurrence checking, care este ineficientă)

Page 186: slide-uri logica

LP1 – RezoluŃie pură 9 Algoritmul Juliei Robinson

Intrare . Orice mulŃime finită, nevidă de literali din LP1, LLLL = {L1,..., Ln}Ieşire .

-„DA” în caz că LLLL este unificabilă şi sub un m.g.u.(normalizat)

-„NU” în caz că LLLL nu este unificabilăMetod ă.Pas1. sub :=[ ] {sub va fi cel mai general unificator în caz de răspuns afirmativ, iar [ ] reprezintă substituŃia vidă}Pas2. j:=0 {j este o variabilă (flag) prin care se testează dacă mulŃimea respectivă este sau nuunificabilă}

Page 187: slide-uri logica

LP1 – RezoluŃie pură 10Pas 3. Cât timp (j = 0 şi card((LLLL)sub)>1) execut ă

{Există L1, L2 ∈ LLLL a.î. L1 ≠ L2 (textual). Fie i poziŃia simbolurilor diferite din L1, L2 (prima de la stânga la dreapta)}

Pas 3.1. Dacă (nici unul dintre cei doi simbolidiferiti de pe poziŃia i din cei doi literali nu este o variabilă)atunci j:=1

altfel {fie x simbolul care este o variabilă (să admitem că este din

L1) şi că în L2 pe poziŃia i corespunzătoare se găseşte (în mod neapărat) un simbol funcŃional de aritate 0 sau mai mare; aceasta înseamnă că la poziŃia i din L2 „începe” un term t}

Page 188: slide-uri logica

LP1 – RezoluŃie pură 11Dacă (x apare în t) atunci j:=1altfel

sub := sub • [x/t]sf

sfsf

Pas4. Dacă (j=1) atunci

„NU” {mulŃimea iniŃială nu este unificabilă}altfel

„DA” {mulŃimea iniŃială este unificabilă} şi subsf

Page 189: slide-uri logica

LP1 – RezoluŃie pură 12

• Comentarii asupra CORECTITUDINII algoritmului

• Teorem ă (a rezolu Ńiei pure pentru LP1) .

Fie F ∈ LP1 o formulă închisă, aflată în FNSC, F = (∀*)F*. Atunci F este nesatisfiabilă dacă şi numai dacă � ∈ Res*(F*), adică dacă şi numai dacă există o demonstraŃie prin rezoluŃie pură a clauzei vide (o respingere), pornind cu clauzele lui F

Page 190: slide-uri logica

LP1 – RezoluŃie pură 13

• DemonstraŃia se face prin intermediulteoremei rezoluŃiei de bază

• Indexul, exerciŃiile …

Page 191: slide-uri logica

Curs 13

• Tratare globală LP, LP1 (teorii logice şi sisteme deductive)

• Teoriile logice au fost introduse deja într-un curs anterior (exact sub forma de mai jos)

• Sistemele deductive au fost de asemenea introduse, dar parŃial; continuăm de unde am rămas (sau…completăm)

Page 192: slide-uri logica

Teorii logice 1 • Teorie logic ă - concept semantic pentru

definirea şi tratarea global ă a unei mul Ńimide „formule ”: TE

• O teorie logic ă este o (sub)clasă de formule închis ă la consecin Ńă semantic ă

• Cu alte cuvinte, o mulŃime TE de formule este teorie logică dacă pentru fiecare submulŃime S ⊆ TE şi fiecare (altă) formulă G care este consecinŃă semantică din S, avem şi G ∈ TE

Page 193: slide-uri logica

Teorii logice 2• Exemple imediate de teorii logice sunt clasele

formulelor valide (din LP, LP1, LP1= etc.); generalizări - FORM; concepte diferite desprenoŃiunea de adevăr; ValValValVal(FFFF) va nota clasaformulelor valide din FFFF ⊆ FORM

• NotaŃii pentru „consecin Ńă semantic ă”:IIII ╞ F; ╞ F

• Cs(FCs(FCs(FCs(F) ) ) ) ––––mulŃimea consecinŃelor semantice din

F F F F ⊆ FORM

• Tipuri de teorii: (ne)degenerate, (in)consistente, complete, recursive (recursiv enumerabile), etc.

Page 194: slide-uri logica

Sisteme deductive 1• Sistem deductiv (de deduc Ńie, de

demonstra Ńie, inferen Ńial ) - concept sintacticpentru definirea şi tratarea global ă a uneimul Ńimi de „formule ”: SD

• Se numeşte sistem deductiv în

FORM - mulŃimea (meta)formulelor - un cuplu SD = <AAAA, RRRR> unde- AAAA ⊆ FORM este o mulŃime de axiome iar

---- RRRR ⊆ FORM+ × CCCC o mulŃime de reguli de inferen Ńă (de deduc Ńie, de demonstra Ńie)

Page 195: slide-uri logica

Sisteme deductive 2• În cele de mai sus, FORM+ denotă mulŃimea

relaŃiilor de oricâte argumente (cel puŃin unul) peste FORM, iar CCCC reprezintă o mulŃime de condiŃii de aplicabilitate. Fiecare regulă de inferenŃă r ∈ RRRR , are astfel aspectulr = < < G1, G2, … , Gn, G>, c>, unde n ∈ N, iar G1, G2, … , Gn ∈ FORM; c ∈ CCCC

• G1, G2, … , Gn sunt ipotezele (premizele) regulii, G reprezintă concluzia (consecinŃa) iar c desemnează cazurile (modalităŃile) în care regula poate fi aplicată. Vom scrie chiar r = < < {G1, G2, … , Gn}, G>, c> deoarece ordinea ipotezelor nu este esenŃială

Page 196: slide-uri logica

Sisteme deductive 3

• MulŃimea CCCC nu a fost specificată formal; putem spune totuşi că elementele sale sunt (meta)predicate , din cauza generalităŃii ei

• Similar cu situaŃia rezoluŃiei, regulile vor fi folosite pentru a construi demonstraŃii în paşi succesivi, la un pas aplicându-se o regulă

Page 197: slide-uri logica

Sisteme deductive 4

• Există însă posibilitatea ca în afara restricŃiilor sintactice „locale”, date de forma formulelor implicate (ceea ce face ca regulile să fie, de fapt, scheme generale) să se interzică aplicarea regulii (schemei) pe considerente semantice „globale” (forma demonstraŃiei, apariŃia în demonstraŃie a unei formule nedorite la acel pas, păstrarea completitudinii unei teorii etc.)

• Dacă c este ataşată unei reguli r (c poate lipsi, mai exact ea poate fi „condiŃia permanent adevărată indiferent de context”), înseamnă că în oricedemonstraŃie, r va putea fi aplicată la un moment dat doar dac ă c este adevărată la momentul respectiv

Page 198: slide-uri logica

Sisteme deductive 5• O regulă r = < < {G1, G2, … , Gn}, G>, c> va fi

scrisă şi ca:

• În cazul în care n = 0 şi c lipseşte, r poate fi identificată ca fiind o axiomă, după cum rezultă din definiŃia care urmează. Câteodată, alături de c, sunt explicitate separat şi restricŃiile sintactice locale asupra (formei) (meta)formulelor

1 2 nG ,G ,....,G,c

G

Page 199: slide-uri logica

Sisteme deductive 6• Defini Ńie (demonstra Ńie, deduc Ńie sintactic ă,

raŃionament) . Fie un sistem deductiv SD = <AAAA, RRRR> în FORM. Se numeşte demonstraŃie (pentru F m, pornind cu AAAA) în SD o listă de metaformule (DDDD) :F1, F2, … , Fm astfel încât pentru fiecare i ∈ [m], fie Fi ∈ AAAA, fie Fi este obŃinut din Fj1, Fj2, … , Fjm folosind o regulă r = < < {Fj1, Fj2, … , Fjm}, Fi>, c> ∈ RRRR, unde j1, j2, ... , jm < i

• Prin urmare, fiecare element al listei (DDDD) este fie o axiomă, fie este concluzia unei reguli de inferenŃă ale cărei ipoteze sunt elemente anterioare din listă

Page 200: slide-uri logica

Sisteme deductive 7

• Reprezentarea ca arbore, exempleseminar

• SD’ = <AAAA’’’’, RRRR>, AAAA’’’’ = = = = AAAA UIIII, I I I I reprezentând„axiomele suplimentare”

• Notăm ThThThTh(SD) = {F ∈ FORM | există o demonstraŃie (DDDD) pentru F în SD} (există şio definiŃie constructivă)

Page 201: slide-uri logica

Sisteme deductive 8• Tipuri de sisteme deductive: complete, (finit)

axiomatizabile, etc.• Clasificarea sistemelor deductive

(exemplele – SD3, SD0, SD1, urmează)- De exemplu, ele se pot clasifica in funcŃie de

conectivele logice alese. Există sisteme boolean complete sau boolean incomplete

• Sistemul SD3 (Hilbert) este boolean complet, în timp ce un sistem care, de exemplu, foloseşte drept conector doar → (rezultând aşa-numitul calcul implicaŃional, SD1), va fi boolean incomplet

Page 202: slide-uri logica

Sisteme deductive 9- Sau, in funcŃie de rela Ńia avută cu o anumită

teorie logică. Sistemele pot fi corecte sau nu, complete sau nu pentru o teorie dată. Pentrutoate sistemele completitudinea este mai greu de atins (demonstrat) şi de aceea este de multe ori doar adoptată prin convenŃie. Corectitudinea este de obicei impusă, deşi poate avea şi ea nişte forme mai deosebite

- Sau, in funcŃie de importan Ńa asociatăaxiomelor sau regulilor de inferenŃă. Din acest punct de vedere, se poate acorda o atenŃie deosebită regulilor (adică modului de raŃionament, de obŃinere de cunoştinŃe noi) în daunaaxiomelor = cuno ştin Ńe primare (bază de

Page 203: slide-uri logica

Sisteme deductive 10

• Acest ultim tip de sisteme se numesc Gentzen-Jaskowski . Un asemenea sistem va fi SD0(deduc Ńia natural ă), care este echivalent cu SD3

• În cazul în care balanŃa este inversată (există „mult mai multe” axiome decât reguli de inferenŃă, ca în cazul SD3), sistemele sunt cunoscute sub numele de sisteme Hilbert

- Sau, după clasa FORM aleasă. De exemplu (pentru logica clasică), putem avea sisteme propozi Ńionale sau sisteme predicative

Page 204: slide-uri logica

Sisteme deductive 11• Reguli de inferen Ńă derivate. Considerând orice prefix

al oricărei demonstraŃii (privită textual) (DDDD) dintr-un sistem SD, acesta poate fi considerat ca o nouă regulă de inferenŃă („derivată” din cele iniŃiale): concluzia noii reguli este ultima formulă din demonstraŃia respectivă, iar ipotezele sunt reprezentate de restul formulelor care apar

• Eliminările de reguli derivate se “aprobă” doar dacă se menŃine echivalenŃa din sistemul iniŃial şi cel rezultat (după efectuarea eliminărilor)

• Defini Ńie. Două sisteme SD şi SD’ sunt echivalente dacă pentru fiecare mulŃime de (meta)formule IIII (poate fi chiarvidă) şi fiecare (meta)formulă F avem: IIII ├⊢SD F dacă şi numai dacă IIII ├⊢SD’ F

Page 205: slide-uri logica

SD3 1• Este un sistem deductiv standard, finit specificat, care

generează, după cum vom vedea din anumite teoremeulterioare, întreaga clasă (şi numai pe aceasta ) a formulelor valide din LP1 (sistemul a fost introdus pentru prima dată de către A. Church în 1954).

• Axiome (AAAASD3). CondiŃiile sintactice sunt: F, G, H ∈ LP1, x ∈ X, t ∈ T, oarecare. Suplimentar, în 4., x trebuie să nu apară liber în F iar în 5., substituŃia s = [x/t] trebuie să fie permisă pentru F (adică t nu conŃine nume de variabile care să apară legate în F):1. F → (G → F)2. (F → (G → H)) → ((F → G) → (F → H))3. ( F → G) → (( F → G) → F)4. (∀x)(F → G) → (F → (∀x)G) 5. (∀x)F → (F)[x/t]

Page 206: slide-uri logica

SD3 2• Să remarcăm faptul că LP1 trebuie considerată ca

fiind construită peste alfabetul care conŃine drept conectori doar pe şi →, iar unicul cuantificator acceptat sintactic este ∀. Dacă dorim să utilizăm şi ceilalŃi conectori (sau cuantori), putem face acest lucru doar utilizându-i ca notaŃii (de exemplu, A ∨ B va reprezenta A → B etc.)

• Reguli de inferen Ńă (RRRRSD3). Există doar restricŃii de natură sintactică (lipsind condiŃiile de aplicabilitate): F, G ∈ LP1, x ∈ X sunt oarecare, dar în 2., x trebuie să nu apară liber în F. Prima schemă de regulă este deja amintită, şi anume modus ponens (pe scurt, (MP)) iar a doua este aşa-numita regulă a generalizării (RG).

• 1I. 2I. .→F G,FG ∀

F( x)F

Page 207: slide-uri logica

SD3 3• Exemplu: să se arate că în SD3 se poate

“genera” teorema

T = (A → A) • Precizăm încă de pe acum că axiomele ar

trebui să fie formule valide (în sensulnoŃiunii de adevăr adoptate) iar regulile de inferenŃă – corecte. De asemenea, axiomele suplimentare (aici nu există) –(măcar) satisfiabile

Page 208: slide-uri logica

SD0 1• Clasa FORM este LP1. Alfabetul conŃine în acest caz

doar conectorii , ∧ şi cuantificatorul ∀. După cum am precizat, într-un asemenea sistem regulile de inferenŃă sunt “mai importante” decât axiomele, sistemul SD0 neavând nicio axiomă. Pentru a simplifica înŃelegerea, vom defini direct o demonstra Ńie în sensul deduc Ńiei naturale ca fiind un anumit arbore , fără a folosi definiŃia generală

• Un arbore de deduc Ńie natural ă are pe nivelul 0 (în frunze) formule oarecare (ipoteze ale unor reguli de inferenŃă din sistem, inclusiv elemente din eventuala mulŃime suplimentară IIII), iar nivelele următoare se obŃin constructiv, conform definiŃiei generale (rădăcina fiind „rezultatul final”).

Page 209: slide-uri logica

SD0 2

• Caracteristic acestui sistem este faptul c ă acele condi Ńii c de aplicabilitate ale regulilor, dacă exist ă, sunt de tipul „se anuleaz ă ipoteza F” (aici termenul ipotez ă nu se refer ă la ipotezele regulii respective, ci la toateformulele F prezente în frunzele arborelui curent) . Pentru ca anularea să nu fie efectivă (având drept consecinŃă ştergerea unui nod din graf, ceea ce conduce întotdeauna la anumite complicaŃii tehnice), vom adopta soluŃia de a marca ipotezele anulate (cu cifre, de exemplu)

Page 210: slide-uri logica

SD0 3

Page 211: slide-uri logica

SD0 4• Pentru a prezenta concret sistemul, rămâne să dăm

regulile de inferen Ńă din care este alc ătuit , care vor primi şi un nume în afara numărului de secvenŃă. Vom avea câte o (schemă de) regulă pentru fiecare A, B ∈LP1, fiecare x ∈ X şi fiecare t ∈ T. În 5., este necesar ca substituŃia [x/t] să fie permisă pentru A, iar în 6., ca x să nu apară liber în nici o ipoteză neanulată. Schemele 3. şi 4. au variante datorită necesităŃii de a se „prinde”comutativitatea conjuncŃiei la nivel sintactic (ne vom referi la ele ca 3’., respectiv 4’.). Deoarece substituŃia [x/x] este permisă pentru orice formulă, regula 5. are şi forma particulară <<{(∀x)A}, A>, true> (care va fi notată 5’.). Să remarcăm şi faptul că regula 6. nu are nevoie de nici o restricŃie sintactică în momentul în care se lucrează cu formule închise. Mnemonicele provin de la următoarele cuvinte: E – eliminare; I – introducere; N – negaŃie; C – conjuncŃie.

Page 212: slide-uri logica

SD0 5

• 1. (EN) , c: se anulează ipoteza A.

• 2. (IN) , c: se anulează ipoteza A.

• 3. (EC)

• 4. (IC)

• 5. (E∀∀∀∀) . •• 6. (I∀∀∀∀) .

¬B, BA¬

¬B, B

A

∧ ∧A B A Bsi

A B

∧ ∧A,B A,B

si A B B A

∀( x)AA[x / ]t

∀A

( x)A

Page 213: slide-uri logica

SD0 6

• Putem spune că SD0 este un sistem predicativ(de tip Gentzen, standard), finit specificat şi boolean complet. Dacă introducem ∨, →, ↔ şi ∃ în alfabetul de bază, putem folosi şi următoarele reguli derivate :

• 7. (ED) 8. (ID)

• 9. (EI)

• 10. (II) , c: se anulează ipoteza A

A B,¬A A B,¬Bsi

B A∨ ∨ A A

siA B B A∨ ∨

A,A BB→

BA B→

Page 214: slide-uri logica

SD0 7

• 11. (EE) 12. (IE)

• 13. (E∃∃∃∃) , c: se anulează ipoteza A din subarboreleavând rădăcina acest B

• 14. (I∃∃∃∃)

• 15. (DN)

A B A Bsi

A B B A⇔ ⇔→ →

A B,B AA B

→ →⇔

( x)A,BB

A[x/t]( x)A∃

A Asi

A A¬¬

¬¬

Page 215: slide-uri logica

SD0 8• Analog cu precizările deja făcute pentru regulile de bază, şi

schemele de mai sus sunt valabile pentru fiecare A, B ∈ LP1, fiecare x ∈ X şi fiecare t ∈ T. În 13., condiŃia sintactică este dată de faptul că x nu trebuie să aibă apariŃii libere în ipotezele neanulate, diferite de A şi prezente în subarborele având rădăcina exact acel B pentru care se aplică regula respectivă. De asemenea, în 14., condiŃia sintactică este ca substituŃia [x/t] să fie permisă pentru A. Mnemonicul E de pe a doua poziŃie (din 11. şi 12.) nu mai provine din cuvântul „eliminare”, ci de la echivalenŃă; mnemonicul I, de pe a doua poziŃie din 9., 10., provine de la implicaŃie, iar D, de la disjuncŃie (D de pe prima poziŃie în 15. provine de la dublă). Reamintim că în regulile având variante cea de a doua schemă va fi referită prin acelaşi număr (nume), urmat de un apostrof. Extinderea alfabetului şi folosirea regulilor derivate pot simplifica mult unele demonstraŃii, care sunt, poate chiar mai mult decât la sistemul SD3, suficient de sofisticate pentru un începător

• Să se arate că avem ( A ∧ C), ( B ∧ C), ( A ∧ B) ├ C, în SD0

Page 216: slide-uri logica

SD1 1• Pornim cu LP1, construit peste un alfabet care conŃine

toŃi conectorii şi cuantificatorii cunoscuŃi (desigur că unii dintre ei pot fi adoptaŃi prin notaŃie, dar îi vom folosi fără restricŃie): , ∧, →, ↔, ∀, ∃, etc.

• Se numeşte secven Ńă orice formulă care are forma: A1 ∧ A2 ∧ … ∧ Am → B1 ∨ B2 ∨ …∨ Bn, unde n, m ∈ N, A1, A2, … , Am, B1, B2, … , Bn ∈ LP1 (m, n pot fi şi egali cu 0, dar nu simultan)

• Prin urmare, vom lucra practic cu clauze, dar notaŃia pe care o vom adopta ne conduce la ideea că secvenŃele sunt mai degrabă metaformule (alt tip de obiect, oricum mai complex) decât formulele cu care am fost familiarizaŃi în capitolele anterioare. Astfel, vom scrie o secvenŃă sub forma:A1, A2, … , Am ⇒ B1, B2, …… , Bn

Page 217: slide-uri logica

SD1 2• Mai mult, vom considera cei doi membri ai

relaŃiei de mai sus ca fiind mulŃimi (atunci când ordinea elementelor va fi esenŃială, vom specifica explicit acest lucru)

• Prin urmare, o secven Ńă va fi de forma U ⇒⇒⇒⇒ V(U şi V pot fi şi mul Ńimea vid ă, dar nu simultan) şi vom putea scrie U’ = U, A în loc de U’ = U U {A}, în ideea că, din anumite motive, elementul A din U’ trebuie pus în evidenŃă

• Vom extinde notaŃia la submulŃimi oarecare, adică vom putea scrie (de exemplu) V, W în loc de V U W şi V, A, B în loc de V U {A} U {B}

Page 218: slide-uri logica

SD1 3• Astfel, punem FORM = {U | U este secvenŃă în

LP1}• Sistemul SD1, atribuit în principal lui Gentzen

(1934) şi având o singură schemă de axiome (este drept, foarte generală), se apropie (în privinŃa modalităŃii de utilizare) mai mult de un sistem de tip Hilbert

• Sistemele deductive bazate pe secvenŃe au şi o răspândită utilizare în situaŃii nestandard (legate numai de definirea constructivă a unor mulŃimi „în mod axiomatic”, fără referire la „adevăr”)

• Mai concret, SD1 este un sistem predicativ finit specificat şi boolean complet, având:

Page 219: slide-uri logica

SD1 4• Axiome . Pentru fiecare U, V ∈ FORM şi pentru fiecare A

∈ LP1:U, A ⇒ V, A.

• Reguli de inferen Ńă. Schemele de mai jos (care, din nou, sunt numerotate dar au ataşat şi un nume mnemonic care nu mai necesită explicaŃii - exceptând poate (RT) care înseamnă regula tăieturii) sunt valabile pentru fiecare U, V ∈ FORM, fiecare A, B ∈ LP1, fiecare x ∈ X şi fiecare t ∈ T

• În regula 5., substituŃia [x/t] trebuie să fie permisă pentru A, iar în 6., x nu trebuie să apară liber în nici o formulă din U sau V

Page 220: slide-uri logica

SD1 5• În momentul în care vor exista mai multe

premize într-o regulă, vom folosi pentru separarea lor „;”

• AtenŃie la faptul că regulile 5. şi 7. au o infinitate de premize (de exemplu, U, (A)[x/t] ⇒ V din (∀∀∀∀⇒⇒⇒⇒) trebuie înŃeles ca reprezentând U, (A)[x/t1] ⇒ V; U, (A)[x/t2] ⇒ V; ... , adică se iau în considerare toate elementele t din T, pentru care [x/t] este permisă pentru A; rolul lui A în (RT) este similar, instanŃele unei scheme referindu-se la celelalte elemente având statutul de a fi „oarecare”

Page 221: slide-uri logica

SD1 6

1. ( ⇒⇒⇒⇒) 2. (∧∧∧∧ ⇒⇒⇒⇒)

3. (⇒⇒⇒⇒ ) 4. (⇒⇒⇒⇒ ∧∧∧∧) .

5. (∀∀∀∀ ⇒⇒⇒⇒) 6. (⇒⇒⇒⇒ ∀∀∀∀)

7. (RT)

• Exemplu seminar (deducerea unor reguliderivate)

U V,AU, A V

¬ ⇒

U,A,B VU,A B V

∧ ⇒

U,A VU V, A

⇒ ¬U V,A;U V,B

U V,A B⇒ ⇒

⇒ ∧

U,(A)[x/t] VU,( x)A V

∀ ⇒

U V,AU V,( x)A

⇒ ∀

U,A V;U V,AU V

⇒ ⇒

Page 222: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 1

• Să ne gândim la reprezentarea prin (meta)formule a unei baze de cunoştinŃe

• Din păcate nu există metode semantice efective (algoritmice) convenabile pentru a testa dacă o mulŃime dată de (meta)formule este sau nu închisă la consecinŃă semantică, sau dacă o anumită (meta)formulă este satisfiabilă sau validă

• Alternativa este de a folosi metode sintactice, care au avantajul că pot fi totuşi automatizate (măcar parŃial)

Page 223: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 2

• Se pune problema axiomatiz ării teoriilor logice, cu ajutorul sistemelor de demonstra Ńie

• Acest lucru înseamnă că având dată o teorie TE ⊆ FORM, trebuie să găsim o submul ŃimeAAAA’’’’ = AAAA U IIII ⊆⊆⊆⊆ TE de „axiome” şi/sau ipoteze suplimentare, precum şi o mul Ńime de reguli de inferen Ńă RRRR (adic ă un sistem de demonstra Ńie SD’ = <AAAA’’’’, RRRR>) astfel încât TE = ThThThTh(SD’)

Page 224: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 3

• În acest caz, se impune de obicei ca AAAA’’’’ să fie măcar o mulŃime satisfiabilă (există măcar o structură Sastfel încât pentru fiecare F ∈ AAAA’’’’ avem S(F) = 1), sau chiar validă (dacă AAAA’’’’ conŃine măcar o contradicŃie, atunci orice (meta)formulă este consecinŃă semantică din AAAA’’’’ )

• Forma generală a lui AAAA’’’’ se explică tocmai prin aceea că am admis că AAAA conŃine formulele valide iar IIII pe cele satisfiabile )

Page 225: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 4• Mai general, să presupunem că pornim cu o mulŃime de

(meta)formule AAAA’’’’ ⊆ FORM, de cunoştinŃe primare, unanim acceptate ca fiind „adevărate”, adică despre care ştim (nu ne interesează deocamdată prin ce metodă am aflat acest lucru) că reprezintă formule valide/satisfiabileîn contextul descris mai sus

• Pentru a axiomatiza teoria dată, trebuie să mai g ăsim şi o mul Ńime de reguli de inferen Ńă RRRR astfel încât s ă avem CsCsCsCs(AAAA’’’’) = ThThThTh(SD’) (am notat cu CsCsCsCs(AAAA’’’’) mulŃimea tuturor consecinŃelor semantice din AAAA’’’’, în raport cu noŃiunea de adevăr adoptată, şi cu SD’ sistemul compus din AAAA’’’’ şi RRRR)

Page 226: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 5

• Putem lua în considerare şi situaŃia inversă, în care avem dat un sistem SD’ = <AAAA’’’’, RRRR> şi dorim s ă vedem dac ă ThThThTh(SD’) este într-adev ăr o teorie logic ă, şi, mai mult, dac ă CsCsCsCs(AAAA’’’’) = ThThThTh(SD’ )

Page 227: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 6

• Defini Ńie. Un sistem de demonstraŃie SD’ = <AAAA’’’’, RRRR> se numeşte corect şi complet pentru o teorie TE dacă TE = ThThThTh(SD’) = CsCsCsCs(A’) şi AAAA’’’’ ⊆ TE. O teorie TE este axiomatizabilă dacă există un sistem deductiv SD’ = <AAAA’’’’, RRRR> corect şi complet pentru ea, adică satisfăcând condiŃiile anterioare

• Dacă SD’ este finit specificabil (axiomatizabil), atunci teoria corespunzătoare se numeşte finit axiomatizabil ă

Page 228: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 7

• În cele de mai sus, dacă IIII este mulŃimea vidă atunci TE este alcătuită doar din (meta)formule valide

• În cazul teoriilor „reale”, IIII cuprinde în general cunoştinŃele primare ale lumii respective, iar AAAA axiomele „logice” (de genul celor „puse” în SD3)

Page 229: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 8

• Teorem ă (de corectitudine şicompletitudine – form ă general ă). Fie o clasă de (meta)formule FORM, o clasă de structuri admisibile StrStrStrStr pentru FORM (princare se defineşte noŃiunea de adevăr), un sistem deductiv SD’ = <AAAA’’’’, RRRR> în FORM, unde AAAA’’’’ = AAAA U IIII (AAAA fiind alcătuită din formule valide şi IIII din formule satisfiabile) şi o teorie logică TE ⊆ FORM, astfel încât TE = CsCsCsCs(AAAA’’’’). Atunci ThThThTh(SD’) = CsCsCsCs(AAAA’’’’)

Page 230: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 9• Observa Ńie. A demonstra corectitudinea înseamnă a

arăta că ThThThTh(SD’) ⊆ CsCsCsCs(AAAA’’’’) iar completitudinea, că ThThThTh(SD’) ⊇ CsCsCsCs(AAAA’’’’)

• Teorema se mai poate enunŃa şi sub una din formele echivalente, destul de des întâlnite:-Teoria TE admite un sistem deductiv corect şi complet-În condiŃiile precizate, avem, pentru fiecare metaformulăF∈ FORM: IIII ├⊢SD F dacă şi numai dacă IIII ╞⊨ F

• Practic, este de dorit ca teoria TE să fie (eventual, chiarfinit) axiomatizabilă

Page 231: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 10

• În cazul în care este vorba de o teorie formată doar din formule valide (atunci va lipsi IIII), teorema capătă forma simplificată:• Pentru fiecare F∈ FORM, avem: ├SD F dacă şi numai dacă ╞ F

• În cele de mai sus am folosit notaŃia ├SD F pentru a exprima faptul că F ∈ThThThTh(SD), unde SD = <AAAA, RRRR>, sau, în momentul în care SD este implicit, ├F poate nota doar faptul că F este o formulă validă

Page 232: slide-uri logica

Legătura dintre teoriile logice şi sistemeledeductive - Teoreme de corectitudine şi

completitudine 11

• Teorem ă (teorema de completitudine a lui K. Gödel, 1930) . IIII ├SD3 F dacă şi numai dacă IIII ╞ F

• Teorem ă. Sistemul SD0 este corect şi complet pentru ValValValVal(LP1)

• Teorem ă. Sistemele SD0 şi SD3 sunt echivalente. Mai mult, pentru fiecare mulŃime de formule închise JJJJ ⊆ LP1 şi fiecare formulă F ∈ LP1, avem:JJJJ ├SD0 F dacă şi numai dacă JJJJ ├SD3 F

• Teorem ă. Fie orice F ∈∈∈∈ LP1. Atunci:├SD1 F dacă şi numai dac ă ╞F

Page 233: slide-uri logica

Teorii logice şi sistemele deductive - final

• D.p.d.v. practic, avem nevoie de teorii„puternice” (care să conŃină măcar „aritmetica”, „egalitatea” şi axiomele logice„primare”); acestea sunt incomplete , din păcate

• Index, comentarii, exemple