Course Syllabus
This syllabus outlines the modules of Discrete Mathematics.
- Equivalence relations and partitions
- partial orders; Hasse diagrams
- chains and antichains; maximal and minimal elements; greatest and least elements
- lattices; complete lattices; distributive and complemented lattices
- direct sum and homomorphisms of lattices
- Principle of inclusion and exclusion
- generalized pigeonhole principle
- permutations and combinations with restrictions
- ordinary and exponential generating functions
- recurrence relations; linear recurrence relations with constant coefficients
- Propositional logic; logical equivalence; tautologies and contradictions; normal forms
- predicate logic: introduction; rules of inference
- mathematical induction and strong induction; recursive definitions
- Boolean algebras; Boolean functions; normal forms; Boolean rings and Karnaugh maps
- algebraic representation of logical structures
- Definition of Graphs; paths, circuits and subgraphs
- induced subgraphs, degree of a vertex, connectivity, planar graphs and their properties
- Trees and simple applications of graphs
- Finite-state machines; automata: elementary introduction
- discrete probability models
- recurrence models in computer science and population problems