Discrete MathLinuxMacTechnologyUncategorizedWindows

Discrete Math An Introduction

What is Discrete Math

Mathematicians are in the business of stating things precisely. When you read a mathematical statement, you are meant to take every word seriously; good mathematical language conveys a clear, unambiguous message. In order to read and write mathematics, you must practice the art of logical thinking. The goal in this section is to assist my readers to communicate mathematically by understanding the basics of logic.
However, Mathematical logic can be difficult particularly the first time you see it. This part really begins with the study of formal or symbolic, logic then we will apply it to the language of mathematics. Expect things to be a bit muddy at first, but eventually the dirt will settle and eventually you will start actually getting what I am attempting to convey to you.
Defining discrete mathematicsis hard because definingmathematicsis hard.What is mathematics? The study of numbers? In part, but you alsostudy 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.In an algebra or calculus class, you might have found a particular set of numbers (maybe the set of numbers in the range of a function). You would represent this set as an interval:[0,∞)is the range off(x)x2since the set of outputs of the function are all real numbers 0 and greater.This set of numbers is NOT discrete. The numbers in the set are not separated by much at all. In fact, take any two numbers in the set and there are infinitely many more between them which are also in the set.Discrete math could still ask about the range of a function, but the set would not be an interval. Consider the function which gives the number of children of each person reading this. What is the range? I’m guessing it is something like{0,1,2,3}. Maybe 4 is in there too. But certainly there is nobody reading this that has 1.32419 children. This output set is discrete because the elements are separate. The inputs to the function also form a discrete set because each input is an individual person.One way to get a feel for the subject is to consider the types of problems you solve in discrete math.

One reason it is difficult to define discrete math is that it is a very broad description which encapsulates a large number of subjects. In this tutorial we will study four main topics:combinatorics(the theory of ways things combine; in particular, how to count these ways),sequences,symbolic logic, and graph theory. However, there are other topics that belong under the discrete umbrella, including computer science, abstract algebra, number theory, game theory, probability, and geometry (some of these, particularly the last two, have both discrete and non-discrete variants). Ultimately the best way to learn what discrete math is about is to do it. Let’s get started! Before we can begin answering more complicated(and fun) problems, we must lay down some foundation. We start by reviewing mathematical statements, sets, and functions in the framework of discrete mathematics.
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. So let me tell ya about Atomic and Molecular Statements, these are statements such as any declarative sentence which is either true or false (In programming or scripting, this is referred to as a boolean). A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular.
These are statements (in fact,


•Telephone numbers in the USA have 10 digits.
•The moon is made of cheese.
•42 is a perfect square.
•Every even number greater than 2 can be expressed as the sum of two primes.
And these are not statements:
•Would you like some cake?
•The sum of two squares.
•Go to your room!
The reason the sentence “3+x=12” is not a statement is that it contains a variable. Depending on what x is, the sentence is either true or false, but right now it is neither. One way to make the sentence into a statement is to specify the value of the variable in some way. This could be done by specifying a specific substitution, for example, “3+x=12 where x=9,” which is a true statement. Or you could capture the free variable by quantifying over it, as in, “for all values of x,3+x=12,” which is false.We will discuss quantifiers in more detail at the end of this section.You can build more complicated (molecular) statements out of simpler(atomic or molecular) ones using logical connectives.
For example, this is a molecular statement:

Telephone numbers in the USA have 10 digits and 42 is a perfect square.

Note that we can break this down into two smaller statements. The two shorter statements are connected by an “and.” We will consider 5connectives: “and” (Sam is a man and Chris is a woman), “or” (Sam is a man or Chris is a woman), “if. . . , then. . . ” (if Sam is a man, then Chris is a woman), “if and only if” (Sam is a man if and only if Chris is a woman),and “not” (Sam is not a man). The first four are called binary connectives(because they connect two statements) while “not” is an example of a unary connective(since it applies to a single statement). These molecular statements are of course still statements, so they must be either true or false. The absolutely key observation here is that which truth value the molecular statement achieves is completely determined by the type of connective and the truth values of the parts. We do not need to know what the parts actually say, only whether those parts are true or false. So to analyze logical connectives, it is enough to consider propositional variables(sometimes called sentential variables), usually capital letters in the middle of the alphabet:P,Q,R,S,.... We think of these as standing in for (usually atomic) statements, but there are only two values the variables can achieve: true or false.1We also have symbols for the logical connectives:∧,∨,→,↔

Logical Connectives

•P∧Q is read “P and Q,” and called a conjunction.
•P∨Q is read “P or Q,” and called a disjunction.
•P→Q is read “if P then Q,” and called an implication or conditional.
•P↔Q is read “P if and only if Q,” and called a biconditional.
•¬Pis read “not P,” and called a negation.

The truth value of a statement is determined by the truth value(s) of its part(s), depending on the connectives:

Truth Conditions for Connectives

•P∧Q is true when both P and Q are true
•P∨Q is true when P or Q or both are true.
•P→Q is true when P is false or Q is true or both.
•P↔Q is true when P and Q are both true, or both false.
•¬Pis true when P is false.

Note that for us,or is the inclusive or (and not the sometimes used exclusive or) meaning that P∨Q is in fact true when both P and Q are true.As for the other connectives, “and” behaves as you would expect, as does negation. The bi-conditional (if and only if) might seem a little strange,but you should think of this as saying the two parts of the statementsareequivalentin that they have the same truth value. This leaves only the conditional P→Q which has a slightly different meaning in mathematics than it does in ordinary usage. However, implications are so common and useful in mathematics, that we must develop fluency with their use, and as such, they deserve their own post.

Comment here