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

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:

- On Proofs, including four different uses of the word
proof

- Symbols we’ll use, which is made available during in-class quizzes
- Axioms, being useful tools out of which we build proofs
- Glossary of logical terms
- Sets primer
- Proof Techniques, a list of techniques with tips on proof writing
- Logical Reduction
- §4 addenda
- Example proofs, including De Morgan’s laws, bubble sort, Cantor diagonalization, and open sets

This is one offering of Discrete Mathematics, a course designed to provide the mathematical tools needed for later CS courses, offered in a flavor designed to meet both the current Discrete Mathematics requirement and to fit with our pilot of a new curriculum. If that new curriculum is adopted, this course is expected to be called discrete math and theory 1

or DMT1.

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

- 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)

- Distinguish between functions, relations, and subroutines
- Categorize functions as invertable, 1-to-1, and onto
- Identify relations with the reflexive, transitive, and associative properties, and identify equivalence relations in particular
- Translate to and from, and manipulate within, propositional logic
- Understand statements in, and perform basic proofs within, first-order (i.e., quantified predicate) logic
- Use and understand summation notation, permutations, combinations, and factoring

I hope to also have time to cover several additional topics, including

- additional discrete structures, including tuples and graphs
- finite automata
- logical reductions

Because I have not taught this class before, I am not confident I will be able to fit these topics in the semester.