ECE 108: Discrete Mathematics and Logic 1

Sources and References

Equivalent UW courses — MATH 135 (Algebra), CS 245 (Logic and Computation), MATH 145 (Honours Algebra) Primary textbook — Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019. Supplementary references — Susanna S. Epp, Discrete Mathematics with Applications, 5th ed., Cengage, 2019; Huth and Ryan, Logic in Computer Science: Modelling and Reasoning about Systems, 2nd ed., Cambridge, 2004.

Equivalent UW Courses

ECE 108 is the Electrical and Computer Engineering department’s first discrete-math course, and it sits at the intersection of three Math/CS offerings. The proof-based algebra, sets, and induction portion corresponds most closely to MATH 135, which all Math and Software Engineering students take in first term; students in the Pure-Math stream take the honours version MATH 145 with more abstract content. The propositional and predicate logic material — syntax, semantics, formal proof, soundness hinted at — overlaps directly with CS 245, which CS majors normally take in second year. Graph theory and counting show up in both MATH 239 and CO 227 at the more advanced level. Roughly, ECE 108 ≈ (MATH 135 proof half) + (CS 245 logic half) + introductory combinatorics and graph theory.

What This Course Adds Beyond the Equivalents

ECE 108 is unusual among introductory courses because it puts formal proof theory front and center from week one: students are expected to write natural-deduction-style proofs in propositional and predicate logic before moving to set theory. That emphasis on formal derivations is closer to CS 245 than to MATH 135, which leans more on informal mathematical proofs (divisibility, GCD, number theory). ECE 108 also directly ties the logic content to engineering applications — specification of digital circuits, Boolean algebra, and reasoning about programs — which neither MATH 135 nor CS 245 do as directly.

What ECE 108 omits relative to the equivalents: no systematic number theory (modular arithmetic, Euclidean algorithm, CRT, RSA) the way MATH 135 has it, no group/ring theory from MATH 145, no computability or program-semantics from the tail end of CS 245, and only a brief introduction to combinatorics and discrete probability compared with MATH 239/STAT 230.

Topic Summary

Propositional Logic

Syntax of propositional formulas, truth-value semantics, logical equivalence, and tautology/contradiction/contingency. Formal proof in a natural-deduction or sequent-calculus style, including introduction and elimination rules for \( \land, \lor, \to, \lnot \). Covered in weeks 1–2.

Predicate (First-Order) Logic

Quantifiers \( \forall \) and \( \exists \), free vs. bound variables, substitution, and interpretations over domains. Formal proof rules for quantifier introduction and elimination. The statement

\[ \forall x\,(P(x) \to Q(x)) \;\land\; \exists x\,P(x) \;\vdash\; \exists x\,Q(x) \]

is the kind of entailment students prove from scratch. Weeks 3–4.

Proof Techniques and Induction

Case analysis, direct vs. contrapositive vs. contradiction proof, and mathematical induction (weak and strong). Structural induction on lists and other recursively defined data. Students prove properties of list functions — a flavor borrowed from functional programming rather than classical MATH 135.

Sets, Functions, and Relations

Set operations, set-builder notation, power sets, and proofs of set identities. Functions as relations, injective/surjective/bijective, inverses, and composition. Equivalence relations, partitions, and partial orders.

Graph Theory

Simple graphs, paths and cycles, connectivity, trees, and basic graph algorithms at an introductory level. Handshake lemma, Eulerian and Hamiltonian circuits, and graph coloring as motivating examples.

Combinatorics

Basic counting principles: product and sum rules, permutations and combinations, binomial coefficients, and Pascal’s identity. Inclusion–exclusion and pigeonhole. Weeks 9–10.

Discrete Probability

Sample spaces, events, and uniform-probability counting problems. Conditional probability, independence, and expected value of discrete random variables. A gentle introduction so later ECE probability courses (ECE 316) can assume baseline familiarity. Weeks 11–12.