INTRODUCTION TO DISCRETE MATHEMATICS

MiNI PW | Main page | Lecture notes | EIDM

COURSE CONTENTS

  1. Introduction (4hrs)
    1. Propositions, propositional calculus, tautologies
    2. Propositional functions and quantifiers
    3. Sets, operations on sets, generalized union and intersection of sets
  2. Relations (6hrs)
    1. Cartesian product of sets. Relations as subsets of the Cartesian product of sets
    2. Equivalence relations, equivalence classes
    3. Posets. Ordering relations, partial and total orders, minimal, maximal, least and largest elements, chains and antichains
    4. Induction. Well ordered sets. The Induction Theorem
  3. Congruence modulo n (4hrs)
    1. Arithmetics modulo n. The Remainder lemma, residues modulo n. Addition and multiplication modulo n. Properties of addition and multiplication mod n
    2. Algebraic systems on Zn
  4. Functions (4hrs)
    1. Functions as relations. One-to-one and onto functions. Image and inverse image of a set by a function
    2. Order preserving (increasing) functions. The concept of a fixed point
  5. Combinatorics (6hrs)
    1. Basic combinatorial principles. Newton binomial formula. Pigeon-hole principle
    2. Inclusion-exclusion principle. Number of subsets of a set, number of fixed-size subsets
    3. Enumeration of permutations, number of functions from one set into another
  6. Graphs (4hrs)
    1. Graphs, subgraphs, induced and spanning subgraphs, paths and cycles, connectivity
    2. Menger theorem. Euler theorem. Hamiltonian graphs
    3. Planar graphs, Kuratowski theorem. Coloring of graphs
  7. Generating functions
  8. Recurrence relation. Recursive equations. Recursive methods in enumeration