Discrete Mathematics


Course Outline: The Foundations: Logic and Proofs: propositional logic, applications of
propositional logic, propositional equivalences, predicates and quantifiers, nested quantifiers, rules
of inference, introduction to proofs; Basic Structures: Sets, Functions, Sequences, Sums, and
Matrices; Number Theory: The division algorithm, divisibility and the euclidean algorithm, prime
numbers, congruence, applications of congruence; Induction and Recursion: Mathematical
Induction, Recursive Definitions and Structural Induction, Program Correctness; Counting: The
addition and multiplication rules, The principle of Inclusion-Exclusion, The pigeon-hole principle,
permutations, combinations, Generalized Permutations and Combinations, Generating Permutations
and Combinations; Relations and Functions: Symmetry, transitivity, reflexivity, equivalence
classes, congruence, closure of relations, partial orderings; Graphs: Graphs and Graph Models,
Graph Terminology and Special Types of Graphs, Representing Graphs and Graph Isomorphism,
Connectivity, Euler and Hamilton Paths; Trees: Introduction to Trees, Tree Traversal, Spanning
Trees.