DISCREATE MATHEMATICS: A BRIEF INTRODUCTION

What is Discrete Mathematics?

 dis·crete / 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, 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? Okay, 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 (maybe the set of numbers in the range of a function). You would be the range of f x x2 since the represent this set as an interval: 0 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 tall. In fact, take any two numbers in the set and there are infinitely many more between them which 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 which gives the number of children of each person reading this. 

What is the range? I’m guessing it is something like 0123. Maybe 4 is in there too. But certainly, there is nobody reading this that 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. One way to get a feel for the subject is to consider the types of problems you solve in discrete math. Here are a few simple examples: 1 2 0.

Introduction and Preliminaries Investigate! Note: Throughout the text you will see Investigate! activities like this one. Answer the questions in these as best you can to give yourself a feel for what is coming next.

1.The most popular mathematician in the world is throwing a party for all of his friends. As a way to kick things off, they decide that everyone should shake hands. 

Assuming all 10 people at the party each shake hands with every other person (but not themselves, obviously) exactly once, how many handshakes take place?

2. At the warm-up event for Oscar’s All Star Hot Dog Eating Contest, Al ate one hot dog. Bob then showed him up by eating three hot dogs. Not to be outdone, Carl ate five. This continued with each contestant eating two more hot dogs than the previous contestant. How many hot dogs did Zeno (the 26th and final contestant) eat? How many hotdogs were eaten all together? 

3. After excavating for weeks, you finally arrive at the burial chamber. The room is empty except for two large chests. On each is carved a message (strangely in English): If this chest is empty, then the other chest’s message is true. This chest is filled with treasure, or the other chest contains deadly scorpions. You know exactly one of these messages is true. 

What should you do?

4. Back in the days of yore, five small towns decided they wanted to build roads directly connecting each pair of towns. While the towns had plenty of money to build roads as long and as winding as they wished, it was very important that the roads not intersect with each other (as stop signs had not yet been invented). Also, tunnels and bridges were not allowed.

Is it possible for each of these towns to build a road to each of the four other towns without creating any intersections? Attempt the above activity before proceeding One reason it is difficult to define discrete math is that it is a very broad description which encapsulates a large number of subjects. 

In this course 0.1. What is Discrete Mathematics?  

