Basic Mathematical concept need to understand the Theory Of Computation

Mathematical concepts you need to understand TOC

SET

A set is a group of similar kinds of elements, that follows some property that characterizes those elements.
One way to specify a set is to enumerate the elements completely. All the elements belonging to the set are explicitly given.

e.g., A = {a,b,c,d,e,f } or A = {1,2, 3,4,5}

Another way to specify a set is to give the properties that characterize elements of the set.

e.g., B = {x | x is a positive integer less than or equal to 5}

SET TERMINOLOGY

Belongs To (∈)

x ∈ B means that x is an element of set B.

Using this notation, we can specify the set {0,1,2,3,4} and call it Z by writing

Z = {x | x ∈ N | x ≤ 5}

where N represents a set of natural numbers.

It is read as “the set of natural numbers that are less than or equal to 5”.

Subset

Let A and B be two sets.

A is a subset of B if every element of A is an element of B.

A is a subset of B is represented as A  ⊆ B.

Note: If A is a subset of B and B is a subset of A, then A = B.

Also, if A is a subset of B, but not equal to B represented as A  ⊂ B.

 Universal Set

The set U of all the elements we might ever consider in the discourse is called the universal set. 

Complement

If A is a set, then the complement of A is the set consisting of all elements of the universal set that are not in A. It is denoted by A¢ or A. Thus A¢ = {x | x ∈ U Λ x ∉ A}, where ∉ means “is not an element of” or “does not belongs to” e.g., If U is set of natural numbers and A = {1, 2, 3}, then

A′ = {x | x ∈ U Λ  x > 3}.

Set Operations

Following operations that can be performed on set are:

1. Union: If A and B are two sets, then the union of A and B is the set that contains all the elements that are in A and B including ones in both A and B. It is denoted by A B.

e.g., If A = {1, 2, 3} and B = {3, 4, 5} then A ∪ B = {1, 2, 3, 4, 5}

2. Difference: If A and B are two sets, then the difference of A from B is the set that consists of the elements of A that are not in B. It is denoted by A – B.

e.g., If A = {1, 2, 3}, B = {3, 4 5} then A – B = {1, 2}

Note: In general, A – B ≠ B – A.

For A and B of the above example B – A = {4, 5}.

3. Intersection: If A and B are two sets, then the intersection of A and B is the set that consists of the elements in both A and B. It is denoted by A ∩ B.

e.g., If A = {1, 2, 3, 8} B = {3, 4, 5, 8}, then A  ∩ B = {3, 8}.

Disjoint sets

A and B are said to be disjoint if they contain no elements in common, i.e. A ∩ B = Φ,

where Φ is the Empty set.

e.g., A = {1, 2, 3, 4, 5} and B = {6, 8, 9} are disjoint, become A ∩ B = Φ

Some standard Set Identities

A, B, C represent arbitrary sets and f is the empty set and U is the Universal Set.

1. Commutative laws:

   • A  ∪ B = B ∪ A
   • A  ∩ B = B ∩ A

2. Associative laws:

   • A  ∪ (B ∪ C) = (A ∪ B) ∪ C
   • A  ∩ (B ∪ C) = (A ∩ B) ∩ C

3. Distributive laws:

   • A  ∪  (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
   • A  ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

4. Indempotent laws:

   • A  ∪ A = A
   • A ∩ A = A

5. Absorptive laws:

   • A  ∪ (A ∩ B) = A
   • A  ∩ (A ∪ B) = A

6. De Morgan laws:

   • (A  ∪ B)´ = A´ ∩  B´
   • (A  ∩ B)´ = A´ ∪ B´

7. Laws involving Complements :

   • (A´)´ = A
   • A ∩ A´ = Φ
   • A ∪ A´ = U

8. Laws involving empty set :

   • A ∪ Φ = A
   • A  ∩ Φ = Φ

9. Laws involving Universal Set :

   • A  ∪ U = U
   • A  ∩ U = A   

RELATIONS

Let A and B be sets. A binary relation from A into B is any subset of the Cartesian product A ´ B.

Relation on a Set

A relation from a set A into itself is called a relation on A. 

R of Example 2 above is relation on A = {2, 3, 5, 6}.

Let A be a set of people and let P = {(a, b) | aÎA Ù bÎA Ù a is a child of b}. Then P is a relation on A which we might call a parent-child relation.

Composition

Let R be a relation from a set A into set B, and S be a relation from set B into set C. The composition of R and S, written as RS, is the set of pairs of the form (a, c)  Î A ´ C, where (a, c)  Î RS if and only if there exists b  Î B such that (a, b)  Î R and (b, c)  Î S.

For example, PP, where P is the parent-child relation given above, is the composition of P with itself and it is a relation which we know as grandparent-grandchild relation.

Properties of Relations

Assume R is a relation on set A; in other words, RÍA ´ A. Let us write a R b to denote (a,b)ÎR.

• Reflexive : R is reflexive if for every a Î A, a R a.
• Symmetric: R is symmetric if for every a and b in A, if aRb, then bRa.
• Transitive: R is transitive if for every a, b, and c in A, if aRb and bRc, then aRc. 
• Equivalence: R is an equivalence relation on A if R is reflexive, symmetric and transitive.

FUNCTIONS

A function is a special type of relation where every input has a unique output. A function is a correspondence between two sets (called the domain and the range) such that to each element of the domain, there is assigned exactly one element of the range.

A function, denoted by f, from a set A to a set B is a relation from A to B that satisfies

• • • for each element a in A, there is an element b in B such that <a, b> is in the relation
    • if <a, b> and <a, c> are in the relation, then b = c.

The set A in the above definition is called the domain of the function and B is its co-domain.

Thus, f is a function if it covers the domain and is single-valued.

We thus understood here the concept of Set and its terminologies, relationships, and functions which are prerequisites for understanding the theory of calculation.