Study Guide for the Discrete Mathematics Comprehensive Exam

Coordinator: William Shoaff, .


Boolean Algebras
  • Example Algebras: Logic Gates, Propositions, Power Set of a Set
  • Defining Properties of a Boolean Algebra
  • Duality Principle
  • Permutations
  • Combinations
  • Pigeonhole Principle
  • The Inclusion-Exclusion Rule
  • The Product Rule for Counting
  • The Sum Rule for Counting
  • Common Functions: Logarithms, Exponentials, Polynomials, Floor and Ceiling, etc.
  • Composition of Functions
  • Inverses of Functions
  • One-to-one Functions
  • Onto Functions
  • Rates of Growth: Big-O Big-Omega, Big-Theta
  • Connectivity
  • Directed and Undirected Graphs
  • Euler and Hamilton Paths
  • Graph Coloring
  • Graph Isomorphisms
  • Planar Graphs
  • Weighted Graphs
  • Propositional Logic
  • Logical Connectives: AND, OR, NOT, IMPLIES, XOR, NAND, etc.,
  • Truth Tables
  • Validity
  • Predicate Logic
  • Quantifiers
Proof Techniques
  • Rules of Inference, e.g., Modus Ponens and Modus Tollens
  • Direct Proofs
  • Proofs by Counterexample
  • Proof by Contradiction
  • Proofs by Mathematical Induction
  • Recursive Definitions
  • Recurrence Equations
  • Antisymmetry
  • Equivalence Relations
  • Orders: Partial, Total, Strict, Hasse Diagrams
  • Reflexivity
  • Representation as Graphs
  • Symmetry
  • Transitivity
  • Cardinality
  • Cartesian Products
  • Countable and Uncountable Sets
  • The Power Set of a Set
  • Set Operations: Union, Intersection, Complement
  • Venn diagrams
  • Arithmetic Summations
  • Geometric Summations
  • Summations Involving Common Numbers: Harmonic Numbers, Binomial Coefficients
  • Binary and n-ary Trees
  • Tree Traversals
  • Spanning Trees
  1. A Course On Mathematics For Computing,
    William Shoaff
  2. Discrete Mathematics and Its Applications,
    Kenneth H. Rosen, 5th Edition,
    McGraw-Hill, ISBN 0-07-242434-6,
  3. A Short Course in Discrete Mathematics
    by Edward A. Bender and S. Gill Williamson,
    Dover, ISBN 0-486-43946-1.
  4. Mathematics for Algorithm and Systems Analysis
    by Edward A. Bender and S. Gill Williamson,
    Dover, ISBN 0-486-44250-0.
  5. Schaum's Easy Outlines: Discrete Mathematics,
    Seymour Lipschutz and Marc Lipson,
    McGraw-Hill, ISBN, 0-07-139877-5