Discrete Mathematics for Information Technology (MATH134)
Sets, operations on sets. Relations and Functions. Boolean functions, digital logic gates, minterm and maxterm expansions. The basic theorems of Boolean algebra. Simplification of Boolean functions using Karnaugh maps. Mathematical induction. Solving recurrence relations, the characteristic polynomial. The principle of Inclusion-Exclusion. The addition and multiplication rules. The Pigeonhole Principle. Permutations, combinations. Derangements. The Binomial Theorem. Basic definitions and properties of graphs. Isomorphism, Eulerian circuits, Hamiltonian circuits, the adjacency matrix. Trees and their properties, spanning trees, minimum spanning trees. Kruskal’s and Prim’s algorithms.