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.6.1 Rephrasing the problem

5.6.2 Expressing the base sequence

5.6.3 Substituting into {Δ}^{(2)} into the expression for {Δ}^{(1)}

5.6.4 Breaking down the complicated expression

5.6.5 Pulling the pieces together

5.6.6 Checking the result

5.7 Homework

6 Solutions for first week’s assignments

6.1 Notes on received homeworks

6.2 Exercises for Section 1.1

6.2.1 Even problems, 2-12

6.3 Explain the “trick” of Section 1.1’s example

6.4 Exercises for Section 1.2

6.4.1 Problems 2, 9, and 10

6.4.2 Problems 14 and 16

6.4.3 Problems 29 and 30

6.4.4 Problems 32, 39, and 51

6.4.5 Problem 49

6.4.6 Problems 51 and 54

7 Notes for 25 August

7.1 Problem solving principles

7.1.1 Pólya’s principles

7.1.2 Understand the problem

7.1.3 Divise a plan

7.1.4 Carry out the plan

7.1.5 Examine your solution

7.2 Making a lists and tables

7.2.1 Example of a table

7.3 Searching by guessing

7.3.1 Example for guessing and checking

7.4 Understanding dependencies, or ”working backward”

7.4.1 Example for following dependencies

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.2.1 Understanding the problem

8.2.2 Forming plans

8.2.3 Carrying out the new plan

8.2.4 Looking back

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.1.1 Problem 6: Understanding

10.1.2 Problem 12: Guessing and checking

10.1.3 Problem 31: Listing

10.1.4 Problem 35: Listing

10.1.5 Problem 28: Following dependencies

10.1.6 Problem 57: Following dependencies

10.1.7 Problem 40: Bisection and guessing a range

10.1.8 Problem 52: Think about bisection

10.1.9 Problem 56

10.1.10 Problem 61: Look for a pattern

10.2 Making change

10.3 Writing out problems

10.3.1 Section 1.2, problem 9

10.3.2 Section 1.2, problem 49

10.3.3 Section 1.3, problem 40

10.4 Computing with numbers

10.4.1 Extra digits from 1∕7

10.4.2 Binary or decimal?

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.8.1 Similarities to arithmetic

13.9 Translating operations into English

13.10 Special operations

13.10.1 Universes and complements

13.10.2 Tuples and cross products

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.2.1 Problems 1-8

15.2.2 Problems 11 and 17

15.2.3 Problems 30 and 32

15.2.4 Problems 62, 63, and 66

15.2.5 Problems 68, 71, 74, and 78

15.2.6 Problem 92

15.3 Section 2.2

15.3.1 Problems 8, 10, 12, 14

15.3.2 Even problems 24-34

15.4 Section 2.3

15.4.1 Problems 1-6

15.4.2 Problems 10, 17, 18, 23, 24

15.4.3 Problem 31

15.4.4 Problem 33

15.4.5 Problems 61, 62

15.4.6 Problems 72, 73

15.4.7 Problems 117, 118, 121-124

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.5.1 De Morgan’s laws

16.5.2 Logical expressions from truth tables

16.6 Conditionals

16.6.1 English and the operator →

16.6.2 Defining p → q

16.6.3 Converse, inverse, and contrapositive

16.6.4 If and only if, or ↔

16.7 Quantifiers

16.7.1 Negating quantifiers

16.7.2 Nesting quantifiers

16.7.3 Combining nesting with negation

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.1.1 Problems 1-5

18.1.2 Problems 40, 42, 44

18.1.3 Problems 49-54

18.2 Section 3.2

18.2.1 Problems 15-18

18.2.2 Problems 37-40

18.2.3 Problems 53-55

18.2.4 Problems 61, 62

18.3 Section 3.3

18.3.1 Problems 1-5

18.3.2 Problems 13, 15, 20

18.3.3 Problems 35-38

18.3.4 Problems 58, 60

18.3.5 Problems 67, 68

18.3.6 Problems 74, 75

18.4 Section 3.4

18.4.1 Problems 1, 3, 6

18.4.2 Problem 51, 57, 58

18.5 Section 3.1 again

18.5.1 Problems 55, 56

18.5.2 Problems 60-64

18.5.3 Problem 75

18.5.4 Problem 76

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.3.1 Understand the problem

19.3.2 Devise a plan

19.3.3 Carry out the plan

19.3.4 Look back at your solution

19.4 Sequences

