Basics of Discrete Mathematics

Discrete Mathematics
Among mathematicians, there is not an agreed-upon definition of discrete math.  What is agreed upon is the fact that discrete math deals with processes that use a finite, or countable, number of elements.  In discrete math, the elements will be discontinuous, as this branch of mathematics does not involve the continuity that processes of calculus do. 

Generally, discrete math uses countable sets of rational numbers, although they do not use the set of all real numbers, as that would then make the math continuous and put it in the category of algebra or calculus. 

Discrete math has numerous applications in the fields of computer science and business.

Element of a Set
A set is a mathematical collection of items, and an element is an item that is included in the set. These items are typically sets of numbers, or sets of geometrical points, or even sets of sets.

Whether an item is an element of a set is a binary property. In other words, a particular item either is or is not an element of a given set. There are not different degrees of belonging to a set, and one element of a set cannot be more an element than another.

Additionally, the elements do not have any particular order, and there is no count of how many times an element appears in a set. for example, in the set
, the numbers
0, 1, 2, and 4 are elements of the set. Two is not more of an element than the others because it is listed twice. Any number other than these, such as 3, is not an element of the set.

The mathematical symbol  means 'is an element of.' for instance, ' ' means that 'the number 1 is an element of set A'.

The symbol can be negated with a diagonal slash, so ' ' means 'the number 1 is NOT an element of set A.'

Empty Set
The empty set contains no elements. the symbol for the empty set is a circle with a line through it, , or the empty set can be written in roster form as
. Although it may seem trivial, the empty set is important for the same reason that zero is an important number—without the empty set, many set operations and definitions would be incomplete. For instance, the intersection of two non-overlapping sets is the empty set. the set of all prime numbers that are perfect squares is the empty set, because there are no such numbers. Other sets can be constructed using the empty set. for instance, a set containing the empty set,
 or {
}, is different from the empty set itself, since it's not actually empty—it contains one element, the empty set.
The empty set is, by definition, a subset of every set, including itself. This is because every element that is an element of the empty set is also an element of any other set, since the empty set contains no elements that could make this statement false.

Subset, Proper Subset, and Superset
Set A is a subset of set B if set A is contained entirely within set B. More formally, set A is a subset of set B if every element of set A is also in set B.
We can write this as
. the symbol for subset is
, so we can write '
' to mean 'set
A is a subset of set B,' or '
' to mean 'set
A is NOT a subset of set B'.
Any set is a subset of itself, since naturally any element in a set is in that set.

A proper subset means a subset that it not equal to the other set. In other words, set A is a proper subset of set B if set A is a subset of set B but they are not the same, so
 but
. for example,
 is a proper subset of
 because every element in the first set is included in the second set but the two sets are not identical. the symbol for proper subset is
, so we write '
' to mean 'set
A is a proper subset of set B,' and '
' to mean 'set A is not a proper subset of set B.'
The converse of a subset is a superset. If A is a subset of B, then B is a superset of A. In the example above,
 is a superset of
 because the first set contains every element of the second plus more.

Union of Two or More Sets
The union of two or more sets includes all the elements that are included in all of the sets. An element is in the union of sets A and B if it is in set A or in set B, or in both. The union is written with the symbol
, so '
'
(read 'A union B') means the union of sets A and B.

For example, given the sets
 and
, then
. 1 and 3 are in
 because they are in set A, and 6 and 8 are in
 because they are in set B. 2 and 4 appear in both A and B, so they are in
, but they only appear once.

The union operation on sets is both commutative and associative. That is,
, and
.

Intersection of Two or More Sets
The intersection of two or more sets is a set including every element that appears in all of the sets. An element is in the intersection of sets A and B if and only if the element appears in both set A and set B. For instance, if set
 and set
, the intersection of sets A and B includes the elements 2 and 3, because these are the only elements that appear in both sets. the intersection is written with the symbol
, so '
'
(read 'A intersection B') means the intersection of sets A and B.

The intersection operation on sets is both commutative and associative. That is,
, and
. The union and intersection operations also jointly have distributive properties:
 and
.

Complement of a Set
The complement of a set is a set containing all the elements that are not in the original set. To determine this, we must also define the universe of discourse—the set of all possible elements we're considering, abbreviated U. For mathematical applications, the universe of discourse is commonly the set of all integers (abbreviated
 would include elements such as
, 0, or 6, but it would not include elements such as
 or
, because these are not in the universe of discourse.

The complement of a set is often written either by drawing a line over the name of the original set, or by adding an apostrophe or a superscripted C. The complement of set A, for instance, could be written as
, as
, or as
.

For example, given set
, the complement of a would be
—all the elements of U that are not in A.

Difference of Two Sets
The difference of two sets is a set containing all the elements that are in the first set but not in the second. the difference of sets A and B is also referred to as the relative complement of set A with respect to set B, and is written
 or
. the difference is always a subset of the first set:
. However, it is not necessarily the case that
. In fact, because any element of
 is by definition not an element of B, the only time that
 can be a subset of B is if
 has no elements, i.e. if
