Information Technology Reference
In-Depth Information
(
,
)
Provided
L
only verifies the reflexive and the transitive properties, is called
a preordered set.
2. An algebraic structure
(
L
,
·
,
+
)
is a lattice, provided the binary operations
·
and
+
verify,
•
Both operations are commutative and associative, that is,
a
·
b
=
b
·
a
,
a
+
b
=
b
+
a
,
a
·
(
b
·
c
)
=
(
a
·
b
)
·
c
,
a
+
(
b
+
c
)
=
(
a
+
b
)
+
c
, for all
a
,
b
,
c
in
L
.
•
Both operations are idempotent, that is,
a
·
a
=
a
,
a
+
a
=
a
, for all
a
in
L
.
Without proof, let's state what follows:
(a) It is easy to prove that the relation
a
a
, is a partial order called
the 'natural order of the lattice', and that it is equivalent to
a
b
⃔
a
·
b
=
b
⃔
a
+
b
=
b
.
(b) Operation
+
verifies:
a
+
b
is the lowest element in
(
L
,
)
such that
a
a
+
b
,
and
b
b
. That is, in the natural order, there is no element in
L
that is
both between
a
and
a
a
+
+
b
, and between
b
and
a
+
b
. Operation
·
verifies:
a
·
b
is the greatest element in
(
L
,
)
such that
a
·
b
a
, and
a
·
b
b
. That is, in
the natural order, there is no element in
L
between
a
·
b
and
a
, and between
a
·
b
and
b
, in the order
.
(c) If
a
b
, then
a
·
c
b
·
c
, and
a
+
c
b
+
c
, for all
c
in
L
.
3. A lattice is bounded if there are elements 0 and 1 in
L
, such that 0
1, for
all
a
in
L
and called, respectively, the minimum and the maximum of the lattice.
These elements verify:
0
a
·
=
·
=
+
=
+
=
a
0, 1
a
a
,0
a
a
, and 1
a
1, for all
a
in
L
. That is, 0 is
·
+
·
+
absorbent for
, and neutral for
, and 1 is neutral for
, and absorbent for
.
4. In a bounded lattice, a mapping
:
L
is a negation provided: 0
=
1, 1
=
L
ₒ
0,
b
a
, and
a
=
(
a
)
=
a
, for all
a
in
L
.
5. A bounded lattice with a negation is dual, provided the operations
a
b
⃒
·
and
+
are
)
a
+
b
, for all
a
,
b
in
L
. This expression is equivalent to
linked by
(
a
·
b
=
)
=
a
·
b
, since it immediately follows from
a
·
b
)
=
a
+
b
=
(
a
+
b
(
a
+
b
.
6. A lattice is distributive, provided:
a
+
b
·
c
=
(
a
+
b
)
·
(
a
+
c
)
, and
a
·
(
b
+
c
)
=
a
c
.
Provided it is dual, a bounded distributive lattice with a negation is a De Morgan
algebra. A bounded lattice with a negation such that it is dual, and:
a
·
b
+
a
·
a
·
=
0
a
=
(law of non-contradiction), and
a
1 (law of excluded-middle), is an Ortho-
lattice. Notice that both laws are equivalent; for instance,
a
+
a
=
a
)
=
·
0
⃒
(
a
·
a
+
1
1.
An Ortho-lattice such that it holds the property
a
⃒
a
=
a
·
b
,
is called an Ortho-modular lattice. Distributive ortho-lattices, are called Boolean
algebras. Notice that in them:
b
⃔
b
=
a
+
a
·
a
)
·
(
•
a
b
⃒
a
+
b
=
(
a
+
a
+
b
)
=
a
+
b
=
b
a
·
•
b
=
a
+
b
≥
a
⃒
a
b
,
that is, all Boolean algebras are Ortho-modular lattices, but not reciprocally.
Search WWH ::
Custom Search