Introduction to Discrete Mathematics

1The subject of discrete mathematics

This lecture explains discrete mathematics as the study of structures consisting of distinguishable elements and their relationships and of proving their properties through finite symbolic descriptions and rules of inference.

A discrete structure is a structure whose elements can be distinguished individually and whose relationships can be specified. Integers, finite strings, graphs, and logical formulas are representative examples.

This distinction does not divide all real-world objects completely into discrete and continuous classes. Temperature, for example, can be modeled as a continuous real-valued quantity, but a computer encodes it as a finite-precision value. Discreteness depends not only on the object but also on the granularity of the model chosen for a problem.

2Fundamental concepts

A proposition is a statement that has a definite truth value, either true or false. Logic provides a language for combining propositions and verifying the validity of inferences.

A set is a collection of objects called elements. A map $$f:A\to B$$f:A\to B is a rule that assigns exactly one element of $$B$$B to every element of $$A$$A.

A relation represents correspondences among elements of one or more sets as a set. A binary relation $$R$$R can be written as $$R\subseteq A\times B$$R\subseteq A\times B.

A graph $$G=(V,E)$$G=(V,E) is a structure that represents objects by a vertex set $$V$$V and relationships between objects by an edge set $$E$$E.

An algorithm is an unambiguous terminating procedure that produces output from input. Discrete mathematics supplies the foundation for defining that input and output and for proving correctness and analyzing computational complexity.

3Learning sequence

First, propositions and logic distinguish assumptions from conclusions and express inferences. They establish the form of every subsequent definition and proof.

Next, sets specify the domain of objects, while maps specify correspondences between inputs and outputs. Relations provide a unified representation of order, equivalence, connectivity, and other associations.

Graphs then provide an important class of relational structures and formalize reachability and distance between vertices.

Finally, algorithms process these structures. Logic and mathematical induction prove correctness, while counting arguments analyze computational complexity.

4Role in information engineering

• Logic clarifies program conditions, specifications, and verification conditions.
• Sets and maps describe data types, state spaces, and the domains, codomains, and images of functions.
• Relations and graphs abstract databases, networks, and dependencies.
• Algorithm analysis evaluates whether a computation can be performed with finite resources.

5Summary

• Discrete mathematics describes distinguishable elements and their relationships and proves their properties through finite descriptions.
• Whether a model is discrete or continuous depends not only on the object but also on the selected representation.
• The sequence propositions, sets, maps, relations, graphs, and algorithms provides a staged route from definitions to computational procedures.