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$
5
  • 1
    $\begingroup$ You reversed the order, so reverse a and c. $\endgroup$ – William Elliot Apr 24 '19 at 3:19
  • $\begingroup$ @WilliamElliot reversed the order where? $\endgroup$ – Sam Apr 24 '19 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 '19 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 '19 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 '19 at 9:24
0
$\begingroup$

This is very simple. If try to find the complement of 'b' you will get 'a' and 'c'. And any element in a distributve lattice should have atmost one complement. Distributive property comes from set theory where every element has atmost one complement and if lattice has an element with more than one complement then the lattice will not follow distributive property.

How to find complement? ans: If any element two elements 'a' and 'b' such that a∨b = upper bound of lattice and a∧b = lower bound of lattice, a and b are complements of each other.

what are upper bound and lower bound? Ans: upper bound : an element to which every element relates. Lower bound :this element relates to every element.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.