Test by Bikram | Mock GATE | Test 1 | Question: 18

Question

Which of the following is not a Boolean algebra under the operation '\'?
  \: is a divisor,  $D_{p}$: divisor of $p$

• A. $\left \{ D18; \ \right \}$
• B. $\left \{ D21; \ \right \}$
• C. $\left \{ D110; \ \right \}$
• D. $\left \{ D91; \ \right \}$

Comments

@Gate2017Aspirant and @Shradha 

see here 

a Boolean algebra or Boolean lattice is a complemented distributive lattice.

why  option A , D₁₈ is not boolean algebra. 
D₁₈ = {1, 2, 3, 6, 9, 18}

The Reasons are as follows :

1. Element 9 is not square free.
2. Total elements in set is not 2^n.
3. Not complemented lattice.
4. Not distributive lattice.

Read  Boolean Algebra Laws : https://en.wikipedia.org/wiki/Boolean_algebra_(structure)

---

necessary and sufficient condition :Square free number

am i right @Bikram sir?

---

@Rishabh Gupta 2

"Element should be a square " is for {$D_n$ , /} or any operation ?

Answer 1

1] A poset [Dn, /]  is a boolean algebra if "n" is square-free number

2] no of element in lattice "2^n"

3] no of edge in lattice " n*2^(n-1) "

4] A lattice is called boolean algebra if it is "distributed and complemented lattice"

5] if the poset [Dn, /]  is a boolean algebra then complement of "X=n/X"    // here x any element of Dn

complement lattice- >in a bounded lattice if there exists "at least one "complement for every element 

Distributive lattice -> complement of an element if exists "unique" i.e each element"at most one" complement

   [Dn ,/] always distributive lattice 

Here [D18,/] fails boolean properties

Comments

@Bikram Sir

how D_{110 is a boolean algebra ??}

complement (10) = 55,11

complement (2) = 55,11

complement (11) = 2,10

complement (55) = 2,10

complement (5) = 22

complement (22) = 5

complement (1) = 110

complement (110) = 1

Hence complemented lattice,

but we are not getting unique compliments for 2,10,11,55

So not a distributive lattice. Hence not a boolean algebra.

So according to me only D₂₁ and D₉₁ are boolean algebra.

D₁₈ and D₁₁₀ are not boolean algebra.

Correct me if i am wrong.

---

@ kash0611

U are finding compliments wrongly

In first case complement of 10 would be:

GLB(10,x) = ULB(universal Lower bound)

LUB(10,x) = UUB(universal upper bound)

But here ULB =1 UUB =110

Compliment of 10 = 110/10 =11...

---

@akash.dinkar12

thanks...got it

compliment of 10 is 11 only.Also for 2,11,55 there will be a unique compliments.

hence D₁₁₀  also a boolean algebra.

Answer 2

D₁₈ is not boolean algebra. 
D₁₈ = {1, 2, 3, 6, 9, 18}
Reason:
1. Element 9 is not square free.
2. Total elements in set is not 2ⁿ.
3. Not complemented lattice.
4. Not distributive lattice.

Comments

@Sushmita

A lattice is called boolean algebra if it is "distributed and complemented lattice"

so only first 2 conditions satisfaction is Not sufficient, you have to satisfy all 4 conditions.

Read this document, page number 21, Topic Name : Boolean Lattices: Definition and Properties

http://digitalcollections.dordt.edu/cgi/viewcontent.cgi?article=1434&context=faculty_work

---

bikram sir, gone through the link. Sir i didnt find the restriction for 2^n elements in the definition of boolean algebra? Though i had been taught this case but i am unable to find the reason..?? in the document the def i found is-

1. Commutative Laws a) x + y = y + x b) x · y = y · x

2. Associative Laws a) (x + y) + z = x + (y + z) b) (x · y) · z = x · (y · z)

3. Distributive Laws a) x · (y + z) = x · y + x · z b) x + (y · z) = (x + y) · (x + z)

4. Identity Laws a) x + 0 = x = 0 + x b) x · 1 = x = 1 · x

5. Complementation Laws a) x + x = 1 = x + x b) x · x = 0 = x · x

---

@sushmita

in that document may not have but it is the rule, so dont worry

and you have to satisfy all rules  for a lattice  to become boolean algebra .

Answer 3

answer should be B definetly not A