Module 5 - Algebraic Structures
CE– SE–DSGT
Dr. Anil Kale
Associate Professor
Dept. of Computer Engineering,
MGMCET, Navi Mumbai
1
Module 5 - Algebraic Structures
5.1 Algebraic structures with one binary operation:Semi
group, Monoid, Groups, Subgroups,Abelian Group, Cyclic
group, Isomorphism
5.2 Algebraic structures with two binary operations: Ring
5.3 Coding Theory: Coding, binary information and error
detection, decoding and error correction
Algebraic Structures
Binary Operations
3
4
5
6
7
8
Monoid
9
10
Isomorphism
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Example: Let Q be the set of positive rational numbers which can be
expressed as 2a3b, where a and b are integers. Prove that algebraic
structure (Q, ∙) is a group. Where ∙ is multiplication operation.
29
30
31
Additive Modulo M
32
33
Example: Prove that the set G= {0, 1, 2, 3, 4, 5} is an Abelian group of
order 6 with respect to addition modulo 6.
34
Hence, +6 is an associative operation. Since it is
satisfying for all a, b, c, ∈ G.
35
36
37
Multiplication Modulo P
A new type of multiplication known as "multiplication modulo P" and written as a XP b
where a and b are any integers and p is fixed positive integer is defined as:
, 0 ≤ r < p where, r is the least non-
negative remainder when ab (ordinary
product of a and b) divided by p.
38
Example: Prove that the set G= {1, 2, 3, 4, 5, 6} is an Abelian group of
order 6 with respect to multiplication modulo 7.
Similarly row 1, row 3, row 4, row 5, and row 6 are calculated.
39
(i) All the entries in the composition table are elements of G. Hence G is closed
under multiplication modulo 7 (X7)
40
41
42
Cyclic Groups
A group (G, *) is said to be a cyclic group if there exists an element a ∈ G such that
every element can be G can be written as some power of a, viz ak, for some integer
k. By ak, we mean a * a* a.. a (k times). We then say that G is generated by a or a is
a generator of G.
A cyclic group is Abelian, since for any two elements ar, as ∈ G,
ar*as= a r+s = a* = as*ar
43
Generation of Subgroups
44
45
46
47
48
CODING
Coding of Binary Information and Error detection
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
Dr. Rajesh Kadu 71
72
Types of Rings
1. Commutative Ring: A ring (R, +, .) is said to be commutative when a.b
= b.a for all a,b ∈ R.
2. Rings with unity element: A ring (R, +, .) is said to be a ring with
unity element if there exists an element, denoted by the symbol 1
such that a.1 = 1.a = a for all a ∈ R.
Examples:
7
7
Cancellation Laws in a Ring
7
SUBRINGS
• Analogous to the concept of subgroup of a group, this is that of a
subring of a ring.
• Let (R, +, ·) be a ring and S be a non-empty subset of R. If (S, +, ·) is
called a subring of R.
• Let (S, +, ·) be a subring of (R, +, ·), where R is a ring with identity
element 1. If 1 ∈ S, then S is called a Unitary Subring of R and the ring
is said to be Unitary over ring (S, +, ·)
• For Example:
– The ring of even integers is a subring of the ring of integers. More
generally, for any positive integer n, the set, nZ = {n m|m ∈ Z} is a
subring of Z
– The set of rationals is a subring of the ring of real numbers.
7
EXAMPLES
Q1. Show that the set {0, 1, 2, 3, 4} is a ring w.r.t addition and
multiplication mod 5.
Soln: Let S = {0, 1, 2, 3, 4}
7
7
7
8
8
8
Q2. Show that A = {0, 1, 2, 3, 4, 5} together addition modulo 6 and multiplication
modulo 6 is a commutative ring.
8
8
8
8
8
8
8
9
9
9
9
9