# Math 311w - Concepts of Discrete Mathematics

## Introduction

This is the web page for section 2 of Math 311w taught by Tim Reluga in the autumn of 2021.

This course introduces students to the use of mathematics as a formal language. Using a theorem-proof framework much like that used in Euclid’s geometry textbook millenia ago, we will study elementary number theory advances from ancient times to our current technological age. Theories of modular arithmetic, set theory, formal logic, groups, and other discrete-math topics will be covered, with applications to encryption and digital information encoding. The course will include several writing assignments to help students develop their communications skills.

Course syllabus, including class data, contact information, office hours, and grading policies (subject to change)

Our textbook is Numbers, Groups, and Codes, by Humphreys and Prest, (library link) (publisher link) and partial solutions courtesy of Prof. Gary Mullen.

## Homework

• For 8/24 – Read Section 1.1.
• For 8/30 – Read Section 1.2.
• Extra practice on the division theorem
• Practice homework: Section 1.2, problems 1-5,8,9,11,12
• Online pratice: A, B
• For 9/10 – Read Section 1.3.
• For 9/20 – Read Section 1.4
• Practice homework: Section 1.4, problems 1,2,3,5,6,7
• Extra problems for Section 1.4: A
• For 9/27 – Read Section 1.5.
• Practice homework: Section 1.5, problems 1-5
• For 10/4 – Read Section 3.1.
• Practice homework: Section 3.1, problems 1,2,3,4
• Online pratice: A, B, C
• More pratice: Making truth-tables, Translating truth-tables
• A handout on common logic rules.
• Use deduction to prove (p → r) ∧ (q → r) = (p ∨ q) → r .
• Use deduction to prove ((p → q) ∧ (q → r)) → (p → r) . (A solution)
• For 10/8 – Read section 3.2
• Practice homework: Section 3.2, all problems
• For 10/8 – Read section 3.2
• Practice homework: Section 3.2, all problems
• For 10/15 – Read section 2.1
• Practice homework: Section 2.1, problems 1,2,3,5,6,7,8,9.
• Extra problems A and B
• Show that the conjecture $$(a \cap b) \cup c = a \cap (b \cup c)$$ is true in general.
• Prove that $$A \cap (B \backslash C) = (A \backslash C ) \cap B$$.
• Prove that $$(A \cup B) \backslash C = (A \backslash C ) \cup (B \backslash C)$$.
• For 10/18 – Read section 2.2
• Practice homework: Section 2.2, problems 1,2,4,5,6,7,8,9.
• Extra problems A
• Using induction, prove that for any partition $$P$$ of a finite set $$S$$, the cardinality of $$S$$ is equal to the sum of the cardinalities of the elements of $$P$$.
• For 10/20 – Read section 2.3
• Practice homework: Section 2.3, problems 1,2,3,4,6,7,9
• these extra problems, updated to include partial answers.
• Sochi medal counts and retroactive update
• Construct an adjacency matrix for Pell’s relation, $$x \sim y$$ if and only if $$y^2 | (x^4 - 1)$$, on the positive integers up to 10 using a calculator.
• Group theory (sections 4.1, 4.3, 5.1, 5.2)
• Extra problems A
• Practice homework: Section 4.1, #1,2,5
• Practice homework: Section 4.3, #1-8
• Practice homework: Section 5.1,
• Practice homework: Section 5.2,

## Essays

Information on our essays will be posted here.

• Essay 1, due Wednesday, October 20th

## Past quizes

Past quizes, posted with their answers.

• Quiz 1, Friday, September 3rd
• Quiz 2, Friday, September 17th
• Quiz 3, Friday, October 15th
• Quiz 4, Friday, October 29th
• Quiz 5, Friday, November 12th
• Quiz 6, Friday, November 19th

## Handouts

These are math-related links fished from the data-torrents as the semester progresses. Feel free to pass on your own.