IIC1253 Discrete Mathematics

An introduction to the mathematical language and proof techniques used in computer science, with emphasis on abstraction, formal modeling, and rigorous problem solving.

Instructor: Rafael Elberg

Term: First Semester

Location: PUC Campus

Time: Mondays and Wednesdays, 9:40-11:00 AM

Course Overview

This course introduces the mathematical concepts and models that support the study of computer science. The focus is both theoretical and practical: students learn to write precise statements, build formal models, and prove or refute claims using the language of logic, sets, relations, functions, cardinality, induction, number theory, and related tools.

The official material for the course is available in the IIC1253 2026-1 GitHub repository. My Section 2 lecture slides are collected under Clases / Seccion 2, and the official course program is available as programa_discretas_2026_01.pdf.

By the end of the course, students should be able to:

  • Translate informal problems into formal mathematical notation.
  • Prove and refute statements using direct proofs, counterexamples, induction, and structural reasoning.
  • Model computational problems with logic, sets, relations, functions, and graphs.
  • Work with finite and infinite cardinalities.
  • Apply modular arithmetic and number-theoretic tools to computational examples such as RSA.

Prerequisites

  • MAT1203 OR IMT2210 OR (IIC1001 AND MAT1207)

Textbooks

  • Kenneth Rosen, Discrete Mathematics and its Applications, 7th edition.
  • Susanna Epp, Discrete Mathematics with Applications, 4th edition.
  • David Makinson, Sets, Logic and Maths for Computing, 2nd edition.
  • Luis Dissett, Apuntes de Matematicas Discretas.
  • Jorge Perez, Apuntes de Matematicas Discretas.

Grading

  • Two interrogaciones, two controles, and a final exam.
  • Optional homework assignments are published throughout the semester and are intended as continuous practice.

Methodology

  • Two in-person lectures per week.
  • One weekly in-person teaching assistant session.
  • Canvas is used for announcements and assignment submission; GitHub is used for class material, evaluations, complementary resources, and content questions through issues.

Schedule

Week Date Topic Materials
Unit I Propositional logic

Logical connectives, truth tables, CNF/DNF, tautologies, logical consequence, proof methods, modeling, and SAT.
Unit II Predicate logic

Predicates, quantifiers, formulas, and examples from arithmetic, geometry, calculus, and asymptotic notation.
Unit III Induction

Standard induction, strong induction, the least number principle, structural induction, and inductive definitions.
Unit IV Set theory

Axiomatic set theory, set operations, Russell’s paradox, separation, Cartesian products, infinity, and natural numbers.
Unit V Relations and functions

Relations, composition, inverse relations, orderings, equivalence relations, graphs, and functions as relations.
Unit VI Cardinality

Finite and infinite cardinality, Schroeder-Bernstein, countability, Kleene star over countable sets, and Cantor’s theorem.
Unit VII Number theory

Divisibility, modular arithmetic, the fundamental theorem of arithmetic, gcd, coprimality, modular inverses, Fermat’s little theorem, and RSA.