Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

PrefaceIntroduction -What is Discrete Mathematics?

As a general description one could say that discrete mathematics is the mathematics that deals with “separated” or discrete sets of objects rather than with continuous sets such as the real line. For example, the graphs that we learn to draw in high school are of continuous functions. Even though we might have begun by plotting discrete points on the plane, we connected them with a smooth, continuous, unbroken curve to form a straight line, parabola, circle, etc. The underlying reason for this is that hand methods of calculation are too laborious to handle huge amounts of discrete data. The computer has changed all of this.

Today, the area of mathematics that is broadly called “discrete” is that which professionals feel is essential for people who use the computer as a fundamental tool. It can best be described by looking at our Table of Contents. It involves topics like sets, logic, and matrices that students may be already familiar with to some degree. In this Introduction, we give several examples of the types of problems a student will be able to solve as a result of taking this course. The intent of this Introduction is to provide an overview of the text. Students should read the examples through once and then move on to Chapter One. After completing their study of discrete mathematics, they should read them over again.

Example.0.3Analog-to-digital Conversion

A common problem encountered in engineering is that of analog-to-digital (a-d) conversion, where the reading on a dial, for example, must be converted to a numerical value. In order for this conversion to be done reliably and quickly, one must solve an interesting problem in graph theory. Before this problem is posed, we will make the connection between a-d conversion and the graph problem using a simple example. Suppose a dial in a video game can be turned in any direction, and that the positions will be converted to one of the numbers zero through seven in the following way. As depicted in Figure .0.4, the angles from 0 to 360 are divided into eight equal parts, and each part is assigned a number starting with 0 and increasing clockwise. If the dial points in any of these sectors the conversion is to the number of that sector. If the dial is on the boundary, then we will be satisfied with the conversion to either of the numbers in the bordering sectors. This conversion can be thought of as giving an approximate angle of the dial, for if the dial is in sector \textit{k}, then the angle that the dial makes with east is approximately \({45k}^{\circ}\).

Analog-Digitial Dial
Figure.0.4Analog-Digitial Dial

Now that the desired conversion has been identified, we will describe a “solution” that has one major error in it, and then identify how this problem can be rectified. All digital computers represent numbers in binary form, as a sequence of 0's and 1's called bits, short for binary digits. The binary representations of numbers 0 through 7 are: \begin{equation*}\begin{array}{c} 0= {000}_{two} = 0 \cdot 4 + 0 \cdot 2 + 0 \cdot 1\\ 1= {001}_{two} = 0 \cdot 4 + 0 \cdot 2 + 1 \cdot 1\\ 2= {010}_{two} = 0 \cdot 4 + 1 \cdot 2 + 0 \cdot 1\\ 3= {011}_{two} = 0 \cdot 4 + 1 \cdot 2 + 1 \cdot 1\\ 4= {100}_{two} = 1 \cdot 4 + 0 \cdot 2 + 0 \cdot 1\\ 5= {101}_{two} = 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1\\ 6= {110}_{two} = 1 \cdot 4 + 1 \cdot 2 + 0 \cdot 1\\ 7= {111}_{two} = 1 \cdot 4 + 1 \cdot 2 + 1 \cdot 1\\ \end{array} \end{equation*}

We will discuss the binary number system in Section 1.4. The way that we could send those bits to a computer is by coating parts of the back of the dial with a metallic substance, as in Figure .0.5. For each of the three concentric circles on the dial there is a small magnet. If a magnet lies under a part of the dial that has been coated with metal, then it will turn a switch ON, whereas the switch stays OFF when no metal is detected above a magnet. Notice how every ON/OFF combination of the three switches is possible given the way the back of the dial is coated.

If the dial is placed so that the magnets are in the middle of a sector, we expect this method to work well. There is a problem on certain boundaries, however. If the dial is turned so that the magnets are between sectors three and four, for example, then it is unclear what the result will be. This is due to the fact that each magnet will have only a fraction of the required metal above it to turn its switch ON. Due to expected irregularities in the coating of the dial, we can be safe in saying that for each switch either ON or OFF could be the result, and so if the dial is between sectors three and four, any number could be indicated. This problem does not occur between every sector. For example, between sectors 0 and 1, there is only one switch that cannot be predicted. No matter what the outcome is for the units switch in this case, the indicated sector must be either 0 or 1, which is consistent with the original objective that a positioning of the dial on a boundary of two sectors should produce the number of either sector.

Analog-Digitial Dial
Figure.0.5Coating scheme for the Analog-Digitial Dial

Is there a way to coat the sectors on the back of the dial so that each of the eight patterns corresponding to the numbers 0 to 7 appears once, and so that between any two adjacent sectors there is only one switch that will have a questionable setting? One way of trying to answer this question is by using an undirected graph called the 3-cube (Figure .0.6). In general, an undirected graph consists of vertices (the circled 0's and 1's in the 3-cube) and the edges, which are lines that connect certain pairs of vertices. Two vertices in the 3-cube are connected by an edge if the sequences of the three bits differ in exactly one position. If one could draw a path along the edges in the 3-cube that starts at any vertex, passes through every other vertex once, and returns to the start, then that sequence of bit patterns can be used to coat the back of the dial so that between every sector there is only one questionable switch. Such a path is not difficult to find; so we will leave it to you to find one, starting at 000 and drawing the sequence in which the dial would be coated.

The 3-cube
Figure.0.6The 3-cube

