## MTH 288 - Discrete Mathematics at Germanna Community College

### Course Description

Effective: 2018-01-01

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.

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