19.5 Set theory

19.6 Symbolic logic

19.6.1 From truth tables to functions

19.6.2 De Morgan’s laws and forms of conditionals

19.6.3 Quantifiers

19.6.4 Nesting and negating quantifiers

20 First exam and solutions

21 Notes for the sixth week: numbers and computing

21.1 Positional Numbers

21.2 Converting Between Bases

21.2.1 Converting to Decimal

21.2.2 Converting from Decimal

21.3 Operating on Numbers

21.3.1 Multiplication

21.3.2 Addition

21.3.3 Subtraction

21.3.4 Division and Square Root: Later

21.4 Computing with Circuits

21.4.1 Representing Signed Binary Integers

21.4.2 Adding in Binary with Logic

21.4.3 Building from Adders

21.4.4 Decimal Arithmetic from Binary Adders

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.1.1 Problem 80

26.2 Section 5.1 (factorization)

26.3 Section 5.4 (modular arithmetic)

26.3.1 Problems 9-13

26.3.2 Other problems

26.4 Section 5.1 (divisibility rules)

26.4.1 Take a familiar incomplete integer\mathop{\mathop{…}}

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.1.1 In general\mathop{\mathop{…}}

30.1.2 The other example

30.2 Into real numbers

30.2.1 Operator precedence

30.3 Rational numbers

30.4 Review of rational arithmetic

30.4.1 Multiplication and division

30.4.2 Addition and subtraction

30.4.3 Comparing fractions

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.2.1 Positive exponents

33.2.2 Zero exponent

33.2.3 Negative exponents

33.2.4 Rational exponents and roots

33.2.5 Irrational numbers

33.3 Decimal expansions and percentages

33.3.1 Representing rationals with decimals

33.3.2 The repeating decimal expansion may not be unique!

33.3.3 Rationals have terminating or repeating expansions

33.3.4 Therefore, irrationals have non-repeating expansions.

33.3.5 Percentages as rationals and decimals

33.4 Fixed and floating-point arithmetic

33.4.1 Rounding rules

33.4.2 Floating-point representation

33.4.3 Binary fractional parts

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

35.4.1 Rounding

35.4.2 Errors in computations

35.4.3 Extra digits

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

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.6.1 Rephrasing the problem

5.6.2 Expressing the base sequence

5.6.3 Substituting into {Δ}^{(2)} into the expression for {Δ}^{(1)}

5.6.4 Breaking down the complicated expression

5.6.5 Pulling the pieces together

5.6.6 Checking the result

5.7 Homework

6 Solutions for first week’s assignments

6.1 Notes on received homeworks

6.2 Exercises for Section 1.1

6.2.1 Even problems, 2-12

6.3 Explain the “trick” of Section 1.1’s example

6.4 Exercises for Section 1.2

6.4.1 Problems 2, 9, and 10

6.4.2 Problems 14 and 16

6.4.3 Problems 29 and 30

6.4.4 Problems 32, 39, and 51

6.4.5 Problem 49

6.4.6 Problems 51 and 54

7 Notes for 25 August

7.1 Problem solving principles

7.1.1 Pólya’s principles

7.1.2 Understand the problem

7.1.3 Divise a plan

7.1.4 Carry out the plan

7.1.5 Examine your solution

7.2 Making a lists and tables

7.2.1 Example of a table

7.3 Searching by guessing

7.3.1 Example for guessing and checking

7.4 Understanding dependencies, or ”working backward”

7.4.1 Example for following dependencies

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.2.1 Understanding the problem

8.2.2 Forming plans

8.2.3 Carrying out the new plan

8.2.4 Looking back

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.1.1 Problem 6: Understanding

10.1.2 Problem 12: Guessing and checking

10.1.3 Problem 31: Listing

10.1.4 Problem 35: Listing

10.1.5 Problem 28: Following dependencies

10.1.6 Problem 57: Following dependencies

10.1.7 Problem 40: Bisection and guessing a range

10.1.8 Problem 52: Think about bisection

10.1.9 Problem 56

10.1.10 Problem 61: Look for a pattern

10.2 Making change

10.3 Writing out problems

10.3.1 Section 1.2, problem 9

10.3.2 Section 1.2, problem 49

10.3.3 Section 1.3, problem 40

10.4 Computing with numbers

10.4.1 Extra digits from 1∕7

10.4.2 Binary or decimal?

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.8.1 Similarities to arithmetic

