0
$\begingroup$

I just started learning Boolean Algebra and have this homework question

Demonstrate that the pentagon lattice is non-distributive enter image description here

I know this is non-distributive because $b$ complements $a$ and $c$. So when I check if distributive law holds for $ a \lor (b \land c) = (a \lor b) \land (a \lor c)$. I get

$$ a \lor (b \land c) = (a \lor b) \land (a \lor c)$$ $$ a \lor 0 = (a \lor b) \land (a \lor c)$$ $$ a = (a \lor b) \land (a \lor c)$$ $$ a = 1 \land c $$ $$ a = c $$

Since $ a \neq c$ the pentagon is not distributive. But why is it if I use the other law of distribution that I don't get the same answer? I would think they both would fail if the lattice is non-distributive. What am I doing wrong here?

$$ a \land (b \lor c) = (a \land b) \lor (a \land c)$$ $$ a \land 1 = (a \land b) \lor (a \land c)$$ $$ a = 0 \lor a$$ $$ a = a $$

$\endgroup$
  • 1
    $\begingroup$ You reversed the order, so reverse a and c. $\endgroup$ – William Elliot Apr 24 at 3:19
  • $\begingroup$ @WilliamElliot reversed the order where? $\endgroup$ – Sam Apr 24 at 8:57
  • 1
    $\begingroup$ When you swap meets and joins, it's the same as doing the same with the order reversed. Now the distributivity, in order to hold, it must be for every three elements of the lattice. So swap $a$ and $c$ in the last verification and you'll get the same result. $\endgroup$ – amrsa Apr 24 at 9:14
  • $\begingroup$ @amrsa Thanks! What's the reason swapping meets and joins reverses $a$ and $c$ in the last verification? $\endgroup$ – Sam Apr 24 at 9:20
  • 1
    $\begingroup$ Yes, as I wrote in the first comment. The underlying reason is that the order-reverse of a lattice is still a lattice, and as properties which are the order-reversal of the original lattice. Now, distributivity is a self-dual property (a lattice is distributive iff its dual is), and that's why the two (dual) definitions of distributivity are equivalent in any lattice (although they don't have to hold to the exact same tuples $(a,b,c)$). $\endgroup$ – amrsa Apr 24 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.