Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu română
Limba de predare: Română

SYLLABUS

I. Date generale
Codul	Disciplina	
MIF0001	Bazele matematice ale calculatoarelor	

Semestrul	Ore: C+S+L	Categoria	Statutul	
1	2+2+0	fundamentala	obligatorie	

II. Cadre didactice cu norma de bază în Universitate
Numele şi	Titlul	Gradul	Catedra	Tipul activităţii	
prenumele	ştiinţific	didactic		C	S	L	
LUPEA Mihaiela

MIHIS Andreea	Dr.	Lect.

Asist.	Limbaje şi Metode de Programare
Limbaje şi Metode de Programare	*	*

*		

Cadre didactice asociate
Numele şi	Titlul	Instituţia	Tipul	Tipul activităţii	
prenumele	ştiinţific		postului	C	S	L	

III. Obiectivele disciplinei
Scopul acestui curs este prezentarea bazelor logice ale informaticii: logica propoziţiilor şi logica predicatelor, metode de demonstrarea teoremelor în aceste sisteme logice, algebre şi funcţii booleene. Se face legătura cu aplicaţii ale logicii în informatică: modelarea raţionamentului, programarea logică, circuite secvenţiale şi combinaţionale. Sunt de asemenea introduse noţiuni de codificarea şi reprezentarea informaţiei în calculator.

IV. Conţinutul disciplinei
1.	Baze de numeraţie: reprezentare, operaţii (algoritmi pentru comparare, adunare, scădere, înmulţire şi împărţire) şi conversii între baze de numeraţie. Reprezentarea internă a numerelor: întregi (fără semn, cu semn - codurile direct, invers şi complementar), reale (reprezentarea în virgulă fixă şi în virgulă mobilă).

2.	Logica propoziţiilor şi logica predicatelor prezentate algebric şi ca sisteme formale. Forme normale ale formulelor. Problema decidabilităţii în aceste sisteme logice. Metode de demonstrare a teoremelor: metoda lui Herbrand, metoda rezoluţiei, calculul secvenţelor, metoda tabelelor semantice. Formalizarea raţionamentului cotidian şi a celui matematic folosind aceste logici clasice.

3.	Algebre booleene, funcţii booleene şi aplicaţii. Simplificarea funcţiilor booleene folosind metoda diagramelor Veitch-Karnaugh, metoda analitică a lui Mc.Quine şi metoda algebrică a lui Moisil. Circuite logice şi combinaţionale. 

V. Bibliografie
1.	M. Ben-Ari: Mathematical Logic for Computer Science, Ed. Springer, 2001. 
2.	F.Boian, Bazele Matematice ale Calculatoarelor, Editura Presa Universitara Clujeana, 2002 – bibliotecă.
3.	C.L.Chang, R.C.T.Lee: Symbolic Logic and Mechanical Theorem Proving, Academic Press.
4.	M. Cocan, B. Pop: Bazele matematice ale sistemelor de calcul, Editura Albastra, Cluj-Napoca, 2001 – bibliotecă.
5.	M.Fitting: First-order logic and Automated Theorem Proving, Ed.Springer Verlag, 1990.
6.	M. Lupea, A. Mihis: Logici clasice şi circuite logice. Teorie şi exemple, ediţia 2, Editura Albastra,
      Cluj-Napoca, 2009 - bibliotecă.
7.	Mihaela Malita, Mircea Malita, Bazele Inteligentei Artificiale, Vol. I, Logici propozitionale, Ed. Tehnica, Bucuresti, 1987 – bibliotecă. 
8.	L.C. Paulson: Logic and Proof, Univ. Cambridge, 2000, curs on-line.
9.	M. Possega: Deduction Systems, Inst. of Informatics, 2002, curs on-line.
D.Tatar: Bazele matematice ale calculatoarelor, ediţia 1999- bibliotecă.	

VI. Tematica activităţilor didactice pe săptămâni
Curs 1-3 + Seminar 1-3:
Baze de numeraţie. Codificarea informaţiei. Reprezentarea numerelor.
Baze de numeraţie
1.	Definiţii, reprezentare şi operaţii (algoritmi de comparare, adunare, înmulţire, împărţire) cu numere într-o bază dată. 
2.	Conversiile numerelor întregi şi raţionale  între baze de numeraţie folosind metodele: calculul în baza sursă, calculul în baza destinaţie, utilizarea unei baze intermediare.
3.	Exemple pentru bazele particulare: 2,3,4,6,8,16.
Reprezentarea internă a numerelor
1.	Reprezentarea numerelor întregi fără semn, operaţii, noţiunea de depăşire, algoritmi de înmulţire şi împărţire. Exemple.
2.	Reprezentarea numerelor întregi cu semn folosind codurile: direct, invers şi complementar, operaţii, depăşire. Exemple. 
3.	Reprezentarea numerelor subunitare cu semn, codurile: direct, invers, complementar.
4.	Reprezentarea numerelor reale: virgulă fixă, virgula mobilă (cu mantisa subunitară, cu mantisa supraunitară). Exemple.