we will study four main topics: combinatorics (the theory of ways things combines; in particular, how to count these ways, sequences, symbolic logic, and graph theory. 

However, there are other topics that belong under the discrete umbrella, including computer science, abstract algebra, number theory, game theory, probability, and geometry (some of these, particularly the last two, have both discrete and non-discrete variants). 

Ultimately the best way to learn what discrete math is about is to do it. Let’s get started! Before we can begin answering more complicated (and fun) problems, we must lay down some foundation. We start by reviewing mathematical statements, sets, and functions in the framework of discrete mathematics

These are statements (in fact, atomic statements):

• Telephone numbers in the USA have 10 digits.
• The moon is made of cheese
• 42is a perfect square. 
• Every even number greater than 2 can be expressed as the sum of two primes. 

Atomic and Molecular Statements

A statement is any declarative sentence which is either true or false. A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular.

The reason the sentence “3 + x 12” is not a statement is that it contains a variable.

Depending on what x is, the sentence is either true or false, but right now it is neither. 

One way to make the sentence into a statement is to specify the value of the variable in some way. This could be done by specifying a specific substitution, for example, “3 + x 12 where x 9,” which is a true statement.

Or you could capture the free variable by quantifying over it, as in, “for all values of x, 3 + x 12,” which is false. 

We will discuss quantifiers in more detail at the end of this section. 

You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives. For example, this is a molecular statement: 

Telephone numbers in the USA have 10 digits and 42 is a perfect square

Note that we can break this down into two smaller statements. 

The two shorter statements are connected by an “and.” We will consider 5 connectives: “and” (Sam is a man and Chris is a woman), “or” (Sam is a manor Chris is a woman), “if..., then...” (if Sam is a man, then Chris is a woman), “if and only if” (Sam is a man if and only if Chris is a woman), and “not” (Sam is not a man). 

The first four are called binary connectives (because they connect two statements) while “not” is an example of a unary connective (since it applies to a single statement).

These molecular statements are of course still statements, so they must be either true or false. The absolutely key observation here is that which truth value the molecular statement achieves is completely determined by the type of connective and the truth values of the parts. We do not need to know what the parts actually say, only whether those parts are true or false. So to analyze logical connectives, it is enough to consider propositional variables (sometimes called sentential variables), usually capital letters in the middle of the alphabet: P,Q,R,S,.... 

We think of these as standing in for (usually atomic) statements, but there are only two values the variables can achieve: true or false.

We also have symbols for the logical connectives: ∧, ∨, →, ↔, ¬

The truth value of a statement is determined by the truth value(s) of its part(s), depending on the connective.

         

Note that for us or is the inclusive or (and not the sometimes used exclusive or) meaning that P ∨Q is in fact true when both P and Q are true. 

As for the other connectives, “and” behaves as you would expect, as does negation. 

The biconditional (if and only if) might seem a little strange, but you should think of this as saying the two parts of the statements are equivalent in that they have the same truth value. 

This leaves only the conditional P → Q which has a slightly different meaning in mathematics than it does in ordinary usage.

However, implications are so common and useful in mathematics, that we must develop fluency with their use, and as such, they deserve their own subsection.

Easily the most common type of statement in mathematics is the implication. Even statements that do not at first look like they have this form conceal an implication at their heart. Consider the Pythagorean Theorem. Manya college freshman would quote this theorem as “a2 +b2 = c2.” This is absolutely not correct. For one thing, that is not a statement since it has three variables in it. Perhaps they imply that this should be true for any values of the variables?

So, 12 + 52 = 22??? How can we fix this? Well, the equation is true as long as a and b are the legs of a right triangle and c is the hypotenuse. In other words:

This is a reasonable way to think about implications: our claim is that the conclusion (“then” part) is true, but on the assumption that the hypothesis (“if” part) is true. We make no claim about the conclusion in situations when the hypothesis is false.2

Still, it is important to remember that an implication is a statement, and therefore is either true or false. The truth value of the implication is determined by the truth values of its two parts. To agree with the usage above, we say that an implication is true either when the hypothesis is false, or when the conclusion is true. This leaves only one way for an implication to be false: when the hypothesis is true and the conclusion is false.

It is important to understand the conditions under which an implication is true, not only to decide whether a mathematical statement is true, but also in order to prove that it is.

Proofs might seem scary (especially if you have had a bad high school geometry experience), but all we are really doing is explaining—very carefully—why a statement is true.

If you understand the truth conditions for an implication, you already have the outline for a proof.

Perhaps a better way to say this is that, to prove a statement of the form $P\to QP\; \backslash rightarrow\; Q$ directly, you must explain why $QQ$ is true, but you get to assume $PP$ is true first.

After all, you only care about whether $QQ$ is true in the case that $PP$ is as well.

This sort of argument shows up outside of math as well. If you ever found yourself starting an argument with “hypothetically, let’s assume . . . ,” then you have attempted a direct proof of your desired conclusion. An implication is a way of expressing a relationship between two statements. It is often interesting to ask whether there are other relationships between the statements. Here we introduce some common language to address this question.

It would be nice to use variables in our mathematical sentences. For example, suppose we wanted to claim that if n is prime, then n +7 is not prime. This looks like an implication. I would like to write something like

where P(n) means “n is prime.” But this is not quite right. For one thing, because this sentence has a free variable (that is, a variable that we have not specified anything about), it is not a statement. A sentence that contains variables is called a predicate.

Now, if we plug in a specific value for n, we do get a statement. In fact, it turns out that no matter what value we plug in for n, we get a true implication in this case. What we really want to say is that for all values of n, if n is prime, then n +7 is not. We need to quantify the variable.

Although there are many types of quantifiers in English (e.g., many, few, most, etc.) in mathematics we, for the most part, stick to two: existential and universal.

As with all mathematical statements, we would like to decide whether quantified statements are true or false. Consider the statement

                                                                ∀x∃y(y < x)

You would read this, “for every x there is some y such that y is less than x.” Is this true? The answer depends on what our domain of discourse is: when we say “for all” x, do we mean all positive integers or all real numbers or all elements of some other set? Usually, this information is implied. In discrete mathematics, we almost always quantify over the natural numbers, 0, 1, 2, . . . , so let’s take that for our domain of discourse here.

For the statement to be true, we need it to be the case that no matter what natural number we select, there is always some natural number that is strictly smaller. Perhaps we could let y be x −1? But here is the problem: what if x 0? Then y −1 and that is not a number! (in our domain of discourse). Thus we see that the statement is false because there is a number which is less than or equal to all other numbers. In symbols,

                                                                       ∃x∀y(y ≥ x)