Discrete Math

What this covers

• Translating English statements into propositional and predicate logic, including nested quantifiers, negation, and contrapositive vs. converse
• Writing direct, contrapositive, contradiction, and case-based proofs about integers, divisibility, and parity, with attention to what counts as a complete argument
• Mathematical induction and strong induction: choosing the right base case, stating the inductive hypothesis, and using it explicitly in the step
• Counting with the product and sum rules, permutations, combinations, inclusion-exclusion, pigeonhole, and combinatorial identities such as Pascal's rule
• Sets, relations, and functions: equivalence relations and partitions, partial orders, injective/surjective/bijective, and cardinality of infinite sets
• Graphs and trees: adjacency representations, paths and connectivity, Euler and Hamilton circuits, bipartite graphs, spanning trees, and simple graph proofs
• Number theory basics: modular arithmetic, the Euclidean algorithm, gcd, and modular inverses

Where learners get stuck

Negating quantified statements — students turn "for all x, P(x)" into "for all x, not P(x)" instead of "there exists x with not P(x)".

Everyday English negation attaches to the verb, not the quantifier, so the habit transfers incorrectly. It shows up again in proofs by contradiction, where the first line is a negation, so one bad negation ruins the whole proof.

Treating induction as a pattern-checking exercise: verifying n = 1, 2, 3 and concluding the statement is true.

Prior courses rewarded finding patterns in sequences. Students often write an inductive step that never actually invokes the inductive hypothesis, which feels fine because the algebra works out, but the logical structure is missing.

Confusing when order matters and when repetition is allowed in counting problems, so combinations get used where permutations are needed (or arrangements get overcounted).

The formulas look similar and the words in the problem ('choose', 'select', 'arrange') don't map reliably. The fix is building the count as a sequence of decisions and checking whether two different decision paths produce the same outcome.

Assuming a proof about graphs is done after drawing one convincing picture.

Diagrams are how the subject is taught, so a diagram feels like evidence. But a picture is one instance, and arguments about all graphs with n vertices need a general argument — often induction on edges or vertices, or a degree-sum count.

What a session looks like

A session usually starts with you stating the problem or theorem you're stuck on, then talking through your current attempt out loud. The tutor asks what you're assuming and what you're trying to conclude, and pushes back when a step is asserted rather than justified. For proof work, you often build the skeleton verbally — hypothesis, goal, method — before filling in algebra. For counting and graph problems, the tutor will ask you to state the set you're counting or the objects in the graph precisely, since most errors trace back to a vague setup. Notation-heavy work can be worked in parallel on paper while you narrate.

Helpful to know first

• Comfort with high school algebra: manipulating expressions, exponents, and summation of simple series
• Familiarity with function notation and basic set notation, though both are re-developed in the course
• Willingness to write arguments in sentences — no calculus is required, and discrete math is often taken alongside or before Calculus I

Questions

Is discrete math harder than calculus?

It's different rather than uniformly harder. Calculus asks for computation with familiar objects; discrete math asks you to justify claims and to work with definitions you've just met. Students who are comfortable with procedures but new to proof-writing often find the first month of discrete math the steepest part.

Why do computer science majors have to take this?

Logic underlies boolean expressions and program correctness, induction underlies recursion and loop invariants, counting underlies algorithm analysis, graphs underlie networks and data structures, and modular arithmetic underlies hashing and cryptography. The course is the vocabulary for later CS theory classes.

Can the tutor help me tell whether my proof is actually correct?

It can walk through your proof step by step, point out where a step doesn't follow from what came before, flag missing base cases or unused hypotheses, and ask you to justify claims you've asserted. Grading standards vary by instructor, so treat feedback as a check on logical structure rather than a prediction of your mark.

My textbook is Rosen. Can sessions follow it?

Yes — you can name the section or the exercise number and work from it. The tutor works from whatever definitions and notation your course uses, which matters here because conventions differ (for example, whether 0 is a natural number, or how relations are composed).