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).
Prerequisite
AMS 151 or MAT 125 or MAT 131 or level 6 on the mathematics placement examination
Course Outcomes
Textbook
Discrete Mathematics: Introduction to Mathematical Reasoning. Susanna S. Epp. Brief Edition.
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