, which is true if and only if
.

Unlike the union and intersection, the operation of the difference between sets is neither commutative nor associative. In general,
, and
.

For example, consider the sets
,
, and
.

Then
 since 1 and 3 are in set A but not in set B. Similarly,
,
,
, and
. However,
, i.e., set C is a subset of set A, so there are no elements that appear in C but not in A, which means the difference between C and A is the empty set.

Symbols for Sets Commonly Used in Mathematics
Certain sets are used frequently enough in mathematics to have their own symbols. the standard symbols for these sets resemble upper-case letters of the Latin alphabet, but in a typeface with double lines. Among the most commonly used sets are:
 – the set of all real numbers
· 
 – the set of all integers
· 
 – the set of all natural numbers
 – the set of all rational numbers (numbers that can be written as the ratio of two integers,
, where
)
 – the set of all complex numbers (numbers of the form
, where
 and b are real numbers and
)

A superscripted plus or minus sign is used to restrict the set to positive or negative numbers. for instance,
 would be the set of all positive real numbers, and
 would be the set of all negative integers.

Some of these sets are, of course, subsets of others.
Specifically,
.

Representing Sets with Recursive and Explicit Formulas
Sets of numbers can have a consistent relationship between the elements of the set. Some of these relationships can be represented with simple recursive or explicit formulas.
For example, consider the set of all positive, even numbers (a) and the set of all positive, odd numbers (b):

Positive, even numbers:
Recursive:

Explicit:
 


Positive, odd numbers:
Recursive:
,

Explicit:


Each set of numbers represents a linear function, with a constant rate of change of 2. The positive, even numbers represent a linear function that is proportional, whereas the positive, odd numbers represent a linear function that is not proportional. The set of even, positive numbers is represented by a function with a y-intercept of 0. The set of odd, positive numbers is represented by a function with a y-intercept of 1.

Set Operations with Venn Diagrams
A Venn diagram is a useful visual tool for representing two or three sets and their common elements. Each set is drawn as a circle, with the different circles overlapping. Elements are placed in the circle corresponding to the appropriate set or sets—or placed outside all the circles if they belong to the universe of discourse but not to any of the sets.

For example, suppose our universe of discourse is the integers from 1 to 9, and we have the three sets
,
, and
.

This could be illustrated with the following Venn diagram:


Note, for example, that 6 appears in the center of the diagram where all three circles overlap, because it is an element of all three sets. On the other hand, 8 is placed outside the three circles because it is not an element of any of the sets. Sometimes, instead of writing the elements themselves in the diagram, the total number of elements in each part of the Venn diagram is noted. This is especially useful for solving problems involving these numbers of elements.

Using Venn Diagrams to Solve Problems
Venn diagrams are useful for solving problems involving the numbers of elements in sets and in their intersections. By putting those numbers into a Venn diagram, it's simple to see how many must be in the 'leftover' parts.
For example, suppose we're told that 200 voters were polled about two propositions, Proposition 1 and Proposition 2. Further,120 support
Proposition 1, 85 support Proposition 2, and 50 support both propositions. To find how many of the voters support neither proposition, we can draw a Venn diagram with a circle representing the supporters of each proposition. We know 50 voters support both propositions, so we can write a 50 in the center of the diagram.


The Proposition 1 circle should contain 120 voters total, so subtracting the 50 voters in the overlap, the other section of the circle must contain
. Similarly, the nonoverlapping part of the Proposition 2 circle should contain
.


Adding all three sections, the total number of voters supporting either proposition is
, so there must be
 voters who support neither.


Properties of Infinite Sets

An infinite set has an infinite number of elements. a more technical definition is that a set is infinite if its elements can be put in one-to-one correspondence with the elements of one of its proper subsets. For instance, consider the set of all positive integers,
. If we remove the number 1, we can still match up every positive integer to an element of the remaining subset (by simply matching the number n to the number ).
 is therefore an infinite set.

The union of an infinite set and any other set is always infinite. the intersection of two infinite sets may or may not be infinite. For instance, consider the set P of prime numbers, the set O of positive odd integers, and the set E of positive even integers—all infinite sets.
 is another infinite set, because there are infinitely many odd prime numbers.
 is finite, because there is only one even prime number. and
 is the empty set. Likewise, the complement of an infinite set may be infinite, finite, or the empty set (if the set equals the universe of discourse).

Cardinality
Although all infinite sets have infinitely many members, they may still have different sizes. Two sets are defined to have the same size—or more technically the same cardinality—if each element of one set can be matched up to a unique element of the other, with none left over. For example, the set of all integers,
, and the set of all even integers have the same cardinality, even though the latter is a proper subset of the former: every number n in
 can be matched to a unique number 2n in the set of all even integers.

Although it's more difficult to prove, the set of all rational numbers,
 are said to be 'countably infinite,' or simply countable. Sets with a larger cardinality are said to be 'uncountably infinite,' or uncountable.

Cartesian Products/Relations
A Cartesian product is the product of two sets of data, X and Y, such that all elements x are a member of set X, and all elements y are a member of set Y. The product of the two sets,
 is the set of all ordered pairs
