Discrete Math #1 intro
Course Context and Goals
Discrete math vs continuous math: this course is not a calculus course; emphasis on discrete structures and reasoning.
Audience context: most students in data science, with some not in data science; aim is to understand discrete math foundations relevant to CS.
Course aim: characterize what makes this a discrete math course (as opposed to continuous math).
Teaching approach: repetition and interactivity; students should skim the textbook ahead of time, discuss it, and review afterward; the textbook is integrated but access may be limited.
Textbook edition and access notes:
The course is using an eighth edition in slides, but the current textbook edition is ninth; section references may shift between editions.
ECLASS access is not available yet; if you buy a digital copy through ECLASS you may not get it immediately.
Weekly structure and pacing:
Not a traditional lecture this week; more of a flexible pace with a mix of writing and commentary.
The instructor emphasizes that there will be more content in writing than spoken words at times; students should focus on what is written on the board.
The pace may vary; there is an option for recordings to watch later if classes move too fast or if you miss live sessions.
Choose-your-pace philosophy:
The instructor aims to customize learning to individual needs and acknowledges it’s impossible to please everyone with every aspect.
There will be a feedback mechanism at the end of the semester to improve the course.
Course scope and structure:
Plan to cover about 32 lectures for roughly 30 textbook sections; typically one section per lecture, though some sections may be shorter or longer.
The syllabus includes topics across logic, sets, functions, graphs, and other discrete structures.
Course logistics and expectations:
Grading and expectations: an A+ is tied to going beyond the instructor’s expectations; some harder questions might appear on tests.
Students should look ahead to decide how much reading to do before the next week, based on pacing and personal goals.
Real-time feedback and class adaptation:
The instructor uses “choose your own adventure” pacing to keep students engaged.
If students fall behind, focus on the board work and formal notation; if fast, focus on the written material rather than every spoken word.
Notation and Language in Discrete Math
Natural language is ambiguous: even simple phrases like "good morning" can have multiple meanings, motivating the need for formal notation and precise semantics.
Introduction of formal symbols (glimpses of notation):
∧ (wedge) is logical AND
∨ (vee) is logical OR
∀ (for all) is a rotated A (universal quantifier)
∃ (exists) is a backwards E (existential quantifier)
The symbols look unfamiliar at first, and that’s by design to avoid ambiguity.
The importance of precise semantics: to determine truth values, we must agree on the meanings of the symbols and the structure of the statements we’re evaluating.
Communication nuance:
Saying the symbol is not the same as the letter; it’s a mathematical symbol with a specific logical meaning.
Ambiguity examples in language:
A single sentence like "good morning" can have at least four meanings; this motivates the move to a structured logical framework.
Counterexamples and universal statements:
To test a universal claim (e.g., everyone wears black socks), a single counterexample suffices to refute it.
If someone hasn’t spoken up (hasn’t seen the symbols), that can serve as a counterexample to the claim that everyone has seen them; illustrates the role of existence vs universality.
Lecture pacing and engagement:
The instructor emphasizes paying attention to what is written on the board as the most reliable guide to what is true at any moment.
The spoken commentary is valuable, but the formal notation carries the authoritative meaning for proofs and logic.
Ambiguity in everyday language is a common incentive to learn a formal language for mathematics and logic.
From Natural Language to Logic: The First Topic
Logic as the foundation:
The course begins with logic to provide an unambiguous framework for truth, falsehood, and logical relationships.
Motivation for new notation:
The historical motivation is to avoid language ambiguity by adopting precise symbols and rules.
The role of simple examples in teaching:
Everyday phrases and simple statements are used to illustrate how to translate natural language into logical expressions.
Meta-lesson on communication:
The instructor acknowledges the difficulty of balancing speed, clarity, and pace, and encourages students to adapt to their own learning styles.
Objects in Discrete Math: Sets, Functions, and Graphs
Foundational objects will be introduced and studied:
Sets
Functions (a prerequisite for this course)
Graphs (here referred to as combinatorial graphs, not the analytic graphs used in calculus)
Relationships between these objects:
How logic interacts with sets and functions to enable formal reasoning.
Notation and structure:
Students should become comfortable recognizing and using basic constructs in these areas.
Study plan and prerequisites:
If you aren’t from Ontario or another region, you may have different prior exposure; be prepared to catch up on foundational topics.
Graphs in discrete math:
The term graph here refers to combinatorial graphs, which connect to pictures and abstract representations rather than plotted curves.
The Multiplication Table: A Case Study in Pattern Recognition and Summation
A concrete problem: summing all entries of a multiplication table up to 9×9 (and including 0 row/column to make a 10×10 table):
The total number of entries is 100; zeros appear in the 0 row and/or 0 column; there are 19 zeros, leaving 81 nonzero entries.
Each nonzero entry is i×j with i, j ∈ {1, 2, …, 9} (or including 0, depending on indexing).
A brute-force approach is straightforward but tedious: adding 81 nonzero numbers by hand is error-prone.
A more clever approach uses patterns and arithmetic:
Observe that the sum of all entries can be computed by summing rows and columns via distributive properties.
Let S be the sum of all entries; then S = (
sum{i=1}^{9} i) × ( sum{j=1}^{9} j) = 45 × 45 = 2025.This relies on the fact that the sum over a product of independent indices factorizes:
From the transcript: sum of 1 through 9 is 45; thus the total sum is 2025.
Worked values and specific numbers mentioned:
45 × 45 = 2025 (the current year was playfully connected to this number).
For a 12×12 table, the sum of all entries is (sum_{i=1}^{12} i)^2 = 78^2 = 6084.
The identity extends to any n×n multiplication table:
ext{Sum} = igg( rac{n(n+1)}{2}igg)^2.
The Python/algorithmic note:
A sample algorithm to compute the sum programmatically:
This demonstrates that a simple double loop computes the same result as the closed-form pattern.
The broader lesson:
Many discrete problems that look brute-force at first can be solved by recognizing algebraic patterns and exploiting properties like independence and distributivity.
Additional observations:
The instructor uses a familiar context (multiplication tables) to illustrate how to identify patterns and avoid tedious calculations.
The discussion includes some practical prompts about choosing the right abstraction (e.g., moving from a single table to a general n×n framework).
Pattern-related terminology:
Ellipses (dots) indicate continuation of a pattern: use them only when the underlying pattern is evident and agreed upon by the audience.
Ellipsis helps avoid hand cramping when listing many similar terms.
Distributive law intuition in this context:
The sum over a product can be reorganized to separate the independent sums:
For the 9×9 (or 0..9 indexing) case, this principle yields the same total 2025.
The Gauss Trick: Summing the First N Natural Numbers
Classic anecdote: Gauss’s story of summing 1 through 100 quickly by pairing terms (1+100, 2+99, etc.)
Generalization to all n:
The sum of the first n natural numbers is
Example values:
For n = 100, the sum is 5050.
This formula can be derived by pairing terms from opposite ends of the sequence, or via induction, or via a combinatorial argument.
Relevance to the course:
Demonstrates turning a specific problem into a general, closed-form expression, a commonDiscrete Math technique.
Patterns, Notation, and the Role of Ellipses in Writing
Ellipses and shorthand:
Ellipses (the pattern of dots) indicate continuation of a pattern once the rule is clear.
They should be used only when the obvious pattern is understood by the audience.
Linking pattern to algebraic closure:
Recognizing the pattern allows you to write a concise expression instead of enumerating all terms.
The broader message about notation:
You will encounter many symbols and notations; early exposure helps you learn to read and apply them without ambiguity.
Real-World Relevance and Practical Implications
The connection to computation:
Even for a seemingly simple counting problem, there is an elegant closed-form solution that saves time and reduces error.
Programming can implement the same idea succinctly with