University Discrete Math Worksheets

Which sets match your course code

University Discrete Math is not one course with one number. The material is split across different courses in the public calendars of Montreal universities, and each orders and weights it its own way. Find your code below for the sets that cover its material, then check your own outline for what your exam includes.

• COMP 232 — Propositional and Predicate Logic, Methods of Proof, Sets, Functions and Relations, Induction and Recursion
• INF1132 — Propositional and Predicate Logic, Methods of Proof, Sets, Functions and Relations, Divisibility and Primes, Induction and Recursion, Recurrence Relations and Advanced Counting, Graphs and Trees
• MAT1500 — Propositional and Predicate Logic, Methods of Proof, Sets, Functions and Relations, Counting Techniques, Recurrence Relations and Advanced Counting, Graphs and Trees
• MAT210 — Propositional and Predicate Logic, Methods of Proof, Sets, Functions and Relations, Divisibility and Primes, Modular Arithmetic and Cryptography, Induction and Recursion, Counting Techniques, Recurrence Relations and Advanced Counting, Graphs and Trees
• MATH 240 — Methods of Proof, Divisibility and Primes, Modular Arithmetic and Cryptography, Counting Techniques, Recurrence Relations and Advanced Counting, Graphs and Trees

What University Discrete Math covers

This is the course that teaches a mathematics, computer science or engineering student how to write a proof, and it teaches the mathematics of the finite and the countable alongside it. It opens with logic: connectives and truth tables, the conditional with its converse and contrapositive, logical equivalences, predicates and quantifiers, and rules of inference. The proof techniques come next — direct, contraposition, contradiction, cases, if and only if, existence and counterexample — and everything afterwards is proved with them. Sets, functions and relations supply the language: subsets and power sets, set identities, injections, surjections and bijections, equivalence relations, partitions and partial orders.

The middle of the course is number theory, and the end is combinatorics and graphs. The division algorithm, primes, the Euclidean algorithm and Bezout's identity lead into congruences, modular inverses, Fermat's little theorem and RSA encryption, with keys small enough to work by hand. Induction and recursion follow, on summation formulas, divisibility and inequalities, strong induction, recursively defined sequences and the correctness of a recursive algorithm. Counting then runs from the sum and product rules, the pigeonhole principle, permutations and combinations to the binomial theorem and repetition, into recurrence relations and inclusion-exclusion, and the course closes with graphs and trees: degrees and the handshake theorem, adjacency matrices, connectivity, Euler and Hamilton circuits, shortest paths, trees and Euler's formula.

The course stands on Secondary 5 mathematics only — algebraic manipulation and the exponent and logarithm laws are used, not re-taught, and no calculus or linear algebra is needed whatever a calendar lists as a prerequisite. Probability is not part of it: a question asks how many, never how likely, and sample spaces, distributions and expectation belong to University Introductory Statistics. Matrices as objects of study belong to University Linear Algebra; here a matrix is only the adjacency matrix of a graph. Algorithm complexity and big-O notation, Boolean circuits, automata and generating functions are left to the courses that follow. The courses that carry this material at university split it differently — some move counting to a combinatorics course, some teach complexity here, and some reach graphs only if the term allows. The list of course codes on this page says which sets each one covers.