5.
a)Prove that the fourth roots of unity 1, i, i, 1 is an abelian group
with respect to multiplication(.)
Proof:
Let 𝐺 = {1, 𝑖, −1, −𝑖}, the fourth roots of unity.
Closure: Product of any two elements is in 𝐺.
Associativity: Multiplication of complex numbers is associative..
Identity: 1 ∈ 𝐺.
Inverses: 1−1 = 1, 𝑖 −1 = −𝑖, (−1)−1 = −1, (−𝑖)−1 = 𝑖.
Commutativity: Multiplication of complex numbers is commutative.
∴ 𝐺 is an abelian group under multiplication.
b) Verify the following system is a group or not G = {0,1,2,3,4,5}and the
operation +6 where+6 represents additive modulo 6.
Proof: To verify if 𝐺 = {0,1,2,3,4,5}with the operation +6 (addition modulo 6) is a group or
not.
Closure
For any 𝑎, 𝑏 ∈ 𝐺, 𝑎+6 𝑏 = (𝑎 + 𝑏)mod 6 ∈ {0,1,2,3,4,5}. Closure holds.
Associativity
Addition modulo 6 inherits associativity from ordinary addition:
(𝑎+6 𝑏)+6 𝑐 = 𝑎+6 (𝑏+6 𝑐)∀𝑎, 𝑏, 𝑐 ∈ 𝐺. Associativity holds.
Identity:
0 ∈ G, a+6 0 = a. Identity exists.
Inverses
For each 𝑎 ∈ 𝐺, there exists 𝑏 ∈ 𝐺such that 𝑎+6 𝑏 = 0mod 6:
0 is the inverse of 0.
5 is the inverse of 1.
4 is the inverse of 2.
3 is the inverse of 3.
2 is the inverse of 4.
1 is the inverse of 5.
So, each element has an inverse.
All group axioms are satisfied.
∴ (𝐺, +6 ) is a group.
6. a) Define (i) POSET (ii) Lattice (iii) Boolean algebra
Sol:
(i) POSET (Partially Ordered Set):
A set 𝑃with a relation ≤is called a partially ordered set if for all 𝑎, 𝑏, 𝑐 ∈ 𝑃:
1. Reflexive: 𝑎 ≤ 𝑎
2. Antisymmetric: if 𝑎 ≤ 𝑏and 𝑏 ≤ 𝑎, then 𝑎 = 𝑏
3. Transitive: if 𝑎 ≤ 𝑏and 𝑏 ≤ 𝑐, then 𝑎 ≤ 𝑐
(ii) Lattice:
A lattice is a partially ordered set in which every pair of elements has:
a least upper bound (join), denoted 𝑎 ∨ 𝑏
a greatest lower bound (meet), denoted 𝑎 ∧ 𝑏
(iii) Boolean Algebra:
A Boolean algebra is a set 𝐵with two binary operations (∨, ∧) and a unary operation ( ' )
satisfying:
1. Commutative, associative, distributive laws
2. Identity elements: 0 and 1
3. Complements: For each 𝑎 ∈ 𝐵, there exists 𝑎′ such that 𝑎 ∨ 𝑎′ = 1and 𝑎 ∧ 𝑎′ = 0
b)Draw the Hasse diagram for the POSET L={1,2,3,5,30} and R be the
relation ‘is divisible by’. Show that L is lattice.
Sol:
The Hasse diagram for the given POSET represents the divisibility relations. Elements are
placed at different vertical levels based on their 'height' or rank in the POSET (number of
elements in the longest chain from the minimum element).
The diagram has three levels:
Bottom Level: Contains the element 1 (the minimum element).
Middle Level: Contains elements 2, 3, and 5, which are all minimal prime divisors
and are incomparable to each other within the set 𝐿.
Top Level: Contains the element 30 (the maximum element).
To show L is lattice:
We verify the lattice properties by checking all incomparable pairs, as all other pairs (where
one divides the other) trivially satisfy the conditions.
For the pair 2 and 3:
o The common multiples in 𝐿 are only 30. Thus, the unique least upper bound
(join) is 2 ∨ 3 = 30.
o The common divisors in 𝐿 are only 1. Thus, the unique greatest lower bound
(meet) is 2 ∧ 3 = 1.
For the pair 2 and 5:
o The unique least upper bound (join) is 2 ∨ 5 = 30.
o The unique greatest lower bound (meet) is 2 ∧ 5 = 1.
For the pair 3 and 5:
o The unique least upper bound (join) is 3 ∨ 5 = 30.
o The unique greatest lower bound (meet) is 3 ∧ 5 = 1.
Since every pair of elements in 𝐿has a unique join and a unique meet, the POSET is a lattice.
7. a)State and prove idempotent and demorgan’s laws in Boolean algebra.
Sol:
Idempotent Laws:
The idempotent laws are 𝐴 ⋅ 𝐴 = 𝐴 and 𝐴 + 𝐴 = 𝐴, meaning a variable ANDed or ORed with
itself is equal to the variable itself.
(a) 𝑨 + 𝑨 = 𝑨
Start with
𝐴 + 𝐴 = 𝐴 + (𝐴 ⋅ 1)(since 𝐴 ⋅ 1 = 𝐴)
Write 1 = 𝐴 + 𝐴′ (complement):
𝐴 + (𝐴 ⋅ 1) = 𝐴 + (𝐴 ⋅ (𝐴 + 𝐴′ )).
Distribute 𝐴 ⋅ (⋅):
𝐴 + (𝐴 ⋅ 𝐴 + 𝐴 ⋅ 𝐴′ ) = 𝐴 + (𝐴 + 𝐴 ⋅ 𝐴′ )(because 𝐴 ⋅ 𝐴 = 𝐴).
Using absorption 𝐴 + 𝐴 ⋅ 𝐴′ = 𝐴(or note 𝐴 ⋅ 𝐴′ = 0, so 𝐴 + 0 = 𝐴):
𝐴 + (𝐴 + 𝐴 ⋅ 𝐴′ ) = 𝐴.
Hence 𝐴 + 𝐴 = 𝐴.
(b) 𝑨 ⋅ 𝑨 = 𝑨
Start from 𝐴 = 𝐴 ⋅ 1and use 1 = 𝐴 + 𝐴′ :
𝐴 = 𝐴 ⋅ 1 = 𝐴 ⋅ (𝐴 + 𝐴′ ) = 𝐴 ⋅ 𝐴 + 𝐴 ⋅ 𝐴′ .
But 𝐴 ⋅ 𝐴′ = 0, so
𝐴 = 𝐴 ⋅ 𝐴 + 0 = 𝐴 ⋅ 𝐴.
Thus 𝐴 ⋅ 𝐴 = 𝐴.
DeMorgan’s laws:
For any a, b ∈ B
b)prove that abc+abcʹ+abʹc+aʹbc = ab+bc+ca
Let
𝐿𝐻𝑆 = 𝑎𝑏𝑐 + 𝑎𝑏𝑐 ′ + 𝑎𝑏′ 𝑐 + 𝑎′ 𝑏𝑐.
= 𝑎𝑏(𝑐 + 𝑐 ′ ) + 𝑎𝑏′ 𝑐 + 𝑎′ 𝑏𝑐
= 𝑎𝑏 + 𝑎𝑏′ 𝑐 + 𝑎′ 𝑏𝑐.
= 𝑎𝑏 + 𝑎′ 𝑏𝑐 + 𝑎𝑏′ 𝑐.
= 𝑏(𝑎 + 𝑎′ 𝑐 ) + 𝑎𝑏′ 𝑐
= 𝑏(𝑎 + 𝑐 ) + 𝑎𝑏′ 𝑐 (using 𝑎 + 𝑎′ 𝑐 = 𝑎 + 𝑐)
= (𝑎𝑏 + 𝑏𝑐) + 𝑎𝑏′ 𝑐
= 𝑎𝑏 + (𝑏𝑐 + 𝑎𝑏′ 𝑐)
= 𝑎𝑏 + 𝑐(𝑏 + 𝑎𝑏′ )
= 𝑎𝑏 + 𝑐(𝑎 + 𝑏) (using 𝑏 + 𝑎𝑏′ = 𝑎 + 𝑏)
= 𝑎𝑏 + 𝑐𝑎 + 𝑐𝑏
= 𝑎𝑏 + 𝑏𝑐 + 𝑐𝑎 = RHS
Hence 𝑎𝑏𝑐 + 𝑎𝑏𝑐 ′ + 𝑎𝑏′ 𝑐 + 𝑎′ 𝑏𝑐 = 𝑎𝑏 + 𝑏𝑐 + 𝑐𝑎
8. a)Show that in boolean algebra complement of each element is unique.
Proof. Let 𝑎be an element and suppose 𝑥and 𝑦are both complements of 𝑎. That means
𝑎 + 𝑥 = 1, 𝑎 ⋅ 𝑥 = 0, 𝑎 + 𝑦 = 1, 𝑎 ⋅ 𝑦 = 0.
Now 𝑥 = 𝑥 ⋅ 1 = 𝑥 ⋅ (𝑎 + 𝑦) = 𝑥 ⋅ 𝑎 + 𝑥 ⋅ 𝑦 = 0 + 𝑥 ⋅ 𝑦 = 𝑥 ⋅ 𝑦,using distributivity
and 𝑥 ⋅ 𝑎 = 0.
Similarly
𝑦 = 𝑦 ⋅ 1 = 𝑦 ⋅ (𝑎 + 𝑥) = 𝑦 ⋅ 𝑎 + 𝑦 ⋅ 𝑥 = 0 + 𝑦 ⋅ 𝑥 = 𝑦 ⋅ 𝑥.
Therefore 𝑥 = 𝑥 ⋅ 𝑦 = 𝑦 ⋅ 𝑥 = 𝑦. Hence 𝑥 and 𝑦 are equal, so the complement of 𝑎is unique.
(This uses only the Boolean identities 1 = 𝑎 + 𝑦when 𝑦is a complement of 𝑎, distributivity,
and 𝑎 ⋅ 𝑦 = 0.)
b)Check the following Hasse diagrams are lattice or not?
Sol:
(i) The diagram is the 4-element diamond (elements {1,2,3,6}) with order 1 < 2 < 6and 1 <
3 < 6, and 2and 3incomparable. For every pair of elements a greatest lower bound (meet)
and a least upper bound (join) exists:
2 ∧ 3 = 1and 2 ∨ 3 = 6.
If one element is below the other (e.g. 1and 2), the meet/join are just the lower/upper
one.
So all pairs have both supremum and infimum — this is a lattice (in fact the 4-
element Boolean lattice).
(ii) The diagram has minimal elements 𝑎, 𝑏, then 𝑐above both, then 𝑑, then maximal elements
𝑒, 𝑓. Consider the pair 𝑎, 𝑏:
The set of common lower bounds of 𝑎and 𝑏is empty (there is no element ≤ 𝑎and ≤
𝑏except possibly something not present), so there is no greatest lower bound (no
meet) for 𝑎and 𝑏.
Equivalently, consider the pair 𝑒, 𝑓: they are distinct maximal elements and have no common
upper bound in the diagram, so their join does not exist. Either failure (no meet for 𝑎, 𝑏or no
join for 𝑒, 𝑓) is enough to conclude the poset is not a lattice.