How to read Hasse diagrams and how they can describe a Boolean Algebra?

Question

Consider a Hasse Diagram for a Boolean Algebra of Order 3

Just by using the diagram and defined Boolean Algebra System as : $\langle B, \vee ,\ \cdot \ , \bar{\ \ } \ ,0, 1 \rangle$ 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

How is that Hasse diagram successfully able to define this Boolean Algebra System; How can I see that it is able to do that?

I know that Boolean Algebra is a distributive lattice that satisfies postulates from $(6)$ to $(10)$. Is there an easy way to check that a lattice is distributive?

I know a method to check if it is Distributive by taking all possible combination of elements and see if they satisfy postulates from $(1)$ to $(5)$. Also, I know that these shapes in a lattice destroys its distributive property

                                          '##`                                                                                                           :##.                                       
                                         #####`                                                                                                         #####,                                      
                                        :######                                                                                                        `######                                      
                                        +######                                                                                                        :######                                      
                                        :#####+                                                                                                        `######                                      
                                        `#####,                                                                                                        ######.                                      
                                        #+;#+:#`                                                                                                     `## :###+                                      
                                       ##  #` ;#`                                                                                                   :#'      #:                                     
                                      ##   #`  '#`                                                                                                 +#,       ,#`                                    
                                     +#`   #`   +#                                                                                               `##          +#                                    
                                    +#     #`    +#                                                                                             .##            #'                                   
                                   '#`     #`   ` ##                                                                                           ;#:             `#`                                  
                                 `;#`      #`      ##                                                                                         ##`               ;#                                  
                                 :+`       #`       #+                                                                                      .##                  ##                                 
                                `#,        #`       `#'                                                                                    :#'                    #,                                
                               `#:         #`        `#;                                                                                  +#,                     ,#                                
                              `#;          #`         `#:                                                                               `##                        +#                               
                              #'           #`          .#,                                                                             ,#+                          #'                              
                             #+            #`           :#`                                                                          `'#:                           .#`                             
                            ##             #`            ;#                                                                          ##`                             '#                             
                           ##              #`             '#                                                                   :###'##                                #+                            
                          ##               #`              +#                                                                 .#####'                                  #,                           
                         +#                #`               +#                                                                +######                                  :#                           
                        '#`                #`                #+                                                               +######                                   ##                          
                       :#`                 #`                 #+                                                              .#####:                                    #'                         
                      ,#.                  #`                  #+                                                              '###+                                     `+`                        
                     .#,                   #`                  `#'                                                               #`                                       +#                        
                    `#;                    #`                   `#;                                                              #                                         #+                       
                   `#'`                    #`                    .#,                                                             #                                         `#,                      
                  `#+                      #`                     ,#,                                                            #                                          :#                      
                  #+                       #`                      ;#.                                                           #                                           ##                     
                 ##                        #`                       ;#`                                                          #                                            #;                    
                ##                         #`                        '#                                                          #                                            .#                    
               ##                          #`                         +#                                                         #                                             '#                   
              '#`                          #`                          ##                                                        #                                              #+                  
             ;#`                           #`                           ##                                                       #                                              `#.                 
            :#`                            #`                            #+                                                      #                                               ;####`             
         ` ,#.                             #`                             #+                                                     #                                               ######             
       +####,                            ,###'                            `#####`                                                #                                               ######`            
      +#####                             #####;                            ######                                                #                                               ######.            
      ######.                           '######                            ######`                                               #                                               ######             
      ######,                           +######                            ######.                                               #                                               `####.             
      ######                            `#####'                            ######                                                #                                               #+``               
       #####`                            ;###+                             #####.                                                #                                              :#                  
        `` ;#`                             #`                             ## ``                                                  #                                              #,                  
            '#                             #`                            ##                                                      #                                             #+                   
             +#                            #`                           +#                                                       #                                            ,#                    
              +#                           #`                          +#`                                                       #                                            #:                    
               ##                          #`                         '#`                                                        #                                           +#                     
                +#                         #`                        ;#`                                                         #                                          .#`                     
                 #+                        #`                       ,#.                                                          #                                          #'                      
                  #'                       #`                      .#,                                                           #`                                        '#                       
                  `#;                      #`                     .#:                                                          :###;                                      `#`                       
                   .#:                     #`                    `#'                                                          `#####,                                     #'                        
                    ,#.                    #`                    #+                                                           +######                                    ;#                         
                     :#`                   #`                   #+                                                            +######                                    #,                         
                      ;#`                  #`                  ##                                                             ,#####:                                   #+                          
                       +#`                 #`                 ##                                                               '#####                                  :#                           
                        ##                 #`                +#                                                                 ``` ##                                 #:                           
                         ##                #`               '#                                                                       +#`                              ++                            
                          #+               #`              '#`                                                                        '#.                            .#`                            
                           #+              #`             ;#`                                                                          ;#.                           #;                             
                            #'             #`            ,#.                                                                            :#,                         '#                              
                           ``#'            #`           .#,                                                                              ,#:                       `#`                              
                             `#;           #`          .#:                                                                                .#;                      #'                               
                              .#,          #`         `#'                                                                                  `#'                    ;#                                
                               ,#.         #`         #+                                                                                    `#'                  `#,                                
                                :#.        #`        #+                                                                                       #+                 #+                                 
                                 ;#        #`       ##                                                                                        `#+               ,#                                  
                                  +#       #`      ##                                                                                           ##              #,                                  
                                   ##      #`     +#                                                                                             ##            ++                                   
                                    ##     #`    '#`                                                                                              +#          .#                                    
                                     ++    #`  `;#`                                                                                                +#`        #;                                    
                                      ##   #`  ;#`                                                                                                  +#`      +#                                     
                                       #+  #` ,#.                                                                                                    '#.    `#`                                     
                                        #',#:.#,                                                                                                      ;#.`;;#'                                      
                                       ``#####;                                                                                                        :#####`                                      
                                        ,#####+                                                                                                        `#####+                                      
                                        +######                                                                                                        :######                                      
                                        '######                                                                                                        .######                                      
                                         #####.                                                                                                         #####;                                      
                                          ###,                                                                                                           +##:

