Unitjhdksjfksdjfksjfhikdlfjiksdfds 1.pptx

dfr

1. TOC UNIT 1 Prepared by ARSHAD NANAKKAL ASST PROFESSOR DEPT OF COMPUTER SCIENCE MCAS, VENGARA

2. Syllabus Introduction to Mathematical preliminaries: Sets, Functions and Relations, graphs and trees, Strings and their Properties, Proof techniques: By induction, by contradiction.

3. Sets A set is a collection of well-defined objects . Well-defined object means object are distinct and distinguishable ex: the set of all students in a college use the capital letters A, B, C,.... for denoting sets. The small letters a, b, c,..... are used to denote the elements of any set. When a is an element of the set A. we write a∈A . When a is not an element of set A, we write a∉A

4. Various Ways Of Describing A Set Method of extension (Roster or Tabular method) Expressing elements of a set within braces where elements are separated by commas Ex: A={1,2,3,4,5} Method of intension (Rule or Set builder method) Expressing elements of a set by rule Ex: A={ x|x is an odd number} Method of recursion: Expressing elements of a set by recursive computational rule Ex: A={ a n | a = 1, a n+1 = a n + 3} i.e it is a set of all natural numbers leaving a remainder 1 when divided by 3

5. Subset A set A is said to be a subset of set B (written as A ⊆ B), if every element of A is also an element of B. Two sets A and B are equal (we write A = B) if their members are the same.  If A =B, then A ⊆ B and B ⊆ A . A set with no element is called an empty set , also called a null set or a void set , and is denoted by ø. ; ø = {} A set A is said to be a superset of set B(written as A ⊇ B), if B is fully contained in A

6. Trivial And Proper Subset For every set A ,A and ø are called trivial subset of A Any subset of A which is not trivial is called proper subset of A Ex: If A={1,2},B={1},C={2} ,then subset {} or φ and subset {1,2} or A are trivial subset and subset {1} 0r B and subset {2} or C are proper subset . i.e B ⊂ A and C ⊂ A B ⊂ A means B is a proper subset A . i.e every element of B is in A, but A has more elements.

7. Power Set The set of all subsets of a set A including the null set ,is called the power set of A. It is denoted by P(A) If set A={1} then P(A) = {{},{1}} If set A={1,2} then P(A) = {{},{1},{2},{1,2}} If set A={1,2,3} then P(A)={{},{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}} For a given set with n elements, power set contains 2 n elements (sets).

8. Operations On Sets Union - A U B = {x |x ∈A or x ∈B} Intersection - A ∩ B = {x | x ∈A and x ∈B} Difference/relative complement – A - B = {x |x ∈A and x ∉ B} Complement - A c = {x |x ∈ U and x ∉ A} U - Universal set, the set of all elements under consideration. Ex: If A={1,2,3} and B={3,4,5}, then AU B={1,2,3,4,5} A ∩ B ={3} , A – B ={1,2} and B-A ={4,5} If A ∩ B = φ ,then set A and set B is called disjoint sets ( i.e they do not have any common element)

9. A U B A ∩ B A B A B A-B A c A B

10. Properties Of Sets: Commutative law:  A ∪ B = B ∪ A and A ∩ B = B ∩ A Associative law:  A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C Distributive law:  A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and  A ∩ (B U C) = (A ∩ B) U (A ∩ C)

11. Idempotent law: A ∪ A = A and A ∩ A = A Identity law: A ∪ φ = A A ∩ φ = φ A ∪ U = U A ∩ U = A Involution law (A’)’ = A

12. Absorption law:  A ∪ (A ∩ B) = A and  A ∩ (A U B) = A Demorgan’s law:  (A ∪ B)’ = A’ ∩ B’ and (A ∩ B)’ = A’ ∪ B’

13. Cartesian Product / Cross Product Cross product of two set A and B is is represented as A x B . A x B = {(a, b) |a ∈ A and b ∈ B} i.e Let A and B be two sets. Then A x B is defined as all possible ordered pair ,whose first coordinate is an element of A and second is an element of B. If set A contain ‘m’ elements and set B contains ‘n’ elements then A x B contain ‘mn’ elements . (a, b) ≠ (b, a) Ex: If A={1,2} and B={ a,b } then A x B={(1,a),(1,b),(2,a),(2,b)}

