This provides a clear, accessible introduction to discrete mathematics that combines theory with practicality. Discrete mathematics describes processes that consist of a sequence of individual steps, as compared to forms of mathematics that describe processes that change in a continuous manner. The major topics we cover in this course are single-membership sets, mathematical logic, induction, and proofs. We will also discuss counting theory, probability, recursion, graphs, trees, and finite-state machines.
Understanding the terms "single-membership" and "discrete" are important as you begin this course. "Single-Membership" refers to something that is grouped within only one set and systems that can be in only one state at a time, at the same hierarchical level. Similarly, "discrete" refers to that which is individually separate and distinct. Each element of anything can be in only one set or one state at a time. This is a result of Aristotelian philosophy, which holds that there are only two values of membership, 0 or 1. An answer is either no or yes, false or true, 0% membership or 100% membership, entirely in a set or state, or entirely not. There are no shades of gray. This is much different from Fuzzy Logic (due to Lofti Zadeh), where something can be a member of any set or in any state to some degree or another. Degrees of membership are measured in percentage, and those percentages add to 100%. But, even in Fuzzy Logic (multiple-membership, multiple-state, non-discrete logic), one ultimately comes to a crisp decision so whether some specific action is taken or not. For this course, it is enough to understand the difference between single-state and multi-state logic.
As you progress through the units of this course, you will develop the mathematical foundation necessary for more specialized subjects in computer science, including data structures, algorithms, cryptology, and compiler design. Upon completion of this course, you will have the mathematical know-how required for an in-depth study of the science and technology that is foundational to the computer age.
Computer scientists often find themselves working with groups of homogeneous or heterogeneous entities. Mathematicians devised single-membership set theory to respond to these situations. In this unit, we will cover the theoretical background of sets and take a look at associated definitions, notations, relations, and functions. This is a fundamental tool of mathematics and computer science, and is essential to understanding the other topics in this course.
Completing this unit should take you approximately 5 hours.
"How many elements do we expect to find within a given set?" This is a simple question, but hard to answer correctly without guessing. Counting theory (also known as combinatorics) lets us do that through several different approaches that depend on the circumstances of the given problem. These approaches are not difficult, but you have to know when to use each one, and which circumstances each approach applies to. In this unit, we will carefully walk through these considerations.
Completing this unit should take you approximately 5 hours.
In this unit, we will discuss basic concepts that are part of the foundation of mathematical logic. As you seek to fully understand these concepts, you must be able to recognize valid logical arguments. Although these arguments will usually be applied to mathematics, they are the same techniques used by lawyers in the courtroom, physicians examining a patient, or engineers trying to solve a difficult problem. The circuits of computers are designed using the same algebra of propositions that we will discuss in this unit. Often, embedded computers (that is, the data processing units within a larger machine) are programmed by using binary, gate-level logic, machine code, or ladder logic. These rely on the basic concepts we will discuss here.
Completing this unit should take you approximately 5 hours.
So far, we have learned about symbology, truth tables, writing equations, and determining how many units could be in a set under specific circumstances. We have done all of this has under the assumption that we can easily see the results of our efforts. However, in practical situations that you will encounter in real life with serious applications, we cannot always see our results quickly, or necessarily even traverse the situation easily. For that, we must turn to the methods behind mathematical systems and proofs. These allow us to "get the big picture" without having to visualize it all at once. Proofs also give us a way to consider all of the available information in a given arrangement of facts, even when some of the "facts" might not actually be true. They also have the added advantage of letting us ignore whole portions of a situation when we know they do not hold the answer we seek.
Completing this unit should take you approximately 5 hours.
Probability is an important component of discrete mathematics. For instance, if you consider a population of 10 and then take four at a time, without duplicates, what is the chance that a certain combination within the subsets of four will occur? Or, given the set of all possible events, what is the chance that a certain event will occur, given that the event can result from various causes? The construction of trees and graphs , which we will discuss later, depends on the probability of combinations of events. Since we want to traverse trees and graphs in order of the most likely and most important events, we need to know probability.
Completing this unit should take you approximately 4 hours.
Using recursion, we can arrive at a succession of elements (such as numbers or events) by operating on one or more of the elements that came earlier. We do this using a rule or formula with a finite number of steps. In computer programming, we implement recursion with procedures, subroutines, functions, or algorithms that run one or more times until a specified condition is met. At that point, the remaining code in each procedure is processed from the last procedure called to the first. From a practitioner's perspective, recursive procedures are simple to write, but they are extremely memory-intensive, and it can be difficult to predict how much memory will be required.
Recursion is common, so you will need to understand it at a fundamental level. A basic example of a recursive sequence is Dt = f(D[t-1]). The data at time t is a function of the data at the previous unit of time. In practice, this can be implemented as a recursive function or an explicit (that is, non-recursive) function. This unit will delve deeper into this topic.
Completing this unit should take you approximately 5 hours.
Graphs are formal mathematical representations of networks, collections of objects, events, or set elements that lead naturally from one to another. In this unit, we will examine the formality of graphs. Graphs are extremely useful in business, science, and engineering. In this unit, we will discuss how to understand graphs, how to build them, how to manipulate them, and how to use them.
Completing this unit should take you approximately 9 hours.
Trees are a special case of graphs. Certain assumptions are made about the structure of trees, so various actions can be taken with them that would not work with graphs. Put simply, a tree is a nondirected graph where any two nodes are connected by exactly one path. There are no cycles in a tree. Although this definition is very simple, it has powerful consequences within graph theory and in the real world. In this unit, we will explore trees further.
Completing this unit should take you approximately 4 hours.
A finite-state machine (FSM) is a mathematical model of computation that describes an abstract machine in one of a finite number of states at any point in time. The FSM can change from one state to another as it responds to data inputs, or when some condition is satisfied. The change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition. Often, state machines are illustrated as graphs whose nodes are the states and whose links are the transition conditions.
Completing this unit should take you approximately 2 hours.
This study guide will help you get ready for the final exam. It discusses the key topics in each unit, walks through the learning outcomes, and lists important vocabulary. It is not meant to replace the course materials!
Please take a few minutes to give us feedback about this course. We appreciate your feedback, whether you completed the whole course or even just a few resources. Your feedback will help us make our courses better, and we use your feedback each time we make updates to our courses.
If you come across any urgent problems, email contact@saylor.org.
Take this exam if you want to earn a free Course Completion Certificate.
To receive a free Course Completion Certificate, you will need to earn a grade of 70% or higher on this final exam. Your grade for the exam will be calculated as soon as you complete it. If you do not pass the exam on your first try, you can take it again as many times as you want, with a 7-day waiting period between each attempt.
Once you pass this final exam, you will be awarded a free Course Completion Certificate.