Effective: 2018-01-01

Course Description

The course outline below was developed as part of a statewide standardization process.

General Course Purpose

The goal is to give the student a solid grasp of the methods and applications of discrete mathematics to prepare the student for higher level study in mathematics, engineering, computer science, and the sciences.

Course Prerequisites/Corequisites

Prerequisite: Completion of MTH 263 with a grade of C or better or equivalent.

Course Objectives

• Note: Methods of proofs and applications of proofs are emphasized throughout the course.
• Logic - Propositional Calculus
• Use statements, variables, and logical connectives to translate between English and formal logic.
• Use a truth table to prove the logical equivalence of statements.
• Identify conditional statements and their variations.
• Identify common argument forms.
• Use truth tables to prove the validity of arguments.
• Logic - Predicate Calculus
• Use predicates and quantifiers to translate between English and formal logic.
• Use Euler diagrams to prove the validity of arguments with quantifiers.
• Logic - Proofs
• Construct proofs of mathematical statements - including number theoretic statements - using counter-examples, direct arguments, division into cases, and indirect arguments.
• Use mathematical induction to prove propositions over the positive integers.
• Set Theory
• Exhibit proper use of set notation, abbreviations for common sets, Cartesian products, and ordered n-tuples.
• Combine sets using set operations.
• List the elements of a power set.
• Lists the elements of a cross product.
• Draw Venn diagrams that represent set operations and set relations.
• Apply concepts of sets or Venn Diagrams to prove the equality or inequality of infinite or finite sets.
• Create bijective mappings to prove that two sets do or do not have the same cardinality.
• Functions and Relations
• Identify a function's rule, domain, codomain, and range.
• Draw and interpret arrow diagrams.
• Prove that a function is well-defined, one-to-one, or onto.
• Given a binary relation on a set, determine if two elements of the set are related.
• Prove that a relation is an equivalence relation and determine its equivalence classes.
• Determine if a relation is a partial ordering.
• Counting Theory
• Use the multiplication rule, permutations, combinations, and the pigeonhole principle to count the number of elements in a set.
• Apply the Binomial Theorem to counting problems.
• Graph Theory
• Identify the features of a graph using definitions and proper graph terminology.
• Prove statements using the Handshake Theorem.
• Prove that a graph has an Euler circuit.
• Identify a minimum spanning tree.
• Boolean Algebra
• Define Boolean Algebra.
• Apply its concepts to other areas of discrete math.
• Apply partial orderings to Boolean algebra.
• Recurrence Relations
• Give explicit and recursive descriptions of sequences.
• Solve recurrence relations.

Major Topics to be Included

• Logic - Propositional Calculus
• Logic - Predicate Calculus
• Logic - Proofs
• Set Theory
• Functions and Relations
• Counting Theory
• Graph Theory
• Boolean Algebra
• Recurrence Relations