## 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)

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.

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)
• well-ordering
• 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
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, 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.