Mathematical Preliminaries

Chapter 1

Mathematical preliminaries

- Sets

- A set is a collection of elements, without any structure other than membership.

- A set is specified by enclosing some description of it's element in curly braces.

Example:

S1= {0, 1, 2}

S2= {a, b, ---. z}

S3= {2, 4, 6, 8, ---}

S4= {2, 4, 2, 8} is not a set because it contains repeated elements.

More explicit notation can be used for example

S = {i : i> 0, i is even }

We read this as "s is the set of all i, such that i is greater than zero, and i is even ".

S5 = { x : x is an odd , x <10 }={ 1,3,5,7,9}

S6 = { a/b : 5 < a <10, 20 < b < 25}

S7 ={a}

S8={}

Operations on the Sets:

* X Î S indication that x is an element of the set S(Belong to). X is an element and S is a set.

Ex: S = {a, b, c, d}

Find the result of:

a Î S is True

g Î S is False

{a, c} Î S Error operation because {a,c} is a set not an element.

* X Ï S indication that x is an not an element of the set S(Not belong to).

a Ï S is False

g Ï S is True

* Operations between sets:

- Union ((U: S1 U S2 = {X: X Î S1 or X Î S2 }

Ex: if s1 = { a,b,c} and s2 = {a,b,d,e} then S1 U S2 = {a, b, c, d, e}

- Intersection (∩) : S1 ∩ S2 = {X : X Î S1 and X Î S2 }

Ex: if s1 = { a,b,c} and s2 = {a,b,d,e} then S1 ∩ S2 = {a, b}

- Difference ( - ) : S1 - S2 = {X : X Î S1 and X Ï S2 }

Ex: if s1 = { a,b,c} and s2 = {a,b,d,e} then S1 - S2 = {c}

- Universal set (u) : the set of all possible elements.

Ex: if s1 = { a,b,c} and s2 = {d,e,w} then the universal set fo s1 and s2 is U ={a,b, c, d,e,…,z}

Ex: s3={x: x is even} then the universal set for s3 = {x:x is an integer}

Ex: s4={1,2,3,4} then the U= {x:0 ≤ x ≤ ¥}

- Complementation ( S ) : S = { X :X Î u and x Ï S }

__

if s1 = { a,b,c} then S1 ={ d,e,f,g,h,i,…,z}

__

if s3={x: x is even} then S3 ={ x:x is odd integer}

- Empty set (null set) : the set with no elements denoted by Ø or {}.

From the definition of a set, it is obvious that :

. S U Ø = S = S- Ø

If s= {4,8,10, 15} then s – Ø={ 4, 8, 10, 15}

. S ∩ Ø = Ø

. Ø = u

_ _____________

. S = S if s= {e, f ,g} then s={a,b,c,d,h,i,…,z} and {a,b,c,d,h,i,…,z}={e,f,g}=s

. S1 U S2 = S1 ∩ S2

. S1 ∩ S2 = S1 U S2

Demorgan's Law.

If s1={1,5,10,20, 25} and s2 = {5,20,25, 30, 35}

S1 U s2 ={ 1,5,10,20,25,30,35}

____________

S1 U s2 ={2,3,4,6,7,…}

_ __

S1 ∩ S2 ={2,3,4,6,7,…}

_ ___

S1 ={2,3,4,6,7,…} and s2 ={1,2,3,4,6,7,…}

S1 = {2, 4, 8, 10}

S2 = {4, 10}

S2 Í S1

S2 Ì S1

- A set S1 is said to be a subset of S if every element of S1 is also an element of S we write this as S1 Í S. S1 Í S = { If X Î S1 and x Î S }

Example: find the result of {a,f,k} Í {b,c,f,g, k, h}

- If S1 Í S but S contains an element not in S1 we say that S1 is a proper subset of S we write this as S1 Ì S. S1 Ì S = { If S1 Í S and S1 ¹ S }

Example: find the result of

{a,f,k} Í {a,b,c,f,g, k, h} èTrue

{a,f,k} Ì {a,b,c,f,g, k, h} èTrue

{a,f,k} Ì {a,f, k} è False

{a,f,k} Í {a,f, k} è True

Example: Is the {a,f,k}are subset or proper subset from {a,f, k}?subset not a proper subset.

Example: Is the {a,f,k}are subset or proper subset from {a,b,c,f,g, k, h}? subset and a proper subset at the same time.

- S1 and S2 are disjoint sets if S1 ∩ S2 = Ø

Example: Is the {a,f,k} and {a,b,c,f,g, k, h}are disjoint sets? False

- A set is said to be finite if it contain finite number of elements; otherwise it is infinite set.

- The size of finite set is the number of element in it, this is dented by | S |.

EX:

S5 ={x : x > 0 and x is even }

S5 is infinite set

|S1| length of S1

(the no. elements)

Finite set

Example find the size of s = {a,b,c,f,g, k, h}?

|s| = 7

- Power set is the set of all subset of a set S and denoted by 2s and ½ 2s ½ = 2½s ½

EX:

S6 ={a,b,z}

2s6 ={ Ø , {a},{b},{z},{a,b},{a,z},{b,z},{a,b,z}}

| 2s6 | = 2|s6| = 8

EX: if S1 ={1,2,4,5} then its power set is:

2s1={f,{1},{2},{4},{5},{1,2},{1,4},{1,5},{2,4},{2,5},{4,5},{1,2,4},{1,2,5},{1,4,5},{2,4,5},{1,2,4,5}}

½ 2s1 ½ = 2½s1½ =24=16

-Cartesian Product of two sets is given by:

S = S1 X S2 = {(x, y) : x Î S1 and y Î S2 }

The order pair is an two set elements delaminated by open and close parenthesis.

Ex: (1,2) is an order pair differ from the pair (2,1).

EX:

S1 = {a,b,c}

S2 = {x,y,z}

S1 * S2 = {(a,x),(a,y),(a,z),(b,x),(b,y),(b,z),(c,x),(c,y),(c,z)}

- Notes: (1,2) ≠ (2,1)

Example:

Let S1 ={2,4},and S2 ={2,3,5,6} then

S1 X S2 = {(2,2),(2,3),(2,5),(2,6),(4,2),(4,3),(4,5),(4,6)}

Example:

Let S1 ={4,9}, S2 ={2,5,7}, and S3 = { 1,3} then

S1 X S2 X S3 = {(

Domain Range

-Functions and Relations:

Ex: f:s1 S2

F(x) = X2

Y= f(X) = 3X+1

Y= f(X) = sin x +cosx2

- A function is a rule that assign to element of one set unique element of another set.

Ex: is √x a function?

√9= 3,-3

9 is an element at the domain it has two elements (3,-3) at the range set so √x is not a function.

-If f denotes a function then the first set is called the domain of F, and the second set is the range.

F:S1 S2 indicates that the domain of f is a subset of S1, and that the range of f is a subset of S2.

- If the domain of F is all of S1.we say that F is a total functions, otherwise f is said to be partial function.

Ex: Let s1={...,-1,0,1,2,..} and s2 ={0,1,2,3,4,...}

F:s1à s2= F(x)= x+5 then is F is a total function or not? why?

- Relations are more general than functions, in a function each element of the domain has exactly one associated element in the range, in relation there may be several such elements in the range.

Ex: is √x a relation? Yes √9= {3,-3} each element can have more than on image at the range.

Ex: <, >, <=, >= ,<>

Prove that > is a relation not a function?

3> 2 and also 3 > 1 so the element 3 has more than one image at the range.

Ex: x ≡ y (the equivalence relation).

2 ≡ 4/2 ≡ 8/4 ≡ 12/6

Relations conditions:

-Reflexive: 21 ≡ 21 Þ21 ≡21

-Symmetric: 2 ≡ 4/2 Þ 4/2≡2

-Transitive: 2≡4/2 , 4/2≡12/6Þ 2≡12/6

-The relation must satisfy three rules:

-reflexivity: x ≡ x for all x

-symmetric: if x ≡ y then y ≡ x

-transitivity: if x ≡ y and y ≡ z then x ≡ z

G1 = {V,E}

V = {1,2,3}

E = {(1,2),(2,3),(3,1),(2,1)}

Graph :

- A graph is a construct consisting of two finite sets.

- Set of vertices V = { V1 , V2 , V3 , ….. Vn} .

- Set of edges E = { e1 , e2 , e3 , ….. em} .

- Each edge is a pair of vertices from v , ei = (Vi , Vk) is an edge from Vj to Vk , out going for Vj and incoming for Vk .

- Such a construct is actually digraph (directed graph) .

- Both vertices and edges my be labeled .

Example : V = {V1 , V2 , V3} .

E = { (V1 , V3) , (V3 , V3) , (V3 , V1) , (V3 , V2) }

- Walk is said to be sequence e of edges :

Example : { (V1 , V3) , (V3 , V3) , (V3 , V1) , (V1 , V3) , (V3 , V2) }

- The length of walk is the total number of edges .

Example : The length of the above walk equal to 5 .

- Path is a walk in which no edge is repeated .

Example : { (V1 , V3) , (V3 , V3) , (V3 , V1) }

- A path is simple if no vertex is repeated .

Example : { (V1 , V3) , (V3 , V1) }

- Cycle is a walk from vertex to itself with no. repeated edges (path) .

Example : { (V1 , V3) , (V3 , V3) , (V3 , V1) }

- A cycle is to be simple if it is represent a simple path .

Example : { (V1 , V3) , (V3 , V1) }

Trees :

- A tress is a directed graph that has no cycles and that has one distinct vertex called the root such that there is exactly one path from the root to every other vertex.

- The root has no incoming edges.

- Leaf is a vertex without outgoing edges.

- If there is an edge from Vi to Vj, then Vi is said to be the parent of Vj and Vj the child of Vi.

- Level is the number of edges in the path from the root to the vertex .

- Height of the tree is the largest level number of any vertex .

EX: Root

Level 0

Leaf Level 1

Height = 3

Level 2

Level 3

- Proof Techniques:

- Proof by Induction:

It is a prove technique with three steps:

1. Basis step prove (prove the rule for any small value).

2. Induction Assumption (Assume that the rule is true for an n value).

3. Inductive step (Prove the rule for n+1 value).

Example 1 : N * M = å M , N ³ 1

1. Basis:

Let n = 1 , m = 2 1 * 2 = 2

= å 2 = 2

2. Inductive Assumption:

Let the Rule true for N

N * M = å M …….(1)

3. Inductive Step: The rule is true for N+1 So (N + 1) * M = å M

(N + 1) * M = N * M From 1 = S M + M = S M

\ (N + 1) * M = S M = S M

n

Example 2 : Show that : Sn = S i = n>=, n>=0

0

- Basis : n = 0 Sn = å i = 0 =

- Inductive Assumption:

n

å i = is true for n ³ 0

i=0

- Induction Step :

Sn + 1 = Sn + n + 1 =

=

=

- Proof by contradiction :

Ex :

Show that 2 is not a rational number .

Note:

A rational no. is a no. that can be expressed as a ratio of two integers n and m so that m and n hare no common factor .

Solution:

Assume Ö2 is a ration no. so that 222 = n/m , where n, m are integers with out common factors.

Ö2=n/m Þ (Ö2)2 =(n/m)2 Þ 2m2 = n2

There for n2 must be even this implies that n is even ,so that we can write n=2k or 2m2=(2k)2 Þ 2m2 = 4k2 Þ m2=2k2

There for m is even .but this contradicts our assumption that n and m have no. common factors, they m and n can not exist and Ö2 is not a rational no.

Language:

-Language means a system suitable for the expression of certain ideas, facts, or concepts including a set of symbols (in natural languages called words or tokens or phrases) and rules (grammar) for their manipulation (for producing statements at the language or strings).

The natural languages are not formal languages because the problem of ambiguity which means the same symbol may have different meanings and that will lead to more than one interpretation for the same string.

-This definition is not sufficient for the study of formal language; to have precise definition for the language we need the following:

å (Alphabet): non empty set of symbols.

- String infinite sequence of symbols form the alphabet.

Ex:

If S ={a,b} then abab and aaabbba are strings on S

Note:

We use a,b,c,……,z as an element of S and u,v,w for string name

Ex:

u = bbbaa

Operations on Strings:

1- Concatenation of two string w and v denoted by wv.

EX: if w = a1,a2,…,an

and v = b1,b2,…,bm

then (concatenation of w an v ) wv=a1 a2…an b1b2…bm

EX: concatenation

W = abab

u = cdcd

Wu = ababcdcd

2- Revers of a string is obtained by writing the symbols in reverse order if W is a string then its revers denoted by WR

EX: if W = a1a2...an then

WR = anan-1...a2a1

EX: WR

Revers

W = abab

WR=baba

Note that if W = WR then we called w as a palindrome (mirror image).

Ex: madam Im adam

3- String length: (denoted by│W│) is the number of symbols in the string.

EX: if V= aaabb then │V│=5

Find the string length W =abab : │W│ = 4

4. Empty string (denoted by l the lamda string): a string with no symbols

EX: │l│= 0 , lW=Wl =W

5- Substring:

Consecutive characters in another string.

EX: V and u are substrings in W where

W = VU , v called prefix and U called suffix.

EX: IF W = abbab then

{l , a,ab,abb,abba,abbab}

is the set of all prefix of W while

bab,ab,b are some of its suffixes.

6- Concatenation Length:

│uv│=│u│+│v│

EX: IF u=aaa andv=bbb then │uv│=│aaabbb│= 6

And │uv│=│u│+│v│=│aaa│+│bbb│= 3+3 = 6

- String power:

Wn stands for string obtained by repeating (concatenating) the string W N times.

A special case Wo = l

* Star – closure : S*

Is the set of strings obtained by concatenating zero or more symbols from S.

EX:

IF S ={a,b} then S*={l,a,b,aa,ab,ba,bb,…}

* Positive closure: S+ = S* - l (Repeat the S concatenations one or more times).

EX:

IF S={a,b} then S+ ={a,b,aa,ab,ba,bb,…}

- S* and S+ are always infinite.

- A language is define very generally as subset of S*. L Í S*

- A string in a language L will be called a sentence. S ÎS*

- Finite languages: is a language with specified number of sentences.

EX:

S={a,b,c}

L1 ={a,ab,ca,bc}

If S ={a,b} then L ={a,aa,aab} is a language in S and called finite language.

- Infinite languages: is a language with unlimited number of sentences.

If S={a,b} then L={anbn : n ³ 0}

Is an infinite language in S and l, ab, aabb, aaabbb are string in L.

Ex: Define a language that generate the sentences { ab, abab, ababab, …}?

Ex: Define a language that generate the sentences { abcab, ababcabab, …}?

Language complements: