Discrete Structures I

Statements, implication, and quantified negation

A proposition has a truth value. An implication P implies Q is false only when P holds and Q does not. It does not assert that P actually occurs. Its contrapositive, not Q implies not P, is equivalent; its converse generally is not. Quantifiers require a stated domain. Negating every student submitted a file gives there exists a student who did not submit a file. Negating a statement with several quantifiers flips each quantifier and negates the inner predicate; changing their order can change the claim entirely.

References: COMP 1805 — Fall 2026 course outline · Lehman, Leighton, and Meyer — Mathematics for Computer Science

Sets, functions, injections, and surjections

A set collects distinct elements without order. Prove set equality by showing containment in both directions, or by showing equivalent membership conditions for an arbitrary element. A function assigns each domain element exactly one codomain element. An injection never maps distinct inputs to the same output; a surjection reaches every codomain element; a bijection does both. The codomain matters: f(n) = n + 1 from natural numbers to natural numbers may miss the least element, although the same formula can be surjective onto a smaller chosen codomain.

References: COMP 1805 — Fall 2026 course outline · Lehman, Leighton, and Meyer — Mathematics for Computer Science

Build proofs from definitions

A direct proof begins with the assumptions and derives the required conclusion. Contradiction assumes the claim false and derives an impossibility. A counterexample disproves a universal statement using one permitted instance. In a proof by cases, ensure the cases cover all possibilities. To prove that the sum of two even integers is even, write them as 2a and 2b for integers a and b; their sum is 2(a+b), and a+b is an integer. Naming the witnesses converts an intuition into a checkable argument.

References: COMP 1805 — Fall 2026 course outline · Lehman, Leighton, and Meyer — Mathematics for Computer Science

Induction, recursive definitions, and invariants

Induction proves a statement for all integers from a starting point. Verify the base case, assume the statement at an arbitrary valid k, and derive it at k+1. For 1 + ... + n = n(n+1)/2, the step adds k+1 to k(k+1)/2 and factors the result into (k+1)(k+2)/2. The hypothesis is available only within its stated range. Strong induction permits all smaller cases when a recurrence depends on several. A loop invariant uses related reasoning: establish it, preserve it, and combine it with termination.

References: COMP 1805 — Fall 2026 course outline · Lehman, Leighton, and Meyer — Mathematics for Computer Science

Graphs, relations, trees, and orders

A relation on a set is a collection of ordered pairs. Check reflexivity, symmetry, antisymmetry, and transitivity separately; symmetry and antisymmetry are different conditions. An equivalence relation partitions elements into classes. A partial order describes consistent precedence even when some pairs are incomparable. A directed acyclic graph admits a topological ordering. An undirected connected graph with no cycles is a tree; between any two vertices there is exactly one simple path. Draw small examples when testing a definition, but use a general argument to establish a universal claim.

References: COMP 1805 — Fall 2026 course outline · Lehman, Leighton, and Meyer — Mathematics for Computer Science

Asymptotic bounds and a worked sum

Big-O gives an eventual upper bound up to a constant factor; Big-Omega gives a lower bound; Big-Theta gives both. State the input-size variable and counted operation. A loop that runs i times for each i from 1 through n performs n(n+1)/2 inner iterations, which is Theta(n squared). Dropping constants describes growth, not exact runtime on small inputs. A logarithmic number of halvings follows because after k steps the remaining scale is n/2^k. Relate algebraic bounds to the program structure rather than memorizing complexity labels.

References: COMP 1805 — Fall 2026 course outline · Lehman, Leighton, and Meyer — Mathematics for Computer Science

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• COMP 1805 — Fall 2026 course outline ↗Course scope · Fall 2026
• Lehman, Leighton, and Meyer — Mathematics for Computer Science ↗Open textbook · 2018