Skip to Main Content


Master Syllabus

Print this Syllabus « Return to Previous Page

Administrative Unit: Computer and Mathematical Sciences Department
Course Prefix and Number: MATH 225
Course Title: Discrete Mathematics I
Number of:
Credit Hours 3
Lecture Hours 3
Lab Hours 0
Catalog Description:

This course provides a foundation in formal mathematics and theorem-proving. Topics include functions, relations, sets, simple proof techniques, Boolean Algebra, propositional logic, elementary number theory, the fundamentals of counting, recursion, and an introduction to languages (finite state machines). Prerequisite: Grade of C or higher in MATH 201.

Prerequisite(s) / Corequisite(s):

Grade of C or higher in MATH 201.

Course Rotation for Day Program: Offered Fall.
Text(s): Most current editions of the following:

Discrete and Combinatorial Mathematics
By Grimaldi (Addison Wesley/Longman)
Discrete Mathematics and Combinatorics
By Anderson (Prentice Hall)
Course Objectives
  • To model and analyze computational processes using analytic and combinatorial methods.
  • To use logical notation to define and reason about fundamental mathematical concepts such as sets, relations, functions and integers.
  • To learn the algorithmic approach to problem solving.
  • To display an understanding of the nature of rigorous proof.
  • To write elementary proofs, especially proofs by induction and basic number theory proofs.
  • To reason mathematically about basic data types and structures used in computer algorithms and systems.
    Measurable Learning Outcomes:
  • Calculate numbers of possible outcomes of elementary combinatorial processes using the sum and product rules, permutations and combinations.
  • Illustrate the use of quantifiers to form mathematical statements and arguments.
  • Apply the fundamental laws of logic and rules of inference to analyze arguments and to form logical arguments.
  • Describe and explain basic set theory definitions and use the set theoretic operations.
  • Describe and explain the well-ordering principles and use in the method of proof by induction.
  • Employ the basic properties of integers such as divisibility, primes and congruences to solve basic number theory problems.
  • Demonstrate a thorough knowledge of the concept of a function including the concepts: range, domain, one-to-one, into, onto, and inverse.
  • Describe and explain the recursive definition of sequences and functions.
  • Recognize a binary relation on a set and a function as a special case of a finery relation.
  • Recognize a binary relation on a set as a special case of finery relation.
  • Use equivalence relations to partition sets.
  • Determine the complexity of an algorithm.
  • Describe and explain languages and finite state machines as applications of discrete structures.
    Topical Outline:

  • Fundamental principles of counting
  • The rules of sum and product
  • Permutations
  • Combinations: The binomial theorem
  • Combinations with repetition
  • Fundamentals of logic
  • Basic connectives and truth tables
  • Logical equivalence: The laws of logic
  • Logical implication: Rules of inference
  • The use of quantifiers
  • Quantifiers, definitions, and proofs of theorems
  • Set theory
  • Sets and subsets
  • Set operations and the laws of set theory
  • Counting and venn diagrams
  • Properties of the integers: Mathematical induction
  • The well-ordering principle: Mathematical induction
  • Recursive definitions
  • The division algorithm: Prime numbers
  • The greatest common divisor: The Euclidean algorithm
  • The fundamental theorem of arithmetic
  • Relations and functions
  • Cartesian products and relations
  • Functions, one-to-one, and onto
  • Special functions such as the floor and ceiling functions
  • The pigeonhole principle
  • Function composition and inverse functions
  • Computational complexity
  • Analysis of algorithms
  • Languages: Finite state machines
  • Language: The set theory of strings
  • Introduction to finite state machines
  • More on relations
  • Properties of relations
  • Equivalence relations
  • Partial orders
  • Computer recognition: zero-one matrices and directed graphs
  • Hasse diagrams
  • Equivalence relations and partitions

    Culminating Experience Statement:

    Material from this course may be tested on the Major Field Test (MFT) administered during the Culminating Experience course for the degree. 
    During this course the ETS Proficiency Profile may be administered.  This 40-minute standardized test measures learning in general education courses.  The results of the tests are used by faculty to improve the general education curriculum at the College.


    Recommended maximum class size for this course: 20

    Library Resources:

    Online databases are available at You may access them from off-campus using your CougarTrack login and password when prompted.

    Prepared by: Suzanne Tourville Date: November 19, 2010
    NOTE: The intention of this master course syllabus is to provide an outline of the contents of this course, as specified by the faculty of Columbia College, regardless of who teaches the course, when it is taught, or where it is taught. Faculty members teaching this course for Columbia College are expected to facilitate learning pursuant to the course objectives and cover the subjects listed in the topical outline. However, instructors are also encouraged to cover additional topics of interest so long as those topics are relevant to the course's subject. The master syllabus is, therefore, prescriptive in nature but also allows for a diversity of individual approaches to course material.

    Office of Academic Affairs