Topic outline

  • General

    Discrete Mathematics

    Fall 2017-2018

    Discrete mathematics is no more about mathematics than astronomy is about telescopes. 

  • Sets and Relations

    Sets: equality of sets, the empty set, subsets, the power set. Operations on sets: complement of a set, union, intersection, set difference and symmetric difference of the sets, proof by Venn diagram, Cartesian product of sets.

    Relations: binary relation, properties of binary relations, higher-order relations, equivalence relations, equivalence classes, partition of a set, partial orders, posets, minimum, maximum, minimal and maximal elements, Hasse diagram.

    • Functions

      Functions: domain and range of a function, the identity function, one-to-one, onto and one-to-one correspondence functions, some discrete and real variable examples, inverse function, composition of functions.

      • Propositional Calculus and Boolean Algebra

        Propositional Calculus: atomic and compound propositions, well-formed propositions, theorem and contradiction, proof by truth table.

        Boolean Algebra: basic boolean functions, digital logic gates, equivalence between logic circuits, minterm  and maxterm expansions, simplified notation for the gates (accepter and rejecter), basic theorems of boolean algebra, simplifying boolean functions with Karnaugh maps.

        • Induction and Recursion

          Induction: the principle of mathematical induction (weak and strong forms).

          Recursion: some special sequences (arithmetic and geometric sequences), 1st and 2nd order recurrence relations, solving homogeneous recurrence relations, the characteristic polynomial.

          • Principles of Counting

            Principles of Counting: the principle of inclusion-exclusion, the addition and multiplication rules, the pigeonhole principle (weak and strong forms).

            • Permutations and Combinations

              Permutations and Combinations: permutations and r-permutations, r-combinations, binomial coefficients, repetitions, derangements, the binomial theorem, Pascal's triangle.

              • Graphs

                Graphs: terminology and basic properties, degree of a vertex, subgraphs, pseudographs, connected graphs, bipartite graphs, complete and complete bipartite graphs, Euler's proposition on sum of the degrees, isomorphism, Eulerian pseudographs, the theorems on Eulerian circuits and Eulerian trails, Hamiltonian cycles, adjacency matrix.

                • Trees

                  Trees: trees and their properties, spanning trees, minimum spanning trees, Kruskal's algorithm, Prim's algorithm.