13.9 Translating operations into English

13.10 Special operations

13.10.1 Universes and complements

13.10.2 Tuples and cross products

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.2.1 Problems 1-8

15.2.2 Problems 11 and 17

15.2.3 Problems 30 and 32

15.2.4 Problems 62, 63, and 66

15.2.5 Problems 68, 71, 74, and 78

15.2.6 Problem 92

15.3 Section 2.2

15.3.1 Problems 8, 10, 12, 14

15.3.2 Even problems 24-34

15.4 Section 2.3

15.4.1 Problems 1-6

15.4.2 Problems 10, 17, 18, 23, 24

15.4.3 Problem 31

15.4.4 Problem 33

15.4.5 Problems 61, 62

15.4.6 Problems 72, 73

15.4.7 Problems 117, 118, 121-124

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.5.1 De Morgan’s laws

16.5.2 Logical expressions from truth tables

16.6 Conditionals

16.6.1 English and the operator →

16.6.2 Defining p → q

16.6.3 Converse, inverse, and contrapositive

16.6.4 If and only if, or ↔

16.7 Quantifiers

16.7.1 Negating quantifiers

16.7.2 Nesting quantifiers

16.7.3 Combining nesting with negation

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.1.1 Problems 1-5

18.1.2 Problems 40, 42, 44

18.1.3 Problems 49-54

18.2 Section 3.2

18.2.1 Problems 15-18

18.2.2 Problems 37-40

18.2.3 Problems 53-55

18.2.4 Problems 61, 62

18.3 Section 3.3

18.3.1 Problems 1-5

18.3.2 Problems 13, 15, 20

18.3.3 Problems 35-38

18.3.4 Problems 58, 60

18.3.5 Problems 67, 68

18.3.6 Problems 74, 75

18.4 Section 3.4

18.4.1 Problems 1, 3, 6

18.4.2 Problem 51, 57, 58

18.5 Section 3.1 again

18.5.1 Problems 55, 56

18.5.2 Problems 60-64

18.5.3 Problem 75

18.5.4 Problem 76

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.3.1 Understand the problem

19.3.2 Devise a plan

19.3.3 Carry out the plan

19.3.4 Look back at your solution

19.4 Sequences

19.5 Set theory

19.6 Symbolic logic

19.6.1 From truth tables to functions

19.6.2 De Morgan’s laws and forms of conditionals

19.6.3 Quantifiers

19.6.4 Nesting and negating quantifiers

20 First exam and solutions

21 Notes for the sixth week: numbers and computing

21.1 Positional Numbers

21.2 Converting Between Bases

21.2.1 Converting to Decimal

21.2.2 Converting from Decimal

21.3 Operating on Numbers

21.3.1 Multiplication

21.3.2 Addition

21.3.3 Subtraction

21.3.4 Division and Square Root: Later

21.4 Computing with Circuits

21.4.1 Representing Signed Binary Integers

21.4.2 Adding in Binary with Logic

21.4.3 Building from Adders

21.4.4 Decimal Arithmetic from Binary Adders

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.1.1 Problem 80

26.2 Section 5.1 (factorization)

26.3 Section 5.4 (modular arithmetic)

26.3.1 Problems 9-13

26.3.2 Other problems

26.4 Section 5.1 (divisibility rules)

26.4.1 Take a familiar incomplete integer\mathop{\mathop{…}}

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.1.1 In general\mathop{\mathop{…}}

30.1.2 The other example

30.2 Into real numbers

30.2.1 Operator precedence

30.3 Rational numbers

30.4 Review of rational arithmetic

30.4.1 Multiplication and division

30.4.2 Addition and subtraction

30.4.3 Comparing fractions

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.2.1 Positive exponents

33.2.2 Zero exponent

33.2.3 Negative exponents

33.2.4 Rational exponents and roots

33.2.5 Irrational numbers

33.3 Decimal expansions and percentages

33.3.1 Representing rationals with decimals

33.3.2 The repeating decimal expansion may not be unique!

33.3.3 Rationals have terminating or repeating expansions

33.3.4 Therefore, irrationals have non-repeating expansions.

33.3.5 Percentages as rationals and decimals

33.4 Fixed and floating-point arithmetic

33.4.1 Rounding rules

33.4.2 Floating-point representation

33.4.3 Binary fractional parts

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

35.4.1 Rounding

35.4.2 Errors in computations

35.4.3 Extra digits

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