CISC 102/3.0 Discrete Mathematics for Computing I
Author: Bob Tennent
Last Revised: September 30, 2013
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)
One-Way Exclusion: May not be taken with or after CISC 203/3.0.
This course is a direct prerequisite to
- CISC-203/3.0 (Discrete Mathematics for Computing II)
- CISC-204/3.0 (Logic in Computing)
and a co- or pre-requisite to CISC-121/3.0.
This course is required in all Computing programs except COMA.
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)
- recursive definitions
- the division algorithm
- the Euclidean GCD algorithm
- the Fundamental Theorem of Arithmetic
Functions (2 weeks)
- Cartesian products and relations
- functions: 1-to-1 and onto, bijections
- inverses and composition
Relations (2 weeks)
- equivalence relations and partitions
- linear and partial orderings
- 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, McGraw-Hill, 3rd ed., 2007
- S. Epp: Discrete Mathematics with Applications, Brooks-Cole, 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.