De Morgan algebra
A bounded distributive lattice
is called a De Morgan algebra if there exists a unary operator such that
- 1.
and
- 2.
.
From the definition, we have the following properties:
- •
is a bijection, since for any , .
- •
, which is the dual statement of (2) above. This, together with condition (2), are commonly known as the De Morgan’s laws.
- •
for all , so . Dually, . As a result, a De Morgan algebra is an Ockham algebra.
- •
iff iff iff .
- •
A Boolean algebra
is always a De Morgan algebra, where the is the complementation operator . The converse
is not true. In general, is not a complement
of (that is, and ). Otherwise, 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 , where is a chain with the usual ordering. Define on by . Then . The De Morgan’s laws follow from the identity applied to each of the two components. But is not Kleene in general. Take , then and . But and are not comparable
.
Next, for any , define . Then is a binary operator. It has the following properties:
- •
.
- •
.
- •
.
- •
.
- •
.
Finally, we define for , . This is again a binary operator, with the following properties:
- •
. This is obvious by the symmetry
in the definition of .
- •
. We have .
- •
, since . In particular .
- •
. If we define , then .
- •
More generally, we have
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 .
References
- 1 G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser (1998)