| Description |
Introduction to the mathematical foundations of computer science. Topics include logic (propositional and predicate); proof techniques (induction/recursion, contradiction, and others); and key concepts of mathematical structures (sequences, sets, functions, relations, and graphs).
|
| Major Topics Covered in Course |
Section numbers come from Discrete Mathematics with Applications by Susanna Epp.
- Course Overview; Variables, Sec. 1.1
- The Language of Sets; The Language of Relations and Functions The Language of Graphs, Secs. 1.2-1.4
- Logical Form and Logical Equivalence, Sec. 2.1
- Conditional Statements, Sec. 2.2
- Valid and Invalid Arguments, Sec. 2.3
- Digital Logic Circuits, Sec. 2.4
- Predicates and Quantified Statements, Secs. 3.1-3.2
- Statements with Multiple Quantifiers, Sec. 3.3
- Arguments with Quantified Statements, Sec. 3.4
- Direct Proof: Introduction; Direct Proofs Involving Rational Numbers, Secs. 4.1-4.3
- Direct Proofs Involving Divisibility, Sec. 4.4
- Direct Proof and Counterexample, Secs. 4.5-4.6
- Proofs by Contradiction and Contraposition, Sec. 4.7
- Indirect Argument: Two Famous Theorems, Sec 4.8
- Sequences, Sec. 5.1
- Mathematical Induction, Secs. 5.2-5.3
- Mathematical Induction, Secs. 5.2-5.3
- Defining Sequences Recursively, Sec. 5.6
- Solving Recurrence Relations by Iteration, Sec. 5.7
- Set Theory: Definitions and the Element Method of Proof, Sec. 6.1
- Properties of Sets, Sec. 6.2
- Sets: Disproofs and Algebraic Proofs, Sec. 6.3
- Functions Defined on General Sets, Sec. 7.1
- One-to-One, Onto, and Inverse Functions, Sec. 7.2
- Composition of Functions, Sec. 7.3
- Cardinality with Applications to Computability, Sec. 7.4
- Relations on Sets; Reflexivity, Symmetry, and Transitivity, Secs. 8.1-8.2
- Equivalence Relations, 8.3
- Modular Arithmetic with Applications to Cryptography, 8.4
- Partial Order Relations, 8.5
|
