What Is Discrete Mathematics?

Discrete mathematics is an abstract, formalized way of understanding real-world objects and phenomena. Discrete math studies things that we describe as distinct (discrete) units, rather than smoothly-varying (continuous) quantities.

For example, if you are interested in the number of bison living in the State of Wyoming, you are in the realm of discrete math. If you are interested in the average rainfall in Wyoming, you are in the realm of continuous math.

This article will help you understand what discrete math is all about and why it's important.

What Does Discrete Mathematics Include?

Discrete mathematics is about distinct, countable entities. It encompasses many topics, including some you might not suspect. The most important and widely-studied topics are:

Mathematical Logic

Set Theory

Algorithms and Data Structures

Relations and Relational Algebra

Graph Theory

Numerical Analysis

Other topics in discrete math include:

Functions, fundamental to artificial intelligence
Algorithm Analysis
Combinatorial Analysis, a foundation of bioinformatics and artificial intelligence
Information Theory
Probability and Statistics, foundations of image processing, artificial intelligence, and biotechnology
Number Theory, a crucial foundation for the study of cryptography
Game Theory, fundamental to some branches of biotechnology
Computability Theory
Formal Languages and Automata, foundations of artificial intelligence
Decision theory
Operations research, a foundation of social network analysis
Discrete geometry
Formal verification
Modeling and modeling languages, required for the study of biotechnology
Process algebras
Computational geometry
Image analysis
Boolean algebra
Coding theory
Discrete transforms
Discrete modeling

Why Study Discrete Mathematics?

You might study discrete mathematics because:

You need to use it, for example to choose the best algorithm to solve a complex problem.
You need it to understand another subject, such as social network analysis.
It is required for your course of study.

Topics in Discrete Mathematics

Mathematical Logic

Mathematical logic tells us how to verify the truth of a mathematical statement, or proposition. Mathematical logic is based on the following concepts:

Axioms—statements we define (or assume) to be true. For example, in geometry, "A point has no length or width" is an axiom.

Propositions—statements that might be true or false.

Logical operators—mathematical operations corresponding to logical ideas such as "and", "or", and "not".

Rules of inference—rules about correctly determining the truth of a proposition, based on the truth or falsehood of other propositions.

An example is the rule of simplification: if we have two propositions, and we know that both are true, we know that each is true. That is, if (A and B) is true, A is true, and B is true. For example, if we know that the weather is cold and rainy, we know that the weather is cold, and also that the weather is rainy.

This rule might seem too obvious to mention. However, simple rules like this are the building blocks for complex proofs.

Theorems—propositions that are proven: that is, the theorem has a proof, and the proof is error-free.

Proofs—formal systems based on axioms, logical operators, and rules of inference, demonstrating the truth of a proposition.

Mathematical logic forms the foundation of all other branches of math.

Mathematical logic, although abstract, is fundamental to real-world pursuits such as formal verification (demonstrating that software performs correctly), artificial intelligence, and biotechnology.

Set Theory

A set is a well-defined collection of members (or elements).

Examples of sets:

My coffee mugs
All integers
All livings species of bear

Set theory is based on the following concepts:

Finite sets
Infinite sets
The empty set, containing no members
The universal set, containing all possible members
Set equality: two sets containing the same members
Subsets and supersets: everything in one set also appears in another set
Union: a set formed from two other sets, containing everything in either of the sets
Intersection: a set formed from two other sets, containing everything in both of the sets
Difference: a set formed from two other sets, containing everything in the first set that is not in the second
Complement: a set consisting of everything that is not in another particular set
Cross Product

Venn Diagrams

Venn diagrams provide a helpful visual representation of sets and their relationships. The following Venn diagram shows two sets, A and B.

Set theory is a foundation of graph theory, artificial intelligence, data structure design and database design.

Algorithms and Data Structures

An algorithm is a sequence of actions, to be taken in a prescribed order, to achieve a specified result. Here are some everyday examples of algorithms:

A recipe for a cake
Instructions to assemble a bookcase
A method to compute a square root
A data structure is a scheme for organizing data so that it can be readily accessed and manipulated by an algorithm.

Examples of data structures:

Linked list

Algorithms and data structures form the foundation of most branches of computer science, including artificial intelligence, as well as many branches of biotechnology.

Relations and Relational Algebra

A relation is a set of data records that match a specified set of rules. Each record contains a collection of information, depending on what the relation is used for.

Examples of relations:

People who live in New York City
Women under age 40 who live in New York City
FDA-approved medications for diabetes

Relational algebra is a language for modeling data and defining data queries. Operations in relational algebra accept one or more relations as input, and produce a relation as output.

Examples of operations:

Cross product

Relations and relational algebra are fundamental to biotechnology and artificial intelligence, and to the design and implementation of relational databases and query languages such as SQL.

Graph Theory

Graph theory is the study of objects in a network of relationships. The objects are called nodes (or vertices). The relationships are called edges.

Some simple examples of graphs:

A road map (towns are nodes, roads are edges)
A social network (people are nodes, "friend" relationships are edges)
A polyhedron (vertices are nodes, edges are edges)
If the edges are bidirectional, the graph is called undirected. If the edges have a preferred direction, the graph is called directed, or a digraph.
Graph theory is a foundation of topology, biotechnology, artificial intelligence, and social network analysis.

Numerical Analysis

Numerical analysis concerns algorithms for solving mathematical problems with digital computers. These algorithms provide approximate methods for carrying out mathematical analyses. While these methods are approximate, algorithms are selected to keep errors within specified bounds.

Numerical analysis attempts to bridge the gap between continuous and discrete mathematics. While real numbers represent many important real-world concepts, computers can only accurately represent integers.

Floating point numbers are a crucial tool to bridge this gap, approximating real numbers as nearly as practical. However, every floating point system has an inherent limit of accuracy, called ε (epsilon). ε is a way of characterizing typical round-off error.

Error propagation is a crucial concept in numerical analysis. Because most real-world mathematical problems require multiple steps, errors in each step can accumulate, sometimes catastrophically. Good algorithms anticipate and avoid error propagation problems.

Numerical analysis is a foundation of image processing, artificial intelligence, biotechnology, and of real-world modeling for engineering, science, medicine and business.

Live Chats