Database Reference
In-Depth Information
7.
aa
=
1,
8.
a
∧
(a b)
=
a
∧
b
,
b
∧
(a b)
=
b
,
9.
a(b
(a c)
.
In a Heyting algebra, we can define the negation
∧
c)
=
(a b)
∧
¬
a
as a pseudo-complement
a
0.
≤¬¬
Then,
a
a
. Each
finite distributive
lattice is a Heyting algebra. A complete
Heyting algebra is a Heyting algebra
H
,
0
,
1
)
which is com-
plete as a poset. A complete distributive lattice is thus a complete Heyting algebra
iff the following
infinite distributivity
holds [
69
]:
10.
a
∧
i
∈
I
b
i
=
i
∈
I
(a
∧
b
i
)
for every
a,b
i
∈
W
,
i
∈
I
.
The negation and implication operators can be represented as the following mono-
tone functions:
=
(W,
≤
,
∧
,
∨
,,
¬
¬:
W
→
W
OP
and
:
W
×
W
OP
→
W
OP
, where
W
OP
is the
OP
OP
lattice with inverse partial ordering and
∧
=∨
,
∨
=∧
.
The following facts are valid in any
H
:
(H1)
a
≤
b
iff
ab
=
1
,(ab)
∧
(a
¬
b)
=¬
a
;
0
OP
OP
(H2)
b
; (additive negation)
with the following weakening of classical propositional logic:
(H3)
¬
0
=
=
1
,
¬
(a
∨
b)
=¬
a
∨
¬
b
=¬
a
∧¬
¬
a
∨
b
≤
ab
,
a
≤¬¬
a,
¬
a
=¬¬¬
a
;
(H4)
a
∧¬
a
=
0
,a
∨¬
a
≤¬¬
(a
∨¬
a)
=
1; (weakening excluded-middle)
(H5)
b)
; (weakening of De Morgan laws)
Notice that since negation
¬
a
∨¬
b
≤¬
(a
∧
W
OP
is a monotonic and additive operator, it is
also a
modal
algebraic negation operator. The smallest complete distributive lattice
is denoted by
2
¬:
W
→
with two classic values, false and true, respectively. It is
also a complemented Heyting algebra and hence it is Boolean.
From the point of view of Universal algebra, given a signature
Σ
with a set of
functional symbols
o
i
∈
={
0
,
1
}
Σ
with arity
ar
:
Σ
→
N
, an algebra (or algebraic struc-
ture)
A
(W,Σ
A
)
is a carrier set
W
together with a collection
Σ
A
of operations on
W
with an arity
n
=
≥
0. An
n
-ary operator (functional symbol)
o
i
∈
Σ
,
ar(o
i
)
=
n
on
W
n
W
will be named an
n
-ary operation (a function)
W
in
Σ
A
that takes
n
elements of
W
and returns a single element of
W
. Thus, a 0-ary operator (or nullary
operation) can be simply represented as an element of
W
, or a constant, often de-
noted by a letter like
a
(thus, all 0-ary operations are included as constants into the
carrier set of an algebra). An algebra
A
is
finite
if the carrier set
W
is finite; it is
finitary
if each operator in
Σ
A
has a finite arity. For example, a lattice is an algebra
with signature
Σ
L
={∧
o
i
:
→
∨
}
∧
∨
are binary operations (meet and
join operations, respectively), while 0
,
1 are two nullary operators (the constants).
The equational semantics of a given algebra is a set of equations
E
between the
terms (or expressions) of this algebra (for example, a distributive lattice is defined
by the first six equations above).
Given two algebras
A
,
,
0
,
1
, where
and
=
(W,Σ
A
)
,
A
=
(W
,Σ
A
)
of the same
type
(with the
same signature
Σ
and set of equations), a map
h
:
W
→
W
is called a
homomor-
phism
if for each
n
-ary operation
o
i
∈
Σ
A
and
a
1
,...,a
n
∈
W
,
h(o
i
(a
1
,...,a
n
))
=
o
i
(h(a
1
),...,h(a
n
))
. A homomorphism
h
is called an
isomorphism
if
h
is a bijec-
tion between respective carrier sets; it is called a monomorphism (or embedding) if
h
is an injective function from
W
into
W
. An algebra
A
is called a homomorphic
image of
A
if there exists a homomorphism from
A
onto
A
. An algebra
A
is a