Logica propoziţiilor
Curs 4 + Seminar 4:
1.	Sintaxa logicii propoziţiilor: conective, formule.
2.	Semantica: interpretarea unei formule, model, formulă consistentă (realizabilă), formulă inconsistentă (contradictorie), tautologie, relaţia de consecinţă logică. Tabela de adevăr a unei formule.
3.	Echivalenţe logice (legi): DeMorgan, absorbţia, comutativitatea, asociativitatea, distributivitatea, idempotenţa.
4.	Clauze şi forme normale: conjunctivă (FNC) şi disjunctivă (FND), algoritmul de transformare a unei formule în FNC şi FND..
5.	Probleme: 
•	Utilizând tabela de adevăr, decideţi dacă o formulă este consistentă/ /tautologie/inconsistentă şi scrieţi toate modelele în cazul consistenţei.
•	Transformaţi o formulă în formele normale echivalente FNC, FND şi decideţi dacă formula este inconsistentă  / tautologie.

Curs 5 + Seminar 5:
1.	Sistemul formal (axiomatic, deductiv) al logicii propoziţionale, deducţie, teoremă.
2.	Teorema de deducţie şi consecinţele sale.
3.	Teorema de corectitudine şi completitudine a logicii propoziţiilor. Proprietăţi ale logicii propoziţiilor: necontradicţia, coerenţa şi decidabilitatea.
4.	Probleme:  
•	Aplicarea teoremei de deducţie pentru a demonstra regula silogismului, separarea premizelor, reuniunea premizelor. 
•	Utilizarea sistemului deductiv în demonstrarea teoremelor.

Curs 6 + Seminar 6:
Metoda tabelelor semantice  în logica propoziţiilor – metodă de demonstrare 
1.	Clase de formule, reguli de descompunere a formulelor, ramură (deschisă, închisă), construcţia tabelei semantice asociate unei formule.
2.	 Teorema de corectitudine şi completitudine a acestei metode. 
3.	Probleme: 
•	Construirea modelelor unei formule propoziţionale consistente din tabela semantică ataşată formulei.
•	 Verificaţi dacă o formulă propoziţională este tautologie / consecinţă logică a unei mulţimi de formule utilizând metoda tabelelor semantice. 

Curs 7 + Seminar  7:
Rezoluţia propoziţională – metodă de demonstrare 
1.	Sistemul formal al rezoluţiei.  Procedura de rezoluţie.
2.	Rafinări ale rezoluţiei: strategia saturării pe nivele, strategia mulţimii suport, strategia eliminării, rezoluţia blocării, rezoluţia liniară  (input, unit).
3.	Corectitudinea şi completitudinea rezoluţiei generale şi a rafinărilor sale.
4.	Probleme: 
•	Utilizând metoda rezoluţiei verificaţi consistenţa / inconsistenţa unei mulţimi de clauze.
•	Verificaţi dacă o formulă propoziţională este teoremă / este deductibilă dintr-o mulţime de formule, utilizând rezoluţia generală sau rafinările acesteia.

Curs 8 + Seminar 8: 
Calculul secvenţelor în logica propoziţiilor
1.	Sistemul formal al calculului secvenţelor: secvenţă, secvenţă de bază, secvenţă adevărată, reguli de inferenţă specifice conectivelor, reducerea unei secvenţe. 
2.	Construirea arborelui asociat reducerii unei secvente. 
3.	Teorema de corectitudine şi completitudine a acestei metode. 
4.	Probleme: 
•	Verificaţi dacă o formulă propoziţională este teoremă / este deductibilă dintr-o mulţime de formule, utilizând calculul secvenţelor.

Logica predicatelor de ordinul I

