INTRODUCTION TO DISCRETE MATHEMATICS

MiNI PW | Main page | EIDM

1. Propositions
2. Quantifiers
3. Relations
4. Equivalence and Ordering relations
5. Functions
6. Wellorders, Induction
7. Groups, sup, inf
8. Fixed-point, combinatorics - introduction
9. Permutations, subsets
10. Stars and bars
11. Inclusion-exclusion, Pigeon-hole
12. Eulerian_Hamiltonian
13. Hamiltonian graphs, Trees
14. Bipartite, Coloring, Planar

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 Z_n
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