Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.
Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.
Contents [hide]
- 0.1 Discrete Mathematics – Day 06: Semigroup in Discrete Mathematics (For GATE CSE)
- 0.2 Introduction to Semigroup
- 0.3 Definition of Semigroup
- 0.4 Examples of Semigroup
- 0.5 Difference Between Semigroup and Monoid
- 0.6 GATE Questions Based on Semigroup
- 0.7 Conclusion
- 0.8 Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.
- 0.9 Discrete Mathematics for Computer Science
- 0.10 DISCRETE MATHEMATICS AND GRAPH THEORY
- 0.11 Title Discrete Mathematics Author Prof. Abhay Saxena ..
- 1
Semigroup – Definition
- 2
Examples of Semigroups
Discrete Mathematics – Day 06: Semigroup in Discrete Mathematics (For GATE CSE)
Introduction to Semigroup
A semigroup is an algebraic structure 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.
Definition of Semigroup
A set SS with a binary operation ∗* is called a semigroup if it satisfies the following property:
Closure Property: If a,b∈Sa, b \in S, then a∗b∈Sa * b \in S.
Associativity: For all a,b,c∈Sa, b, c \in S, (a∗b)∗c=a∗(b∗c)(a * b) * c = a * (b * c).
Note: A semigroup does not necessarily have an identity element or inverses.
Examples of Semigroup
Example 1: (Natural Numbers with Addition)
Set: S=N={1,2,3,4,… }S = \mathbb{N} = \{1, 2, 3, 4, \dots\}
Operation: ++ (Addition)
Closure: a+ba + b is always a natural number.
Associativity: (a+b)+c=a+(b+c)(a + b) + c = a + (b + c) always holds.
Conclusion: (N,+)(\mathbb{N}, +) is a semigroup.
Example 2: (Non-zero Integers with Multiplication)
Set: S=Z∗={…,−3,−2,−1,1,2,3,… }S = \mathbb{Z}^* = \{ \dots, -3, -2, -1, 1, 2, 3, \dots\}
Operation: ×\times (Multiplication)
Closure: Multiplication of two integers is an integer.
Associativity: (a×b)×c=a×(b×c)(a \times b) \times c = a \times (b \times c).
Conclusion: (Z∗,×)(\mathbb{Z}^*, \times) is a semigroup.
Example 3: (Set of Matrices with Matrix Multiplication)
Set: Mn(R)M_n(\mathbb{R}), the set of all n×nn \times n real matrices.
Operation: Matrix Multiplication.
Closure: The product of two n×nn \times n matrices is an n×nn \times n matrix.
Associativity: Matrix multiplication follows the associative property.
Conclusion: (Mn(R),×)(M_n(\mathbb{R}), \times) forms a semigroup.
Difference Between Semigroup and Monoid
Property | Semigroup | Monoid |
---|---|---|
Closure | Required | Required |
Associativity | Required | Required |
Identity Element | Not required | Must exist |
Pro Tip: If a semigroup has an identity element, it becomes a monoid.
GATE Questions Based on Semigroup
Q1: Which of the following is a semigroup but not a monoid?
A) (Z,+)(\mathbb{Z}, +)
B) (N,×)(\mathbb{N}, \times)
C) (Mn(R),×)(M_n(\mathbb{R}), \times)
D) (N,+)(\mathbb{N}, +)
Answer: C (Matrix multiplication is associative but does not have an identity for all elements).
Conclusion
A semigroup is a set with an associative binary operation.
It does not require an identity element.
Common examples include natural numbers under addition and matrices under multiplication.
Understanding semigroups helps in algebra, automata theory, and computer science applications.
Want more GATE-level examples on semigroups? Let me know!
Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.
Discrete Mathematics for Computer Science
DISCRETE MATHEMATICS AND GRAPH THEORY
Title Discrete Mathematics Author Prof. Abhay Saxena ..
Here’s a quick and clear explanation of Semigroups in Discrete Mathematics (Day 06) with examples—especially useful for GATE Computer Science preparation:
Semigroup – Definition
A semigroup is a set equipped with a binary operation (like +, ×, etc.) that is:
-
Closed
-
Associative
A semigroup does not require an identity element or inverses (unlike a monoid or group).
Formal Definition
A *semigroup (S, ) satisfies:
-
∀ a, b ∈ S: a * b ∈ S (Closure)
-
∀ a, b, c ∈ S: (a * b) * c = a * (b * c) (Associativity)
Examples of Semigroups
Example 1:
Set: ℕ (Natural Numbers)
Operation: Addition (+)
-
Closure: a + b ∈ ℕ
-
Associativity: (a + b) + c = a + (b + c)
So, (ℕ, +) is a semigroup
Example 2:
Set: {1, 2, 3}
Operation: Multiplication modulo 4
-
Create a table for all a × b mod 4
-
Check closure and associativity
If both hold, it’s a semigroup.
Example 3:
String concatenation over set of characters
-
Set: All strings over alphabet Σ = {a, b}
-
Operation: Concatenation (e.g., “a” + “b” = “ab”)
-
Closure: Concatenation of any two strings is a string
-
Associativity: (“a” + “b”) + “c” = “a” + (“b” + “c”)
So, this is a semigroup
Non-example:
Set of integers under subtraction (ℤ, -)
-
(a – b) – c ≠ a – (b – c)
Not associative → Not a semigroup
Would you like practice problems, GATE-style MCQs, or visual examples of semigroup tables?