slide-uri logica

Click here to load reader

Post on 29-Jun-2015

205 views

Category:

Documents

1 download

Embed Size (px)

TRANSCRIPT

CURS 1-2 Sunt, n anul universitar 2010-2011, semestrul I, 16 sptmni de coal; sptmnile a 8-a i a 16-a sunt destinate lucrrilor 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 Rmn deci 13 cursuri i 14 seminarii (teoretic, pentru c vom avea tot 13 seminarii) n perioada 4-9 octombrie 2010 suntem n sptmna a doua cu primul curs i al doilea seminar, dar acesta ar putea fi considerat i el primul (innd cont de faptul c trebuie s reprezinte primul curs) INFORMAI-V LA TIMP (pagini web)

DE CE LOGICA ? Introducere

LOGICA PENTRU INFORMATICFacultatea de Informatic Universitatea Al.I.Cuza Iai (http://www.info.uaic.ro)

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

Profesori 2 Asist. drd. Cosmin Vrlan (seminar) [email protected] http://profs.info.uaic.ro/~vcosmin

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

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

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)

Orar 2 (http://www.info.uaic.ro/~orar) Seminarii (tii 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)

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)

Orar 4 (http://www.info.uaic.ro/~orar) Ore de consultaii C.Masalagiu, V.Alaiba, M.Barat:

Miercuri: 10.00 12.00Cabinet C305 C.Varlan:

Miercuri: 18.00 20.00Cabinet C211

Cerine 1http://www.info.uaic.ro -> Membri -> Personal Academic (pentru a cunoate i ali profesorii a naviga ctre paginile noastre)

http://www.info.uaic.ro -> Studeni -> Regulamente http://profs.info.uaic.ro/~masalagiu/ -> Seciunea Logic

Cerine 2 Nota final se obine n urma acumulrii unui numr de puncte (maxim 100) i n urma aplicrii unui algoritm de tip Gauss (conform regulamentului n vigoare)

Cerine 3 60 din cele 100 de puncte se pot obine la cele dou lucrri din sptmnile 8 respectiv 16 40 de puncte se pot obine n urma activitii la seminar din timpul semestrului Urmrii paginile web!

Cerine 4 Sunt necesare un minim de 30 de puncte pentru a promova A se consulta (deja menionat) mcar pagina http://profs.info.uaic.ro/~masalagiu (Logic)

Cerine 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 logica si limbajele de programare logica , Ed. Universitatii Al. I. Cuza, Iasi, 1996. Cazacu, C., Slabu, V. - Logica matematica , Editura Stefan Lupascu, Iasi, 1999, ISBN 973-99044-0-8.

Cerine 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 seciunea Logic - Bibliografie de baz; linkurile pot fi accesate doar din cadrul FII) A se nva i dup carte, nu numai dup slide-uri !!!

Capitolele tematice (unele nu vor fi prezentate chiar n aceast ordine) Logica n Informatic Algebre booleene Logica propoziional Logica cu predicate de ordinul I Sisteme deductive i teorii logice Introducere n Programarea logic OBDD-uri i Verificare

RealitateRealitate: obiecte i fenomene aflate n relaii de interdependen Relaiile (legturile) se reflect, n procesul gndirii umane, prin afirmaii (judeci)

Logica (intuitiv) 1 Logica (n sens filozofic) este tiina regulilor generale ale gndirii, cu accent pe aspectele exacte i de natur structural ale acesteia Alte definiii dup cum urmeaz

Logica (intuitiv) 2 Logica studiaz modul de alctuire a raionamentelor corecte, prin care, pornind de la afirmaii iniiale (presupuse a fi adevrate) se obin (utiliznd reguli de inferen) afirmaii noi (de asemenea adevrate)

Afirmaii O afirmaie este adevrat dac reflect n mod adecvat realitatea i fals n caz contrar Este acceptat faptul c valorile de adevr ataate unei afirmaii pot avea o natur subiectiv i, n consecin, pot fi i altceva dect cele standard (adevrat i fals); dar astan alte logici De exemplu: necunoscut, posibil adevrat, adevrat din cnd n cnd, etc.

Logica clasic Logica clasic (aristotelic, bivalent) folosete doar afirmaii crora li se poate asocia n mod unic o valoare de adevr standard (independent de context, moment de timp, etc.) i se bazeaz n esen pe principiul tertium non datur (teriul exclus: dac o afirmaie nu este adevrat, atunci ea este cu certitudine fals i reciproc) Un alt principiu este cel al extensionalitii (adevrul unei formule) Exist i logici neclasice (exemple)

Idei suplimentare 1 Logica matematic, formal (simbolic), preia problemele logicii filozofice i le cerceteaz folosind mijloace matematice specifice, punndu-se baz pe rigurozitate i claritate n detrimentul nuanelor sau intuiiei

