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

3.1k Views Asked by At

Consider a Hasse Diagram for a Boolean Algebra of Order 3

enter image description here

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: enter image description here 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

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

There are 1 best solutions below

1
On BEST ANSWER

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.