dsa

Discrete structure: 

By:- Kumar S iddarth Bansal (100101114)  Group Mansi M ahajan (100101126)  Semi Group Anadi Vats (100101030)  M onoid Ashwin Soman (100101056 )  Permutation group Jishnu V. Nair (100101100)  homomorphism and isomorphism Discrete structure Presented to:- Mrs. Shashi P rabha

group: 

(G,*) be an algebraic structure where * is binary operation, then (G,*) is called a group if following conditions are satisfied: 1. Closure law : The binary * is a closed operation i.e. a*b є G for all a,b є G. 2 .Associative law : The binary operation * is an associative operation i.e. a*(b*c)=(a*b)*c for all a,b,c є G. 3.Identity element : There exist an identity element i.e. for some e є S, e * a=a* e ,a є G. 4.Inverse law : For each a in G, there exist an element a′ ( inverse of a) in G such that a*a′=a′*a=e. group

examples: 

examples Consider three colored blocks (red, green, and blue), initially placed in the order RGB. Let a be the operation "swap the first block and the second block", and b be the operation "swap the second block and the third block". We can write xy for the operation "first do y , then do x "; so that ab is the operation RGB → RBG → BRG, which could be described as "move the first two blocks one position to the right and put the third block into the first position". If we write e for "leave the blocks as they are" (the identity operation), then we can write the six permutations of the three blocks as follows: e : RGB → RGB a : RGB → GRB b : RGB → RBG ab : RGB → BRG ba : RGB → GBR aba : RGB → BGR

Semi group: 

An algebraic structure (S,*) is called a semigroup if the following conditions are satisfied: 1. The binary operation * is a closed operation i.e. . a*b є S for all a,b є S (closure law) 2. The binary operation * is an associative operation i.e. a*(b*c)=(a*b)*c for all a,b,c є S. (associative law) Semi group

examples: 

1. (N,+),(N,*) (Z,+),(Z,*) (Q,+),(Q,*) (R,+),(R,*) are all semigroup where N,Z,Q,R respectively denote set of natural numbers, set of integers ,set of rational numbers, set of real numbers as; (N,+) is set of natural numbers a+( b+c )=( a+b )+c(associative law) 1+(2+3)=(1+2)+3 1+5=3+3 6+6 Hence ,it holds associative law, and a,b,c є N, follows Clouser law examples

examples: 

2.We know that every group (G,*) is a semigroup.Thus G={1,2,3,4} is a group under multiplication moduls 5 is also the semi group. Proof: i)Closure law verified ii)Associative law verified i.e.(1*2)*3=1*(2*3). iii)Identity element = 1 thus, it is a semigroup . examples * 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1

monoid: 

An algebraic structure (S,*) is called monoid if following conditions are satisfied: 1.The binary operation * is a closed operation. 2.The binary operation * is an associative operation 3.There exist an identity element i.e. for some e є S, e * a=a * e =a for all a є S. Thus a monoid is a semi group (S,*) that has identity element monoid

examples: 

1. For each operation * define below, determine whether it is a monoid or not: i)on N ,a*b=a 2 +b 2 a)Closure  2*5=4+25=29, 3*4=9+16=25…. i .e (a*b є G) b) Asociative  (2*5)*3=2*(5*3) 29*3=2(25+9) (29)+(3)=(2)+(34) 850=4+1156 850 != 1160 not a monoid . examples

examples: 

ii) on R,where a*b= ab /3 a) Closure : 5*3=5*3/3=5 --- real 6*4=6*4/3=8 --- real b) Associative : 2*(5*3)=(2*5)*3 2*5=(2*5/3)*3 2*5/3=2*5*3/3*3 10/3=10/3 examples

examples: 

iii)Identity ae =a ae = ae /3 2ae=0 e=0 Thus it is a monoid … examples

examples: 

2. Let * be the operation on set R of real numbers defined by a*b=a+b+2ab Find 2*3,3*(-5), and 7* (½) Is (R,*) is a monoid ??? Find identity element Which element have inverse and what are they??? i) 2*3 = 2+3+2*2*3 =17 ii)3*(-5) = 3 – 5 + 2 * 3 * -5 = 3 – 5 -30 = -32 examples

examples: 

