Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate
SUBJECT
| MIF0001 | Mathematical Foundations of Computer Science |
| Teaching Staff in Charge |
Lect. LUPEA Mihaiela, Ph.D., lupea cs.ubbcluj.roAssoc.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: • 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, 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’ presence is mandatory for at least 70%. |
| Links: | Syllabus for all subjects Romanian version for this subject Rtf format for this subject |