MAT3003
Introduction to the mathematics of discrete structures with emphasis on structures for computer science.
Catalog entry
Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.
Contents: (1) Propositional logic: Axioms and Rules of Inference. Limitations of propositional logic: Informal introduction to quantifiers and syllogisms. (2) Predicate Logic: Existential and universal quantification, free variables and substitutions. Discussion of the various axiomatic systems for firstorder logic (including axioms and rules of inference). The power and the limitations of axiomatic systems for logic: Informal discussion of the completeness and incompleteness theorems. (3) Sets and boolean algebras: Operations on sets. Correspondence between finitary set operations and propositional logic. Correspondence between infinitary operations and quantifiers. The power and limitations of the language of set theory: Informal discussion of the settheoretic paradoxes and the need for axiomatic systems for set theory. (4) Relations: Special relations: Equivalence relations, partially ordered sets, maximum/minimum, maximal/minimal elements, least upper bounds and greatest lower bounds, totally ordered sets. (5) Functions: Operations of functions, direct image and inverse image. (6) Wellordered sets: Correspondence between wellordering relations and induction. Correspondence between wellordering relations and choice functions. (7) Introduction to computability. Classical models of computation (recursive functions, and Turing models). Limitations of computation (the Halting Problem, fastgrowing functions). Contemporary models of computation.
Sample textbooks:
[1] Gordon Pace, Mathematics of Discrete Structures foe Computer Science, Springer, 2012
[2] Vladlen Koltun, Discrete Structures Lecture Notes, Stanford University, 2008. Freely available here.
Topics List
Week  Topic  Sections from Pace's book  Sections from Pace's book  Prerequisites.  

1  Propositional logic  2.12.4 

MAT1313 or CS2233/2231, or equivalent.  
2  Completeness and soundness  2.5 


56  Predicate calculus  3.13.5 


7  Sets and boolean algebras  4.14.5 


8  Sets and boolean algebras  4.6 


9  Relations  5.15.7 


10  Classifying Relations  6.16.3 


1112  Discrete structures  7.18.4 


1314  Reasoning about programs  10.110.4 