Idei suplimentare 2 Aplicarea acesteia n Informatic necesit ns o anumit adaptare, att a modului de prezentare a conceptelor (terminologiei) ct i a metodelor de demonstraie, accentul cznd pe constructivism (algoritmic)

Despre CURSStructura Cursului; sugestii privind examinarea Dificulti de nvare (sunt i avantaje) Paradoxuri, greeli frecvente, exemple Sfer, coninut, gen proxim, diferen specific Silogisme, axiome, teoreme, reguli de inferen, raionamente, exemple Axiome adevrate i reguli de inferen corecte (sound) pot exista raionamente corecte, dar dac se pleac cu premize false(vezi i paradoxuri) Sintax + semantic Logica este un limbaj de programare: formul + valoare de adevr (execuie = evaluare) Nr. de pagin s-ar putea s nu coincid cu ceea ce avei voi pe site (eu m refer la cartea publicat)

Mulimi 1 Clasa funciilor booleene (intuitiv) Notaii Din manualele de matematic de liceu sunt bine cunoscute cel puin dou modaliti de a prezenta o mulime: -Prin enumerarea elementelor sale: N = {0, 1, 2, ...} este mulimea numerelor naturale

Mulimi 2-Prin specificarea unei proprieti caracteristice: A = {x R | x2 + 9x 8 = 0}, este mulimea rdcinilor reale ale unei ecuaii polinomiale de gradul al II-lea -Mai avem o posibilitate, bazat pe constructivism:

Mulimi 3 (Peano) Baza. 0 N (zero este numr natural) Pas constructiv (structural). Dac n N, atunci s(n) N (dac n este numr natural, atunci succesorul su imediat este numr natural) Nimic altceva nu mai este numr natural

Mulimi 4 Un prim avantaj este acela c se poate folosi aceeai metod pentru a introduce alte definiii, care sunt legate de mulimea respectiv n totalitatea ei. Putem da astfel o definiie constructiv (recursiv) a adunrii numerelor naturale: -Baza. x + 0 = x, pentru fiecare x N (a aduna 0 la orice numr natural nseamn a-l lsa neschimbat) -Pas constructiv. x + s(y) = s(x + y), pentru fiecare x, y N (dac tim s calculm x + y i cunoatem succesorul imediat al numrului natural y, atunci tim s calculm i suma x + s(y); mai exact, aceasta coincide cu succesorul imediat al numrului care reprezint suma x + y) -Nimic altceva

Mulimi 5 Un al doilea, i cel mai important, avantaj este posibilitatea folosirii n demonstraii a Principiului induciei structurale: -Fie A o mulime definit constructiv, A A mulimea elementelor iniiale (definite prin pasul Baza al definiiei) i P o afirmaie care trebuie demonstrat pentru toate elementele lui A -Acceptm c P(a) este adevrat pentru fiecare a A dac i numai dac:

Mulimi 6 1 (Baza elemente iniiale). Artm c P(a) este adevrat pentru fiecare a A 2 (Pas inductiv elemente noi din elemente vechi): -Fie orice b A, element nou obinut din elementele deja construite a1, a2, ... , an, cu ajutorul operatorului f (vom conveni s scriem acest lucru prin b = f(a1, a2, ... , an), dei relaia dintre elementele vechi i cele noi nu este ntotdeauna de natur funcional) i presupunem c este adevrat P(ai) pentru fiecare i {1, 2, ..., n} -Artm c este adevrat P(b) Probleme seminar: http://profs.info.uaic.ro/~masalagiu/pub/Seminar1.pdf

Algebre booleene 1 Se numete algebr boolean un 4-uplu M, M = , format din orice mulime nevid M (suportul algebrei) dou operaii binare , : M M M i o operaie unar ~ : M M, care satisfac condiiile (legile): 1) x y = y x 2) (x y) z = x (y z) comutativitate (a lui )

asociativitate (a lui ) 3) x (y z) = (x y) (x z) distributivitate (a lui fa de ) 4) (x y) y = y absorbie 5) (x (~x)) y = y legea contradiciei

Algebre booleene 2i respectiv 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 absorbie 5) (x (~x)) y = y legea tautologiei

Algebre booleene 3 Dualitate; principiul dualitii Notaii (reamintit: M B, 2V; - , ; - +, U; ~ - , CV) Reprezentare (tabele de adevr, standard) Funcii importante (0, 1, 2 argumente): 0, 1, c0, c1, 1B, , +, , , | . Numrul de funcii din FB-uri Reprezentarea numeric a tabelelor standard Alte considerente algebrice (latici) Alte legi (Tabelul 1.1 pag.30 cartea tiprit)

CURS 3 Reprezentarea funciilor booleene Forme normale Clase speciale de funcii booleene Sintaxa LP

Reprezentarea funciilor booleene 1 Notaii: x1 = x i x0 = x Indicii (superiori) precedeni nu se supun principiului dualitii (de exemplu, nu este adevrat c (x1 =