## 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**

**Subsets**

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 6^{th} edition. Upper Saddle River, NJ: Pearson Prentice Hall.

MAR