14. Relation A Relation or Binary relation R from set A to B is a subset of cartesian product A x B   i.e R ⊆ (A x B) = {( x,y ) | x ∈ A and y ∈ B } When (x, y) is in R, we write xRy or R( x,y ) or ( x,y ) ∈ R Ex: A={2,4,6,8} ,B={1,3,7} ;R={( x,y )|x<y} then R={(2,3),(2,7),(4,7),(6,7)} Here (2,3) ∈ R and (2,1) ∉ R

15. Domain and Range If there are two sets A and B, and relation R have order pair (x, y), then − The  domain  of R, Dom(R), is the set {x|( x,y )∈R for some y in B} The  range  of R, Ran(R), is the set {y|( x,y ) ∈R for some x in A} Ex: If set A={1,2},set B={2,4} and relation R={(1,2),(2,2)},then Dom(R)={1,2},Ran(R)={2}

16. Properties of Relation Reflexive Relation:  A relation R on a set A is called reflexive if ( a,a ) ∈ R holds for every element a ∈ A . Ex: If set A = {1,2,3} then R = {(1,1), (2,2),(3,3)} is reflexive. Symmetric Relation:  A relation R on a set A is called symmetric if ( b,a ) ∈ R holds when ( a,b ) ∈ R . Ex: Relation R = {(1,2),(2,1)} on set A = {1,2,3} is symmetric. Transitive Relation:  A relation R on a set A is called transitive if ( a,b ) ∈ R and ( b,c ) ∈ R then ( a,c ) ∈ R for all a,b,c ∈ A. Ex: Relation R={(1,2),(2,3),(1,3)} on set A={1,2,3} is transitive. Antisymmetric Relation: A relation R on a set A is called antisymmetric if ( x,y ) ∈ R and ( y,x ) ∈ R then x=y Ex: Relation R = {(1,2),(2,3)(1,1)} on set A = {1,2,3} is antisymmetric

17. Equivalence Relation:  A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive. Ex: R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)} on set A={1,2,3,4} is equivalence relation Partial order Relation:  A relation is an Partial order Relation if it is reflexive, transitive and antisymmetric. Ex: R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,4),(1,4)} on set A={1,2,3,4} is partial order relation

18. Equivalence Class Let A be a non empty set and R be a equivalent relation on A Let x ∈ A then equivalence class of x with respect to R is denoted as [x] [x] = {y| y ∈ A and ( x,y ) ∈ R} Ex: Given R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)} on set A={1,2,3,4} is equivalence relation, then [1]={1,2}; [2]={1,2}; [3]={3}; [4]={4}

19. Closure of Relation Sometime a given relation R defined in a set A may not be reflexive, symmetric or transitive By adding more ordered pair to R we can make it reflexive or symmetric or transitive Closure of relation is obtained by adding minimum number of ordered pairs to make the relation reflexive, symmetric or transitive

20. Reflexive closure The reflexive closure of a relation R on set A is obtained by adding ( a,a ) to R for each a ∈ A . Symmetric closure The symmetric closure of a relation R on set A is obtained by adding ( b,a ) to R for each ( a,b ) ∈ R . Transitive closure The transitive closure of a relation R on set A is obtained by repeatedly adding ( a,c ) to R for each ( a,b ) ∈ R and ( b,c ) ∈ R .

21. Ex: Given a relation R ={(1, 2), (2, 3), (1,1), (2, 2)} on set A= {1, 2, 3} ,then - Reflexive closure r(R) = {(1, 2), (2, 3), (1,1), (2, 2), (3,3)} - Symmetric closure s(R) = {(1, 2), (2, 3), (1,1), (2, 2), (2,1), (3,2) } - Transitive closure t(R) = {(1, 2), (2, 3), (1,1), (2, 2), (1,3)}

22. Let R be a relation in a set A. Then the transitive closure of R (denoted by R + ) is the smallest transitive relation containing R. Let R be a relation in a set A. Then the reflexive-transitive closure of R (denoted by R* ) is the smallest reflexive and transitive relation containing R. Ex: Let R = {(1, 2), (2, 3), (2, 4)} be a relation in set A = {1, 2, 3, 4}. Find R + ? R + = {(1, 2), (2, 3), (2, 4), (1,3), (1,4)} Ex: If R = {(a, b), (b, c), (c, a)} is a relation in {a, b, c}, find R* ? R* = {(a, b), (b, c), (c, a), (a, c), (b, a), (c, c), (c, b), (b, b), (a, a) }

23. Function A function f from a set A to a set B is a rule which associates every element x ϵ A , to a unique element in B , which is denoted by f(x) If f is a function from A to B, it is written as f: A -> B  i.e f maps A to B.

