CISC 102/3.0 Discrete Mathematics for Computing I
Author: Bob Tennent
Last Revised: September 30, 2013
Calendar Description
Introduction to mathematical discourse and proof methods. Sets, functions, sequences, and relations. Properties of the integers. Induction. Equivalence relations. Linear and partial orderings.
Learning Hours: 120 (36L;36Lb;48P)
OneWay Exclusion: May not be taken with or after CISC 203/3.0.
This course is a direct prerequisite to
 CISC203/3.0 (Discrete Mathematics for Computing II)
 CISC204/3.0 (Logic in Computing)
and a co or prerequisite to CISC121/3.0.
This course is required in all Computing programs except COMA.
Topics
Introduction to Mathematical Discourse (2 weeks)
 propositions and connectives
 terminology: hypothesis, conclusion, converse, contrapositive
 quantifiers and predicates
 logical implications and equivalences
Sets (2 weeks)
 sets and subsets
 set operations and the laws of set theory
 counting and Venn diagrams
 countable and uncountable sets, orders of infinity
Integers and Induction (3 weeks)
 wellordering
 recursive definitions
 the division algorithm
 the Euclidean GCD algorithm
 the Fundamental Theorem of Arithmetic
Functions (2 weeks)
 Cartesian products and relations
 functions: 1to1 and onto, bijections
 inverses and composition
Relations (2 weeks)
 equivalence relations and partitions
 linear and partial orderings
Possible Textbooks
 G. Pace: Mathematics of Discrete Structures for Computer Science, Springer, 2012.
 D. Makinson: Sets, Logic and Maths for Computing, Springer, 2nd ed. 2012.
 K. Devlin: Sets Functions and Logic, An introduction to abstract mathematics, Chapman Hall/CRC, 3rd ed., 2004.
 E. D.Bloch: Proofs and Fundamentals, A First Course in Abstract Mathematics, Springer 2011.
 S. Lipschutz: Discrete Mathematics, Schaum's Outline Series, McGrawHill, 3rd ed., 2007
 S. Epp: Discrete Mathematics with Applications, BrooksCole, PWS/ITP, 4th ed., 2011.
 M. Piff: Discrete Mathematics, an Introduction for Software Engineers, Cambridge University Press, 1991.
 J. Truss: Discrete Mathematics for Computer Scientists, Pearson, 2nd edition, 1999.
