# Functional Completeness of 3-valued logic

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.

• The $3$-element field is functionally complete. The $3$-element Post algebra is functionally complete. Commented Jan 23, 2012 at 13:38
• @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. Commented Jan 23, 2012 at 15:40
• 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. Commented Jan 23, 2012 at 17:33

• 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.