Discrete Mathematics (Levin)

 Introduction and Preliminaries

Welcome to Discrete Mathematics. If this is your first time encountering the subject, you will probably find discrete mathematics quite different from other math subjects. You might not even know what discrete math is! Hopefully this short introduction will shed some light on what the subject is about and what you can expect as you move forward in your studies.

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.

Mathematical Statements

While walking through a fictional forest, you encounter three trolls guarding a bridge. Each is either a knight, who always tells the truth, or a knave, who always lies. The trolls will not let you pass until you correctly identify each as either a knight or a knave. Each troll makes a single statement:

Troll 1: If I am a knave, then there are exactly two knights here.

Troll 2: Troll 1 is lying.

Troll 3: Either we are all knaves or at least one of us is a knight.

Which troll is which?

In order to do mathematics, we must be able to talk and write about mathematics. Perhaps your experience with mathematics so far has mostly involved finding answers to problems. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process.

Communication in mathematics requires more precision than many other subjects, and thus we should take a few pages here to consider the basic building blocks: mathematical statements.

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.