Introduction to Discrete Mathematics
[Video Introduction] (coming soon)
This set of tutorials covers basic discrete mathematics topics, a core area of study for computer science students, mathematics students, and more. The coverage here is complete, so these tutorials could be used as a stand-alone introductory course in discrete mathematics, or they can be used as supplemental materials for students learning discrete mathematics from other sources. Once you get beyond the foundational materials about core mathematical structures and proofs, the topics are mostly independent and can be covered in any order, or in isolation. For instance, you don’t need to know any of the number theory material to learn about counting, probability, or graphs. The only exception to the “mostly independent” nature of the topics is that the probability material does depend on some of the material we cover in “Counting.”
Some additional materials for learning discrete mathematics are on our Outside Resources page. If you’re using these tutorials as a supplement to a class you’re taking, you might find your textbook on that page!
What is Discrete Mathematics?
Discrete mathematics is the study of distinct mathematical objects and structures built with them, and can be contrasted with continuous mathematics as studied in Calculus, Differential Equations, and more. When we talk about “mathematical objects” it can refer to anything we write down in mathematics, and it doesn’t have to have any specific properties. If you are a computer science student, don’t confuse this with “objects” in “object-oriented programming” where those objects have inheritance, polymorphism, and other properties. A mathematical object can be anything from a number (integer, rational, or real) to a logical value (true or false) to a complex structure describing the relation between other mathematical objects.
Discrete mathematics looks at objects such as integers, logic, and graphs. We study how discrete objects combine in various ways, looking at combinations, permutations, and other ideas in combinatorics. We study numbers and operations on integers, natural numbers, and finite sets of numbers. We study relations between discrete objects, such as those modeled by a discrete structure called a graph (this is not the graph of a function, which you have probably seen, but a discrete structure that models relations between discrete objects).
While the structures we study are important and very useful, one of the most important parts of a standard course in discrete mathematics is learning about proofs. A proof is simply a rigorous argument of some mathematical property, and it’s a way of explaining why something is true. The “explaining” part is important. You write proofs for other people to read, so think of it as a way of communicating. We’ll look at ways of writing proofs so they are not only precise, but also clear communication. Don’t think that means that a well-written proof will be perfectly clear as you start learning about proofs, or that your proofs need to be clear to someone who hasn’t studied proofs! It will be awkward at first, just like reading or writing in a new language is at first. Your goal should be to write proofs that are clear to someone who understands proofs, much like your goal in learning to speak Spanish is to speak in a way that a Spanish-speaker will understand.
Pay attention to the spelling! It’s discrete mathematics, not discreet mathematics. “Discrete” is contrasted with “continuous,” while “discreet” is something you don’t talk about. “Discreet mathematics” would be math you don’t talk about. We don’t do that!
Why Study Discrete Mathematics?
If you are studying discrete mathematics because you want to learn more mathematics, or because you find it interesting, or for the pure joy of learning, the “why” for you is obvious. If you are a computer science student who has been told “you need to take this class” then you might be struggling to understand the “why” for you. At a superficial level, the “why” for a computer science student is that it’s a required part of every reputable undergraduate curriculum, making up the majority of the “Mathematical and Statistical Foundations” core knowledge area of the ACM/IEEE/AAAI computer science curriculum guide that defines what computer science students should learn. This isn’t a very satisfying answer to “why” however, because it comes across as “because we said so.”
The better answer to “why” for computer science students is that everything in a computer is discrete. Everything. It all boils down to logic, bits, and logical operations. Computer hardware is made out of logic gates, based on the exact logic that we study in discrete mathematics. Moving up to numbers, you might think you’re programming with real numbers or continuous functions, but the computer is really using discrete approximations of those mathematical abstractions. Furthermore, topics that at first seem like pure mathematical mind games turn out to be incredibly important in computing. Take number theory, for instance. We provide tutorials in basic number theory, modular arithmetic, prime numbers, and more. Working with numbers in this way provides a context we can use for a lot of clever reasoning and problem solving, with an incredibly rich palette for creating proofs, but it also provides the basis for the modern cryptography that is used to protect information in real computing systems. Fun puzzles? Yes! Intellectually stimulating? Yes! Practical? Also yes!
Beyond the direct usefulness and practicality of discrete structures, you will be building skills in clear, precise reasoning. If you’re building something – anything, not just software – and you can’t clearly and precisely explain why it works, you should feel uncomfortable. “It seems OK” isn’t an acceptable answer from any scientist or engineer! Can you explain why your program works? Not just “it passed these tests,” but a more reasoned explanation? This is a vital skill if you care about making reliable creations, and you should certainly care about reliability!
Some students look at this material as separate from what they want to do, which is often to create software. Will you need to write formal proofs as a software developer? Probably not, although you might be surprised. But programs work by executing a series of logical steps, and you will constantly have to think about how that logic works. The skills you develop by writing formal proofs will help you think carefully about how your programs work. Think of it this way: Football players spend a lot of time in the weight room, lifting weights and conditioning, so should they complain that it’s not what they will be doing on the field? Of course not, because they know that the strength they build is useful on the field doing things quite different from what they do in the weight room. It’s the same here: you’re building your logical muscles, and you’ll be a stronger programmer because of it.
Relation to Other CS Topics
Discrete mathematics fits in naturally to a computer science curriculum, related to courses such as programming, data structures, algorithms, theory of computing, and more. A knowledgeable computer science student needs to be able to look at problems from a variety of standpoints, and discrete mathematics is one of the vital standpoints.
Consider making a program to plan a route for a car trip using a map. You obviously need to know how to write programs, so that’s the first course or two in a computer science curriculum. Next, you need to know how to logically represent the problem, including the map – that’s a discrete structure known as a graph. You need to know the fundamental properties of graphs, which is what we study in discrete mathematics. Next, you need to know how to represent that structure in code, which is what you learn in data structures. And finally, you need to know how to efficiently find the shortest route when you’re given that map as a data structure – that’s what you learn in an algorithms class. And given that algorithm, how do you know that it always finds the shortest route? Now you’re back in the realm of reasoning, proofs, and discrete mathematics.
Finding a route to drive is a clear and useful problem to solve with software, and there are a surprising number of layers of knowledge that come into play in order to create a quality solution. If you are a computer science student, hopefully your professors are relating concepts from one class to things you learn in other classes. They’re all interconnected, and all necessary!
Structure of Tutorial Topics
The menu on the left (you may have to open this if you’re on a narrow screen like a phone) and the discrete mathematics landing page both list the topics covered in this set of tutorials.
We start with an introduction, and a review of some basic mathematical concepts such as sets, sequences, relations, and functions.
The following three topics, on logic and proofs, are the core material that serves as the basis for all other topics. Logic covers how to make precise mathematical statements, and proofs are how you reason about these statements. There are several common types of proofs, and we cover all the basic types, with an entire tutorial section covering the particularly important technique of proof by induction.
Beyond proofs, the topics are mostly independent of each other. Inductive definitions are closely related to recursion in programming and inductive proofs, and provide good practice to look at a common mathematical structure: objects that are made up of smaller versions of the same type of object. All our core discrete structures, including natural numbers, graphs, trees, and more, can be defined inductively, and exposing and understanding that structure gives valuable insights.
In the tutorials on number theory, we look at numbers (primarily the natural numbers) and properties we see from basic arithmetic operations of addition up through powering. Most importantly, we look at interesting properties of arithmetic over restricted domains of numbers, called modular arithmetic. Modular arithmetic has some fascinating properties related to prime numbers and some other “pure math” topics, and has important applications in modern cryptography.
When we talk about discrete structures of unbounded size, meaning they can get larger and larger without any pre-set limit, we are often interested in how quickly these structures (or properties of the structures) grow. Our best tool for this is known as asymptotic notation, which we cover in the “Function Growth” tutorials. Asymptotic notation is also the language we use when we talk about the efficiency of programs and algorithms, and while we don’t dwell a lot on algorithms in these discrete mathematics tutorials we will demonstrate some of the basics.
We have mentioned graphs a few times in this introduction, and we have a set of tutorials on graphs, how they model relationships, and various properties of graphs. Many of these properties, such as planarity, colorability, and spanning trees, are very useful in practice, and we will give some glimpses into how these can be used for some important real-world problems.
Finally, we have tutorials on counting and probability theory. Counting is a deceptively simple title, and you may think “I’ve been counting since I was two years old.” Well, you haven’t been counting like this since you were two! We explore how to count the number of ways we can sample or arrange objects, whether we sample with replacement or without, and whether order is significant or not. This can be a confusing topic for many students, so we break this down into the application of some simple counting rules. The probability theory tutorials do depend on the counting tutorials, and are the exception to the “mostly independent topics” of the tutorials. The good news is that once you learn the counting topics, probability theory is mostly just a matter of learning some terminology and context. Most of the problem-solving in our coverage of discrete probability really just comes back to counting though!
If you want to follow these tutorials in a recommended order, all you have to do is click the “Next” link at the bottom of each page. Let’s go!
YouTube
Facebook