Topics on Discrete Mathematics

Objectives

Students should

  • apply elementary properties of propositional logic operations of quantifications;
  • operate with sets;
  • apply Natural Induction as a proof method;
  • identify injective functions and surjective functions;
  • apply basic concepts about equivalence relations and order relations;
  • manipulate basic graph concepts.
  • apply acquired knowledge in the construction of proofs or in solving problems related to the topics addressed

Program

  1. Basics of Logic: Propositional Logic (connectives, formulas, truth values, truth tables, tautologies, logical equivalences); Relational Logic (predicates, quantifiers); proof techniques.
  2. Sets: representation of sets; set operations.
  3. Natural induction.
  4. Functions: definition; image set; reverse image set; injective functions; surjective functions; bijective functions; invertible functions.
  5. Binary relations: definition; basic concepts, properties, equivalence relations, and order relations.
  6. Graphs: basic concepts, related graphs, trees.

Bibliography

How to prove it: a structure approach, Daniel Velleman, Cambridge University Press [1994]. The Foundations of Mathematics, Ian Stewart, David Tall, Oxford Science Publication [1990]. Proofs and Fundamentals: a first course in Abstract Mathematics, Ethan D. Bloch, Birkhuser [2000]. Mathematical Fundamentals of Computer Science, P. Fejer, D. Simovici, Springer-Verlag [1991]. A Logical Introduction to Proof, Daniel Cunningham, Springer-Verlag [2013].

Updated: