Noida Institute of Engineering and Technology Algebraic Structures PDF

Noida Institute of Engineering and Technology, Greater Noida Algebraic Structures Unit: II Discrete Structures (ACSE-306) Mr. Eshank Jain Asst. P...

Noida Institute of Engineering and Technology, Greater Noida Algebraic Structures Unit: II Discrete Structures (ACSE-306) Mr. Eshank Jain Asst. Prof., CSE Deptt. B.Tech 3rd Semester  Noida Institute of Engineering and Technology, Greater Noida Eshank Jain is an Assistant Professor at Computer Science and Engineering Department, Noida Institute of Engineering and Technology, Gr Noida. he has done M.Tech from Gautam Budh Technical University, Lucknow His area of research includes distributed system , Database ,Computer Networks and Internet of Things. She has published research paper in reputed journal and conference proceedings. 10/27/2024 Eshank Jain Discrete Structures Unit 2 2  Evaluation Scheme End Periods Evaluation Schemes Semest er Cour Sl. Subject To Cre Subject se No. code tal dit Type L T P CT TA TOTAL PS TE PE 1 Engineering Mathematics-III 3 1 0 30 20 50 100 150 4 BSC 2 Discrete Structures 3 1 0 30 20 50 100 150 4 ESC 3 Digital Logic and IoT Systems 3 0 0 30 20 50 100 150 3 ESC Data Structures and 4 3 0 0 30 20 50 100 150 3 PCC Algorithms - 1 Computer Organization and 5 3 0 0 30 20 50 100 150 3 PCC Architecture Object Oriented Techniques 6 0 0 6 50 100 150 3 PCC using Java Data Structures and 7 Algorithms - 1 0 0 4 50 50 100 2 PCC Lab Digital Logic and IoT Systems 8 0 0 2 25 25 50 1 ESC Lab 9 Internship Assessment 0 0 2 50 50 1 PW AI & 10 Cyber Ethics/Environmental 2 0 0 30 20 50 50 100 0 NC Science 10/27/2024 11 MOOCsEshank Jain Discrete Structures Unit 2 3 110  Subject Syllabus B. TECH. SECOND YEAR ACSE0306 DISCRETE STRUCTURES Course objective: The subject enhances one’s ability to develop logical thinking and ability to problem-solving. The objective of discrete structure is to enables students to formulate problems precisely, solve the problems, apply formal proofs techniques and explain their reasoning clearly.. Pre-requisites: 1. Basic Understanding of mathematics 2. Basic knowledge algebra. 3. Basic knowledge of mathematical notations 10/27/2024 4 Eshank Jain Discrete Structures Unit 2  Subject Syllabus Course Contents / Syllabus UNIT-I Set Theory, Relation 8 Hours Set Theory: Definition of sets, countable and uncountable sets, Set operations, Partition of set, Cardinality, Venn Diagrams, proofs of some general identities on sets. Relation: Definition, types of relation, composition of relations, Equivalence relation, Partial ordering relation. UNIT-II Algebraic Structures 8 Hours Algebraic Structures: Definition, Properties, types: Semi Groups, Monoid, Groups, Abelian group, Properties of groups, Subgroup, cyclic group, Permutation group, Cosets, Normal subgroup, Homomorphism and isomorphism of Groups. 10/27/2024 5 Eshank Jain Discrete Structures Unit 2  Subject Syllabus UNIT-III Posets, Hasse Diagram and Lattices 8 Hours Introduction, ordered set, Hasse diagrams of partially ordered set, isomorphic ordered set, well ordered set, properties of lattices, types of lattices. UNIT-IV Propositional Logic 8 Hours Propositional Logic: Propositions and compound Propositions, Basic logical operations, truth tables, tautologies, Contradictions, CNF, DNF Algebra of Proposition, logical implications, logical equivalence, predicates and quantifiers, Rules of Inference Predicate Logic: First order predicate, Well-formed formula of Predicate, Quantifiers, Inference Theory of Predicate Logic. 10/27/2024 6 Eshank Jain Discrete Structures Unit 2  Subject Syllabus UNIT-V Graphs 8 Hours Definition and terminology, Representation of Graphs, Paths connectivity, Walks, Paths, Cycles, Bipartite, Regular, Planar and connected graphs, Components, Euler graphs, Euler's theorem, Hamiltonian path and circuits, Graph coloring, chromatic number, isomorphism and homomorphism of graphs. Mr. Eshank Jain Discrete 10/27/2024 7 Structures Unit 2  Application in CSE 1. Discrete Structures are useful in studying and describing objects and problems in branches of computer science such as computer algorithms, programming languages. 2. Computer implementations are significant in applying ideas from discrete mathematics to real-world problems, such as in operations research. 3. It is a very good tool for improving reasoning and problem- solving capabilities. 4. Discrete mathematics is used to include theoretical computer science, which is relevant to computing. 5. Discrete structures in computer science with the help of process algebras. 10/27/2024 Eshank Jain Discrete Structures Unit 2 8  Course Objective The subject enhances one’s ability to develop logical thinking and ability to problem solving. The objective of discrete structure is to enables students to formulate problems precisely, solve the problems, apply formal proofs techniques and explain their reasoning clearly. 10/27/2024 9 Eshank Jain Discrete Structures Unit 2  Course Outcome Course Bloom’s Outcome At the end of course , the student will be able to Knowledge (CO) Level (KL) CO1 Apply the basic principles of sets, relations & functions and mathematical K3 induction in computer science & engineering related problems CO2 Understand the algebraic structures and its properties to solve complex K2 problems CO3 Describe lattices and its types and apply Boolean algebra to simplify digital K2 circuit. CO4 Infer the validity of statements and construct proofs using predicate logic K4 formulas. CO5 Design and use the non-linear data structure K4 like tree and graphs to solve real world problems. 10/27/2024 10 Eshank Jain Discrete Structures Unit 2  Program Specific Outcomes Program S. No Specific PSO Description Outcomes 1. PSO 1 Identify, analyse real world problems and design their ethical solutions using artificial intelligence, robotics, virtual/augmented reality, data analytics, block chain technology, and cloud computing. 2. PSO 2 Design and develop the hardware sensor devices and related interfacing software systems for solving complex engineering problems. 3. PSO 3 Understand inter-disciplinary computing techniques and to apply them in the design of advanced computing. 4. PSO 4 Conduct investigation of complex problems with the help of technical, managerial, leadership qualities, and modern engineering tools provided by industry-sponsored laboratories. 10/27/2024 11 Eshank Jain Discrete Structures Unit 2  Program Education Objectives (PEOs) S. PE PEO Description No Os 1. PEO 1 To have an excellent scientific and engineering breadth to comprehend, analyze, design and provide sustainable solutions for real-life problems using state-of-the-art technologies. 2. PEO 2 To have a successful career in industries, to pursue higher studies or to support entrepreneurial endeavours and to face global challenges. 3. PEO 3 To have an effective communication skill, professional attitude, ethical values and a desire to learn specific knowledge in emerging trends, technologies for research, innovation and product development and contribution to society. 4. PEO 4 To have life-long learning for up-skilling and re-skilling for successful professional career as engineer, scientist, 10/27/2024 entrepreneur, and bureaucrat for betterment of society. 12 Eshank Jain Discrete Structures Unit 2  Program Outcomes Engineering Graduates will be able to Understand: 1. Engineering knowledge 2. Problem analysis 3. Design/development of solutions 4. Conduct investigations of complex 5. Modern tool usage 6. The engineer and society 7. Environment and sustainability 8. Ethics 9. Individual and team work 10. Communication 11. Project management and finance 12. Life-long learning 10/27/2024 13 Eshank Jain Discrete Structures Unit 2  CO-PO Mapping PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 ACSE0306.1 3 2 2 - - 1 - - - 1 1 3 ACSE0306.2 3 3 2 2 1 - - - - - 2 1 ACSE0306.3 3 3 2 1 - - 3 - 2 2 2 2 ACSE0306.4 3 3 2 1 - - 1 - - 3 2 2 ACSE0306.5 3 3 2 1 - - 3 - - 1 3 3 AVERAGE 3 2.8 2 1.25 1 1 2.33 2 1.75 2 2.2 10/27/2024 14 Eshank Jain Discrete Structures Unit 2  CO-PSO Mapping PSO1 PSO2 PSO3 PSO4 ACSE030 6.1 1 2 3 - ACSE030 6.2 1 2 3 1 ACSE030 6.3 3 2 3 1 ACSE030 6.4 2 3 3 - ACSE030 6.5 2 3 2 - AVERAGE 1.8 2.4 2.8.6 10/27/2024 Eshank Jain Discrete Structures Unit 2 15  End Semester Question Paper Templates (Offline Pattern/Online Pattern 10/27/2024 16 Eshank Jain Discrete Structures Unit 2  End Semester Question Paper Templates (Offline Pattern/Online Pattern 10/27/2024 17 Eshank Jain Discrete Structures Unit 2  End Semester Question Paper Templates (Offline Pattern/Online Pattern 10/27/2024 18 Eshank Jain Discrete Structures Unit 2  End Semester Question Paper Templates (Offline Pattern/Online Pattern 10/27/2024 19 Eshank Jain Discrete Structures Unit 2  End Semester Question Paper Templates (Offline Pattern/Online Pattern 10/27/2024 20 Eshank Jain Discrete Structures Unit 2  End Semester Question Paper Templates (Offline Pattern/Online Pattern 10/27/2024 21 Eshank Jain Discrete Structures Unit 2  End Semester Question Paper Templates (Offline Pattern/Online Pattern 10/27/2024 22 Eshank Jain Discrete Structures Unit 2  Result Analysis 10/27/2024 Eshank Jain Discrete Structures Unit 2 23  Prerequisite & Recap Prerequisite Knowledge of Mathematics upto 12th standard. Recap The fundamental concepts of Sets & Relations. 10/27/2024 Eshank Jain Discrete Structures Unit 2 24  Brief Introduction about the subject with video Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic. https://www.youtube.com/watch?v=Dsi7x-A89Mw&list=PL0862D1A94725 2D 20&index=28 https://www.youtube.com/watch?v=74l6t4_4pDg&list=PL0862D1A947252D20 &index=29 https://www.youtube.com/watch?v=4d2XEn1j_q4&list=PL0862D1A947252D2 0&index=30 10/27/2024 25 Eshank Jain Discrete Structures Unit 2  Prerequisite & Recap Prerequisite Basic Understanding of class 10 mathematics NCERT. Recap None – we will begin with basics. Eshank Jain Discrete Structures 10/27/2024 26 Unit 2  Unit Content  Definition  Properties  types: Semi Groups, Monoid, Groups & Abelian group  Properties of groups  Subgroup  cyclic group  Permutation group  Cosets,  Normal subgroup  Homomorphism  Isomorphism of Group Eshank Jain Discrete Structures 10/27/2024 27 Unit 2  Brief Subject Introduction Discrete mathematics is the branch of mathematics dealing with objects that can consider only distinct, separated values. This tutorial includes the fundamental concepts of Sets, Relations, Mathematical Logic, Group theory, Graph Theory Eshank Jain Discrete Structures 10/27/2024 28 Unit 2  Algebraic Structures 10/27/2024 Eshank Jain Discrete Structures Unit 2 29  Operations Commutative: Let * be a binary operation on a set A. The operation * is said to be commutative in A if a * b= b * a for all a, b in A  Associativity: Let * be a binary operation on a set A. The operation * is said to be associative in A if (a * b) * c = a *( b * c) for all a, b, c in A  Identity: For an algebraic system (A, *), an element ‘e’ in A is said to be an identity element of A if a * e = e * a = a for all a ∈ A.  Note: For an algebraic system (A, *), the identity element, if exists, is unique.  Inverse: Let (A, *) be an algebraic system with identity ‘e’. Let a be an element in A. An element b is said to be inverse of A if a * b = b * a = e 10/27/2024 Eshank Jain Discrete Structures Unit 2 30  Algebraic structures Groupoid: Let operation * is binary operation on set G and satisfies the closure property then the algebraic structure (G,*) is called groupoid. Semi Group: An algebraic structure (A, *) is said to be a semi group if 1. * is closed operation on A. 2. * is an associative operation, for all a, b, c in A. Ex. (N, +) ,(z,+) are semi group. Ex. (N,.), (z,.) are semi group. Ex. (N, – ) , (z, -) are not semi group. Monoid: An algebraic structure (A, *) is said to be a monoid if the following conditions are satisfied. 1) * is a closed operation in A. 2) * is an associative operation in A. 3) There is an identity in A. 10/27/2024 Eshank Jain Discrete Structures Unit 2 31  Monoid Example Ex. Show that the set ‘N’ is a monoid with respect to multiplication. Solution: Here, N = {1,2,3,4,……} 1. Closure property : We know that product of two natural numbers is again a natural number. i.e., a.b = b.a for all a,b belongs to N Multiplication is a closed operation. 2. Associativity : Multiplication of natural numbers is associative. i.e., (a.b).c = a.(b.c) for all a,b,c belongs to N 3. Identity : We have, 1 belongs to N such that a.1 = 1.a = a for all a belongs to N. Identity element exists, and 1 is the identity element. Hence, N is a monoid with respect to multiplication. 10/27/2024 Eshank Jain Discrete Structures Unit 2 32  Group and Abelian group Group: An algebraic system (G, *) is said to be a group if the following conditions are satisfied. 1) * is a closed operation. 2) * is an associative operation. 3) There is an identity in G. 4) Every element in G has inverse in G. Abelian group (Commutative group): A group (G, *) is said to be abelian (or commutative) if a*b =b*a a, b G. 10/27/2024 Eshank Jain Discrete Structures Unit 2 33  Example of Abelian group The composition table of G is. 1 –1 i -i 1 1 -1 i - i G = {1, –1, i, –i } is an abelian group -1 -1 1 -i i under multiplication. i i -i -1 1 -i -i i 1 -1 1. Closure property: Since all the entries of the composition table are the elements of the given set, the set G is closed under multiplication. 2. Associativity: The elements of G are complex numbers, and we know that multiplication of complex numbers is associative. 3. Identity : Here, 1 is the identity element and 1 ∈ G. 4. Inverse: From the composition table, we see that the inverse elements of 1, -1, i, -i are 1, -1, -i, i respectively. 5. Commutativity: The corresponding rows and columns of the table are identical. Therefore the binary operation. is commutative. Hence, (G,.) is an abelian group. 10/27/2024 Eshank Jain Discrete Structures Unit 2 34  Example of Abelian group The composition table of G is. 1  2 1 1   2 G = {1, , 2} is an abelian group under    1 multiplication. Where 1, , 2 are cube 2  2  2 1  roots of unity. (CO2) 1. Closure property: Since all the entries of the composition table are the elements of the given set, the set G is closed under multiplication. 2. Associativity: The elements of G are complex numbers, and we know that multiplication of complex numbers is associative. 3. Identity : Here, 1 is the identity element and 1 G. 4. Inverse: From the composition table, we see that the inverse elements of 1 , 2 are 1, 2,  respectively. Hence, G is a group w.r.t multiplication. 5. Commutativity: The corresponding rows and columns of the table are identical. Therefore the binary operation. is commutative. Hence, G is an abelian group w.r.t. multiplication. 10/27/2024 Eshank Jain Discrete Structures Unit 2 35  Sub-semigroup & Sub-monoid Sub-semigroup: Let (S, * ) be a semigroup and let T be a subset of S. If T is closed under operation * , then (T, * ) is called a subsemigroup of (S, * ). Ex: (N,.) is semigroup and T is set of even positive integers then (T,.) is a sub semigroup. Sub-monoid : Let (S, * ) be a monoid with identity e, and let T be a non- empty subset of S. If T is closed and associative under the operation * and e T, then (T, * ) is called a submonoid of (S, * ). 10/27/2024 Eshank Jain Discrete Structures Unit 2 36  Sub groups Definition. A non empty sub set H of a group (G, *) is a sub group of G, if (H, *) is a group. Note: For any group {G, *}, {e, * } and (G, * ) are improper or trivial sub groups ,others are called proper or non trivial sub group. Ex. G = {1, -1, i, -i } is a group w.r.t multiplication. H1 = { 1, 1 } is a subgroup of G. H2 = { 1 } is a trivial subgroup of G. 10/27/2024 Eshank Jain Discrete Structures Unit 2 37  Sub groups Ex. Let (Z, *) be an algebraic structure, where Z is the set of integers and the operation * is defined by n * m = maximum of (n, m). Show that (Z, *) is a semi group. Is (Z, *) a monoid ?. Justify your answer. Solution: Let a , b and c are any three integers. Closure property: Now, a * b = maximum of (a, b) belongs to Z for all a,b belongs to Z Associativity : (a * b) * c = maximum of {a,b,c} = a * (b * c) belongs to (Z, *) is a semi group. Identity : There is no integer x such that a * x = maximum of (a, x) = a for all a belongs to Z Identity element does not exist. Hence, (Z, *) is not a monoid. 10/27/2024 Eshank Jain Discrete Structures Unit 2 38  Theorem 1 Theorem: If every element of a group is its own inverse, then show that the group must be abelian. Proof: Let (G, *) be a group. If a is an element of the group then inverse of a is also a. That means, a-1 =a. Let a and b are any two elements of G. we can write that the product of a and b should also be equal to its inverse. So we will proceed as: (a. b) = (a. b)-1 = b-1. a-1  (a. b) = b. a (since, b-1 =b and a-1 =a) Hence, a. b = b. a, And so G is abelian. 10/27/2024 Eshank Jain Discrete Structures Unit 2 39  Theorem 2 Theorem: A necessary and sufficient condition for a non empty subset H of a group (G, *) to be a sub group is that a  H, b  H  a * b-1  H. Proof: Case1: Let (G, *) be a group and H is a subgroup of G Let a, b  H  b-1  H ( since H is a group)  a * b-1  H. ( By closure property in H) Case2: Let H be a non empty set of a group (G, *). Let a * b-1  H  a, b  H Now, a * a-1  H ( Taking b = a )  e  H i.e., identity exists in H. 10/27/2024 Eshank Jain Discrete Structures Unit 2 40  Continue Now, e  H, a  H  e * a-1  H  a-1  H  Each element of H has inverse in H. Further, a  H, b  H  a  H, b-1  H  a * (b-1)-1  H.  a * b  H.  H is closed w.r.t *. Finally, Let a, b, c  H  a, b, c  G ( since H  G )  (a * b) * c = a * (b * c)  * is associative in H Hence, H is a subgroup of G. 10/27/2024 Eshank Jain Discrete Structures Unit 2 41  Theorem 3 Theorem :In a group (G, *), if (a * b)2 = a2 * b2 a , b  G then show that G is abelian group. Proof: Given that (a * b)2 = a2 * b2  (a * b) * (a * b) = (a * a )* (b * b)  a *( b * a )* b = a * (a * b) * b ( By associative law)  ( b * a )* b = (a * b) * b ( By left cancellation law)  ( b * a ) = (a * b) ( By right cancellation law) Hence, G is abelian group. Note: a2 = a * a a3 = a * a * a etc. 10/27/2024 Eshank Jain Discrete Structures Unit 2 42  Modulo systems Addition modulo m ( +m ) let m is a positive integer. For any two positive integers a and b a +m b = a + b if a + b < m a +m b = r if a + b  m where r is the remainder obtained by dividing (a+b) with m. Multiplication modulo p ( p ) let p is a positive integer. For any two positive integers a and b a p b = a b if a b < p a p b = r if a b  p where r is the remainder obtained by dividing (ab) with p. Ex. 3 5 4 = 2 , 5 5 4 = 0 , 2 5 2 = 4 10/27/2024 Eshank Jain Discrete Structures Unit 2 43  Addition Modulo (+m ) (CO2) The set G = {0,1,2,3,4,5} is a group with respect to addition modulo 6. The composition table of G is +6 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 1. Closure property: Since all the entries of the composition table are the elements of the given set, the set G is closed under +6. 10/27/2024 Eshank Jain Discrete Structures Unit 2 44  Addition Modulo (+m ) (CO2) 2. Associativity: The binary operation +6 is associative in G. for ex. (2 +6 3) +6 4 = 5 +6 4 = 3 and 2 +6 ( 3 +6 4 ) = 2 + 6 1 = 3 3. Identity : Here, The first row of the table coincides with the top row. The element heading that row , i.e., 0 is the identity element. 4.. Inverse: From the composition table, we see that the inverse elements of 0, 1, 2, 3, 4. 5 are 0, 5, 4, 3, 2, 1 respectively. 5. Commutativity: The corresponding rows and columns of the table are identical. Therefore the binary operation + 6 is commutative. Hence, (G, +6 ) is an abelian group. 10/27/2024 Eshank Jain Discrete Structures Unit 2 45  Multiplication Modulo (m ) The set G = {1,2,3,4,5,6} is a group with respect to multiplication modulo 7. The composition table of G is 7 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 4 6 1 3 5 3 3 6 2 5 1 4 4 4 1 5 2 6 3 5 5 3 1 6 4 2 6 6 5 4 3 2 1 1. Closure property: Since all the entries of the composition table are the elements of the given set, the set G is closed under 7. 10/27/2024 Eshank Jain Discrete Structures Unit 2 46  Multiplication Modulo (m ) (CO2) 2. Associativity: The binary operation 7 is associative in G. for ex. (2 7 3) 7 4 = 6 7 4 = 3 and 2 7 ( 3 7 4 ) = 2 7 5 = 3 3. Identity : Here, The first row of the table coincides with the top row. The element heading that row , i.e., 1 is the identity element. 4. Inverse: From the composition table, we see that the inverse elements of 1, 2, 3, 4. 5 ,6 are 1, 4, 5, 2, 5, 6 respectively. 5. Commutativity: The corresponding rows and columns of the table are identical. Therefore the binary operation 7 is commutative. Hence, (G, 7 ) is an abelian group. 10/27/2024 Eshank Jain Discrete Structures Unit 2 47  Order Order of an element of a group: Let (G, *) be a group. Let ‘a’ be an element of G. The smallest integer n such that a n = e is called order of ‘a’. If no such number exists then the order is infinite. Order of group: The number of elements in a group is called order of group.  Ex: Group of order 1, 2 and 3  G = {1, -1, i, -i} is a group w.r.t multiplication of order 4.  G = ({0,1,2,3,4,5}, +6) is a group of order 6.  G = {1, w, w2} is a group. Find order of its elements. 10/27/2024 Eshank Jain Discrete Structures Unit 2 48  Cyclic group Cyclic group: Cyclic groups are groups in which every element is an integral power of some fixed element. A group G is called cyclic if for some element a belongs to G, every element is of the form an where n is some integer. G = {an :n belongs to Z} and, G = [a], The element a is called a generator. If order of group and order of any element of that group is equal then that element will be the generator of that group.  Cyclic groups are Abelian.  If a is the generator of Cyclic group G then a -1 is also the generator of group G.  For an infinite cyclic group, there can be two and only two generators. 10/27/2024 Eshank Jain Discrete Structures Unit 2 49  Homomorphism and Isomorphism Homomorphism : Consider the groups ( G, *) and ( G1, ) A function f : G G1 is called a homomorphism if f ( a * b) = f(a)  f (b) a , b  G and f(a), f(b)  G1 Isomorphism : If a homomorphism f : G G1 is a bijection then f is called isomorphism between G and G1.Then we write G  G1 10/27/2024 Eshank Jain Discrete Structures Unit 2 50  Permutation Group A group G is called a permutation group on a nonempty set A if the elements of G are some permutations of A and the group operation is the composition of two functions.. This permutation group is called the symmetric group on n elements and is denoted by Sn. Let α ∈ Sn. Generally we demonstrate α in the following way: 1 −→ α(1) 2 −→ α(2) α : 3 −→ α(3)... n −→ α(n) 10/27/2024 Eshank Jain Discrete Structures Unit 2 51  Example of Homomorphic group Ex. Let R be a group of all real numbers under addition and R + be a group of all positive real numbers under multiplication. Show that the mapping f : R + R defined by f(x) = log10 x for all x  R is an isomorphism. Solution: First, let us show that f is a homomorphism. Let a , b  R+. Now, f(a.b) = log10 (a.b) = log10 a + log10 b = f(a) + f(b)  f is an homomorphism. Next, let us prove that f is a Bijection. 10/27/2024 Eshank Jain Discrete Structures Unit 2 52  Continue For any a , b  R+ , Let, f(a) = f(b)  log10 a = log10 b  a = b  f is one.to-one. Next, take any c  R. Then 10c  R and f (10c) = log10 10c = c.  Every element in R has a pre image in R+. i.e., f is onto.  f is a bijection. Hence, f is an isomorphism. 10/27/2024 Eshank Jain Discrete Structures Unit 2 53  Theorem for Homomorphism Theorem: Consider the groups ( G1, *) and ( G2, ) with identity elements e1 and e2 respectively. If f : G1 G2 is a group homomorphism, then prove that a) f(e1) = e2 b) f(a-1) = [f(a)]-1 c) If H1 is a sub group of G1 and H2 = f(H1), then H2 is a sub group of G2. d) If f is an isomorphism from G1 onto G2, then f –1 is an isomorphism from G2 onto G1. 10/27/2024 Eshank Jain Discrete Structures Unit 2 54  Proof a) we have in G2, e2  f(e1) = f (e1) ( since, e 2 is identity in G2) = f (e1 * e1) ( since, e1 is identity in G1) = f(e1)  f(e1) ( since f is a homomorphism) e2 = f(e1) ( By right cancellation law ) b) For any a  G1, we have f(a)  f(a-1) = f (a * a-1) = f(e1) = e2 and f(a-1)  f(a) = f (a-1 * a) = f(e1) = e2  f(a-1) is the inverse of f(a) in G2 i.e., [f(a)]-1 = f(a-1) 10/27/2024 Eshank Jain Discrete Structures Unit 2 55  Continue… c) H2 = f (H1) is the image of H1 under f; this is a subset of G2. Let x , y  H2. Then x = f(a) , y = f(b) for some a,b H 1 Since, H1is a subgroup of G1, we have a * b-1  H1. Consequently, x  y-1 = f(a)  [f(b)]-1 = f(a)  f(b-1) = f (a * b-1) f(H1) = H2 Hence, H2 is a subgroup of G2. 10/27/2024 Eshank Jain Discrete Structures Unit 2 56  Continue… d) Since f : G1 G2 is an isomorphism, f is a bijection.  f –1 : G2 G1 exists and is a bijection. Let x, y  G2. Then x  y  G2 and there exists a, b  G1 such that x = f(a) and y = f(b).  f –1 (x  y ) = f –1 (f(a)  f(b) ) = f –1 (f (a* b ) ) = a*b = f –1 (x) * f –1 (y) This shows that f –1 : G2 G1 is an homomorphism as well.  f –1 is an isomorphism. 10/27/2024 Eshank Jain Discrete Structures Unit 2 57  Cosets If H is a sub group of( G, * ) and a  G then the set Ha = { h * a, h  H}is called a right coset of H in G. Similarly, aH = {a * h, h  H}is called a left coset of H is G. The index of H in G, denoted [G : H], is equal to the number of left cosets of H in G. Note:- 1) Any two left (right) cosets of H in G are either identical or disjoint. 2) Let H be a sub group of G. Then the right cosets of H form a partition of G. i.e., the union of all right cosets of a sub group H is equal to G. 3) Lagrange’s theorem: The order of each sub group of a finite group is a divisor of the order of the group. 4) The order of every element of a finite group is a divisor of the order of the group in particular a m = e 5) The converse of the lagrange’s theorem need not be true. 10/27/2024 Eshank Jain Discrete Structures Unit 2 58  State and prove Lagrange’s Theorem Lagrange’s theorem: The order of each sub group H of a finite group G is a divisor of the order of the group. Proof: Since G is finite group, H is finite. Therefore, the number of cosets of H in G is finite. Let Ha1,Ha2, …,Har be the distinct right cosets of H in G. Then, G = Ha1Ha2 …, Har So that O(G) = O(Ha1)+O(Ha2) …+ O(Har). But, O(Ha1) = O(Ha2) = ….. = O(Har) = O(H)  O(G) = O(H)+O(H) …+ O(H). (r terms) = r. O(H) This shows that O(H) divides O(G). 10/27/2024 Eshank Jain Discrete Structures Unit 2 59  Normal Subgroup Let G be a group. A subgroup H of G is said to be a normal subgroup of G if for all h∈ H and x∈ G, x h x-1∈ H If x H x-1 = {x h x-1| h ∈ H} then H is normal in G if and only if xHx - 1 ⊆H, ∀ x∈ G Normal subgroups are also known as invariant subgroups or self- conjugate subgroup. A subgroup H of a group G is known as normal subgroup of G if every left coset of H in G is equal to the corresponding right coset of H in G. That is, gH=Hg for every g ∈ G. The normal subgroup is often denoted by using the symbol ► or◄. That is, if N is a normal subgroup of G or N is normal in G, then it is denoted as N◄G. Quotient Group: A quotient group or factor group is a group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure. It is denoted 10/27/2024 Eshankby JainZ/pZ, where Discrete p is anUnit Structures Integer. 2 60  Weekly Assignment 1. Let (G, *) be a group, where * is usual multiplication operation on G. Then show that for any x, y ∈G following equations holds: (x-1)-1 = x (xy)-1 = y-1x-1 2. Write the properties of Group. Show that the set(1,2,3,4,5)is not group under addition and multiplication modulo 6. 3. Show that (R – {1}, *) where the operation is defined as a*b = a +b –ab is an abelian group. 4. Let G = (Z2, +) be a group and let H be a subgroup of G where H = {(x, y) | x = y}. Find the left cosets of H in G. Here Z is the set of integers 5. Let u8 = {1, 3, 5, 7} be a group with binary operation multiplication modulo 8. Find all proper subgroups of u8. 6. Prove that (R, +, *) is a ring without zero divisors, where R is 2×2 matrix and + and * are usual addition and multiplication operations. Eshank Jain Discrete Structures 10/27/2024 61 Unit 2  Daily Quiz 1. In a group there must be only __________ element. a) 1 b) 2 c) 3 d) 5 2. _____ is the multiplicative identity of natural numbers. a) 0 b) -1 c) 1 d) 2 3. The set of even natural numbers, {6, 8, 10, 12,..,} is closed under addition operation. Which of the following properties will it satisfy? a) closure property b) associative property c) symmetric property d) identity property 4. If (M, *) is a cyclic group of order 73, then number of generator of G is equal to ______ a) 89 b) 23 c) 72 d) 17 10/27/2024 Eshank Jain Discrete Structures 62 Unit 2  Daily Quiz A group G, ({0}, +) under addition operation satisfies which of the following properties? a) identity, multiplicity and inverse b) closure, associativity, inverse and identity c) multiplicity, associativity and closure d) inverse and closure 6. Let G be a finite group with two sub groups M & N such that |M|=56 and |N|=123. Determine the value of |M ⋂N|. a) 1 b) 56 c) 14 d) 78 7. Let * be the binary operation on the rational number given by a*b=a+b+ab. Which of the following property does not exist for the group? a) closure property b) identity property c) symmetric property d) associative property 10/27/2024 Eshank Jain Discrete Structures 63 Unit 2  UNIT WISE MCQ 11. A function f:(M,∗)→(N,×) is a homomorphism if ______ a) f(a, b) = a*b b) f(a, b) = a/b c) f(a, b) = f(a)+f(b) d) f(a, b) = f(a)*f(a) 12. Condition of semigroup homomorphism should be ____________ a) f(x * x) = f(x * y) b) f(x) = f(y) c) f(x) * f(y) = f(y) d) f(x * y) = f(x) * f(y) 13. The set of rational numbers form an abelian group under _________ a) Association b) Closure c) Multiplication d) Addition 10/27/2024 Eshank Jain Discrete Structures 64 Unit 2  UNIT WISE MCQ 14. If F is a free semigroup on a set S, then the concatenation of two even words is ________ a) a semigroup of F b) a subgroup of F c) monoid of F d) cyclic group of F 15. The set of odd and even positive integers closed under multiplication is ________ a) a free semigroup of (M, ×) b) a subsemigroup of (M, ×) c) a semigroup of (M, ×) d) a subgroup of (M, ×) 16. If a * b = a such that a ∗ (b ∗ c) = a ∗ b = a and (a * b) * c = a * b = a then ________ a) * is associative b) * is commutative c) * is closure d) * is abelian 10/27/2024 Eshank Jain Discrete Structures 65 Unit 2  Expected Questions for University Exam Q1. What is algebraic structure ? List properties of algebraic system. Q2. Show that the set G = {x + y √2 |x,y ∊ Q} is a group with respect to addition. Q3. Prove that (Z6, (+6)) is an abelian group of order 6, where Z6={0,1,2, 3, 4, 5}. Q5. Let G be a group and let a, b ∊ G be any elements. Q6. Prove that the intersection of two subgroups of a group is also subgroup. 10/27/2024 Eshank Jain Discrete Structures Unit 2 66  Old Question Papers 1.Define normal subgroup. 2. Let G = {1,-1, 𝑖, }𝑖 with the operation of ordinary multiplication on G be an algebraic structure, where 𝑖=√-1. (i) Determine whether G is abelian. (ii) Determine the order of each element in G. (iii) Determine whether G is a cyclic group, if G is a cyclic group, then determine the generator/generators of the group G. (iv) Determine a subgroup of the group G. For more Previous year Question papers: https://drive.google.com/drive/folders/1xmt08wjuxu71WAmO9Gxj2iDQ0lQf-so1 Eshank Jain Discrete Structures 10/27/2024 67 Unit 2  Recap of Unit Now you were able to understand the concepts discrete structures include Algebraic Structures. Eshank Jain Discrete Structures 10/27/2024 68 Unit 2  Summary The subject enhances one’s ability to develop logical thinking and ability to problem solving. 10/27/2024 Eshank Jain Discrete Structures Unit 2 69  Faculty Video Links, Youtube & NPTEL Video Links and Online Courses Details Youtube/other Video Links https://www.youtube.com/watch?v=dQ4wU0k7JKI&list=PL0862D1A 947252D20&index=35 https://www.youtube.com/watch?v=urd468CJCcU&list=PL0862D1A 947252D20&index=36 https://www.youtube.com/watch?v=YB6CP1RUvgk&list=PL0862D1 A947252D20&index=37 https://www.youtube.com/watch?v=yDQhErltWUg NEPTEL video link: https://nptel.ac.in/courses/111/105/111105112/ 10/27/2024 Eshank Jain Discrete Structures Unit 2 70  Glossary Questions 1. Write the properties of Group. Show that the set(1,2,3,4,5)is not group under addition and multiplication modulo 6. 2. Show that (R – {1}, *) where the operation is defined as a*b = a +b –ab is an abelian group. 3. Let G = (Z2, +) be a group and let H be a subgroup of G where H = {(x, y) | x = y}. Find the left cosets of H in G. Here Z is the set of integers 4. Let (G, *) be a group, where * is usual multiplication operation on G. Then show that for any x, y ∈G following equations holds:(x -1)-1 = x and (xy)-1 = y-1x-1 5. Let u8 = {1, 3, 5, 7} be a group with binary operation multiplication modulo 8. Find all proper subgroups of u8. 10/27/2024 Eshank Jain Discrete Structures Unit 2 71  References  B. Kolman, R.C. Busby, and S.C. Ross, Discrete Mathematical Structures, 5/e, Prentice Hall, 2004.  Liptschutz, Seymour, “ Discrete Mathematics”, McGraw Hill.  Trembley, J.P & R. Manohar, “Discrete Mathematical Structure with Application to Computer Science”, McGraw Hill  Koshy, Discrete Structures, Elsevier Pub. 2008 Kenneth H. Rosen, Discrete Mathematics and Its Applications, 6/e, McGraw-Hill, 2006. 10/27/2024 Eshank Jain Discrete Structures Unit 2 72  Thank You 10/27/2024 Eshank Jain Discrete Structures Unit 2 73