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.

  • $\begingroup$ The $3$-element field is functionally complete. The $3$-element Post algebra is functionally complete. $\endgroup$ Commented Jan 23, 2012 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
    Commented Jan 23, 2012 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$ Commented Jan 23, 2012 at 17:33

2 Answers 2


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.


Page 64 of Nicholas Rescher's book Many-Valued Logic (McGraw Hill, 1969) states that the following three connectives form a functionally complete three-valued system:

  • the usual unary negation
  • the Łukasiewicz implication connective
  • another unary connective which always evaluates to $\bot$ (This is formally known as the Slupecki T-function.)

More generally, the authors of this paper have a paragraph summarizing Jobe's paper; Theorem 2 of Jobe essentially means that a three-valued system with $\wedge$ and $\vee$ (as they are typically interpreted in a three-valued system, e.g., Kleene's strong logic) is functionally complete for all truth tables if it is functionally complete with respect to just the unary connectives.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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