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
Search WWH ::




Custom Search