Curs 9 + Seminar 9:
1.	Sintaxa logicii predicatelor: conective, cuantificatori, termeni, atomi, formule, literali, clauze. Sistemul formal (axiomatic) asociat logicii predicatelor.
2.	Semantica logicii predicatelor: interpretare, model, formulă validă, formulă consistentă, formulă contradictorie, relaţia de consecinţa logică.
3.	Forme normale ale formulelor predicative: forma normală prenexă, forma normală Skolem. Algoritmii de aducere a unei formule la formele normale.
4.	Teorema de corectitudine şi completitudine. Proprietăţile logicii predicatelor: necontradicţia, coerenţa, semi-decidabilitatea.
5.	Probleme referitoare la noţiunile teoretice prezentate.

Curs 10 + Seminar  10:
1.	Calculul secvenţelor în logica predicatelor – reguli de reducere specifice cuantificatorilor.
2.	Metoda tabelelor semantice în calculul predicatelor – reguli de descompunere specifice cuantificatorilor.
3.	Univers Herbrand, sistem Herbrand, interpretare Herbrand, teorema lui Herbrand. Demonstrarea prin respingere pe baza teoremei lui Herbrand.
4.	Probleme:
•	Demonstrare teoremelor în calculul predicatelor utilizând calculul secvenţelor şi metoda tabelelor semantice.
•	Verificarea inconsistenţei unei mulţimi de clauze folosind procedura bazată pe teorema lui Herbrand.

Curs 11 + Seminar 11:
1.	Substituţii şi unificatori ai termenilor şi atomilor. Algoritmul de obţinere al celui mai general unificator a doi atomi.
2.	Metoda rezoluţiei în logica predicatelor. Strategii de aplicare a rezoluţiei. Corectitudinea şi completitudinea rezoluţiei generale şi ale rafinărilor acesteia.
3.	Probleme:
•	Calcularea celui mai general unificator a doi atomi.
•	Verificarea dacă o formulă predicativă este teoremă/deductibilă dintr-o multime de ipoteze utilizând metoda rezoluţile şi rafinările acesteia.
 
Curs 12-14 + Seminar  12-14:
 Algebre booleene, funcţii booleene, circuite logice.
1.   Algebre booleene: definiţii, proprietăţi, principiul dualităţii.
2.   Funcţii booleene, formele canonice echivalente.
4.	Simplificarea funcţiilor booleene
•	definiţii: monoame maximale, monoame centrale, factorizare;
•	metoda diagramelor Veitch-Karnaugh pentru funcţii cu 2-3 variabile;
•	metoda analitică a lui Mc.Quine şi metoda algebrică a lui Moisil.
4. Circuite logice
•	definiţii, reprezentarea circuitelor poartă de bază (“and”, “or”, “not”) şi a circuitelor poartă derivate (“xor”, “nand”, “nor”);
•	exemple de circuite logice.	

VII. Metode didactice folosite
•	prelegeri ce conţin aspecte teoretice şi exemple;
•	seminarii care constau în exerciţii pentru aprofundarea teoriei şi prezentări individuale ale studenţilor a unor probleme existente într-o bază de probleme propusă (M. Lupea, A. Mihis: Logici clasice şi circuite logice. Teorie şi exemple, ediţia 2, Editura Albastra, Cluj-Napoca, 2009 ) pentru studiul logicii propoziţiilor şi logicii predicatelor.	

VIII. Evaluare
Examinarea constă dintr-un examen scris cu subiecte din toată materia, nota obtinută având o pondere de 70%  în nota finală.
Nota pentru activitatea de la seminarii  are o pondere de 30% în nota finală şi se compune din:
-	răspunsuri + prezentări individuale de probleme ;
-	program (Pascal, C, C++, Java, etc) care conţine implementarea algoritmilor de conversii şi operaţii în diferite sisteme de numeraţie.

Observatie: Prezenţa la seminarii este obligatorie în proporţie de 70%.
http://cs.ubbcluj.ro/~lupea/BMC/Romana

IX. Bibliografie suplimentară
1.  W.Bibel: Automated theorem proving, View Verlag, 1987.
2.  Cl.BENZAKEN: Systeme formels. Introduction a la logique, ed.Masson, 1991.
3.   J.P.DELAHAYE: Outils logiques pour l'intelligence artificielle, ed.Eyrolls, 1986.
4. D.Tatar: Inteligenta artificiala: demonstrare automata de teoreme si NLP, Ed. Microinformatica, 2001.
5.  (ed) A.Thayse: From standard logic to Logic Programming, Ed. J.Wiley, vol1(1989), vol2(1989), vol3(1990). 	

	Data,							Titular curs,

      1.10.2009						     Lect. Dr. LUPEA Mihaiela