Unit 4 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes

Unit 4 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes

Algebraic Structure

- An algebraic structure is a mathematical system comprising a collection of elements. 

- One or more operations defined on the set, such as addition, multiplication, or binary operations. 

- Suppose * is a binary operation on G. Then (G, *) is an algebraic structure 

The behavior of elements within the structure is determined by properties like: 

1. Closure property : Result of combining elements is always in the group 

(a * b) ∈ S ∀ a, b, ∈ S 

2. Associativity: Grouping doesn't change the result 

(a * b) * c = a * (b * c) ∀ a, b, c ∈ S 

3. Commutativity: Order of operands doesn't matter. 

(a * b) = (b * a) 

4. Distributivity: Operation interacts with another in specific way. 

a * (b + c) = (a * b) + (a * c) (right distributive) 

(b + c) * a = (b * a) + (c * a) (left distributive) 

5. Identity Elements: Elements that don't change others.

a * e = a = e*a

6. Inverse Elements: Elements that cancel each other

 a * a –1 = e = a – 1 * a

Semigroup

- Set with closure and associative property . 

- Ex: (N,+) (Z, +), (R, +), and (Q, +) are all semigroups

Group

- Set with closure , associative property, identity, inverses. 

- Ex: (Z, +), (R, +), and (Q, +) are all groups 

Abelian Group

- Group with commutative operation. 

- Ex: (Z, +) is abelian group 

Note: z = set(integer), N = set(natural), Q = set(rational), R = set(real) 

Question:

Show that the set G = {x + 2y |x, y  Q} is a group with respect to addition 

i) Closure : 

- Let X = x1 + 2y1 Y = x2 + 2y2 where x1 , x2 , y1 , y2 ∈ Q and X, Y ∈ G 

Then X + Y = (x1 + 2y1 ) + (x2 + 2y2 ) 

= (x1 + x2 ) + 2(y1 + y2 ) 

= X1 + 1 2Y ∈ G where X1 , Y1 ∈ Q 

Therefore, Sum of two rational numbers is rational.

ii) Associativity : 

Let X, Y and Z ∈ G 

Therefore X = x1 + 2y1 

Y = x2 + 2y2 

Z = x3 + 2y3 where x1 ,x2 , x3 , y1 , y2 , y3 ∈ Q 

Consider (X + Y) + Z = (x1 + 2 y1 + x2 + 2y2 ) + (x3 + 2 y3 ) 

= ((x1 + x2 ) + 2(y1 + y2 ) ) + (x3 + 2y3 ) 

= (x1 + x2 + x3 ) + (y1 + y2 + y3 ) ---- eq(1) 

Also X + (Y + Z) = (x1 + 2y1 ) + ((x2 + 2y2 ) + (x3 + 2y3 )) 

= (x1 + 2y1 ) + ((x2 + x3 ) + 2(y2 + y3 ) ) ---- eq(2) 

= (x1 + x2 + x3 ) + (y1 + y2 + y3 ) 

From eq. ( 1) and (2) (X + Y) + Z = X + (Y + Z) 

Therefore, G is associative under addition. 

iii) Identity element : 

Let e ∈ G be identity elements of G under addition then (x + 2y ) + (e 1 + 2e2 ) = x +2y where e = e 1 + 2e2 and e1 , e2 , x, 

y ∈ Q 

e1 + 2e2= 0 + 0 2 e1 = 0 and e 2 = 0 Therefore, 0 ∈ G is identity element. 

iv) Inverse element : 

 – x – 2y ∈ G is inverse of x + 2y ∈ G. Therefore, inverse exist for every element x + 2y ∈ G 

such that, y ∈ Q. Hence, G is a group under addition.

Ring

- A ring is an algebraic system (R, +, •) where R is a non-empty set and + and • are two binary operations 

- if the following conditions are satisfied : 

1. (R, +) is an abelian group. 

2. (R, •) is semigroup 

3. The operation • is distributive over +. 

i.e., for any a, b, c ∈ R 

a • (b + c) = (a • b) + (a • c) 

or (b + c) • a = (b • a) + (c • a) 

- Ex: (Z, +,*), (R, +,*), and (Q, +,*) are all ring 

Integral Domain

- A ring is called an integral domain if : 

   1. It is commutative 

   2. It has unit element 

   3. It is without zero divisors 

- Ex:(Z, +, *),(R, + ,*), and (Q, + ,*) are all integral domain

Field

- A ring R with at least two elements is called a field 

- if it has following properties : 

   - R is commutative 

   - R has unity 

   - R is such that each non-zero element possesses multiplicative inverse 

- Ex: (R, +, *), and (Q, +, *) are fields 

Order of Group

- it refers to the number of elements in the group. 

- It represents the size or cardinality of the group. 

- For Ex: Z4={0,1,2,3} with order 4. 

Cyclic Group

- A cyclic group is a group that is generated by a single element, often denoted <g>. 

- where g is called a generator. 

- The group consists of all powers of g, including positive and negative powers.

Question:

Prove that every cyclic group is an abelian group 

Let G be a cyclic group and let a be a generator of G so that G = {a n : n ∈ Z} If g1 and g2 are any two elements of G, there 

exist integers r and s such that g1 = a^r

 and g2 = a^s>

Then g1 g2 = a^r a s = a^(r+s) = a^(s+r) = a^s . a^r = g2 g1 So, G is abelian. 

Subgroup

- If (G, *) is a group and H ⊆ G. Then (H, *) is said to subgroup of G if (H, *) is also a group by itself. i.e., 

1. a * b ∈ H ∀ a, b ∈ H (Closure property) 

2. ∃ e ∈ H such that a * e = a = e * a ∀ a ∈ H where e is called identity of G. 

3. ∃ a^(-1) ∈ H such that a * a^(–1) = e = a^(–1) * a ∀ a ∈ H

Permutation Group

- A permutation group G on a non-empty set A under the binary operation ∗. 

- If A={1,2,3,…,n}, then the permutation group formed by A is called the symmetric group of degree n, denoted by Sn. 

- Number of Elements in Symmetric Group: 

- The number of elements in Sn is n!

Cyclic Permutation

- Cyclic permutation cyclically rearranges elements in a fixed sequence, typically returning to the initial element after a certain number of steps 

- For example : Consider A = {a, b, c, d, e}. Then P =[ a b c d e ] 

                [ c b d a e ]. 

then P has a cycle of length 3 given by (a, c, d).

Cosets

- Let H be a subgroup of group G and let a∈G then 

- set Ha = {ha : h ∈ H} is called right coset generated by H and a. 

- Also the set aH = {ah : h ∈ H} is called left coset generated by a and H

Question: 

Find the left cosets of {[0], [3]} in the group (Z6 , +6 ). 

Let Z6 = {[0], [1], [2], [3], [4], [5]} be a group. 

H = {[0], [3]} be a subgroup of (Z6 , +6 ). 

The left cosets of H are, 

[0] + H = {[0], [3]}   [1] + H = {[1], [4]} 

[2] + H = {[2], [5]}    [3] + H = {[3], [0]} 

[4] + H = {[4], [1]}    [5] + H = {[5], [2]}

Normal Subgroup

- A subgroup H of group G is a normal subgroup if aH=Ha for all a in G, indicating that left and right cosets of H generated by a are identical.

- Property: 

1. every subgroup H of an abelian group G is a normal subgroup of G. For a ∈ G and h ∈ H, ah = ha. 

2. Since a cyclic group is abelian, every subgroup of a cyclic group is normal.