1 List of reference pages

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

2 Course Overview

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.

2.1 Eligibility

You should take this course if and only if

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

2.2 Learning Outcomes

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.