The Unapologetic Mathematician

Mathematics for the interested outsider

DeMorgan’s Laws

And here’s the post I wrote today:

Today, I want to prove two equations that hold in any orthocomplemented lattice. They are the famous DeMorgan’s laws:

\displaystyle\neg(x\vee y)=\neg x\wedge\neg y
\displaystyle\neg(x\wedge y)=\neg x\vee\neg y

First, we note that x\leq x\vee y by definition. Since our complementation reverses order, we find \neg(x\vee y)\leq\neg x. Similarly, \neg(x\vee y)\leq\neg y. And thus we conclude that \neg(x\vee y)\leq\neg x\wedge\neg y.

On the other hand, \neg x\wedge\neg y\leq\neg x by definition. Then we find x=\neg\neg x\leq\neg(\neg x\wedge\neg y) by invoking the involutive property of our complement. Similarly, y\leq\neg(\neg x\wedge\neg y), and so x\vee y\leq\neg(\neg x\wedge\neg y). And thus we conclude \neg x\wedge\neg y\leq\neg(x\vee y). Putting this together with the other inequality, we get the first of DeMorgan’s laws.

To get the other, just invoke the first law on the objects \neg x and \neg y. We find

\displaystyle\begin{aligned}\neg x\vee\neg y&=\neg\neg(\neg x\vee\neg y)\\&=\neg(\neg\neg x\wedge\neg\neg y)\\&=\neg(x\wedge y)\end{aligned}

Similarly, the first of DeMorgan’s laws follows from the second.

Interestingly, DeMorgan’s laws aren’t just a consequence of order-reversal. It turns out that they’re equivalent to order-reversal. Now if x\leq y then x=x\wedge y. So \neg x=\neg(x\wedge y)=\neg x\vee\neg y. And thus \neg y\leq\neg x.

May 8, 2009 - Posted by | Algebra, Lattices

8 Comments »

  1. When I play briefly with high school kids and sets, and when I play with them (a little less briefly) with logic, I run into math that looks like this (without the proof), twice. I draw, naturally, the analogy.

    Is there any difference of consequence between the complement of a union and the negation of a disjunction?

    (train of thought started since you’ve used what I would consider a mix of symbols)

    Jonathan

    Comment by jd2718 | May 9, 2009 | Reply

  2. Sure there’s a difference. One takes place in the lattice of subsets of a given ambient set, and the other takes place in the lattice of propositions in a given propositional calculus.

    Comment by John Armstrong | May 9, 2009 | Reply

  3. But the mechanics look identical?

    Comment by jd2718 | May 9, 2009 | Reply

  4. As far as the lattices are concerned, yes. Union is the join in the lattice of subsets, while disjunction is the join in the lattice of propositions. Similarly, complementation (in the set theory sense) is the complementation in the lattice of subsets, while negation is the complementation in the lattice of propositions.

    In fact, there’s a way of making this all even more explicit, building a propositional calculus for a given set so that the two lattices are isomorphic. But that’s more something I’ll leave to the (possibly far) future when I talk more about the logical structure of classical (and eventually quantum!) mechanics.

    Comment by John Armstrong | May 9, 2009 | Reply

  5. it is very best and very good text

    Comment by arvin in iran | July 2, 2009 | Reply

  6. […] DeMorgan’s Laws, the intersection of all these complements is the complement of the union of all the . […]

    Pingback by Inclusion-Exclusion Again « The Unapologetic Mathematician | December 28, 2009 | Reply

  7. […] and the difference , along with and . But from this we can get complements — — and DeMorgan’s laws give us intersections — […]

    Pingback by Algebras of Sets « The Unapologetic Mathematician | March 15, 2010 | Reply

  8. […] also happens that our base is closed under finite unions. Indeed, we use DeMorgan’s laws and […]

    Pingback by Stone’s Representation Theorem II « The Unapologetic Mathematician | August 19, 2010 | Reply


Leave a reply to Algebras of Sets « The Unapologetic Mathematician Cancel reply

« Previous | Next »