PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
De Morgan algebra (Definition)

A bounded distributive lattice $ L$ is called a De Morgan algebra if there exists a unary operator $ \sim:L\to L$ such that

  1. $ \sim(\sim a)=a$ and
  2. $ \sim(a\vee b)=(\sim a )\wedge (\sim b)$.

From the definition, we have the following properties:

  • $ \sim$ is a bijection, since for any $ a\in L$, $ a=\sim (\sim a)$.
  • $ \sim(a\wedge b)=\sim [(\sim (\sim a ))\wedge (\sim (\sim b))]= \sim [\sim ((\sim a)\vee (\sim b)) ]=(\sim a)\vee (\sim b)$, which is the dual statement of (2) above. This, together with condition (2), are commonly known as the De Morgan's laws.
  • $ \sim 0 =\ \sim (0 \wedge (\sim a))=(\sim 0) \vee a$ for all $ a\in L$, so $ \sim 0 = 1$. Dually, $ \sim 1=0$. As a result, a De Morgan algebra is an Ockham algebra.
  • $ a \le b$ iff $ b=a \vee b$ iff $ \sim b=\ \sim(a\vee b)=(\sim a)\wedge (\sim b)$ iff $ \sim b \le\ \sim a$.
  • A Boolean algebra is always a De Morgan algebra, where the $ \sim$ is the complementation operator $ '$. The converse is not true. In general, $ \sim a$ is not a complement of $ a$ (that is, $ (\sim a)\wedge a \ne 0$ and $ (\sim a)\vee a\ne 1$). Otherwise, $ L$ is a complemented lattice and consequently a Boolean algebra.

Furthermore, a Kleene algebra is, by definition, a De Morgan algebra. But the converse is false. For example, consider $ L=\mathbf{n}\times \mathbf{n}$, where $ \mathbf{n}=\lbrace 0,1,\ldots,n\rbrace$ is a chain with the usual ordering. Define $ \sim$ on $ L$ by $ \sim(a,b)=(n-b,n-a)$. Then $ \sim^2(a,b)=(a,b)$. The De Morgan's laws follow from the identity $ n-(a\vee b)=(n-a)\wedge (n-b)$ applied to each of the two components. But $ L$ is not Kleene in general. Take $ n=3$, then $ \sim (1,2)=(1,2)$ and $ \sim (2,1)=(2,1)$. But $ (1,2)=\sim (1,2)\wedge (1,2)$ and $ (2,1)=\sim (2,1)\vee (2,1)$ are not comparable.

Next, for any $ a,b\in L$, define $ a-b:=a\wedge (\sim b)$. Then $ -$ is a binary operator. It has the following properties:

  • $ a-0 = a\wedge (\sim 0)=a\wedge 1 =a$.
  • $ 0-a = 0\wedge (\sim a)=0$.
  • $ a-1 = a\wedge (\sim 1)=a\wedge 0=0$.
  • $ 1-a = 1\wedge (\sim a)=\ \sim a$.
  • $ (a-b)-c=(a\wedge (\sim b))\wedge (\sim c)=a\wedge (\sim (b\vee c))=a-(b\vee c)$.

Finally, we define for $ a,b\in L$, $ a+b=(a-b)\vee (b-a)$. This is again a binary operator, with the following properties:

  • $ a+b=b+a$. This is obvious by the symmetry in the definition of $ +$.
  • $ a+0=a$. We have $ a+0=(a-0)\vee (0-a)=a\vee 0=a$.
  • $ a+1=\ \sim a$, since $ a+1=(a-1)\vee (1-a)=0\vee (\sim a)=\ \sim a$. In particular $ 1+1=0$.
  • $ a+a=(a-a)\vee(a-a)=a-a=a\wedge (\sim a)$. If we define $ 2a:=a+a$, then $ a+2a=(a-2a)\vee (2a-a)=(a\wedge (a\vee (\sim a))\vee ((a\wedge (\sim a)\wedge (\sim a))=a\vee ((a\wedge (\sim a))=a$.
  • More generally, we have
    $\displaystyle a+(a+b)$ $\displaystyle =$ $\displaystyle (a-(a+b))\vee ((a+b)-a)$  
      $\displaystyle =$ $\displaystyle (a-((a-b)\vee(b-a)))\vee (((a-b)\vee(b-a))-a)$  
      $\displaystyle =$ $\displaystyle (a\wedge (\sim a\vee b)\wedge (\sim b\vee a))\vee (((\sim b \wedge a)\vee (\sim a\wedge b))\wedge (\sim a))$  
      $\displaystyle =$ $\displaystyle (a\wedge (\sim a\vee b))\vee (((\sim b\wedge a)\wedge (\sim a))\vee (\sim a\wedge b))$  
      $\displaystyle =$ $\displaystyle ((a\wedge (\sim a\vee b))\vee (\sim a\wedge b)) \vee (\sim b\wedge (\sim a\wedge a))$  
      $\displaystyle =$ $\displaystyle ((\sim a\wedge a) \vee (a\wedge b)\vee (\sim a \wedge b))\vee (\sim b\wedge 2a)$  
      $\displaystyle =$ $\displaystyle (2a \vee ((\sim a \wedge a)\vee b))\vee (\sim b\wedge 2a)$  
      $\displaystyle =$ $\displaystyle (2a \vee (2a \vee b))\vee (\sim b\wedge 2a)$  
      $\displaystyle =$ $\displaystyle (2a \vee b)\vee (\sim b\wedge 2a)$  
      $\displaystyle =$ $\displaystyle 2a \vee (\sim b \wedge 2a) \vee b$  
      $\displaystyle =$ $\displaystyle 2a \vee b.$  

Remark. Since a De Morgan algebra is an Ockham algebra, a morphism between any two objects in the category of De Morgan algebras behaves just like an Ockham algebra homomorphism: it preserves $ \sim$.

Bibliography

1
G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser (1998)



Anyone with an account can edit this entry. Please help improve it!

"De Morgan algebra" is owned by CWoo. [ full author list (2) ]
(view preamble)

View style:

Log in to rate this entry.
(view current ratings)

Cross-references: preserves, category, objects, morphism, obvious, binary, comparable, components, identity, ordering, chain, Kleene algebra, complemented lattice, complement, converse, Boolean algebra, iff, Ockham algebra, de Morgan's laws, bijection, properties, operator, unary, distributive lattice, bounded
There are 3 references to this entry.

This is version 10 of De Morgan algebra, born on 2006-08-09, modified 2007-05-24.
Object id is 8238, canonical name is DeMorganAlgebra.
Accessed 998 times total.

Classification:
AMS MSC: 03G10 (Mathematical logic and foundations :: Algebraic logic :: Lattices and related structures)
 06D30 (Order, lattices, ordered algebraic structures :: Distributive lattices :: De Morgan algebras, Lukasiewicz algebras)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)