maths.free › Discrete Math & Logic › 1. Introduction and Preliminaries › What is Discrete Mathematics?

What is Discrete Mathematics?

discrete / dis'krët. Adjective: Individually separate and distinct. Synonyms: separate - detached - distinct - abstract. Defining discrete mathematics is hard because defining mathematics is hard. What is mathematics?

What is Discrete Mathematics?

discrete / dis'krët.

Adjective: Individually separate and distinct.

Synonyms: separate - detached - distinct - abstract.

Defining discrete mathematics is hard because defining mathematics is hard. What is mathematics? The study of numbers? In part yes, but you also study functions and lines and triangles and parallelepipeds and vectors and . Or perhaps you want to say that mathematics is a collection of tools that allow you to solve problems. What sort of problems? Well, those that involve numbers, functions, lines, triangles, . Whatever your conception of what mathematics is, try applying the concept of discrete to it, as defined above. Some math fundamentally deals with stuff that is individually separate and distinct.

In an algebra or calculus class, you might have found a particular set of numbers (perhaps they constitute the range of a function). You would represent this set as an interval: \([0,\infty)\) is the range of \(f(x) = x^2\) since the set of outputs of the function are all real numbers 0 and greater. This set of numbers is NOT discrete. The numbers in the set are not separated by much at all. In fact, take any two numbers in the set and there are infinitely many more between them that are also in the set.

Discrete math could still ask about the range of a function, but the set would not be an interval. Consider the function that gives the number of children of each person reading this. What is the range? I'm guessing it is something like \(\{0, 1, 2, 3, 4\}\). Maybe 5 or 6 is in there too.Even larger natural numbers for old ladies who live in shoes. But certainly nobody reading this has 1.32419 children. This output set is discrete because the elements are separate. The inputs to the function also form a discrete set because each input is an individual person.

There are many discrete mathematical objects besides sets of numbers; we will introduce some of these in . Studying these discrete structures is the main focus of discrete mathematics and this book. However, the reason we want to study these structures is because they provide a way to model real-world problems.Many of the problems discussed in this book are admittedly contrived and clearly fictional, but hopefully you will see how these toy problems can be generalized to actually represent problems that people would care about in reality.

To get a feel for the subject, let's consider the types of problems you solve in discrete math. Here are a few simple examples:

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (2)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Right now, how would you describe what discrete mathematics is about, if you were telling your friends about the class you are in? Write one or two sentences.

  2. What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.

Symbols used here

\infty
infinity
Not a number: "grows without bound" in limits and intervals.
\sup,\ \inf
supremum, infimum
Least upper bound, greatest lower bound.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
a \bmod n
remainder
What is left after dividing a by n.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Sankhani wanu

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Zambiri pa Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions