GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
451 views

Consider a Hasse Diagram for a Boolean Algebra of Order 3

What can we comment about it? 
How is it successfully able to represent the Boolean Algebra System?
Is there an easy way to check for distributive lattice, or any other properties of a lattice?

Given/Know :
$\langle B, \vee ,\ \cdot \ , \bar{\ \ } \ ,0, 1 \rangle$ is a Boolean Algebra, and for any 3 of its arbitrary elements $a, b, c$ in $B$ the following postulates are satisfied:

where, $\vee$ is Boolean Sum
$\cdot$ is Boolean Product
$\bar{\ \ }$ is Complement


 

 

It is not expected that one should provide a complete answer to all parts of the question. Whatever one can supply to support its answer is welcomed.

asked in Set Theory & Algebra by Veteran (29.3k points) 75 220 379 | 451 views

3 Answers

+1 vote

According to me::

Suppose we have A={a,b,c}

now if we calculate power set of of A like P(A)={Phi,{a},{b},{c},{ab},{bc},{ca},{abc}};

Then Poset =[P(A);under subset]

Now u can check below hasse diagram that it is both complemented as well as Distributed lattice that's why it will be boolean algebra.One special point is that in boolean algebra number of vertex will be 2^n and edges n*2^n-2.U can check above. 

answered by Boss (5.6k points) 3 9 32

correct it total no of  edges in boolean algebra if no of element is n should be ( n * 2n-1

+1 vote

A lattice is called a Boolean Algebra, if it is distributive and complemented( if complement exists for every element of lattice).

So, For $2-order$ Boolean Algebra, it's easy to check for these properties to say whether a lattice is boolean Algebra (or) not, But for lattices for higher order (say $3$, $4$ (or) $20$), it becomes worse to Check for distributive properties and finding complement for each element.

One way here would be eliminating options using the property that Every element has a unique complement in a Boolean Algebra, but the converse is not True.

Any $n-order$ boolean Algebra is isomorphic to any other $n-order$ boolean algebra. And we know that $\color{olive}{\big[ P(A),\subseteq \big]}$ is a boolean Algebra.

So, any boolean Algebra of $\color{green}{order-2}$ and $\color{green}{order-3}$ must be isomorphic to these two. And also note that a Boolean Algebra of order $n$ has $\color{red}{2^n}$ vertices(nodes) and $\color{red}{n*2^{n-1}}$ edges.

So, now coming to the question the above Hasse diagram is isomorphic to the Boolean Algebra of order-3, Hence it is Boolean Algebra.

answered by Veteran (27.3k points) 19 70 243
edited by
0 votes

 

It is a bounded, distributive and complemented lattice. So, it must be a boolean algebra

answered by Veteran (65k points) 35 222 625


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23324 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7808 Points

  4. srestha

    6222 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4958 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4286 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Notable Question makhdoom ghaya
Popular Question LavTheRawkstar
Avid Voter atul_21
Popular Question hem chandra joshi
100 Club nikhil_cs
Notable Question Sukannya
Notable Question Sourabh Kumar
Notable Question shikharV
Nice Comment Sachin Mittal 1
Popular Question ManojK
27,287 questions
35,134 answers
83,910 comments
33,223 users