1.1 What Discrete Math Studies

This is the starting point for the entire course. We do not assume that you already know sets, logic, or proof. This section builds four basic ideas—object, state, model, and discrete—from which later notation will grow.

By the end of the section, you should be able to:

• Decide whether a simple question is better served by a discrete or continuous model.

• State exactly which information a model preserves.

• Break a small real system into finite state variables.

• Identify information lost during discretization instead of confusing a model with reality.

Begin without formulas. Imagine standing in front of an elevator whose display reads “3.” At least three different levels are involved:

• The object is the thing under study, such as this elevator.

• A state is one distinguishable condition of the object, such as “displaying floor 3.”

• A model is the information we retain to answer a question. If passengers only need the current floor, a floor number may be sufficient.

The physical elevator also has height, speed, vibration, and motor temperature. Their absence from the model does not make them unreal; it means the current question does not require them.

Discrete mathematics studies structures made from distinguishable objects and the rules connecting those objects. “Discrete” does not mean disconnected or unimportant. It means that states can be distinguished, enumerated, or counted.

An elevator is on floor 3 or floor 4. Two devices are connected or not connected. A password contains eight characters. A computer network contains twelve links. These are discrete states. The state space need not be small, but each state has a meaningful boundary.

“Countable” does not necessarily mean finite. The integers $0,1,2,3,\ldots$ never end, but there is a procedure for listing them one after another. Such a collection is called countable. By contrast, the real numbers between 0 and 1 contain endlessly finer intermediate values and cannot be listed in the same way. Keep only this intuition for now; later material can treat infinite sets more carefully.

Turning continuous phenomena into discrete states

Real systems often contain continuous and discrete quantities at the same time. An idealized temperature varies continuously through an interval, while a thermostat may display only whole degrees. An elevator’s physical height changes continuously, while passengers see a floor number.

Do not decide merely by asking whether something is written as a number. Floor labels and temperature readings are both numeric, but their meanings differ:

A continuous model permits intermediate values between two different values. Between $20.1$ and $20.2$, for example, lies $20.15$. A discrete model first specifies allowed states, such as a thermostat storing only 20 or 21.

Discretization represents a detailed input with finite or countable states. Threshold classification is one of the simplest examples.

Let $x$ denote a sensor reading and let $t$ denote a chosen threshold. The notation $q_t(x)$ means “the result of processing input $x$ with threshold $t$.” Only two results are allowed, 0 and 1. The following piecewise formula simply places two ordinary-language rules together:

• If $x<t$, output 0.

• If $x\ge t$, output 1. The symbol $\ge$ means “greater than or equal to.”

This model preserves whether the reading reaches a threshold and discards precise differences within each class. Both $2.1$ and $9.7$ might become 1. A discrete model is not reality itself; it is information retained for a particular family of questions.

Work through one trace. Choose threshold $t=2$ and process inputs $1.2,1.7,2.1,2.4$ in order:

The four inputs become bit string 0011. A bit is a position that can hold only 0 or 1. The example also exposes a boundary case: an input exactly equal to 2 produces 1 because the rule uses $x\ge t$.

Changing the sample count changes when the signal is observed. Moving the threshold changes where state boundaries lie. Either operation may change the final bit string. More samples do not automatically create a better model, because purpose, noise, and storage cost also matter.

Two different operations are happening here:

• Sampling decides where or when the continuous signal is measured.

• Quantization decides which discrete state receives each measurement. Threshold classification is a very simple quantizer.

With too few samples, a fast change between sample points may disappear completely. With too few output states, different readings collapse to the same result. The lab lets you observe both types of information loss.

The question determines the model

The same object can have several valid models. Cars are discrete objects when counting traffic. Speed and road friction are usually continuous when studying braking distance. When studying road connectivity, the cars may disappear entirely, leaving only intersections and roads.

Therefore, “discrete or continuous” is not a permanent label attached to an object. The object, the question, and the required precision determine the choice together. A model is useful when it answers its target question reliably; irrelevant detail may only increase cognitive and computational cost.

When selecting a model, ask:

• What question must the model answer?

• Which objects must remain distinguishable?

• What states can each object occupy?

• Which details can be safely omitted?

• At which boundaries could an omitted detail make the model fail?

All allowed states together form a state space. For now, we list allowed values inside braces. The next section formally names such a collection a set and develops its notation.

The floor states of a six-floor elevator are

The letter $F$ is simply a name for this collection. Vertical bars in $|F|$ mean the number of states it contains, so $|F|=6$. This quantity is called cardinality and will reappear in the next section.

If the model also stores direction $D=\{\text{up},\text{down},\text{stopped}\}$ and door state $O=\{\text{open},\text{closed}\}$, one record can use the fixed order “floor, direction, door,” written $(f,d,o)$. For example, $(3,\text{up},\text{closed})$ means floor 3, upward direction, closed door. Changing the order would change the fields’ meanings.

For now, use ordinary multiplication: each floor has three direction choices, and every floor–direction choice has two door choices. There are at most

combinations. Rules can later eliminate impossible states such as “moving upward while the door is open.”

This multiplication gives an upper bound, not a guarantee that every combination is physically allowed. State variables say what is recorded; constraints say which combined states are forbidden. Keeping those roles separate prepares us for logic, relations, and graph models later in the course.

The sorter’s answers depend on explicit idealizations. A digital thermometer displays discrete digits, but the physical temperature it represents is normally modeled first as continuous. Seeing a number does not determine the model; the object and the question do.

After sorting the cards, complete this sentence for each one: “I classified it this way because the model must answer ___.” A changed question can change the classification. A stopwatch display has discrete character states, while actual elapsed time is commonly modeled as continuous.

Bridge to the next section

This section repeatedly listed allowed states in braces, such as $\{1,2,3,4,5,6\}$. The next section gives this “collection of objects” a formal name—a set—and answers three natural questions: How do we state that an object belongs? How do we compare two collections? How many subsets can one collection produce?