@Raphael My reputation on this site was low enough that it didn't allowed me to post more than 2 links for images, so I came up with this. — amarVashishth, Nov 12 '15 at 12:55
@avDec25 Better solutions: 1) Get rid of redundant image #2 in favor of MathJax. 2) Post the third image as link and wait for editors to make it an image link. — Raphael, Nov 12 '15 at 18:27
I don't understand your question. Can you edit the question to (a) fix all of the issues others have pointed out, and (b) clarify what you are asking? I don't know what you mean by "How is that Hasse diagram successfully able to define..." -- what do you mean by "able"? Later you ask how to tell whether a lattice is distributive, but then you tell us you already know how to do that (by checking all triples of elements), so I'm not sure what you are asking. Are you asking for an algorithm to check whether a lattice is distributive that's more efficient? for a theorem or technique? (cont.) — D.W., Nov 12 '15 at 20:21
(cont.) If so, what properties do you want that algorithm/theorem/technique to have? And if that's what you're asking, you should be able to ask a much more concise question: I don't know why you have a bunch of writing about Hasse diagrams, the definition of a lattice, Boolean algebra system, and so on -- it seems extraneous and makes the question harder to follow. See if you can formulate a easier-to-understand question? Also, we try to only migrate well-articulated questions, so while this might be more appropriate on Math.SE, it needs some editing before it can be migrated. — D.W., Nov 12 '15 at 20:24
@D.W. Yes I am asking for an algorithm to check if a given Hasse Diagram represent a Boolean Algebra and also to check for a Distributive lattice. But Yuval has cleared now that we need to check for all permutations of elements and verify if they satisfy postulates; there is no quick method to do that. — amarVashishth, Nov 13 '15 at 06:57

score 2 · Accepted Answer · answered Nov 12 '15 at 20:26

Hasse diagrams describe general posets (partially ordered sets) according to the following rule: $x \prec y$ if there is a directed path from $x$ to $y$, where we direct all edges up. Going the other way, there is an edge from $x$ to $y$ if $x \prec y$ and there is no $z$ satisfying $x \prec z \prec y$.

Given two elements $x,y$, their join $x \lor y$ is an element $z$ such that $x,y \preceq z$ and all $w$ satisfying $x,y \preceq w$ also satisfy $z \preceq w$. The meet $x \land y$ is defined analogously by replacing $\preceq$ with $\succeq$. (Your notation is $\cdot$.)

An element $0$ is the bottom element if $0 \preceq x$ for all $x$. Similarly, an element $1$ is the top element if $x \preceq 1$ for all $y$. In your diagram these elements are $(0,0,0),(1,1,1)$, and you can identify them as the unique elements at the bottom and top.

For an element $x$, a complement $x'$ is an element satisfying $x \land x' = 0$ and $x \lor x' = 1$ (your notation is $\bar{x}$). I'm not sure under what conditions the complement is unique.

This allows you to define a Boolean algebra given a Hasse diagram, assuming that the corresponding poset has joins and meets, top and bottom elements, and complements.

In your case, your Boolean algebra is an algebra of sets, so it is easy to verify all axioms directly. You can also verify them by going over all $a,b,c$ and performing the required computation, but that's better left to a computer.

Distributivity makes the complement unique: If $x\wedge y=0$ then $y=1\wedge y=\left(x\vee x^{c}\right)\wedge y=\left(x\wedge y\right)\vee\left(x^{c}\wedge y\right)=0\vee\left(x^{c}\wedge y\right)=x^{c}\wedge y\leq x^{c}$. Likewise $x\vee y=1\implies x^{c}\leq y$. — drhab, Nov 14 '15 at 09:50

How to read Hasse diagrams and how they can describe a Boolean Algebra?

1 Answers1