Discrete Mathematics I (Math 131)
Virginia Intermont College

Jason Riedy

Fall semester, 2008

These pages are available as PDF, either as one growing PDF document for the entirety or as individual documents for each session’s notes.

If you have difficulties viewing these or have particular accessibility needs, please mail me at jason@acm.org.

Contents
I  Introduction
1 Syllabus
 1.1 Discrete Mathematics I
 1.2 Goals
 1.3 Instructor: Jason Riedy
 1.4 Text
 1.5 Grading
 1.6 On homework
 1.7 Submitting homework
2 Syllabus schedule
II  Notes for chapters 1, 2, and 3
3 Notes for 18 August
 3.1 Syllabus and class mechanics
 3.2 Introductions
 3.3 Inductive and deductive reasoning
 3.4 Inductive
 3.5 Deductive
4 Notes for 20 August
 4.1 Review: Inductive and deductive reasoning
 4.2 Inductive reasoning on sequences
 4.3 A tool for sequences: successive differences
 4.4 Successive differences are not useful for everything.
 4.5 An application where successive differences work, amazingly.
 4.6 Next time: Problem solving techniques.
 4.7 Homework
5 Notes for 22 August
 5.1 The problem solving section is important enough for a full class
 5.2 Review successive differences: a tool for inductive reasoning on sequences
 5.3 Moving from a table to a formula
 5.4 Starting point
 5.5 The plan for deriving a formula
 5.6 The derivation
 5.7 Homework
6 Solutions for first week’s assignments
 6.1 Notes on received homeworks
 6.2 Exercises for Section 1.1
 6.3 Explain the “trick” of Section 1.1’s example
 6.4 Exercises for Section 1.2
7 Notes for 25 August
 7.1 Problem solving principles
 7.2 Making a lists and tables
 7.3 Searching by guessing
 7.4 Understanding dependencies, or ”working backward”
 7.5 Next time: more techniques
 7.6 Homework
8 Notes for 27 August
 8.1 Review: Pólya’s problem-solving principles
 8.2 Effective trial and error by bisection
 8.3 Simpler sub-problems for finding patterns
 8.4 Other sources for tactics and examples
 8.5 Next time: Reading graphs and charts
 8.6 Homework
9 Notes for 29 August
 9.1 Review: Pólya’s problem-solving principles
 9.2 Notes on the homework
 9.3 Reading graphs: delayed until Monday (or later)
 9.4 Homework
10 Solutions for second week’s assignments
 10.1 Exercises for Section 1.3
 10.2 Making change
 10.3 Writing out problems
 10.4 Computing with numbers
11 Notes for reading graphs
 11.1 Reading graphs
 11.2 Creating a graphical depiction of data
 11.3 Graph galleries and resources
12 Homework for reading graphs
 12.1 Homework
13 Notes for the third week: set theory
 13.1 Language of set theory
 13.2 Basic definitions
 13.3 Translating sets into (and from) English
 13.4 Relations
 13.5 Translating relations into (and from) English
 13.6 Consequences of the set relation definitions
 13.7 Visualizing two or three sets: Venn diagrams
 13.8 Operations
 13.9 Translating operations into English
 13.10 Special operations
 13.11 Cardinality and the power set
14 Homework for the third week: set theory
 14.1 Homework
15 Solutions for third week’s assignments
 15.1 Section 1.4, problem 54
 15.2 Section 2.1
 15.3 Section 2.2
 15.4 Section 2.3
III  Notes for chapters 4, 5, and 6
16 Notes for the fourth week: symbolic logic
 16.1 Language of logic
 16.2 Symbolic logic
 16.3 Logical operators and truth tables
 16.4 Properties of logical operators
 16.5 Truth tables and logical expressions
 16.6 Conditionals
 16.7 Quantifiers
 16.8 Logical deduction: Delayed until after the test
17 Homework for the fourth week: symbolic logic
 17.1 Homework
18 Solutions for fourth week’s assignments
 18.1 Section 3.1
 18.2 Section 3.2
 18.3 Section 3.3
 18.4 Section 3.4
 18.5 Section 3.1 again
 18.6 Negating statements
 18.7 Function from truth table