. For example, given a standard deck of 52 playing cards, there are four possible suits (hearts, diamonds, clubs, and spades) and thirteen possible card values (the numbers 2 through 10, ace, jack, queen, and king). If the card suits are set X and the card values are set Y, then there are
 possible different
 combinations, as seen in the 52 cards of a standard deck.

A binary relation, also referred to as a relation, dyadic relation, or 2-place relation, is a subset of a Cartesian product. It shows the relation between one set of objects and a second set of objects, or between one set of objects and itself. The prefix bi- means two, so there are always two sets involved – either two different sets, or the same set used twice. The ordered pairs of the Cartesian product are used to indicate a binary relation. Relations are possible for situations involving more than two sets, but those are not called binary relations.

The five types of relations are reflexive, symmetric, transitive, antisymmetric, and equivalence.

A reflexive relation has
 for all values of x and y in the set.

A transitive relation has
 for all values of x, y, and z in the set.

An antisymmetric relation has
 for all values of x and y in the set.

A relation that is reflexive, symmetric, and transitive is called an equivalence relation.

Vertex-Edge Graphs
A vertex-edge graph is a set of items or objects connected by pathways or links. As an example, consider the following set of nodes and a few graphs representing ways of connecting them with edges.







Vertex-edge graphs are useful for solving problems involving schedules, relationships, networks, or paths among a set number of objects. The number of objects may be large, but it will never be infinite. The vertices or points on the graph represent the objects and may also be referred to as nodes.

The nodes are joined by line segments called edges or links that show the specific paths that connect the various elements represented by the nodes.

The number of nodes does not have to equal the number of edges. There may be more or less, depending on the number of allowable paths. A. endpoint on a vertex-edge graph is a vertex on exactly one edge. In the case of a vertex that is an endpoint, the edge that the vertex is on is incident with the vertex. Two edges are considered to be adjacent if they share a vertex. Two vertices are considered to be adjacent if they share an edge.

In a vertex-edge graph, a loop is an edge that has the same vertex as both endpoints. To calculate the degree of a vertex in a vertex-edge graph, count the number of edges that are incident with the vertex, counting loops twice since they meet the vertex at both ends. The degree sum formula states that the sum of the degrees of all vertices on a vertex-edge graph is always equal to twice the number of edges on the graph. Thus, the sum of the degrees will never be odd, even if there are an odd number of vertices. Consider the following graph. Node d is an endpoint, there is a loop on node b, and the degree sum of the graph is .

In a vertex-edge graph, a path is a given sequence of vertices that follows one or more edges to get from vertex to vertex. There is no jumping over spaces to get from one vertex to the next, although doubling back over an edge already traveled is allowed. A simple path is a path that does not repeat an edge in traveling from beginning to end. Think of the vertex-edge graph as a map, with the vertices as cities on the map, and the edges as roads between the cities. To get from one city to another, you must drive on the roads. A simple path allows you to complete your trip without driving on the same road twice.

In a vertex-edge graph, a circuit is a path that has the same starting and stopping point. Picturing the vertex-edge graph as a map with cities and roads, a circuit is like leaving home on vacation and then returning home after you have visited your intended destinations. You may go in one direction and then turn around, or you may go in a circle. A simple circuit on the graph completes the circuit without repeating an edge. This is like going on vacation and returning home without driving on the same road twice.

Graph



Example Paths

Path:
a-b-c-b-d

Simple path:
a-b-d

Circuit:
b-a-c-a-b

Simple circuit:
a-b-c-a

On a vertex-edge graph, any path that uses each edge exactly one time is called an Euler path. One simple way to rule out the possibility of an Euler path is to calculate the degree of each vertex. If more than two vertices have an odd degree, an Euler path is impossible.

A path that uses each vertex exactly one time is called a Hamiltonian path.


Euler path:
b-c-d-a-b-d

Hamiltonian path:
a-b-c-d

If every pair of vertices is joined by an edge, the vertex-edge graph is said to be complete. If the vertex-edge graph has no simple circuits in it, then the graph is said to be a tree.
If every vertex is connected to every other vertex by some path, then the graph is said to be connected, otherwise it is disconnected.

Complete and Connected



Tree and Connected



Disconnected



Problems:

P1. Given the sets
,
, and
 find the following:
(a)

(b)

(c)

(d)

P2. Give the most precise description of the following paths for the vertex-edge graph:

(a) a-d-c b-d-b-d-b
(c) b-c-d-a-b-d
(d) b-c-d-a
(e) b-c-d-a-b

Solutions:

P1. (a) The union operation includes all elements of the sets being operated on. Thus:

The intersection operation includes only elements in both sets being operated on. Thus:

(c) First, find the intersection of Y and Z:

Then, since the intersection of Y and Z is the null set, the union with X is just the elements of X:

(d) First, find the union of X and Y:

Then, the intersection of
 with
Z is:


P2. Determine the start and end vertices, whether the path uses all vertices or edges, and whether the path repeats any vertices or edges: