MAT-220 Discrete Mathematics for Computing
This course introduces students to ideas and techniques from mathematics that are widely used in computer science. Topics include the fundamentals of logic (propositional and predicate calculus), set theory, relations, recursive structures, and combinatorics. This course will increase students' mathematical sophistication and ability to handle abstract problems. This course carries SUNY General Education Mathematics (and Quantitative Reasoning) credit.
For more detailed course information view the
Course Outline
Course Description
This course introduces students to ideas and techniques from mathematics that are widely used in computer science. Topics include the fundamentals of logic (propositional and predicate calculus), set theory, relations, recursive structures, and combinatorics. This course will increase students' mathematical sophistication and ability to handle abstract problems. This course carries SUNY General Education Mathematics (and Quantitative Reasoning) credit.
Credit Hours
3Semester(s) Course Will Be Offered
Fall, Spring
SUNY General Education Course
- Mathematics and Quantitative Reasoning
Course Learning Outcomes
- Apply precise mathematical reasoning in the use and analysis of course content.
- Justify conclusions supported by appropriate evidence, presented with proper terminology and notation.
- Articulate clear solutions to problems by applying definitions, properties, techniques and logical structure included with course concepts.
Topic Outline
- 1. Logic
- a. Propositional logic operators: negation, conjunction, disjunction, conditional, and biconditional
- b. Conditional statements: converses, inverses, contrapositives, and negations
- c. Arguments and valid conclusions
- d. Propositional equivalences and truth tables
- e. Predicates and quantifiers
- f. Multiple quantifications (nested quantifiers)
- 2. Principles of mathematical proof
- a. Axioms, lemmas, and theorems
- b. Direct proof
- c. The explosion principle (ex contradictione quodlibet)
- d. Proof by contradiction
- 3. Set theory
- a. Naive concept of a set, set elements, subsets, and set equality
- b. Formal representation of a set
- c. Russell's paradox and the comprehension axiom
- d. Set operations: union, intersection, complement, and set difference
- e. Set equalities: logically equivalent formulas and the element method for demonstrating set equality
- f. Power set and an algorithm for its enumeration
- g. Set partitions
- h. Cartesian products
- 4. Relations and functions
- a. Binary, ternary, and n-ary relations
- b. Properties of binary relations
- i. Partial, total, one-to-one, and onto
- ii. Inverse relations
- iii. Compositions: Boolean product
- c. Properties of relations of a set on itself
- i. Representations: matrices and graphs
- ii. Reflexive, symmetric, antisymmetric, and transitive
- d. Equivalence relations using partitions
- e. Equivalence relations and arithmetic on ℤₙ
- f. Partial and total orderings
- g. Functions
- i. Injections (one-to-one), surjections (onto), and bijections
- ii. Bijections and set cardinality
- iii. Countable and uncountable sets
- iv. Inverse functions
- v. Recursive definitions of functions
- vi. Operations on functions
- 5. Recursive definitions and mathematical induction
- a. Recursively defined sequences
- b. Recursively defined sets, strings, and formulas
- c. Mathematical induction: complete and structural
- 6. Combinatorics
- a. Basic principles of counting: sum and product rules
- b. The pigeonhole principle
- c. Permutations and combinations
- d. The binomial theorem
- e. Combinations with repetitions
- f. The inclusion-exclusion principle
- 7. Optional topics (as time and student needs permit)
- a. Closures of relations
- b. Topological and well-founded ordering
- c. Rings: properties and homomorphisms
- d. Discrete probability
- i. Conditional probability
- ii. Independence, Bernoulli trials, and binomial distribution
- e. Number theory
- i. Prime numbers and their properties
- ii. Applications to data encryption
- f. Non-classical logic
- i. Fuzzy logic, multivalued logics, and paraconsistent logics