Many A-D conversion problems require many more sectors and switches than this example, and the same kinds of problems can occur. The solution would be to find a path within a much larger yet similar graph. For example, there might be 1,024 sectors with 10 switches, resulting in a graph with 1,024 vertices. One of the objectives of this text will be to train you to understand the thought processes that are needed to attack such large problems. In Chapter 9 we will take a closer look at graph theory and discuss some of its applications.

One question might come to mind at this point. If the coating of the dial is no longer as it is in Figure .0.5, how would you interpret the patterns that are on the back of the dial as numbers from 0 to 7? In Chapter 14 we will see that if a certain path is used, this “decoding” is quite easy.

The 3-cube and its generalization, the \(n\)-cube, play a role in the design of a multiprocessor called a hypercube. A multiprocessor is a computer that consists of several independent processors that can operate simultaneously and are connected to one another by a network of connections. In a hypercube with \(M=2^n\) processors, the processors are numbered 0 to \(M-1\). Two processors are connected if their binary representations differ in exactly one bit. The hypercube has proven to be the best possible network for certain problems requiring the use of a “supercomputer.” Denning's article in the May-June 1987 issue of “American Scientist” provides an excellent survey of this topic.

Example.0.7Logic Design

Logic is the cornerstone of all communication, whether we wish to communicate in mathematics or in any other language. It is the study of sentences, or propositions, that take on the values true or false, 1 or 0 in the binary system. Its importance was recognized in the very early days of the development of logic (hardware) design, where Boolean algebra, the algebra of logic, was used to simplify electronic circuitry called gate diagrams. Consider the following gate diagram:

A logic diagram
Figure.0.8A logic diagram for \((x_1 \lor (x_1 \land x_2))\land (x_1 \lor \bar{x_3})\)

The symbols with heavy line borders in this diagram are called a gates, each a piece of hardware. In Chapter 13 we will discuss these circuits in detail. Assume that this circuitry can be placed on a chip which will have a cost dependent on the number of gates involved. A classic problem in logic design is to try to simplify this circuitry to one containing fewer gates. Indeed, the gate diagram can be reduced to the following diagram.

A reduced logic diagram
Figure.0.9A reduced logic diagram for \(x_1 \lor (x_2 \land \bar{x_3})\)

The result is a less costly chip. Since a company making computers uses millions of chips, we have saved a substantial amount of money.

This use of logic is only the “tip of the iceberg.” The importance of logic for computer scientists in particular, and for all people who use mathematics, cannot be overestimated. It is the means by which we can think and write clearly and precisely. Logic is used in writing algorithms, in testing the correctness of programs, and in other areas of computer science.

Example.0.10Recurrence Relations

Suppose two students miss a class on a certain day and borrow the class notes in order to obtain copies. If one of them copies the notes by hand and the other walks to a “copy shop,” we might ask which method is more efficient. To keep things simple, we will only consider the time spent in copying, not the cost. We add a few more assumptions: copying the first page by hand takes one minute and forty seconds (100 seconds); for each page copied by hand, the next page will take five more seconds to copy, so that it takes 1:45 to copy the second page, 1:50 to copy the third page, etc.; photocopiers take five seconds to copy one page; walking to the “copy shop” takes ten minutes, each way.

One aspect of the problem that we have not specified is the number of pages to be copied. Suppose the number of pages is \(n\), which could be any positive integer. As with many questions of efficiency, one method is not clearly better than the other for all cases. Since the only variable in this problem is the number of pages, we can simply compare the copying times for different values of \textit{ n}. We will denote the time it takes (in seconds) to copy \textit{ n} pages manually by \(t_h(n)\), and the time to copy n pages automatically by \(t_a(n)\). Ideally, we would like to have formulas to represent the values of \(t_h(n)\) and \(t_a(n)\). The process of finding these formulas is an important one that we will examine in Chapter 8. { }The formula for \(t_a(n)\) is not very difficult to derive from the given information. To copy pages automatically, one must walk for twenty minutes (1,200 seconds), and then for each page wait five seconds. Therefore, \(t_a(n)=1200 + 5n\).

The formula for \(t_h(n)\) isn't quite as simple. First, let \(p(n)\) be the number of seconds that it takes to copy page \textit{ n}. From the assumptions, \(p(1) = 100\), and if \(n\) is greater than one, \(p(n) = p(n-1) + 5\). The last formula is called a \textit{ recurrence relation}. We will spend quite a bit of time discussing methods for deriving formulas from recurrence relations. In this case \(p(n) = 95 + 5n\). Now we can see that if \(n\) is greater than one, \[t_h(n)= p(1)+p(2)+\cdots +p(n)= t_h(n-1)+p(n)=t_h(n-1)+5 n+95\] This is yet another recurrence relation. The solution to this one is \(t_h(n)=97.5 n+2.5 n^2\).

Now that we have these formulas, we can analyze them to determine the values of \(n\) for which hand copying is most efficient, the values for which photocopying is most efficient, and also the values for which the two methods require the same amount of time.

What is Discrete Structures?

So far we have given you several examples of that area of mathematics called discrete mathematics. Where does the “structures” part of the title come from? We will look not only at the topics of discrete mathematics but at the structure of these topics. If two people were to explain a single concept, one in German and one in French, we as observers might at first think they were expressing two different ideas, rather than the same idea in two different languages. In mathematics we would like to be able to make the same distinction. Also, when we come upon a new mathematical structure, say the algebra of sets, we would like to be able to determine how workable it will be. How do we do this? We compare it to something we know, namely elementary algebra, the algebra of numbers. When we encounter a new algebra we ask ourselves how similar it is to elementary algebra. What are the similarities and the dissimilarities? When we know the answers to these questions we can use our vast knowledge of basic algebra to build upon rather than learning each individual concept from the beginning.