Revised 8/2018

MTH 288 - Discrete Mathematics (3 CR.)

Course Description

Presents topics in sets, counting, graphs, logic, proofs, functions, relations, mathematical induction, Boolean Algebra, and recurrence relations. Lecture 3 credits. Total 3 credits per week.

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: 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