tautologies in Kleene algebras (fuzzy logic and set theory)

Wlodzimierz Holsztynski (everest@netcom.com)
Tue, 27 Feb 1996 16:58:16 +0100

It is well known that for arbitrary boolean algebra B
strings of the form f=g which are
tautologies in B are the same as tautologies in the 2-element boolean
algebra {0,1} (it coincides with Lukasiewicz algebra L_2).
This means that 2^n substitutions are sufficient to verify
a tautology in any (even infinite) boolean algebra. All this
is a classical result. I'd like to ask if the similar results were
*published* for fuzzy logic and set theory, i.e. for Kleene algebras.
I have discovered and proved them recently but they have such a "classical"
feel that I expect them to be known. If this is the case
I would appreciate specific references (rather than intuitive opinions).

Here are the main results.


A = (K, \cup, \cap, ~,0,1) is a Kleene algebra
if K is a set, \cup and \cap are commutative and associative
binary operations such that

a \cap (\a \cup b) = b and
a \cup (\a \cap b) = a for every a b \in A,

and the distributivity of \cap w.r. \cup holds (then the other
distributivity law holds too); and ~ is a unary operation which
such that ~~a = a for every a \in K, and ~ is a dual isomorphism
between (K, \cap) and (K, \cup), i.e. De Morgan law:

~(a \cap b) = ~a \cup ~b (then the other law holds too),

and finally, the Kleene axiom should hold:

(a \cap ~a) \cup (b \cup ~b) = b \cup ~b for every a b \in K

(i.e. a \cap ~a \le b \cup ~b or what is still equivalent

(a \cup ~a) \cap (b \cap ~b) = b \cap ~b for every a b \in K).

We see that Kleene algebras have the same signature (operation symbols)
as boolean algebras, they form a larger class than boolean algebras.

NOTATION: [0;1] := { x : 0 \le x \le 1} is the unit interval of reals.

EXAMPLE: ([0;1], max, min, \, 0, 1) where \a := 1-a for every
a \in [0;1], is a Kleene algebra. It contains Lukasiewicz algebras
as subalgebras, L_n := (T_n, max, min, \, 0, 1), where

T_{n+1} := { 0/n, ..., n/n }

is the (n+1)-element set of fractions k/n (k=0,...,n).

THEOREM 1. Every Kleene algebra A admits an injective homomorphism
into L_3^V for a certain set V (the cardinality of V depends on A).

THEOREM 2. Every Kleene algebra which is not boolean admits
a surjective homomorphism onto L_3.

THEOREM 3. Let A be a Kleene algebra. If A is boolean than
the set of tautologies f=g in A is the same as for L_2,
and if A is not boolean that its set of tautologies is the same
as for L_3 (the former set of tautologies, for L_2, contains
the later one, that for L_3).

In the above theorem f and g stand for arbitrary strings which
are what is commonly called boolean expressions which produce values
from a given Kleene algebra A after replacing
variables with the elements of the given algebra A.
And f=g is called a tautology in A if all possible substitutions
of variables by elements of A in the string f=g produce an equality
in A each time.

Thank you,

Wlodzimierz Holsztynski