Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate
SUBJECT

Code	Subject	
MIF0001	Mathematical Foundations of Computer Science	

Section	Semester	Hours: C+S+L	Category	Type	
Computer Science	1	2+2+0	fundamental	compulsory	
Information engineering	1	2+2+0		compulsory	

Teaching Staff in Charge	Lect. LUPEA Mihaiela, Ph.D., lupea@cs.ubbcluj.ro
Assoc.Prof. ROBU Judit, Ph.D., robu@cs.ubbcluj.ro	
Aims	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.	
Content	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;
	
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, 2008.
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.	
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%.