Discrete Math › Section A · Introduction and preliminaries › Topic A.1
What is discrete mathematics?
Discrete mathematics studies things that come in separate, countable pieces: people, steps, connections and true-or-false statements. It is the mathematics behind computing, networks and careful proof, and this topic shows the kinds of questions it asks.
Separate and distinct
The word discrete means individually separate and distinct. Compare two questions about a class of students. How tall is each student? A height can be any value in a range, such as 162.4 cm or 162.43 cm, so the possible answers fill a continuous interval. How many siblings does each student have? Now the answers are 0, 1, 2, 3 and so on, with nothing in between: nobody has 1.7 siblings. Calculus is built for the first kind of question. Discrete mathematics is built for the second, where the objects can be listed and counted one at a time.
Discrete versus continuous
Between any two real numbers there are infinitely many others, so an interval such as \([2, 5]\), all the real numbers from 2 to 5, has no gaps. The integers behave differently: after 4 comes 5, and no integer lies between them. Discrete does not mean finite. The natural numbers 0, 1, 2, 3, ... go on for ever, yet each one is separated from the next, so the set is still discrete. Digital computers are discrete machines through and through: every value they store is a pattern of bits, each bit 0 or 1, which is one reason this subject is central to computer science.
Four families of questions
Most problems in an introductory course fall into four families. Counting, or combinatorics, asks how many ways something can happen. Sequences track a list of numbers in order and look for the rule behind it. Symbolic logic studies statements that are true or false and how their truth values combine. Graph theory studies objects joined by connections, such as towns joined by roads. Number theory, discrete probability and the analysis of algorithms belong to the subject too. The next cards solve one small problem from each family and, more importantly, show how each is turned into a precise mathematical model.
Worked example: counting handshakes
Eight people meet, and each pair shakes hands exactly once. How many handshakes take place? 1. Model: a handshake is a pair of different people, and the pair {Ana, Ben} is the same handshake as {Ben, Ana}, so order does not matter. 2. Count ordered pairs first: the first person can be any of 8 and the second any of the other 7, giving \(8 \times 7 = 56\). 3. Each handshake was counted twice, once in each order, so divide by 2: \(56 \div 2 = 28\). 4. Check with a small case: 3 people give \(3 \times 2 \div 2 = 3\) handshakes, and listing them, AB, AC and BC, confirms it.
Worked example: seats in a theatre
A theatre's first row has 12 seats, and each row has 3 more than the row in front of it. There are 20 rows. How many seats are in row 20, and how many in total? 1. Model: the row sizes form a sequence 12, 15, 18, ..., one term per row. 2. Row 20 is 19 steps after row 1, so it has \(12 + 19 \times 3 = 69\) seats. 3. For the total, pair rows from the two ends: row 1 with row 20 gives \(12 + 69 = 81\), row 2 with row 19 gives \(15 + 66 = 81\), and every such pair gives 81. 4. Twenty rows make 10 pairs, so the total is \(10 \times 81 = 810\) seats. 5. Check: the average row holds 40.5 seats, and \(20 \times 40.5 = 810\).
Logic: true or false, nothing between
In logic every statement is either true or false. Here is a puzzle. Ana says, "Ben is lying." Ben says, "Ana and I are both telling the truth." Each of them either always tells the truth or always lies. Suppose Ben tells the truth. Then both are truthful, so Ana's statement must be true, which means Ben is lying: a contradiction. So Ben lies. Then Ana's statement, "Ben is lying", is true, so Ana tells the truth. Check Ben: his claim that both are truthful is false, as a liar's claim must be. Trying a case and following its consequences to an impossibility is a small proof by contradiction.
Graphs: dots and connections
Four villages want a road joining every pair, with no two roads crossing and no bridges. A graph models this: each village is a vertex, drawn as a dot, and each road is an edge, a line joining two vertices. Four vertices need \(4 \times 3 \div 2 = 6\) edges, the same count as handshakes among four people. Draw three villages as a triangle and put the fourth inside it, joined to each corner: all six roads fit without crossing. With five villages and ten roads it cannot be done, a fact proved in the topic Planar graphs. This kind of graph is a network, not the graph of a function.
Why discrete mathematics matters
These puzzles are small, but they stand for real problems. Counting tells a security engineer how many passwords an attacker would have to try. Sequences describe how the running time of a program grows with the size of its input. Logic is the language of circuits, database searches and program checks. Graphs model the internet, social networks, delivery routes and timetables; finding the quickest route between two places on a map is a graph problem. Discrete structures are the tools for building such models, and the next topic, A tour of discrete structures, introduces the main ones.
Answers need reasons
Discrete mathematics asks you to justify answers, not just find them. A formula that works for the first ten cases can fail at the eleventh, so an answer is accepted only when an argument shows that it must hold in every case. Such an argument is a proof, and the logic and proof topics in the next section teach how to write one. A good habit starts now: solve a small version of the problem first, look for the structure behind it, then explain why that structure forces the answer, as the check with 3 people did for the handshakes.
Common mistakes to avoid
First, confusing discrete, meaning separate, with discreet, meaning tactful. Second, thinking discrete means finite: the natural numbers are infinite but discrete. Third, counting each unordered pair twice, as in 56 handshakes instead of 28; always ask whether order matters. Fourth, reading graph as the graph of a function rather than a network of vertices and edges. Fifth, trusting a pattern because it held in a few cases; an answer needs an argument that covers every case.
Key takeaways
Discrete mathematics studies objects that are separate and countable, such as integers, people, statements and connections, rather than continuous quantities, and a discrete set can still be infinite. Its main families of problems are counting, sequences, logic and graphs, with number theory, probability and algorithms close by. Each problem is solved by building a model: unordered pairs for handshakes, a sequence for rows of seats, true-or-false statements for a puzzle, vertices and edges for roads. Answers are justified by proofs that cover every case.
Flashcards
Flashcard
Individually separate and distinct
Test your understanding
Question 1 of 5
Which of these quantities is discrete?
Question 2 of 5
Twelve people each shake hands with every other person exactly once. How many handshakes take place?
Question 3 of 5
Which statement about discrete sets is true?
Question 4 of 5
A garden bed has 5 plants in its first row, and each row has 2 more plants than the one before. How many plants are in row 10?
Question 5 of 5
In graph theory, what is a graph?