19 Notes for the fifth week: review
 19.1 Review
 19.2 Inductive and deductive reasoning
 19.3 Problem solving
 19.4 Sequences
 19.5 Set theory
 19.6 Symbolic logic
20 First exam and solutions
21 Notes for the sixth week: numbers and computing
 21.1 Positional Numbers
 21.2 Converting Between Bases
 21.3 Operating on Numbers
 21.4 Computing with Circuits
22 Homework for the sixth week: numbers and computing
 22.1 Homework
23 Solutions for sixth week’s assignments
 23.1 Section 4.1, problems 35 and 36
 23.2 Section 4.2
 23.3 Section 4.3
 23.4 Positional form
 23.5 Operations
24 Notes for the seventh week: primes, factorization, and modular arithmetic
 24.1 Divisibility
 24.2 Primes
 24.3 Factorization
 24.4 Modular Arithmetic
 24.5 Divisibility Rules
25 Homework for the seventh week: primes, factorization, and modular arithmetic
 25.1 Homework
26 Solutions for seventh week’s assignments
 26.1 Section 5.1 (prime numbers)
 26.2 Section 5.1 (factorization)
 26.3 Section 5.4 (modular arithmetic)
 26.4 Section 5.1 (divisibility rules)
27 Notes for the eighth week: GCD, LCM, ax + by = c
 27.1 Modular arithmetic
 27.2 Divisibility rules
 27.3 Greatest common divisor
 27.4 Least common multiple
 27.5 Euclidean GCD algorithm
 27.6 Linear Diophantine equations : Likely delayed
28 Homework for the eighth week: GCD, LCM, ax + by = c
 28.1 Homework
29 Solutions for eighth week’s assignments
 29.1 Exercises 5.3
 29.2 Computing GCDs
 29.3 Computing LCMs
30 Notes for the ninth week: ax + by = c and fractions
 30.1 Linear Diophantine equations
 30.2 Into real numbers
 30.3 Rational numbers
 30.4 Review of rational arithmetic
 30.5 Complex fractions
31 Homework for the ninth week: ax + by = c and fractions
 31.1 Homework
32 Solutions for ninth week’s assignments
 32.1 Linear Diophantine equations
 32.2 Exercises 6.3
33 Notes for the tenth week: Irrationals and decimals
 33.1 Real numbers
 33.2 Exponents and roots
 33.3 Decimal expansions and percentages
 33.4 Fixed and floating-point arithmetic
34 Homework for the tenth week: Irrationals and decimals
 34.1 Homework
35 Solutions for tenth week’s assignments
 35.1 Exercises 6.4
 35.2 Exercises 6.3
 35.3 Exercises 6.5
 35.4 Rounding and floating-point
36 Second exam and solutions
IV  Notes for chapters 7 and 8
37 Notes for the twelfth week
 37.1 Covered So Far
 37.2 What Will Be Covered
 37.3 An Algebraic Example
 37.4 The Example’s Graphical Side
 37.5 Definitions
 37.6 Algebraic Rules for Transformations Between Equivalent Equations
 37.7 Transformation Examples
 37.8 Manipulating Formulæ by Transformations
38 Homework for the twelfth week
 38.1 Homework
39 Solutions for twelfth week’s assignments
 39.1 Exercises for 7.1
 39.2 Exercises for 7.2
40 Homework for the thirteenth week
 40.1 Homework
41 Solutions for the thirteenth week’s assignments
 41.1 Exercises for 8.2
 41.2 Exercises for 8.3
 41.3 Exercises for 8.7
 41.4 Exercises for 8.8
42 Homework for the fourteenth week
 42.1 Homework
43 Solutions for the fourteenth week’s assignments
 43.1 Exercises for 7.3
 43.2 Exercises for 7.4
 43.3 Exercises for 7.5
 43.4 Exercises for 7.7
 43.5 Exercises for 8.1
 43.6 Exercises for 8.3
 43.7 Exercises for 8.6
 43.8 Exercises for 8.7
 43.9 Exercises for 8.8
44 Third exam, due 1 December
45 Third exam solutions
46 Final exam
V  Resources
47 Math Lab
48 On-line
 48.1 General mathematics education resources
 48.2 Useful software and applications

[next]