## INTRODUCTION TO DISCRETE MATHEMATICS

MiNI PW | Main page | Lecture notes | EIDM

### COURSE CONTENTS

- Introduction (4hrs)
- Propositions, propositional calculus, tautologies
- Propositional functions and quantifiers
- Sets, operations on sets, generalized union and intersection of sets

- Relations (6hrs)
- Cartesian product of sets. Relations as subsets of the Cartesian product of sets
- Equivalence relations, equivalence classes
- Posets. Ordering relations, partial and total orders, minimal, maximal, least and largest elements, chains and antichains
- Induction. Well ordered sets. The Induction Theorem

- Congruence
*modulo n* (4hrs)
- Arithmetics modulo n. The Remainder lemma, residues modulo n. Addition and multiplication modulo n. Properties of addition and multiplication mod n
- Algebraic systems on
**Z**_{n}

- Functions (4hrs)
- Functions as relations. One-to-one and onto functions. Image and inverse image of a set by a function
- Order preserving (increasing) functions. The concept of a fixed point

- Combinatorics (6hrs)
- Basic combinatorial principles. Newton binomial formula. Pigeon-hole principle
- Inclusion-exclusion principle. Number of subsets of a set, number of fixed-size subsets
- Enumeration of permutations, number of functions from one set into another

- Graphs (4hrs)
- Graphs, subgraphs, induced and spanning subgraphs, paths and cycles, connectivity
- Menger theorem. Euler theorem. Hamiltonian graphs
- Planar graphs, Kuratowski theorem. Coloring of graphs

- Generating functions
- Recurrence relation. Recursive equations. Recursive methods in enumeration