Discrete Mathematics: Introduction and Roadmap

If you have been following the site lately, you have probably noticed that the articles have been devoted to more fundamental aspects of computer science. From the internal organization of components to the logical formalism that guides the design of circuits.

In this article, I will lay out a roadmap of the upcoming content so that I can later use it as a point of unification for the ideas. I will also give a bit more context and the reasons for the choice of topics that I have been making recently and that I intend to keep in the near future.

Relating theory and practice

#

The previous articles, as I mentioned, cover fundamental aspects of computer science. However, unlike more academic approaches, I tried whenever possible to include more practical aspects. For example, with code snippets in programming languages so that the reader can understand the consequences of the more abstract aspects. Since Python is the language I am most familiar with, I usually use it to make this link between theory and practice. But I try to write in a way that lets the reader see that the language is just a tool and can apply the concepts in any other.

In the next articles, I will follow this practice of adding practical aspects to content that is usually approached in a fundamentally theoretical way, as if it were closed in on itself. The next target of this approach will be Discrete Mathematics.

Discrete mathematics

#

Discrete mathematics is the part of Mathematics devoted to the study of discrete objects and structures, that is, finite or countably infinite ones (discrete means that it is made up of distinct elements, disconnected from one another).

The problems that discrete mathematics addresses include:

• In how many ways can we choose a valid password for a computer?
• What is the probability of winning the lottery?
• What is the shortest path between two cities for a given transportation system?
• How can we sort a list of integers in ascending order?
  • In how many steps can we do this sorting?
• How can we design a circuit to add two integers?

These questions can be grouped into three major types of problems:

• Existence problems - Is there an arrangement of objects from a given set satisfying a certain property?
• Counting and enumeration problems - How many arrangements (configurations) of this type exist?
• Optimization problems - Of all the possible configurations, which is the best according to a certain criterion?

To make the study of these problems easier, we divide discrete mathematics into fields of study. Among these fields we have:

• Logic
• Set theory
• Functions
• Recurrence relations
• Combinatorics
• Graphs

Generally speaking, discrete mathematics is used when we count objects, when we study relations between finite sets, and when we analyze processes (algorithms) involving a finite number of steps.

Since the second half of the 20th century it has become a very important discipline of Mathematics because, in computers, information is stored and manipulated in a discrete way.

Upcoming series on the site

#

Logic already has articles here on the site: Logic for programmers, Boolean Algebra and Simplifying Logic Functions. Functions do not get a series of their own: they appear as a tool throughout the others, as in the bijection that defines graph isomorphism. For the remaining fields, the upcoming articles will be grouped into four series:

• The Language of Sets: set theory
• From Base Case to Infinity: mathematical induction and recurrence relations
• The Art of Counting: combinatorics
• The Mathematics of Connections: graphs

The links above point to the page of each series. All four are complete, with 28 articles in total.

The series are not independent: some use tools from the others. The diagram below shows these dependencies. Sets and Induction do not depend on each other, and Graphs, which builds on the other three, closes the path:

graph LR
    CONJ["The Language of Sets
set theory"]
    IND["From Base Case to Infinity
induction and recurrence"]
    CONT["The Art of Counting
combinatorics"]
    GRAF["The Mathematics of Connections
graphs"]

    CONJ --> CONT
    IND --> CONT
    CONJ --> GRAF
    IND --> GRAF
    CONT --> GRAF

Going back to the questions from the beginning, here is where each one finds its answer:

Origin of the series and inspiration for the material

#

I have already covered here on the site a bit about my background, saying that I am pursuing a second degree, in Computer Systems at CEDERJ. Follow the previous link for details.

One of the courses in the program has the pompous name of Fundamentals of Algorithms for Computing. But its syllabus is purely discrete mathematics. The course was very well taught, but it lacked a bit of practical applications in everyday programming. And the material is quite old. So I decided to use the material as inspiration and build a more modern and applied view.

The care I took when turning my notes into articles is the same I described, in more detail, in the introduction to the Inside the Computer series. In short:

• I have no connection with CEDERJ other than as a student, and the articles are independent of the course material: they were written for anyone interested in the topic and are not meant to replace it.
• Nothing was copied from the slides, neither passages nor figures. The figures were recreated with Draw.io, Mermaid, LaTeX or Python, created from scratch or generated by AI (and, in that case, they carry the tool’s watermark). Some of the examples are inspired by the course material or by reference books, with adaptations; others are original.
• The articles go beyond the syllabus: they bring examples in Python and SQL and more recent information, because the course material is old. The criticism, on this point, is aimed at the institution, which does not invest in updating it, and not at the professors who produced it.

For those who are curious, here are the course slides. And also the distance-learning activities and the exams from recent years. All of these links are from a Google Drive maintained by the program’s Student Association, which I am not part of.

The same Student Association made the videos from the study platform available on YouTube, in this playlist. The reason is the platform’s instability, which constantly harms students. With the videos on YouTube, the chance of them going offline drops drastically.

I have already written a little about CEDERJ and the issue of outdated materials in another article when I was starting a series on computer organization. I recommend reading it if you are not familiar with the institution and want more details.

Finally, when I wanted to go deeper into some subject, I used the book Fundamentos matemáticos para a ciência da computação: matemática discreta e suas aplicações, by Judith L. Gersting, the Brazilian edition of Mathematical Structures for Computer Science. Another classic reference in the field, and one of the most widely adopted textbooks, is Discrete Mathematics and Its Applications, by Kenneth H. Rosen, which also has a Portuguese edition.

Prerequisites

#

None. The articles start from zero and build each concept from the definition. Basic familiarity with natural numbers and integers is enough.

For those reading on the day this article was published, the first article of the first series comes out tomorrow. See you then!