Discrete mathematics is the mathematics of discrete structures. What do we mean by discrete structures? By discrete, we mean things that can be thought of as distinct chunks or units, like whole numbers and counting. That sounds pretty elementary and it's an interesting quirk that the educational system seems to be eager to shuffle us off into things like fractions, "decimals", lines, and so on. These things are not discrete: lines are typically smooth and this smoothness is such a desirable feature that it plays a big role when we eventually get to calculus. Calculus is very concerned about continuous functions, which are very not discrete.
But why should we be concerned with discrete mathematics as computer scientists? There are a number of different levels from which we can examine this relationship. Here is a summary to start.
The most immediately obvious relationship is what happens when we ask students to complete a programming exercise in a class like CMSC 14100. For many people, programming has nothing to do with mathematics—after all, you're probably in this class after finishing CMSC 14100. Whether or not you took that class, we can think about what the problem solving process for a beginner programmer might look like. In the best case, we systematically think through modelling and abstracting our problem into a math problem and then try to solve that problem. What usually happens is that we throw ourselves against a wall trying things out until it works.
When people say that programming doesn't need math, this is what they're describing. You don't strictly need to know math, because you can just brute force your way into getting your program working. That's fine, but eventually, one gets tired of smashing their head against walls so much and you'd begin to wonder whether there was a better way.
This is the first level at which we can think about the connections between computer science and math. When we say that we want to solve problems using computer science, what we really want is a program that solves a mathematical problem that represents our "real" problem. Knowing more math gives us more options when mapping "real" problems to math problems.
What's the next step? At the top level, we model "real" problems onto mathematical problems. However, we then need to go a bit deeper and think about the structures that we use in order to this. That is, how is our data represented? In programming, we are introduced to the idea of types like integers, strings, and lists and even more complex types like trees. But these are discrete structures!
Here is the next idea: that many of the structures and representations in computer science are discrete. Hence, the need to understand the mathematics of discretre structures.
Let's start by talking about one of the discrete structures that we'll be examining in more detail later: the natural numbers. You may be familiar with the natural numbers already as "whole numbers" or maybe slightly more formally as "nonnegative integers" (we consider 0 to be a natural number, though this is disputed by various kinds of mathematicians).
For instance, here is a definition you will likely have run across recently as you began to learn how to program.
Let $n$ be a natural number. The factorial $n!$ is defined by \[n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1.\] This makes for a simple programming exercise.
def factorial(n: int) -> int:
result: int = 1
for i in range(1,n+1):
result = result * i
return resultHowever, you may also recall that the factorial function can be written recursively.
def factorial(n: int) -> int:
if n == 0:
return 1
else:
return n * factorial(n-1)This function comes from the more formal definition for the factorial.
Let $n$ be a natural number. The factorial $n!$ is defined as follows:
Notice that this definition itself is already an algorithm. We can compute the factorial simply by using substitution and the definition.
What's $3!$? According to the definition, $3! = 3 \times 2!$. Okay, so what's $2!$? According to the definition, $2! = 2 \times 1!$. But what's $1!$? According to the definition, $1! = 1 \times 0!$. But what's $0!$? According to the definition, $0! = 1$. Putting it all together, we have the following. \begin{align*} 3! &= 3 \times 2! \\ &= 3 \times (2 \times 1!) \\ &= 3 \times (2 \times (1 \times 0!)) \\ &= 3 \times (2 \times (1 \times 1)) \end{align*}
Why does this definition work? We recall that recursive functions are computations on recursive data. So the definition of the factorial gets its structure from the formal mathematical definition for the natural numbers, due to the Italian mathematician Giuseppe Peano in the late 19th Century.
The natural numbers are defined as follows:
We denote the set of natural numbers by $\mathbb N$.
Here, we have an element that we've just called $z$—this happens to be the thing that we call zero or 0. Zero is a natural number. Here I've made a deliberate choice not to use 0 to make it clear there's nothing particularly special about this element. Then we have the function $\operatorname{succ}$, which is called the successor function.
This definition for the natural numbers (and the definition for factorial from above) is an example of a recursive or inductive definition. These are definitions that are defined in terms of itself. Let's dissect this.
The first part of the definition is called the base case. The base case defines the most basic element of the definition. Often, one can think of this as kind of the "smallest" or "least" case. The second part of the definition is called the recursive or inductive case. This is the part of the definition that refers to itself.
Surprisingly, even though this defintion is recursive, we can hammer out a definition of the type (yes, even in Python! crazy!) in code just like before.
@dataclass
class Succ:
p: Natural
Natural = None | SuccHere, we define the type Natural to be
None, which we use as our "zero", or
Succ, where Succ is implemented as a class (rather than a function in the literal sense) containing a Natural, the predecessor p.
In case you really want to try working with this yourself, here are some notes on implementation that are not that important to the mathematics:
from dataclasses import dataclass).
from __future__ import annotations.
The key idea here is that types in computer science and structures in math are often the same thing. The reason that we can have data structures in CS is because they have formal mathematical definitions.
It so happens that all of the numbers we already know and love can be described using this definition. "Zero" or "0" we already said was $z$. Then "one" or "1" is $\operatorname{succ}(z)$. "Two", or "2", is $\operatorname{succ}(\operatorname{succ}(z))$, and so on. But notice that we never actually defined these other natural numbers: the only natural number we explicitly defined was zero. Every other number is expressed as the successor of another number.
In a way, we might think of this as naming constants like
zero = None
one = Succ(zero)
two = Succ(one)
three = Succ(two)
...Is $3$ a natural number? Here, we're using $3$ as a shorthand for \[\operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))).\] So how do we know if $\operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z)))$ is a natural number? Well, we have to figure out if it's the successor of a natural number, or if the argument to $\operatorname{succ}$ is also a natural number. So we look at $\operatorname{succ}(\operatorname{succ}(z))$ and see if that's a natural number. Again, this depends on the argument to $\operatorname{succ}$, so we check to see if $\operatorname{succ}(z)$ is a natural number. We go through the same argument and check if $z$ is a natural number. It is! So we can conclude that $3$ was a natural number after all.
So what can we do with this? One of the first things we learn when we learn about numbers is how to add them together, so let's do that. Now, we typically think of adding in terms of combining numbers of things together. However, we need to try to do this without that kind of intuition, because as we discussed before, computers do not know that putting three apples and five apples together makes eight apples.
For natural numbers $m$ and $n$, we define addition on the natural numbers, denoted $m + n$, as follows:
Let's think about this definition a bit. We want to add two natural numbers, $m$ and $n$. What should be the outcome? Well, let's think about the first one, $m$. Recall our definition for natural numbers: it's either $z$ or the successor of some other natural number.
Okay, so if $m = z$, that is $m$ is zero, then adding it to $n$ should just produce $n$ (at this point, I need to point out that we didn't really define zero's properties, but let's set that aside for later).
But what if it's not $z$? Then $m = \operatorname{succ}(p)$, where $p$ is some other natural number. At this point, we have a few pieces to work with: we have the natural numbers $m$, $p$, and $n$ (and $m$ and $p$ are related), and we have two functions, $\operatorname{succ}$ and $+$.
The key here is to think about what $p+n$ is in relation to $m+n$. We know that $p$ is the number that comes "before" $m$, which means that $p+n$ should be the number that comes before $m+n$. And so, we arrive at $m+n = \operatorname{succ}(p+n)$.
Let's try to do some simple math: what's $2+3$? By following our definitions from above, we get: \begin{align*} 2+3 &= \operatorname{succ}(\operatorname{succ}(z)) + \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))) \\ &= \operatorname{succ}(\operatorname{succ}(z) + \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z)))) \\ &= \operatorname{succ}(\operatorname{succ}(z + \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))))) \\ &= \operatorname{succ}(\operatorname{succ}(\operatorname{succ}(\operatorname{succ}(\operatorname{succ}(z))))) \\ &= 5 \end{align*}
Another way of looking at this is to use the usual notation for numbers and see that our definition says that $m+n$ is defined in the following way:
Now recall that all of these inductive definitions also tell us how to compute these things so we get a nice algorithm.
def plus(m: Natural, n: Natural) -> Natural:
match m:
case None:
return n
case Succ(p):
return Succ(plus(p,n))Now, we can continue this line of thinking and reproduce many basic results on natural numbers (for example, how do we define multiplication?). However, let's observe and reiterate a point that was made in early CS classes. We arrived at our algorithm from the mathematical definition that we gave. And we arrived at our definition based on the definition of the structure that we're working with.
That is, the problems that we're solving and the algorithms that we use to solve them are determined by the structures that we use to represent our data. This is very easy to see when working with simple recursive types like naturals, lists, and even trees. However, this is still true for more complex data, like objects.