• • Definitions, notation, Venn Diagrams
  • Operators on sets
    • Union
    • Intersection
    • Complement

• • • Cartesian products

• • Boolean functions and formulae

• • Limitations of predicate logic

• Model theory
  • Finite model theory
• Lambda calculus
• Automated deduction
• Automated verification

• Nonmonotonic reasoning
• Logic Programming
• Descriptive Complexity

• Constraint programming

• • strong induction

Discrete Structures

• Sets
  • Definitions and notation

• • The algebra of sets
  • Venn diagrams
  • Enumeration
    • permutation
    • combination

Functions, relations, and sets

• Functions
  • surjections and injections
  • inverse
  • composition of functions
• Relations * reflexivity, symmetry, transitivity
  • equivalence relations
• Sets (Venn diagrams, complements, Cartesian products, power sets)
  • Venn diagrams
  • Union, interesection, complement
  • Power sets
  • Cartesion products
• Cardinality and countability
  • finite sets
  • countably infinite sets
  • uncountable sets
• Well orderings

Mathematical (or Computational) logic

• Set theory
• Propositional logic
  • Logical connectives
  • Truth tables
  • Normal forms (e.g., conjunctive and disjunctive)
  • Valid, satisfiable, unsatisfiable formulas
• Predicate logic
  • Universal and existential quantification
• Limitations of predicate logic (Relates to AI)
• Modal logic
• Temporal logic
• Model checking
• Finite Model Theory
• Model thoery
  • finite model theory
• proof theory
• Lambda calculus (OR in Prog. Languages)
• Automated deduction (could be in AI)
• Automated verification (could be in Software Engineering)
• Nonmonotonic reasoning (Could be in AI)
• Logic Programming (Probably belongs in AI)
• Descriptive Complexity (or move to be with computational complexity)
• Logics of uncertainty
  • Fuzzy logic
• Proof Theory
• Term rewriting systems
• Constraint programming (probably belongs someplace else)

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 (small topic, not a research area, belongs in CS undergrad teaching)

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
• Pseudo random numbers and their generation (could be elsewhere like algorithms)