MA 134 - Discrete Mathematics
This course provides the background necessary for advanced study of mathematics or computer science. Topics include propositional calculus, predicates and quantifiers, elementary set theory, countability, functions, relations, proof by induction, elementary combinatorics, elements of graph theory, mends, and elements of complexity theory.
This is a one-semester introduction to the mathematical topics that must be mastered by an undergraduate computer science student. The specific topics are listed in the section on “Learning Outcomes.” In addition to teaching the specific subject matter, the student is taught how to think precisely and algorithmically. After various proof techniques are learned, the student is expected to construct very short (two or three line) proofs. The emphasis is on making sure the argument is started correctly (get the first line right) and ended correctly (get the last line right). The objective is to help the students understand more complicated arguments, and to help them understand and construct algorithms. They should also understand how the arguments they will encounter in courses such as Data Structures, Algorithms, and Automata Theory are structured.
Upon completing this course, it is expected that a student will be able to do the following:
1. Mathematical Foundations
- Fundamentals of Logic: Formulate and interpret statements presented in disjunctive normal form and determine their validity by applying the rules and methods of propositional calculus.
- Application of Logic: Reformulate statements from common language to formal logic using the rules of propositional and predicate calculus, and assess the validity of arguments.
- Methods of Proof: Formulate short proofs using the following methods: direct proof, indirect proof, proof by contradiction, and case analysis.
- Set Theory: Demonstrate a working knowledge of set notation and elementary set theory, recognize the connection between set operations and logic, prove elementary results involving sets, and explain Russell's paradox.
- Functions: Apply the different properties of injections, surjections, bijections, compositions, and inverse functions, as well as the pigeon-hole principal.
- Cardinality: Use bijections to compare the cardinality of finite and infinite sets, and explain the difference between countable and uncountable sets.
- Proof by Induction: Construct elementary proofs using ordinary and strong induction in the context of studying the properties of recursion, relations, and graph theory, and identify fallacious inductive arguments.
- Combinatorics: Apply basic counting principles including the pigeonhole principle and rules for counting permutations and combinations.
- Relations: Determine when a relation is reflexive, symmetric, antisymmetric, or transitive, apply the properties of equivalence relations and partial orderings, and explain the connection between equivalence relations and partitioning a set.
- Graph theory: Explain basic definitions and properties associated with simple planar graphs, including isomorphism, connectivity, and Euler's formula, and describe the difference between Eulerian and Hamiltonian graphs.
Epp, S., Discrete Mathematics with Applications, 3rd edition, PWS Publishing Company.
Rosen, K.H., Discrete Mathematics and its Applications, 6th edition (McGraw Hill).
Bauer, D., Lecture Notes in Discrete Math, Stevens Tech edition.