{"id":2910,"date":"2025-06-06T04:30:50","date_gmt":"2025-06-06T04:30:50","guid":{"rendered":"https:\/\/diznr.com\/?p=2910"},"modified":"2025-06-06T04:30:50","modified_gmt":"2025-06-06T04:30:50","slug":"discrete-mathematics-day-06-discrete-mathematics-for-gate-computer-science-examples-based-on-group-semi","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/discrete-mathematics-day-06-discrete-mathematics-for-gate-computer-science-examples-based-on-group-semi\/","title":{"rendered":"Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group."},"content":{"rendered":"

Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.<\/p>\n

[fvplayer id=”170″]<\/p>\n

Discrete Mathematics – Day 06: Semigroup in Discrete Mathematics (For GATE CSE)<\/strong><\/h3>\n

\u00a0Introduction to Semigroup<\/strong><\/h3>\n

A semigroup<\/strong> is an algebraic structure<\/strong> consisting of a set and an associative binary operation. It is one of the fundamental concepts in discrete mathematics, especially in abstract algebra and theoretical computer science.<\/p>\n

Definition of Semigroup<\/strong><\/h3>\n

A set SS<\/span>S<\/span><\/span><\/span><\/span> with a binary operation \u2217*<\/span>\u2217<\/span><\/span><\/span><\/span> is called a semigroup<\/strong> if it satisfies the following property:<\/p>\n

Closure Property<\/strong>: If a,b\u2208Sa, b \\in S<\/span>a<\/span>,<\/span>b<\/span>\u2208<\/span><\/span>S<\/span><\/span><\/span><\/span>, then a\u2217b\u2208Sa * b \\in S<\/span>a<\/span>\u2217<\/span><\/span>b<\/span>\u2208<\/span><\/span>S<\/span><\/span><\/span><\/span>.
Associativity<\/strong>: For all a,b,c\u2208Sa, b, c \\in S<\/span>a<\/span>,<\/span>b<\/span>,<\/span>c<\/span>\u2208<\/span><\/span>S<\/span><\/span><\/span><\/span>, (a\u2217b)\u2217c=a\u2217(b\u2217c)(a * b) * c = a * (b * c)<\/span>(<\/span>a<\/span>\u2217<\/span><\/span>b<\/span>)<\/span>\u2217<\/span><\/span>c<\/span>=<\/span><\/span>a<\/span>\u2217<\/span><\/span>(<\/span>b<\/span>\u2217<\/span><\/span>c<\/span>)<\/span><\/span><\/span><\/span>.<\/p>\n

Note<\/strong>: A semigroup does not necessarily<\/strong> have an identity element or inverses.<\/p>\n

\u00a0Examples of Semigroup<\/strong><\/h3>\n

Example 1: (Natural Numbers with Addition)<\/strong><\/h4>\n

\u00a0Set: S=N={1,2,3,4,\u2026\u2009}S = \\mathbb{N} = \\{1, 2, 3, 4, \\dots\\}<\/span>S<\/span>=<\/span><\/span>N<\/span>=<\/span><\/span>{<\/span>1<\/span>,<\/span>2<\/span>,<\/span>3<\/span>,<\/span>4<\/span>,<\/span>\u2026<\/span>}<\/span><\/span><\/span><\/span>
\u00a0Operation: ++<\/span>+<\/span><\/span><\/span><\/span> (Addition)<\/p>\n

Closure<\/strong>: a+ba + b<\/span>a<\/span>+<\/span><\/span>b<\/span><\/span><\/span><\/span> is always a natural number.
Associativity<\/strong>: (a+b)+c=a+(b+c)(a + b) + c = a + (b + c)<\/span>(<\/span>a<\/span>+<\/span><\/span>b<\/span>)<\/span>+<\/span><\/span>c<\/span>=<\/span><\/span>a<\/span>+<\/span><\/span>(<\/span>b<\/span>+<\/span><\/span>c<\/span>)<\/span><\/span><\/span><\/span> always holds.<\/p>\n

Conclusion<\/strong>: (N,+)(\\mathbb{N}, +)<\/span>(<\/span>N<\/span>,<\/span>+<\/span>)<\/span><\/span><\/span><\/span> is a semigroup<\/strong>.<\/p>\n

Example 2: (Non-zero Integers with Multiplication)<\/strong><\/h4>\n

Set: S=Z\u2217={\u2026,\u22123,\u22122,\u22121,1,2,3,\u2026\u2009}S = \\mathbb{Z}^* = \\{ \\dots, -3, -2, -1, 1, 2, 3, \\dots\\}<\/span>S<\/span>=<\/span><\/span>Z<\/span>\u2217<\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>{<\/span>\u2026<\/span>,<\/span>\u2212<\/span>3<\/span>,<\/span>\u2212<\/span>2<\/span>,<\/span>\u2212<\/span>1<\/span>,<\/span>1<\/span>,<\/span>2<\/span>,<\/span>3<\/span>,<\/span>\u2026<\/span>}<\/span><\/span><\/span><\/span>
\u00a0Operation: \u00d7\\times<\/span>\u00d7<\/span><\/span><\/span><\/span> (Multiplication)<\/p>\n

Closure<\/strong>: Multiplication of two integers is an integer.
Associativity<\/strong>: (a\u00d7b)\u00d7c=a\u00d7(b\u00d7c)(a \\times b) \\times c = a \\times (b \\times c)<\/span>(<\/span>a<\/span>\u00d7<\/span><\/span>b<\/span>)<\/span>\u00d7<\/span><\/span>c<\/span>=<\/span><\/span>a<\/span>\u00d7<\/span><\/span>(<\/span>b<\/span>\u00d7<\/span><\/span>c<\/span>)<\/span><\/span><\/span><\/span>.<\/p>\n

Conclusion<\/strong>: (Z\u2217,\u00d7)(\\mathbb{Z}^*, \\times)<\/span>(<\/span>Z<\/span>\u2217<\/span><\/span><\/span><\/span><\/span><\/span><\/span>,<\/span>\u00d7<\/span>)<\/span><\/span><\/span><\/span> is a semigroup<\/strong>.<\/p>\n

Example 3: (Set of Matrices with Matrix Multiplication)<\/strong><\/h4>\n

\u00a0Set: Mn(R)M_n(\\mathbb{R})<\/span>M<\/span>n<\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span>(<\/span>R<\/span>)<\/span><\/span><\/span><\/span>, the set of all n\u00d7nn \\times n<\/span>n<\/span>\u00d7<\/span><\/span>n<\/span><\/span><\/span><\/span> real matrices.
\u00a0Operation: Matrix Multiplication.<\/p>\n

Closure<\/strong>: The product of two n\u00d7nn \\times n<\/span>n<\/span>\u00d7<\/span><\/span>n<\/span><\/span><\/span><\/span> matrices is an n\u00d7nn \\times n<\/span>n<\/span>\u00d7<\/span><\/span>n<\/span><\/span><\/span><\/span> matrix.
Associativity<\/strong>: Matrix multiplication follows the associative property.<\/p>\n

Conclusion<\/strong>: (Mn(R),\u00d7)(M_n(\\mathbb{R}), \\times)<\/span>(<\/span>M<\/span>n<\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span>(<\/span>R<\/span>)<\/span>,<\/span>\u00d7<\/span>)<\/span><\/span><\/span><\/span> forms a semigroup<\/strong>.<\/p>\n

\u00a0Difference Between Semigroup and Monoid<\/strong><\/h3>\n
\n\n\n\n\n\n\n\n
Property<\/strong><\/th>\nSemigroup<\/strong><\/th>\nMonoid<\/strong><\/th>\n<\/tr>\n<\/thead>\n
Closure<\/strong><\/td>\n\u00a0Required<\/td>\n\u00a0Required<\/td>\n<\/tr>\n
Associativity<\/strong><\/td>\n\u00a0Required<\/td>\n\u00a0Required<\/td>\n<\/tr>\n
Identity Element<\/strong><\/td>\n\u00a0Not required<\/td>\n\u00a0Must exist<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

Pro Tip:<\/strong> If a semigroup has an identity element<\/strong>, it becomes a monoid<\/strong>.<\/p>\n

\u00a0GATE Questions Based on Semigroup<\/strong><\/h3>\n

Q1:<\/strong> Which of the following is a semigroup but not a monoid?
A) (Z,+)(\\mathbb{Z}, +)<\/span>(<\/span>Z<\/span>,<\/span>+<\/span>)<\/span><\/span><\/span><\/span>
B) (N,\u00d7)(\\mathbb{N}, \\times)<\/span>(<\/span>N<\/span>,<\/span>\u00d7<\/span>)<\/span><\/span><\/span><\/span>
C) (Mn(R),\u00d7)(M_n(\\mathbb{R}), \\times)<\/span>(<\/span>M<\/span>n<\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span>(<\/span>R<\/span>)<\/span>,<\/span>\u00d7<\/span>)<\/span><\/span><\/span><\/span>
D) (N,+)(\\mathbb{N}, +)<\/span>(<\/span>N<\/span>,<\/span>+<\/span>)<\/span><\/span><\/span><\/span><\/p>\n

