MTH 231 Discrete Mathematics 1

Lecture Hours: 4
Credits: 4

Introduces logic, sets, functions, algorithms, matrices, graph theory, and trees, with applications. Offers the first course for computer science and mathematics majors.

Prerequisite: Placement into WR 115 (or higher), or completion of WR 090 (or higher); and placement into MTH 112Z or higher; or completion of MTH 111Z, or equivalent course as determined by instructor; or consent of instructor. (All prerequisite courses must be completed with a grade of C or better.)
Student Learning Outcomes:

Apply basic set operations
Apply concepts of propositional logic to analyze and interpret compound and quantified statements, as well as to negate and form contrapositives of such statements.
Construct direct proofs by applying mathematical definitions.
Apply principles of combinatorics to solve counting problems.
Construct indirect proofs, including those by contraposition, contradiction.
Apply the principle of mathematical induction.
Construct, and apply recursive definitions, and solve first order recurrence relations.
Represent finite graphs as matrices.
Find minimal spanning trees in finite connected graphs

Statewide General Education Outcomes:

Use appropriate mathematics to solve problems.
Recognize which mathematical concepts are applicable to a scenario, apply appropriate mathematics and technology in its analysis, and then accurately interpret, validate, and communicate the results.

Content Outline

Basic Logic
- Definitions
- Propositional logic
- Mathematical Statements
- Proofs and counterexamples
- Mathematical induction
Basic Set Theory
- Definitions and notation
- Set operations
Combinatorics
- Addition and multiplication rules
- Permutations
- Combinations (binomial coefficients)
- Recurrence relations
Relations
- Digraphs
- Partitions
- Equivalence relations
- Functions
Spanning Trees and Graphs
- Definitions
- Matrix representations of graphs
- Algorithms to find spanning trees