24. Terms Related To Functions: Domain and co-domain  – if f is a function from set A to set B, then A is called Domain and B is called co-domain. Range  – Range of f is the set of all images of elements of A. Basically Range is subset of co- domain. Image and Pre-Image  – b is the image of a and a is the pre-image of b if f(a) = b.

25. Function Representation Two methods Giving the image of all elements Ex: f: A -> B defined by A = {a,b,c} , B = {1,2,3,4} f(a)=1, f(b)=2 and f(c)=3 2. By computation rule Ex: f: R -> R defined by f(x) =x 2 +1 , x ϵ A

26. Function Types Injection (One - One) Surjection (On - to) Bijection (One – One On - to)

27. Injection (One - One) A function f:A→B is called injective if there is a unique output for every input   i.e for all elements a and b in set A, if f(a) = f(b) , then it must be a = b. Ex: f: A -> B

28. Surjection (On - to)   A function f:A→B is called surjective if each element of B has it’s pre-image in A. Here range = co-domain Ex: f: A -> B

29. Bijection (One – One On – to) A function is Bijective function if it is both injective and surjective Ex: f: A -> B

30. The Pigeonhole Principle It states that if there are fewer pigeon holes than total number of pigeons and each pigeon is put in a pigeon hole, then there must be at least one pigeon hole with more than one pigeon i.e If m pigeons are put into n pigeonholes where n < m , there's a hole with more than one pigeon.

31. Graph  A graph consists of a non-empty set of vertices or nodes and a set of edges. i.e a graph  G=(V,E) ,Where V is the vertices and E is the Edges V={v1,v2,v3,… v n } ; E={(v i , v j )| v i , v j ϵ V} No of vertices is order and no of edges is size Ex Here V={1,2,3,4} and E={{1,2},{2,4},{4,3},{3,1}}

32. Types of Graph (1) Simple graph It does not contain any loops or multiple edges(parallel edges). Ex :

33. (2 ) Multi-Graph It is a graph having at least one self loop or multiple edges(parallel edges ). Ex:

34. (3) Directed Graph (Digraph) It is a graph with edges having a direction i.e it is made of ordered vertex pair . Ex: Here V={1,2,3,4} E={(1,2),(1,4),(2,4)(3,1)(4,3)} ( u,v ) means there is an edge from vertex u to vertex v ( u,v ) ≠( v,u ) ( u,v ) is uni directional

35. (4) Undirected Graph It is a graph with edges having a no direction i.e it is made of unordered vertex pair . Ex: Here V={1,2,3,4} E={{1,2},{1,4},{2,4}{3,1}{4,3}} { u,v } means there is an edge from vertex u to vertex v and vertex v to vertex u { u,v } = { v,u } { u,v } is bi directional

36. Weighted Graph It is a graph whose each edge carry a weight or cost Ex:

37. Graph Representation

38. Tree Tree is a discrete structure that represents hierarchical relationships between individual elements or nodes.  A Tree is a connected acyclic graph. In tree between every pair of vertices there exist a unique path Ex:

39. A tree with N number of vertices contains (N−1)  number of edges.  A tree in which every node has at most two children( i.e 0,1 and 2) is called a binary tree. Ex :

40. String It is a finite collection of symbols from the alphabet( ∑ ). The string is denoted by w . A string with zero occurrences of symbols is known as an empty string . It is denoted by ε . The Kleene Closure (∑*) gives the infinite set of all possible strings of all possible lengths over ∑ including  ε . ( i.e it is a universal set ) The Positive Closure( ∑ + ) gives the infinite set of all possible strings of all possible lengths over ∑ excluding ε .

41. String Operations (1) Length of a String : Definition − It is the number of symbols present in a string. (Denoted by  |w| ). Examples − If w = ‘ cabcad ’, |w|= 6 If |w|= 0, it is called an  empty string  (Denoted by  ε )

42. (2) Substring: Let “w” be a string on an alphabet ∑, a string “u” is said to be substring of w, if u appears within the string w. Examples − For the string “ abb ” the substrings are: -Zero length substring:  ε -One  length substring: a,b -Two  length substring: ab,bb -Three  length substring: abb

43. ( 3) Prefix of a string : Definition - A substring with the sequence of beginning symbols of a given string is called a “prefix”. Ex:For a string “ abb ” , the possible prefixes are: - ε (zero length prefix) - a(one length prefix) - ab (two length prefix) - abb (three length prefix) Proper prefix is a prefixes except the given string. Ex: for a string “ abb ” the possible proper prefixes are : ε, a , ab.