Answer:<\/strong> C<\/strong> (Matrix multiplication is associative but does not have an identity for all elements).<\/p>\n

\u00a0Conclusion<\/strong><\/h3>\n

\u00a0A semigroup<\/strong> is a set with an associative binary operation<\/strong>.
\u00a0It does not require<\/strong> an identity element.
\u00a0Common examples include natural numbers under addition<\/strong> and matrices under multiplication<\/strong>.
\u00a0Understanding semigroups helps in algebra, automata theory, and computer science applications.<\/p>\n

\u00a0Want more GATE-level examples on semigroups? Let me know!<\/strong><\/p>\n

Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.<\/a><\/h3>\n

Discrete Mathematics for Computer Science<\/a><\/h3>\n

DISCRETE MATHEMATICS AND GRAPH THEORY<\/h3>\n

Title Discrete Mathematics Author Prof. Abhay Saxena ..<\/a><\/h3>\n

Here\u2019s a quick and clear explanation of Semigroups<\/strong> in Discrete Mathematics (Day 06)<\/strong> with examples<\/strong>\u2014especially useful for GATE Computer Science<\/strong> preparation:<\/p>\n

\n

\ud83d\udcd8 Semigroup \u2013 Definition<\/strong><\/h2>\n

A semigroup<\/strong> is a set<\/strong> equipped with a binary operation<\/strong> (like +, \u00d7, etc.) that is:<\/p>\n

    \n
  1. \n

    Closed<\/strong><\/p>\n<\/li>\n

  2. \n

    Associative<\/strong><\/p>\n<\/li>\n<\/ol>\n

    \n

    \u26a0\ufe0f A semigroup does not require<\/strong> an identity element or inverses (unlike a monoid or group).<\/p>\n<\/blockquote>\n

    \n

    \ud83d\udd0d Formal Definition<\/strong><\/h3>\n

    A *semigroup (S, )<\/em> satisfies:<\/p>\n