Common Course Outline

Course discipline/number/title MATH 2218: Discrete Mathematics

Catalog Description

Credits 4
Hours/Week 4
Prerequisites (Course discipline/number) MATH 1115
Other requirements Successful completion of prerequisite courses with a grade of C or higher, College-level reading
MnTC Goals (if any) NA

Course Description

This is a course for mathematics and/or computer science majors. Topics include sets, relations, symbolic language, graph theory, matrices, and Boolean algebra.

Date Last Revised (Month, year)

March, 2025

Outline of Major Content Areas

  1. Formal Logic and Logic Design
  2. Set Theory and Elementary Number Theory
  3. Proof Methods (Direct, Contradiction, Contrapositive, Induction)
  4. Combinatorics and Discrete Probability
  5. Relations, Graphs, and Trees
  6. Algorithm Analysis

Learning Outcomes (General)

The student will be able to:

  1. Apply concepts in propositional logic and predicate logic by:
    1. Creating truth tables for compound propositional logic statements
    2. Using truth tables and laws of logic to determine validity of a proposition (tautology, contradiction, contingency) and logical equivalence.
    3. Verifying an argument’s validity by means of truth tables and rules of inference.
    4. Interpreting and negating quantifications and nested quantifications.
  2. Sketch simple logic circuits from a truth table using AND, OR, NOT, NOR, and NAND logic gates.
  3. Prove statements using mathematical induction, direct proof, counterexamples, direct proof, proof by contradiction, proof by contraposition, and induction.
  4. Demonstrate knowledge in set theory, number theory and functions by:
    1. Implementing set operations such as Compliments, Intersections, Unions, Differences, and Products.
    2. Computing solutions to sequence, series, recursion, recurrence, and sigma notation summations.
    3. Computing solutions to linear congruences and systems of congruences by computation of modulo inverses and the chines remainder theorem
    4. Representing relations (sets, functional notations, or directed graphs).
    5. Identifying an equivalence relation and determining its equivalence classes.
    6. Identifying a partial order relation and constructing its Hasse diagram.
  5. Find encryptions and decryptions for Shift Ciphers, Affine Ciphers, and RSA.
  6. Compute combinations, permutations, discrete probability and conditional probability.
  7. Develop a working knowledge of graphs, graph isomorphisms, finite state automata, and trees related to computer science and electrical engineering problems.
  8. Analyze and implement algorithms relevant to computer science including big-O notation, path finding, spanning trees, and optimization.

Learning Outcomes (MnTC)

NA

Methods for Evaluation of Student Learning

Methods may include but are not limited to:

RCTC Core Outcome(s)

This course contributes to meeting the following RCTC Core Outcome(s):

Critical Thinking
Students will think systematically and explore information thoroughly before accepting or formulating a position or conclusion.

Special Information (if any)

Successful completion of COMP 1150 suggested. A graphing calculator is likely to be highly beneficial for this course.