44. (4) Suffix of a string : Definition   - A substring with the sequence of ending symbols of a given string is called a “suffix”. Ex:For a string abb , the possible suffixs are: - ε (zero length suffix) - b(one length suffix) - bb (two length suffix) - abb (three length suffix) Proper suffix is a suffix except the given string Ex: For a string abb,the possible proper suffix are : ε, b , bb

45. ( 5) Reversal : Definition   - Reversal of a string w denoted w R is the string spelled backwards Ex: if w=00111 then w R =11100 (6) Concatenation : It combines two strings by putting them one after the other. Example - - x = abc , y = mnop , then x ◦ y = abcmnop , or simply xy = abcmnop .Here yx = mnopabc - The concatenation of the empty string with any other string gives the string itself

46. Properties Of String Concatenation Concatenation is associative - Let x, y and z be three strings over the alphabet ∑ , then x ( y z ) = ( x y ) z 2. Existence of   Identity element . - For all strings x ϵ ∑* there exist an identity element ε ϵ ∑* such that x ε . = ε x = x  

47. 3. Left and Right cancellations Let x,y,z ϵ ∑* , then zx = zy implies x =y (left cancellation) xz = yz implies x =y (right cancellation) 4. For strings x, y we have | xy | = |x| + |y| where |x|, |y| , | xy | denote the lengths of the strings x, y, xy , respectively .

48. Proof Techniques Two methods Proof by induction Proof by contradiction

49. Method Of Proof By Induction This method consists of three basic steps: Step 1: Prove P(n) for n = 0/1. This is called the proof for the basis . Step 2: Assume the result for P(n). This is called the induction hypothesis . Step 3: Prove P(n + l) using the induction hypothesis of P(n)

50. Prove the following theorem by induction: 1 + 2 + 3 + ... + n = n(n + 1)/2 Solution (a) Proof for the basis. For n = 1, L.H.S . = 1 and R.H.S . = 1(1 + 1)/2 = 1 i.e P(1) is true (b) Assume P(n) is true i.e P(n) = 1 + 2 + 3 + ... + n = n(n + 1)/2 is true (c) We have to prove P(n + 1) is true P(n+1) = 1 + 2 + 3 + … + (n + 1) = (n + 1)(n + 2)/2 = > LHS = 1 + 2 + 3 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) =(n(n+1)+2(n+1))/2 = (n + 1)(n + 2)/2 = RHS

51. Prove the following theorem by induction: 1 + 3 + 5 + ... + r =n 2 . for all n > 0. Where r is an odd integer and n is the number of terms in the sum. (Note: r = 2n - 1.) Solution (1) Proof for the basis. For n =1. L.H.S. =1 and R.H.S. =1 2 =1. Hence the result is true for n = 1. i.e P(1) is true (2 ) By induction hypothesis, we have P(n) = 1 + 3 + 5 + ... + r = n 2 . As r = 2n - 1. i.e P(n)=1 + 3 + 5 + ... + (2n - 1) = n 2 (3) We have to prove that P(n+1) is true P(n+1) = 1 + 3 + 5 + ... + (2n - 1) + (2(n +1)-1)= (n + 1) 2 : L.H.S . = 1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = = n 2 + 2n + 1 = (n + 1) 2 = R.H.S . Prove 1 2 + 2 2 + 3 2 + ... + n 2 = n(n + 1)(2n + 1)/6 by induction.

52. Method Of Proof By Contradiction Assume your statement to be false. Proceed as you would with a direct proof. Come across a contradiction. State that because of the contradiction, it can't be the case that the statement is false, so it must be true

53. prove “ √2 is irrational “ by contradiction Solution Suppose √ 2 is rational. Then integers a and b exist , So that √ 2 = a/b. Hence we can assume that a and b have no common factors. Squaring both side , we get 2 = a 2 /b 2 i.e a 2 = 2 b 2 So we see that a 2 is even. This means that a is even .

54. So a = 2m for some m ∈ Z.  a 2  = (2m) 2 = 4m 2 .  We have a 2 = 2 b 2 i.e 2b 2 = 4m 2 which, after dividing by 2, gives b 2 = 2m 2 so b 2 is even. This means b = 2n for some n ∈ Z.  We’ve seen that if √ 2 = a/b then both a and b must be even and so are both multiples of 2. This contradicts the fact that we know a and b can be chosen to have no common factors.  Thus, √ 2 must not be rational,  so √ 2 is irrational.