What Prerequisite need to understand TOC?

Prerequisite need to understand TOC

SET

The set is a group of similar kind of elements, 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} call it Z by writing

Z = {x | x Î N | x £ 5}

where N represents 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 sets 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}

Not e : 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 = f,

where f is the Empty set.

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

Some standard Set Identities

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

A È B = B È A

A Ç B = B Ç A

Associative laws:

A È (B È C) = (A È B) È C

A Ç (B Ç C) = (A Ç B) Ç C

Distributive laws:

A È (B Ç C) = (A È B) Ç (A È C)

A Ç (B È C) = (A Ç B) È (A Ç C)

Idempotent laws:

A È A = A

A Ç A = A

Absorptive laws:

A È (A Ç B) = A

A Ç (A È B) = A

De Morgan laws:

(A È B)¢ = A Ç B

(A È B)¢ = A È B

Laws involving Complements :

(A¢)¢ = A

A Ç A¢ = f

A È A¢ = U

Laws involving empty set :

A È f= A

A Ç f = f

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.

FUNCTI ONS

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 its co domain.

Thus, f is a function if it cover's the domain and it is single valued.

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

Also, Study about: