Skip to content
Tutorials Center
My learning

Topics

Lesson 1 of 68 Β· Getting Started

What Is Discrete Mathematics?

Discover what discrete mathematics is, how it differs from calculus, where it powers software, and how to explore proofs and notation by running Python.

Discrete mathematics is the mathematics of things you can count one by one: whole numbers, yes/no statements, collections of objects, networks of dots and lines. It is the math underneath every program you have ever written. A loop that runs ten times, a database table with a million rows, a password hash, a route between two cities: each one is a discrete object, and discrete mathematics gives you the language and the tools to reason about it precisely.

This course teaches the subject with Python as a lab bench. Instead of only reading a definition, you will run it, break it, and compare it with a hand-made proof. By the end you will be able to read the notation in algorithms papers, count possibilities without listing them, prove that a loop is correct, and understand why modern cryptography works.

Discrete versus continuous

Calculus studies quantities that change smoothly: the position of a falling ball, the temperature in a room. Between any two values there is always another one. Discrete mathematics studies quantities that jump. Between 3 apples and 4 apples there is no "3.5 apples" that makes sense, and between the states "logged in" and "logged out" there is nothing at all.

Two kinds of mathematics

Continuous Smooth values, such as time, distance and temperature.
Discrete Separate values, such as counts, states and objects.

Computers store everything in discrete form, even when they imitate smooth change.

1 / 2

This does not mean the two worlds never meet. A computer simulates a smooth curve with a list of numbers, and a sum of many tiny pieces approximates an integral. But whenever you ask "how many?", "is it possible?", "what is the fastest way?" or "is this always true?", you are in discrete territory.

Where it shows up in software

You do not need to look far. Here are four everyday places:

  • Algorithms. How long does a nested loop take as the input grows? Counting the steps of an algorithm is a counting problem, and solving the recurrence for a recursive function is a discrete math exercise. See Big O for the practical side.
  • Databases. A table is a relation, which is a set of tuples. A join is a Cartesian product filtered by a condition. Query optimizers rely on logical equivalences to rewrite your SQL into a faster form.
  • Cryptography. Public-key encryption depends on modular arithmetic and the difficulty of factoring large integers. You will build a toy version in a later lesson.
  • Networks. Roads, friendships, web links and packet routes are graphs. Finding a shortest path or checking whether everyone is connected are classic graph problems.

Other places include compilers (automata and grammars), version control (a commit history is a directed graph), scheduling (graph coloring) and machine learning (probability and counting).

A map of this course

The chapters build on each other, but each also stands on its own once you know the basics.

The path through this course

Logic Statements, truth tables and quantifiers.
Sets and functions Relations, orders and cardinality.
Proofs Direct, contradiction and induction.
Number theory Primes, gcd and modular arithmetic.
1 / 2

Python as a laboratory

A good habit in discrete math is to test a claim on small cases before trying to prove it. Python makes that cheap. Suppose someone tells you that the sum of the first n odd numbers is always a perfect square. You can check it in a few lines.

Python Test a conjecture on small cases

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every row prints True, and the totals are 1, 4, 9, 16, and so on: the n-th total is n squared. That is evidence, not proof. Eight cases cannot cover infinitely many numbers. A proof, which you will learn to write in How Proofs Work and Mathematical Induction, explains why it holds for every n. Experiments tell you what to try to prove; proofs tell you it is really true.

Experiments can also kill a false claim quickly. A single counterexample is enough. Consider the claim "n squared plus n plus 41 is prime for every whole number n":

Python Find a counterexample

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The formula produces primes for n from 0 up to 39, which looks convincing, and then fails at n = 40, where the value is 1681, which equals 41 times 41. Forty successes proved nothing.

How to read proofs and notation

Mathematical writing is compressed. A few habits make it readable:

  1. Read definitions slowly. Every word is chosen on purpose. "Even" means "equals 2k for some integer k", and later arguments use exactly that.
  2. Translate symbols into code. A capital sigma is a loop that adds. The symbol for "for all" is a loop that checks every item. The next lesson, Mathematical Notation and Python, makes this dictionary explicit.
  3. Find the claim, then the strategy. A proof usually states what will be shown and how: "by contradiction", "by induction on n", "by cases". Knowing the plan helps you follow each step.
  4. Try an example. If a statement says "for every graph", draw a tiny graph and check each line of the proof against it.
  5. Ask what would break. Remove one assumption and see which step fails. That shows you why the assumption is there.

When you meet an unfamiliar symbol, write down one concrete example in Python. A symbol you can run is a symbol you understand.

What you need to start

You need comfortable high-school algebra and basic Python: variables, loops, functions, lists and if statements. If you want a refresher, the Python comprehensions lesson and the sets lesson cover the two features you will use most. No calculus is required.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. Which quantity is naturally discrete?

    A count of users is made of separate whole values. Temperature, position and elapsed time can take any value in a range, so they are continuous.
  2. 2. You test a formula for n = 1 to 1000 and it always works. What can you conclude?

    Testing builds confidence and suggests what to prove, but it cannot cover infinitely many cases. The expression n squared plus n plus 41 works for 40 values and still fails.
  3. 3. How many counterexamples are needed to disprove a claim of the form 'for every n, P(n) holds'?

    One value of n where P(n) is false is enough to show the universal claim is false.
  4. 4. Which part of software relies most directly on modular arithmetic?

    Schemes such as RSA are built on arithmetic with remainders and on the difficulty of factoring large numbers.

Summary

  • Discrete mathematics studies countable, separate objects: integers, sets, statements, graphs.
  • It underlies algorithms, databases, cryptography, networks and compilers.
  • The course moves from logic and sets through proofs, number theory, counting, graphs and computation.
  • Use Python to test conjectures and find counterexamples, then use proofs to establish truth for all cases.
  • Read mathematical text by studying definitions, translating symbols into code, and checking small examples.

Next: Mathematical Notation and Python, a dictionary between math symbols and code.