<p>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. </p>

<p>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.</p>

CC BY-SA 4.0
2018-07-07T15:27:04.320Z
2018-07-07T15:27:04.320Z
Gustav Nordh
<p>Page 64 of Nicholas Rescher's book <em>Many-Valued Logic</em> (McGraw Hill, 1969) states that the following three connectives form a functionally complete three-valued system:</p>
<ul>
<li>the usual unary negation</li>
<li>the Łukasiewicz implication connective</li>
<li>another unary connective which always evaluates to <span class="math-container">$\bot$</span> (This is formally known as the <em>Slupecki T-function</em>.)</li>
</ul>
<p>More generally, the authors of <a href="https://www.sciencedirect.com/science/article/abs/pii/S0020025513004775?via%3Dihub" rel="nofollow noreferrer">this paper</a> have a paragraph summarizing Jobe's paper; Theorem 2 of Jobe essentially means that a three-valued system with <span class="math-container">$\wedge$</span> and <span class="math-container">$\vee$</span> (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.</p>

CC BY-SA 4.0
2022-12-15T07:57:47.767Z
2022-12-15T07:57:47.767Z
nsnave
<p>In the context of some recent <a href="http://arxiv.org/abs/1111.5767">work</a>, 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. </p>

<p>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: </p>

<blockquote>
  <p><strong>Jobe 1962 Theorem</strong> <a href="http://www.jstor.org/pss/2964548">Paper</a> (restricted access). </p>
  
  <p>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.</p>
  
  <p>$$
    \begin{array}{c|ccc|c|c}
        ~\bullet~ &amp; ~3~ &amp; ~2~ &amp; ~1~ &amp; ~E_1~ &amp; ~E_2~ \\ \hline
        3     &amp; 3 &amp; 2 &amp; 1 &amp; 3   &amp; 1 \\
        2     &amp; 2 &amp; 2 &amp; 1 &amp; 1   &amp; 2 \\
        1     &amp; 1 &amp; 1 &amp; 1 &amp; 2   &amp; 3
    \end{array}
$$</p>
</blockquote>

<p>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). </p>

<p>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. </p>

<p>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. </p>

CC BY-SA 3.0
2012-01-23T13:38:40.843Z
The $3$-element field is functionally complete. The $3$-element Post algebra is functionally complete.
Emil Jeřábek
CC BY-SA 3.0
2012-01-23T15:40:24.087Z
@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
CC BY-SA 3.0
2012-01-23T17:33:40.783Z
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
<reference-request><lo.logic>
Functional Completeness of 3-valued logic
Charles
# Functional Completeness of 3-valued logic

(Asked by: username_0 on 2012-01-23)

In the context of some recent [work](http://arxiv.org/abs/1111.5767), 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](http://www.jstor.org/pss/2964548) (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.

**Tags:** reference-request, lo.logic
> **Comments:**
> **username_1**: The $3$-element field is functionally complete. The $3$-element Post algebra is functionally complete.  
> **username_0**: @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.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2018-07-07. Score: 3

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.


---

### Answer by username_3 on 2022-12-15. Score: 2

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](https://www.sciencedirect.com/science/article/abs/pii/S0020025513004775?via%3Dihub) 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.


---

