Universitatea "Babeş-Bolyai" din Cluj-Napoca

Facultatea de Matematică şi Informatică
FISA DISCIPLINEI

Bazele matematice ale calculatoarelor Mathematical foundations of Computer Science
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MI039
1
2+2+0
7
obligatorie
Tehnologie Informatică
(College of Computer Technology)
MI039
1
2+2+0
6
obligatorie
Informatică
(Computer Science)
Cadre didactice indrumatoare Teaching Staff in Charge
Conf. Dr. TĂTAR Doina, dtatar@cs.ubbcluj.ro
Lect. ROBU Judit, robu@cs.ubbcluj.ro
Obiective Aims
Scopul cursului este insusirea de catre studenti a acelor cunostinte din logica pentru informaticienii care vor fi utilizate in cursurile din anii urmatori: logica propozitiilor si a predicatelor, algebre si functii booleene. Se face legatura, acolo unde e posibil, cu aceste aplicatii ale logicii: circuite secventiale si combinationale, programarea logica, etc. Aditional, se predau notiuni de codificarea informatiei in calculator.
 The aims of the course is the presentation of logic foundations for computer science: propositional and predicate calculus, boolean algebra and boolean functions. The connection with logic programming and logical circuits is presented. Additionally, the codes of information representation are introduced.
Continut
1. Abordarea algebrica a logicii propozitiilor si predicatelor. Algebra propozitiilor. Formule in calculul propozitional. Decidabilitate.Forme normale conjunctive si disjunctive. Demonstratie prin respingere. Cuantificatori. Formule in calculul predicatelor.Definitii alternative. Forme normale ale formulelor. Problema decidabilitatii in logica predicatelor: teorema lui Herbrand, Skolem.
2. Abordarea logicii propozitiilor si predicatelor ca sisteme deductive. Sisteme formale.Calculul propozitiilor ca sistem formal. Notiunea de teorema. Teorema de deductie, necontradictie si de completitudine. Calculul predicatelor ca sistem formal. Alte metode de abordare a problemei decidabilitatii: metoda rezolutiei. Legatura calculului predicatelor cu programarea logica.
3.Functii booleene si aplicatii. Algebre si inele booleene.Functii booleene. Proprietati ale functiilor booleene. Forma canonica conjunctiva si disjunctiva si aplicatii. Monoame canonice,maximale si centrale. Simplificarea functiilor prin metoda diagramelor Veitch, prin metoda Mc.Quine si prin metoda Moisil. Ecuatii booleene. Tipuri de ecuatii si metode de rezolvare. Circuite logice,combinationale si secventiale.
4.Reprezentarea informatiei. Sisteme de numeratie si conversiunea numerelor.Codul direct, invers, complementar. Teoremele de adunare si legatura cu tipurile de sumator. Reprezentarea cu virgula fixa si virgula mobila.
Bibliografie
1. Cl.Benzaken, "Systeme formels. Introduction a la logique", ed.Masson, 1991.
2. N.Both, "Capitole speciale de logica matematica", litografiat, 1994.
3. M.Clarke, "Logic for Computer Science", ed. Addison-Wesley 1990.
4. J.P.Delahaye, "Outils logiques pour l'intelligence artificielle", ed.Eyrolls, 1986.
5. M.Fitting, "First-order logic and Automated Theorem Proving", Ed.Springer Verlag, 1990.
6. D.Mandrioli, C.Ghezzi, "Theoretical foundations of Computer Science", ed.John Wiley, 1987.
7. U.Nielsson, J.Maluszynski, "Logic programming", ed.John Wiley, 1990.
8. D.Tatar, "Bazele matematice ale calculatoarelor", litografiat, 1993.
9. *** "Turbo Prolog", Borland International, 1988, vol 1 si
Evaluare Assessment
Este urmarit gradul de insusire de catre studenti a conceptelor de baza din logica computationala si a modului lor de utilizare. Forma de examinare este prin examen scris.
 The examination consists of writed exam with the subject from all the matter.