Discrete Mathematics

Overview

Discrete mathematics is the study of mathematical structures that are separate and distinct, rather than continuous. You can “count” the objects in discrete mathematics; they are not smoothly connected like points on a line or values on a curve in calculus.

This subject underlies many areas of modern technology and theoretical computer science. Whenever you deal with individual steps in an algorithm, bits in a computer, or connections in a network, you are operating in the world of discrete mathematics.

In this course, the Discrete Mathematics part will focus on three major themes:

• Logic and Proof
• Combinatorics
• Graph Theory

Each of these has its own chapter later, where we will go into detail. Here, the goal is to explain what is special about discrete mathematics as a whole, and how these topics fit together.

What Makes Mathematics “Discrete”?

In everyday life, you encounter both discrete and continuous quantities.

• Discrete: number of students in a class, number of messages in your inbox, the result of a dice roll.
• Continuous: your height, time passing, distance traveled by a car, temperature during the day.

In discrete mathematics, we study structures built from “separate” pieces. Examples include:

• Finite sets: such as $\{1, 2, 3, 4\}$.
• Sequences of symbols: like a password A9k2!.
• Collections of connections: such as a network of friends on a social media platform.

These structures do not depend on infinitesimal changes or smooth variation. Instead, we count, list, and analyze combinations and relationships.

Key features of discrete mathematics:

• Often deals with finite or countable sets of objects.
• Emphasizes counting (how many ways?), arrangement (in what order?), and connection (who is linked to whom?).
• Naturally suited to tasks a computer performs step by step.

How Discrete Mathematics Relates to the Rest of the Course

Many other parts of this course (like calculus or real numbers) focus on continuous mathematics. Discrete mathematics complements them by focusing on different kinds of questions.

Some connections:

• Sets and logic: Earlier, you encounter sets and basic logical ideas. Discrete mathematics builds heavily on these.
• Number theory: Uses many discrete ideas, such as divisibility and counting arguments.
• Probability and statistics: Discrete probability (like dice or cards) uses combinatorics to count possible outcomes.
• Algorithms and linear algebra: While algorithms are not a dedicated chapter here, discrete mathematics provides the language to describe processes, decisions, and networks that algorithms work on. Vectors and matrices can represent graphs and discrete structures.

You do not need advanced background to begin discrete mathematics, but familiarity with basic sets, logic, and arithmetic is useful.

Central Themes in Discrete Mathematics

1. Logic and Proof (What We Do With Statements)

In the Logic and Proof part of this course, you will study:

• How to combine simpler statements using logical words such as “and”, “or”, “not”, and “if … then …”.
• How to evaluate whether a composite statement is always true, sometimes true, or false.
• How to construct correct mathematical arguments, called proofs.

Logic in discrete mathematics is precise. Every statement must have a clear meaning, and there are strict rules for moving from assumptions to conclusions.

Proof techniques you will see later (like direct proof, proof by contradiction, and mathematical induction) are essential tools throughout mathematics, but discrete mathematics uses them especially often. For example, when proving a property for all positive integers, induction is a common method.

In this introductory chapter to Discrete Mathematics, it is important to recognize:

• Logic turns “informal reasoning” into a formal, step-by-step process.
• Proofs are not just for advanced mathematics; they appear in basic results about integers, sets, and graphs.
• Discrete mathematics provides many simple yet rich examples to practice proof techniques (such as properties of even and odd numbers, or simple properties of graphs).

2. Combinatorics (Counting and Arranging)

Combinatorics is the part of discrete mathematics concerned with counting and arranging objects. The core idea is to answer questions such as:

• How many different passwords of a certain type are possible?
• In how many ways can you arrange a set of objects?
• How many ways can you choose a group from a larger set?

Later, in the Combinatorics chapter, you will see specific methods like permutations and combinations, but here we simply note what role combinatorics plays in discrete mathematics:

• It provides tools to count possibilities without listing them one by one.
• It underpins discrete probability, where we often need to know the number of possible outcomes.
• It appears naturally in everyday contexts like scheduling tasks, organizing tournaments, and planning routes.

Discrete mathematics focuses on these finite arrangements and selections rather than continuous ranges.

3. Graph Theory (Networks of Connections)

Graph theory studies networks made of:

• Points (often called vertices or nodes).
• Links between them (called edges).

Examples of graphs include:

• A social network, where people are vertices and friendships are edges.
• A map of cities and roads.
• A diagram of how web pages link to each other.

Graphs are discrete structures: vertices and edges are separate objects, and we count and compare them.

Later, the Graph Theory chapter will formalize these ideas. For now, understand that:

• Graphs represent relationships between discrete objects.
• Many practical problems—such as finding the shortest path, connecting locations efficiently, or checking whether a network is fully connected—are graph problems.
• Graph theory often combines ideas from logic (to describe properties precisely) and combinatorics (to count or estimate configurations).

Why Discrete Mathematics Is Important

Discrete mathematics is foundational for many modern fields:

• Computer science and programming:
• Algorithms operate on discrete steps and data structures.
• Logic underlies conditional statements (if, and, or, not).
• Combinatorics helps analyze how long algorithms might take (how many possibilities must be checked).
• Graph theory helps model networks, data relationships, and communication paths.
• Cryptography:
• Relies on number theory and combinatorial structures to secure information.
• Uses discrete concepts like modular arithmetic and combinatorial designs.
• Network design and communications:
• Graphs model connections between computers, routers, and communication channels.
• Discrete optimization problems help design efficient networks.
• Operations research and scheduling:
• Many scheduling, allocation, and routing problems are discrete.
• Combinatorial methods help to explore and optimize possible arrangements.

Within mathematics, discrete topics also give clear, small-step examples for practicing proof techniques and logical reasoning.

Ways of Thinking in Discrete Mathematics

Discrete mathematics encourages a particular style of thinking:

• Step-by-step reasoning:
• Problems are often solved by breaking them into discrete steps and cases.
• You may consider different possibilities systematically (case analysis).
• Structural thinking:
• You examine how objects are built from parts: nodes and edges, steps in a sequence, choices in a decision tree.
• You focus on patterns and structures rather than just numbers.
• Exact counting:
• Instead of approximating, you often want exact counts: the precise number of outcomes, paths, or arrangements.
• Proof-based reasoning:
• You justify why a pattern always works, not just that it seems to work in examples.
• Discrete structures often allow proofs using simple, concrete arguments.

These habits will be useful throughout the rest of mathematics, not only in the discrete topics themselves.

What to Expect in the Discrete Mathematics Chapters

The Discrete Mathematics part of the course is organized into three focused chapters, each building on these general ideas.

1. Logic and Proof
• Formal statements (propositions) and logical operations.
• Ways of showing statements are logically equivalent or follow from each other.
• Common proof techniques and how to structure a clear argument.
2. Combinatorics
• Systematic counting of arrangements and selections.
• Fundamental counting ideas that lead to permutations and combinations.
• Simple applications to problems involving choosing, ordering, and distributing objects.
3. Graph Theory
• Basic definitions of graphs, vertices, and edges.
• Simple properties like paths, cycles, and connectedness.
• Basic examples of graph problems and how to describe them mathematically.

Each of these chapters will assume you understand what discrete mathematics is broadly about from this chapter, and then focus on its own specific concepts and methods.