# 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. – Emil Jeřábek 3.0 Jan 23 '12 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. – Charles Jan 23 '12 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. – Emil Jeřábek 3.0 Jan 23 '12 at 17:33