Queen's School of Computing

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.