Discrete Structures
Basic Set Theory
- Functions
- surjections and injections
- inverse
- composition of functions
- Relations
- reflexivity, symmetry, transitivity
- equivalence relations
- Sets
- Definitions, notation, Venn Diagrams
- Operators on sets
- Union
- Intersection
- Complement
- Power sets
- Cartesian products
- Cardinality and countability
- finite sets
- countably infinite sets
- uncountable sets
- Well orderings
Mathematical (or Computational) logic
- Propositional logic
- Logical connectives
- Boolean functions and formulae
- Truth tables
- Normal forms (e.g., conjunctive and disjunctive)
- Valid, satisfiable, unsatisfiable formulas
- Predicate logic
- Universal and existential quantification
- Limitations of predicate logic
- Modal logic
- Model theory
- Lambda calculus
- Automated deduction
- Automated verification
- Nonmonotonic reasoning
- Logic Programming
- Descriptive Complexity
- Logics of uncertainty
- Proof Theory
- Term rewriting systems
- Constraint programming
Proof techniques
- Notions of implication, converse, inverse, contrapositive, negation, and contradiction
- The structure of formal proofs
- Direct proofs
- Modus ponens and modus tollens
- Proof by counterexample
- Proof by contraposition
- Proof by contradiction
- Mathematical induction
- strong induction
- weak induction
- induction on things other than integers
Recursive mathematical definitions
Combinatorics
- Counting arguments
- The pigeonhole principle
- Permutations and combinations
- Solving recurrence relations
- Generating functions
Graphs and trees
- Trees
- Undirected graphs
- Directed graphs
- Hypergraphs
- Spanning trees
- Traversal strategies
Discrete probability
- Finite probability space, probability measure, events
- Probability measure
- Events
- (Discrete) Random variables
- Expectation
- Conditional probability
- Independences
- Bayes Theorem
to top