Fundamentals of Discrete Math

Fundamentals of Discrete Mathematical Structures

This post contains a synopsis of the fundamentals of discrete mathematical structures. This post was created during my second year of college while studying to attain a Bachelors of Science in Computer Science.  The discrete math course is a necessary requirement in attaining a B.S. in Computer Science.

“The origins of matrices goes back to approximately 200 B.C.E, when they were used by the Chinese to solve linear systems of equations” (Kolman, Busby, & Ross, 2009).

Are you interested in learning discrete math on your own?
Check out http://www.ocw.mit.edu

Discrete Math: Sets and Subsets

A set can be defined as a group of related objects. The objects within the set are known as elements or members of the set. For example, a collection of percusssion musical instruments, a collection of 3 legged dogs, or the collection of real numbers between 1 and 12 are all sets. A set is known to be well-defined; for, an element or member is well-defined when it is known if the object belongs to the set. Set theory is the foundation in which virtually all of mathematics is constructed.

Another example of a set is one that has a finite number of elements listed between braces. All positive integers that are more than 3 and less than 7 would be written as
{4,5,6}
The order in which the set is listed is not important.

When writing sets, we use uppercase letters such as A, B, C to denote sets, and lower case letters such as a, b, c, x, y, z, t to denote members(or elements) of the sets.

If x is an element of set A it would be written as:
x ∈ A
If x is not an element of set A it would be written as:
x ∉ A

discrete math subsetsSubsets

If every element of A is  contained in element B then
A ⊆ B
If A is not a subset of B then
A ∉ B

 

Discrete Math: Operations on Sets

If A and B are sets, their union is the set of all elements that belong to A or B.
This is written as:
A ∪ B
Therefore
A ∪ B = {x | x ∈ A or x ∈ B}
Please note that x ∈ A ∪ B if x ∈A or x ∈ B or x belongs to both A and B

Example
Let A = {a,b,c,e,f} and B = {b,d,r,s}
Find A ∪ B
Answer A ∪ B  = {a,b,c,d,e,f,r,s}

 

Discrete Math: Sequences

A sequence is a list of objects that are arranged in a specific order.
The list may stop at n steps, n ∈N, or it may go on forever. In other words, the sequence can be finite or infinite.

The sequence
1,0,0,1,0,1,1 is finite.

The sequence
6,29,52,75,98,… is infiinte.
The three dots in the sequence stand for “and so on”.

 

Discrete Math: Properties of the Integers

Division and factoring of integers.

If m is an integer and n is a positive integer, we can plot the integer multiples of n on a line, and locate m as in Figure 1

If m is a multiple of n, we say
m = qn
then we can write
m = qn + r, where r is 0.

On the other hand, as shown in Figure 1, if m is not a multiple of n, we let qn be the first multiple of n lying to the left of mand let r be m – qn. Then r is the distance from qn to m, so clearly 0 < r < n , and again we have m = qn + r. We state these observations as a theorem.

 

Discrete Math: Matrices

A matrix is a rectangular array of numbers arranged in m horizontal rows and n vertical columns.

Example
Color Combination Matrix

YELLOW BLUE RED
YELLOW YELLOW GREEN ORANGE
BLUE GREEN BLUE PURPLE
RED ORANGE PURPLE RED

Boolean Matrix

A boolean matrix (or bit matrix) is an m x n matrix whose entries are either 0 or 1.

 

 

Discrete Math: Mathematical Structures

A mathematical structure includes:

  • mathematical object (set, matrix).
  • notation for object used to determine whether objects are the same as described
  • classification of objects of new type (finite or infinte for sets, boolean or symmetric for matrices)
  • then operations are defined for objects and properties of these operations are examined

 

 

Reference

Kolman, Busby, & Ross (2009). Discrete Mathematical Structures 6th edition. Upper Saddle River, NJ: Pearson Prentice Hall.

0
  Related Posts