Mathematical Foundation of Computer Science

DHARM

82 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Hence, (X, ⊗) is a semigroup. Further,
l Algebraic structure (X, ⊗) not posses a unique identity element for all elements of X.
Here elements identity elements are {p, q, r}.
l Since corresponding rows and columns are not same hence operation ⊗ is not commu-
tative.
Therefore, (X, ⊗) is not monoid and also not a group.
Example 4.3. Let X = {1, – 1, i, – i} and the binary operation H is define in the operation table
(Fig. 4.4). Prove that algebraic system (X, H) is a group.
Sol.
H 1– 1 i– i
1 1– 1 i – i

• 1 – 1 1 – ii
  i i – i – 1 1


• i – ii1– 1
  Fig. 4.4 Operation table.
  (Ready self verify that operation table holds all restrictions required by a group)
  Modulo Operation
  Now we define two special operations called additional modulo and multiplication modulo
  over the set X, where
  l Additional Modulo n if a, b ∈ X then a addition b modulo n is defined as,
  (a +n b) = (a + b) mod n = r (where r > 0)
  For example, let a = 11 and b = 6 then its addition modulo 5 is given by (11 + 5 6) = (11 + 6) mod
  5 = 2 (> 0). Consider another set of values such that a = – 15 and b = 5, then
  (– 11 + 5 5) = (– 11 + 5) mod 5 = (– 6) mod 5 = [(– 5 ∗ 2) + 4] mod 5 = 4 (> 0).
  Let a = – 10 and b = – 7 then
  (– 10 + 5 7) = (– 10 + (– 7)) mod 5 = (– 17) mod 5 = [(– 5 ∗ 4) + 3] mod 5 = 3 (> 0).
  lMultiplication Modulo n if a, b ∈ X then a multiplication b modulo n is defined as,
  (a *n b) = (a ∗ b) mod n = r (where r > 0)
  Example 4.4. Let (X, ×) be a group, where × is the multiplication operation on X, then for any
  x, y ∈ X prove that,

1. (x–1)–1 = x, and


2. (x × y)–1= y–1 × x–1 or (x × y) = (y–1 × x–1)–1;
   Sol.


3. Recall the definition of the group, such that for every element x ∈ X there exists an unique
   inverse say x′ ∈ X i.e.,
   x × x′ = ê (identity element) = x′ × x;
   From the symmetricity,
   x′ = x–1 or x′–1 = x
   Replace value of x′ by x–1 in so, we get
   (x–1)–1 = x (Proved)