9
$\begingroup$

In the context of some recent work, we have been defining a language based on a three-valued logic à la Kleene, where $1$ stands for true, $0$ for false, and $\bot$ for error or don't-know. In order to show that our language was expressive, we wanted to prove that we could build a set of operators functionally complete.

It was quite hard to find existing results in the literature. We found one paper written in 1962 by Jobe, which states the following theorem:

Jobe 1962 Theorem Paper (restricted access).

The three-valued logic $E$ expressed over the set $\{1, 2, 3\}$ and defined by the operators $\bullet, E_1$ and $E_2$, given below, is functionally complete.

$$ \begin{array}{c|ccc|c|c} ~\bullet~ & ~3~ & ~2~ & ~1~ & ~E_1~ & ~E_2~ \\ \hline 3 & 3 & 2 & 1 & 3 & 1 \\ 2 & 2 & 2 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 2 & 3 \end{array} $$

In our paper, we have used this result by showing a correspondance between our operators and those defined by Jobe (roughly speaking, we use the strong conjunction, the negation, and an operator that transforms don't-know in false).

My main concern is that I'm actually not able to understand the proof of functional completeness of Jobe, and we haven't been able to find any other result (positive or negative) after this date, which is somehow a bit surprising.

So my question is the following: are there some more known results about the functional completeness of 3-valued logics? Any info in this direction would be helpful.

$\endgroup$
  • $\begingroup$ The $3$-element field is functionally complete. The $3$-element Post algebra is functionally complete. $\endgroup$ – Emil Jeřábek Jan 23 '12 at 13:38
  • $\begingroup$ @EmilJeřábek Thanks, I just read about the Ternary Post Logic, and that seems to correspond (although I can't find much on this topic either). Would you have some reference about the 3-element field? Google is a bit too vague. $\endgroup$ – Charles Jan 23 '12 at 15:40
  • 1
    $\begingroup$ I can’t give you a reference off-hand, but it’s an easy fact: standard (multivariate) interpolation implies that any operation on a finite field can be expressed by a polynomial. Moreover, if the field is prime (such as here), then the coefficients of the polynomial are definable by constant terms ($1+1+\cdots+1$). Thus, prime fields in the language $\{+,\cdot,1\}$ are functionally complete. $\endgroup$ – Emil Jeřábek Jan 23 '12 at 17:33
2
$\begingroup$

Chapters 5 and 6 of the book [Function algebras on finite sets, Dietlinde Lau, 2006] contain an in depth treatment of functional completeness in many-valued logic (including proofs). In summary: Rosenbergs [1965, 1970] characterization of maximal clones (also called precomplete clones) give a criterion for functional completeness in k-valued logic for any k.

For the special case of 3-valued logic such a characterization (consisting of 18 maximal/precomplete classes) was given by Jablonskij already in 1954. Hence, in order to verify that your set of 3-valued "operators" are functionally complete, it is enough to check that they don't fall into any of the 18 precomplete classes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.