TAUTOLOGIES in DE MORGAN and KLEENE ALGEBRAS

Wlodzimierz Holsztynski (everest@netcom.com)
Sat, 9 Mar 1996 00:15:33 +0100


TAUTOLOGIES in DE MORGAN and KLEENE ALGEBRAS
===============================================

This article complements my previous one,

tautologies in Kleene algebras (fuzzy logic and set theory)

posted to this (and one more) group. I have asked about
the references and I am grateful to everybody who has responded.
It seems fairly certain that while there are related results
in the literature or preprints, my results are new (I still would
like to know more about references).

Here are the main results.

Definition:

A = (K, \cup, \cap, ~,0,1) is a DeMorgan 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 holds:

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

Observe that then ~0 = 1 and ~1 = 0.

A DeMorgan algebra is called a Kleene Algebra
if the Kleene axiom holds:

(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 DeMorgan and Kleene algebras have the same signature
(operation symbols) as boolean algebras,
they form larger classes than boolean algebras.

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

EXAMPLE 1. ([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).
Hence Lukasiewicz algebras are Kleene algebras; L_2 is boolean
only for n=2.

EXAMPLE 2. Let D := {0,a,b,1} be a partially ordered 4-element set
such that 0 is the minimal, 1 the maximal element, while a, b are not
compatible. Let \cup and \cap be defined accordingly (hence D as
a lattice with 0 and 1 is isomorphic to the 4-element boolean
algebra). Finally let ~0 := 1, ~1 := 0, ~a :=a and ~b :=b.
Then D is a DeMorgan algebra, which is not a Kleene algebra.

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).
And every DeMorgan algebra admits an injective homomorphism into
a certain D^V.

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

THEOREM 3. Let A be a DeMorgan algebra. Then:

(i) if A is boolean than the set of tautologies f=g in A
is the same as for L_2;

(ii) if A is a Kleene but not boolean algebra than 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);

(iii) if A is not a Kleene algebra than its set of tautologies
is the same as for D.

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 DeMorgan algebra A after replacing
variables with the elements of the given algebra A.

To avoid trivialities I always assume that 0 is different
from 1. (A very healthy view :-).

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
everest@netcom.com

Acknowledgement: I'd like to express my gratitude to Elbert
Walker for mailing me the preprint:

"A Mathematical Setting for Fuzzy Logic"

by Mai Gehrke, Carol Walker and Elbert Walker (still warm from
the printer, dated 1996-March-04). It has alerted me to the existence
of DeMorgan algebras in the literature.

W. Holsztynski