iii) 7 * (½) = 7 + (½) + 2 * 7 * (½) = 14(½) =14.5 b) Is (R,*) a monoid ??? a) closure: 2*3=17, 3*-5 = -32, 7 * (½) = 14.5 all are real no. i.e. ( a*b є G ) checked b) associative : (2*3)*4 = 2*(3*4) (2+3+2*2*3)*4 = 2*(3+4+2*3*4) (17*4) = (2*31) examples

examples: 

(17+4+2*17*4) = (2+31+2*31*2) 21+136 = 33+124 157=157 Checked c)Identity : a e=a identity a e = a+e+ae  0= ae+e+ae 0= 2ae+e e(2a+1)=0 e=0 identity element = 0 examples

examples: 

c) Find inverse a a -1 = e [ but e = 0] a a -1 = 0 let a -1 = x ax = 0 [ax = a+x+2ax] 2ax+x = -a x(2a+1)= -a x = (-a/2a+1) a -1 = [-a/2a+1]……. No inverse will be at a= (½) examples

Permutation group: 

Let A be finite set .then a function f : A  A is said to be permutation of A if f is one-one f is onto i.e. A bijection from A to itself is called permutation of A. The number of distinct element in the finite set A is called the degree of permutation Permutation group

Equality of two permutation: 

Let f and g be two permutation on a set X.Then f=g if and only if f(x)=g(x) for all x in X. Example: f= g = Evidently f(1)=2=g(1) , f(2)=3=g(2) f(3)=4=g(3) Thus f(x)=g(x) for all x ϵ {1,2,3} which implies that f=g Equality of two permutation

Identity permutation: 

If each element of a permutation be replaced by itself.then it is called the identity permutation and is denoted by the symbol I. For example: I = I s an identity permutation. Identity permutation

Product of permutation: 

The product of two permutations f and g of same degree is denoted by fog or fg , meaning first perform f then perform g. f= g= Then fog = Product of permutation

Inverse permutation: 

Since a permutation is one-one onto map and hence it is inversible , i.e , every permutation f on a set P={a1,a2,a3,….an} Has a unique inverse permutation denoted by f -1 Thus if f= Then f -1= Inverse permutation

properties: 

Closure property Associative property Existence of identity Existence of inverse properties

Cyclic permutation: 

A permutation which replaces n objects cyclically is called a cyclic permutation of degree n. Let , P= We can simply write it S=(1 2 3 4) Cyclic permutation

examples: 

Let A = {1,2} then number of permution group = 2 Similarly if A={1,2,3} then no. of permutation group = 6 The six permutations on  written as permutations in cycle form are 1,(1 2),(1 3),(2 3),(1 2 3),(2 1 3) examples

example: 

example

Homomorphism and isomorphism: 

Homomorphism and isomorphism A homomorphism is a map between two groups which respects the group structure. More formally, let G and H be two group, and f a map from G to H (for every g∈G , f(g)∈H). Then f is a homomorphism if for every g 1 ,g 2 ∈G, f(g 1 g 2 )=f(g 1 )f(g 2 ). For example, if H<G, then the inclusion map i(h)= h∈G is a homomorphism. Another example is a homomorphism from Z to Z given by multiplication by 2, f(n)=2n. This map is a homomorphism since f( n+m )=2( n+m )=2n+2m=f(n)+f(m).

Homomorphism and isomorphism: 

A group isomorphism is a special type of group homomorphism. It is a mapping between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the respective group operations. If there exists an isomorphism between two groups, then the groups are called isomorphic . Isomorphic groups have the same properties and the same structure of their multiplication table. Let ( G , *) and ( H , #) be two groups, where "*" and "#" are the binary operations in G and H , respectively. A group isomorphism from ( G , *) to ( H , #) is a bijection from G to H , i . e . a bijective mapping f : G → H such that for all u and v in G one has f ( u * v ) = f ( u ) # f ( v ). Two groups ( G , *) and ( H , #) are isomorphic if an isomorphism between them exists. This is written: ( G , *)  ( H , #) If H = G and the binary operations # and * coincide, the bijection is an automorphism . Homomorphism and isomorphism

EXAMPLES: 

EXAMPLES The group of all real numbers with addition, (R,+), is isomorphic to the group of all positive real numbers with multiplication (R + ,×): via the isomorphism f ( x ) = e x