MTH 288 Discrete Mathematics

Course Title:  MTH 288: Discrete Mathematics

Course Description

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

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 Calculus I with a grade of C or better or equivalent.

Course Objectives

Upon completing the course, the student will be able to:

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