Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MIF0001	Mathematical Foundations of Computer Science	

Semester	Hours: C+S+L+P	Category	Status	
1	2+2+0+0	fundamental	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
LUPEA Mihaiela	Ph.D.	Lect.	Programming  Languages and Methods	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
The aim of the course is the presentation of logical foundations of computer science: propositional and predicate calculus, theorem proving methods, Boolean algebras and Boolean functions. The connection with logic programming and logical circuits is presented. Additionally, notions related to information representation are introduced.	

IV. Course contents
1. Numeration systems and numbers representation
- Definitions, representation and operations (algorithms for comparison, addition, 
  subtraction, multiplication, division) of numbers in a base b. 
- Conversions between bases using the methods (calculus in the source base, calculus in 
  the destination base, using an intermediate base) for integer and rational numbers.
- Examples for particular bases: 2,3,4,6,8,10,16.
- Representation for unsigned integers, operations (!!overflow!!), algorithms for 
  multiplication and division. 
- Representation for signed integers: direct code, inverse code, complementary code, 
  operations and subunitary convention. 
- Representations for real numbers: fixed-point representation, floating-point 
  representation . 

2. Propositional and predicate calculus are presented from an algebraic point of view 
   and as deductive systems. Theorem proving methods are used to decide if a statement 
   (conjecture) is a logical consequence of a set of statements (axioms and hypotheses).
- Syntax and the deductive systems associated to propositional/predicate logic.
- Semantics: interpretation, model, consistent/inconsistent formula, tautology, logical 
  consequence, logical equivalences (DeMorgan, absorption, commutativity, associativity, 
  distributivity, idempotency).
- Normal forms in propositional logic (conjunctive and disjunctive forms) and predicate 
  logic( prenex, Skolem, clauzal forms).
- Properties of propositional/predicate logics: soundness, completness, coherence,
  non-contradiction, and decidability/semidecidability.
- Theorem proving methods in these logical systems.

3.Boolean algebras, Boolean functions and Logical circuits
- Boolean algebras: definition, properties, principle of duality, example.
- Boolean functions: definitions, maxterms, minterms, canonic forms.
- Simplification of boolean functions:
  &#8226; definitions: maximal monoms, central monoms, factorization;
  &#8226; Veitch-Karnaugh diagrams method &#8211; for functions with 2-3 variables;
  &#8226; Quine&#8217;s method, Moisil method.
- Logical circuits
  &#8226; definitions, representations for basic gates (&#8220;and&#8221;, &#8220;or&#8221;, &#8220;not&#8221;) and derived gates 
    (&#8220;xor&#8221;, &#8220;nand&#8221;, &#8220;nor&#8221;) and relations between them.
  &#8226; examples of simple logical circuits: &#8220;decoder&#8221;, &#8221;binary codification&#8221; circuit 
    &#8220;comparison circuit&#8221;, &#8220;addition&#8221; circuit;

V. Bibliography
1. M. Ben-Ari: Mathematical Logic for Computer Science, Ed. Springer, 2001.
2. C.L. Chang, R.C.T. Lee: Symbolic Logic and Mechanical Theorem Proving, Academic Press,
   1973.
3. M. Clarke: Logic for Computer Science, Ed. Eddison-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. M. Lupea, A. Mihis: Logici clasice si circuite logice. Teorie şi exemple,
   Ed. Albastra, Cluj-Napoca, 2009.
7. Mihaela Malita, Mircea Malita: Bazele Inteligentei Artificiale, Vol. I, Logici 
   propozitionale, Ed. Tehnica, Bucuresti, 1987.
8. L.C. Paulson: Logic and Proof, Univ. Cambridge, 2000, on-line course.
9. M. Possega: Deduction Systems, Inst. of Informatics, 2002, on-line course.
10.D.Tatar: Bazele matematice ale calculatoarelor, edition 1999- library.	

VI. Thematic of didactic activities per weeks

VII. Didactic methods used

VIII. Assessment
- The examination consists of a written exam with the subject from all the matter (70%). 
- In the final marks will be considered the activity (responses, individual  
  presentations, short tests) at the seminars (30%). 
Remark: Seminars&#8217; presence is mandatory for at least 70%.	

IX. Additional references

	Dean,							Chair head,

	Date,							Course responsible,
								Lect. LUPEA Mihaiela, Ph.D.