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
fundamental
compulsory
Teaching Staff in Charge
Lect. LUPEA Mihaiela, Ph.D.,  lupeacs.ubbcluj.ro
Assoc.Prof. ROBU Judit, Ph.D.,  robucs.ubbcluj.ro
Lect. EGRI Edith,  egrieditcs.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:
• definitions: maximal monoms, central monoms, factorization;
• Veitch-Karnaugh diagrams method – for functions with 2-3 variables;
• Quine’s method, Moisil method.
- Logical circuits
• definitions, representations for basic gates (“and”, “or”, “not”) and derived gates
(“xor”, “nand”, “nor”) and relations between them.
• examples of simple logical circuits: “decoder”, ”binary codification” circuit
“comparison circuit”, “addition” circuit;
References
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.
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’ presence is mandatory for at least 70%.
Links: Syllabus for all subjects
Romanian version for this subject
Rtf format for this subject