## Study Guide for the Discrete Mathematics Comprehensive Exam

Coordinator: William Shoaff, .

##### Topics:

Boolean Algebras
• Example Algebras: Logic Gates, Propositions, Power Set of a Set
• Defining Properties of a Boolean Algebra
• Duality Principle
Counting
• Permutations
• Combinations
• Pigeonhole Principle
• The Inclusion-Exclusion Rule
• The Product Rule for Counting
• The Sum Rule for Counting
Functions
• 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
Graphs
• Connectivity
• Directed and Undirected Graphs
• Euler and Hamilton Paths
• Graph Coloring
• Graph Isomorphisms
• Planar Graphs
• Weighted Graphs
Logic
• 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
• Proofs by Mathematical Induction
Recursion
• Recursive Definitions
• Recurrence Equations
Relations
• Antisymmetry
• Equivalence Relations
• Orders: Partial, Total, Strict, Hasse Diagrams
• Reflexivity
• Representation as Graphs
• Symmetry
• Transitivity
Sets
• Cardinality
• Cartesian Products
• Countable and Uncountable Sets
• The Power Set of a Set
• Set Operations: Union, Intersection, Complement
• Venn diagrams
Summations
• Arithmetic Summations
• Geometric Summations
• Summations Involving Common Numbers: Harmonic Numbers, Binomial Coefficients
Trees
• Binary and n-ary Trees
• Tree Traversals
• Spanning Trees
##### References:
1. A Course On Mathematics For Computing,
William Shoaff
http://cs.fit.edu/~wds/CourseOnComputing/Material_files/Book.pdf
2. Discrete Mathematics and Its Applications,
Kenneth H. Rosen, 5th Edition,
McGraw-Hill, ISBN 0-07-242434-6,
http://www.mhhe.com/rosen
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