Discrete Mathematics

What this covers

• Translating English statements into propositional and predicate logic, including nested quantifiers, and negating them correctly with De Morgan's laws
• Building direct, contrapositive, contradiction, and case-based proofs, and knowing which shape fits a given claim
• Writing mathematical induction and strong induction proofs with an explicit basis, inductive hypothesis, and inductive step — including summation identities and divisibility claims
• Set operations, power sets, Cartesian products, and proving set identities by double inclusion or membership tables
• Functions and relations: injective/surjective/bijective, equivalence relations and partitions, partial orders and Hasse diagrams
• Counting with the sum and product rules, permutations and combinations, the pigeonhole principle, inclusion-exclusion, and binomial identities
• Modular arithmetic, gcd and the Euclidean algorithm, and graph fundamentals: degree sums, paths, connectivity, trees, and bipartite graphs

Where learners get stuck

Treating 'if P then Q' as if it were false when P is false, so vacuous truths look like errors

Everyday English uses 'if' with an implied causal link and an implied 'if not P, then not Q'. The material conditional has neither, so a statement like 'every element of the empty set is prime' feels wrong even though the truth table makes it true.

Confusing the converse and the contrapositive, and 'proving' a claim by assuming what was to be shown

Both involve swapping P and Q, and students memorise the words rather than checking the truth tables. In induction this shows up as assuming the statement holds for all n instead of assuming it for a single fixed k and deriving k+1.

Reaching for the binomial coefficient whenever the word 'choose' appears, without asking whether order matters or whether items are distinguishable

Introductory counting problems are stated in near-identical language, so students pattern-match on phrasing. Problems with repetition, indistinguishable objects, or an ordered arrangement need stars-and-bars, multinomials, or permutations instead.

Swapping the order of nested quantifiers when translating or negating

English word order hides the difference between 'for every x there is a y' and 'there is a y for every x'; only after writing the negation does the logical gap become visible.

What a session looks like

You bring a problem set, lecture notes, or a topic you are stuck on. The tutor asks you to state the claim in symbols first, then decide on a proof strategy before writing anything, and talks through the structure step by step — what the hypothesis gives you, what you are obliged to produce, where the argument is currently jumping. For counting and graph problems, you are asked to describe the objects being counted or the graph invariant in play. Sessions are spoken, so you practise the verbal reasoning that oral quizzes and office hours demand, and you leave with the proof skeleton to write up yourself.

Helpful to know first

• Comfort with high school algebra: manipulating summations, exponents, factorials, and solving simple equations
• Some programming exposure (loops, recursion, boolean conditions) helps but is not required
• No prior proof-writing experience assumed — proof structure is taught from the ground up
• Familiarity with basic set notation is useful but is reviewed as needed

Questions

Why is discrete math required for a computer science major?

It supplies the vocabulary the later courses assume: induction underlies recursion and loop invariants, graph theory underlies networks and dependency analysis, modular arithmetic underlies hashing and cryptography, and counting underlies complexity and probability arguments. Courses in algorithms typically expect you to already read and write proofs.

I can follow proofs in lecture but freeze on a blank page. Can that be fixed?

That is usually a strategy problem, not a comprehension problem. Sessions focus on the decision you make before writing: identifying the logical form of the claim, choosing between direct, contrapositive, contradiction, and induction, and writing the first and last lines before filling in the middle.

Does this cover the same ground as an algorithms or data structures course?

No. Analysis of specific algorithms and structures belongs to those courses. Here the focus is the mathematics itself — logic, proof technique, sets, relations, counting, graphs, and number theory — though recurrence relations and asymptotic notation overlap where your syllabus includes them.

My textbook is Rosen (or Epp, or Lehman's Mathematics for Computer Science). Does that matter?

You can name your textbook, notation conventions, and where your course is in the sequence, and the session will follow those. Notation for things like relation composition, floor and ceiling, and quantifier scope varies between texts, so it is worth mentioning at the start.