This page does not represent the most current semester of this course; it is present merely as an archive.

Discrete Mathematics is a course designed to provide the mathematical tools needed for later CS courses. This version of the course is shared by Elizabeth Orrico and Luther Tychonievich, including sharing a common set of assessments and grading schemes.

Course meetings are synchronous, with recordings posted after class for asynchronous review. Some class meetings will be announced as mandatory with no recordings provided. Connecting to the course meetings is managed through Collab:

- 10:00 section: https://collab.its.virginia.edu/portal/site/5f8620a6-2dcf-458f-9b41-34b8207aca35
- 11:00 section: https://collab.its.virginia.edu/portal/site/9c5db4ed-7a44-41b1-8243-95da5c55229c
- 14:00 section: https://collab.its.virginia.edu/portal/site/5f8620a6-2dcf-458f-9b41-34b8207aca35

Collab pulls participant information once each day from SIS. If you add the course, you may need to wait up to 24 hours before you have Collab access.

You should take this course if and only if

- You have credit (or passed the placement test) for at least one of CS 1110, CS 1111, CS 1112, CS 1113, or CS 1120

At the conclusion of this course, a successful student will be able to

- Communicate using first-order logic to unambiguously specify claims, including
- converting between English and logic
- proper use of alternating quantifiers

- Prove theorems and write prose proofs by hand, utilizing the following proof techniques
- direct proof
- proof by contradiction
- proof by cases
- induction

- Converse in the language of sets, including proper use of
- set operators (notation and meaning)
- set-builder notation
- cardinality, both finite and infinite (but not classes of infinity)

- Categorize functions as invertible, 1-to-1, and onto
- Identify relations with the reflexive, transitive, and associative properties, and identify equivalence relations in particular
- Understand and use
- summation notation
- counting rules
- prime factorization
- logarithms

From time to time I create reference pages intended to supplement the textbooks (MCS and ∀x, the latter also having a solution book); I have no obvious place to list those supplements so I’m listing them here. They are:

- A summary of many different structures and vocabulary terms
- On Proofs, including four different uses of the word
proof

- Symbols we’ll use, which is made available during in-class quizzes
- Six meanings of
everyone can fit in a bus

, an introduction to quantifiers and the purpose of jargon - Operator precedence and how it helps convert between English and logic
- Logical Rules, being useful tools out of which we build proofs
- Guide to Direct Proof
- English to Quantifiers
- Sets primer
- induction addenda
- Proof Techniques, a list of techniques with tips on proof writing
- Logical Reduction
- MCS 4 addenda
- Glossary of logical terms
- Example proofs, including De Morgan’s laws, bubble sort, Cantor diagonalization, open sets, irrationality of various numbers
- All in-class practice and quiz questions from previous semesters