Day 06Part 02- Discrete Mathematics for Gate Computer – Algebraic Structure and Binary operations.<\/p>\n
[fvplayer id=”175″]<\/p>\n
Here\u2019s a detailed learning guide for:<\/p>\n
A binary operation<\/strong> on a set S<\/strong> is a function:<\/p>\n \u2217:S\u00d7S\u2192S*: S \\times S \\rightarrow S<\/span>\u2217<\/span>:<\/span><\/span>S<\/span>\u00d7<\/span><\/span>S<\/span>\u2192<\/span><\/span>S<\/span><\/span><\/span><\/span><\/span><\/p>\n That means: An algebraic structure<\/strong> is a set equipped with one or more binary operations. Here are common types:<\/p>\n Set + Binary Operation<\/p>\n<\/li>\n Operation is Associative<\/strong><\/p>\n<\/li>\n<\/ul>\n Semigroup + Identity Element<\/strong><\/p>\n<\/li>\n<\/ul>\n Monoid + Inverse Exists for All Elements<\/strong><\/p>\n<\/li>\n<\/ul>\n Group + Commutativity<\/strong><\/p>\n<\/li>\n<\/ul>\n Let \u2217*<\/span>\u2217<\/span><\/span><\/span><\/span> be a binary operation defined on the set S={0,1,2}S = \\{0, 1, 2\\}<\/span>S<\/span>=<\/span><\/span>{<\/span>0<\/span>,<\/span>1<\/span>,<\/span>2<\/span>}<\/span><\/span><\/span><\/span> as
For any two elements a,b\u2208Sa, b \\in S<\/span>a<\/span>,<\/span>b<\/span>\u2208<\/span><\/span>S<\/span><\/span><\/span><\/span>, the result a\u2217b\u2208Sa * b \\in S<\/span>a<\/span>\u2217<\/span><\/span>b<\/span>\u2208<\/span><\/span>S<\/span><\/span><\/span><\/span>.<\/p>\n
\n\u2734\ufe0f 2. Examples of Binary Operations<\/strong><\/h3>\n
\n\n
\n \nOperation<\/th>\n Set<\/th>\n Binary?<\/th>\n Reason<\/th>\n<\/tr>\n<\/thead>\n \n a+ba + b<\/span>a<\/span>+<\/span><\/span>b<\/span><\/span><\/span><\/span><\/td>\n Integers<\/td>\n \u2705 Yes<\/td>\n Result is an integer<\/td>\n<\/tr>\n \n a\u2212ba – b<\/span>a<\/span>\u2212<\/span><\/span>b<\/span><\/span><\/span><\/span><\/td>\n Natural Numbers<\/td>\n \u274c No<\/td>\n Result may be negative<\/td>\n<\/tr>\n \n a\u22c5bmod\u2009\u2009na \\cdot b \\mod n<\/span>a<\/span>\u22c5<\/span><\/span>b<\/span><\/span>mod<\/span><\/span>n<\/span><\/span><\/span><\/span><\/td>\n Zn\\mathbb{Z}_n<\/span>Z<\/span>n<\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/td>\n \u2705 Yes<\/td>\n Remains in Zn\\mathbb{Z}_n<\/span>Z<\/span>n<\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\n\ud83e\uddf1 3. Algebraic Structures<\/strong><\/h3>\n
\ud83d\udd39 Semigroup<\/strong><\/h4>\n
\n
\ud83d\udd39 Monoid<\/strong><\/h4>\n
\n
\ud83d\udd39 Group<\/strong><\/h4>\n
\n
\ud83d\udd39 Abelian Group<\/strong><\/h4>\n
\n
\n\ud83d\udd01 4. Important Properties of Binary Operations<\/strong><\/h3>\n
\n\n
\n \nProperty<\/th>\n Definition<\/th>\n<\/tr>\n<\/thead>\n \n Closure<\/strong><\/td>\n \u2200a,b\u2208S,a\u2217b\u2208S\\forall a,b \\in S, a * b \\in S<\/span>\u2200<\/span>a<\/span>,<\/span>b<\/span>\u2208<\/span><\/span>S<\/span>,<\/span>a<\/span>\u2217<\/span><\/span>b<\/span>\u2208<\/span><\/span>S<\/span><\/span><\/span><\/span><\/td>\n<\/tr>\n \n Associativity<\/strong><\/td>\n a\u2217(b\u2217c)=(a\u2217b)\u2217ca * (b * c) = (a * b) * c<\/span>a<\/span>\u2217<\/span><\/span>(<\/span>b<\/span>\u2217<\/span><\/span>c<\/span>)<\/span>=<\/span><\/span>(<\/span>a<\/span>\u2217<\/span><\/span>b<\/span>)<\/span>\u2217<\/span><\/span>c<\/span><\/span><\/span><\/span><\/td>\n<\/tr>\n \n Commutativity<\/strong><\/td>\n a\u2217b=b\u2217aa * b = b * a<\/span>a<\/span>\u2217<\/span><\/span>b<\/span>=<\/span><\/span>b<\/span>\u2217<\/span><\/span>a<\/span><\/span><\/span><\/span><\/td>\n<\/tr>\n \n Identity<\/strong><\/td>\n a\u2217e=aa * e = a<\/span>a<\/span>\u2217<\/span><\/span>e<\/span>=<\/span><\/span>a<\/span><\/span><\/span><\/span> and e\u2217a=ae * a = a<\/span>e<\/span>\u2217<\/span><\/span>a<\/span>=<\/span><\/span>a<\/span><\/span><\/span><\/span><\/td>\n<\/tr>\n \n Inverse<\/strong><\/td>\n For each aa<\/span>a<\/span><\/span><\/span><\/span>, a\u2217a\u22121=ea * a^{-1} = e<\/span>a<\/span>\u2217<\/span><\/span>a<\/span>\u22121<\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>e<\/span><\/span><\/span><\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\n\ud83d\udcdd GATE-Style Sample Question:<\/strong><\/h3>\n
\n
a\u2217b=(a+b)mod\u2009\u20093a * b = (a + b) \\mod 3<\/span>