Mathematical Foundations of Computer Science


In preparation for the examination, you may wish to review the following textbooks.

  1. Mathematics for Computer Science by E. Lehman, F.T. Leighton and A.R. Meyer (
  2. Lecture Notes on Mathematical Logic by Vladimir Lifschitz (
  3. Probability course notes by Richard Weber (

Course Content


  • Set Theory: Sets, relations and functions, composition, inversion
  • Algebra of sets and Boolean relations 
  • Induction and recursion, and recurrence relations
  • Structural inductions, inductive definitions
  • Recurrence Relations and Generating Functions
  • Number Theory

Mathematical Logic:

  • Propositional logic (syntax and semantics; transforming English specification into logical statements and creating proofs; consistence and completeness w/out proofs)
  • Predicate logic w/examples (syntax and semantics; transforming English specification into logical statements; consistence and completeness w/out proofs)
  • Practice/problem solving by proving theorems/finding counterexamples; hand vs. mechanized proofs and counterexamples; theorem proving vs. model checking
  • Practice with computing applications

Probability Theory:

  • Sample spaces, probability, random variables (discrete)
  • Continuous sample spaces. Probability density.
  • Joint, marginal, and conditional probabilities
  • The rules of probability: Sum and product rules
  • Bayes' theorem
  • Independence of random variables
  • Expectations. Mean, Variance, and Covariance
  • Biased and unbiased estimators
  • Univariate and multivariate Gaussian distributions
  • Other important distributions: Poisson, Exponential, Bernoulli, Binomial, Multinomial; Exponential family of distributions.
  • Maximum likelihood estimation
  • Bayesian inference (e.g. for the Gaussian)
  •  Examples of applications in Computer Science
  • Probabilistic reasoning