# How to decide if propositional function is complete

I have two 3-ary propositional functions given by the table

$$\begin{array}{|c|c|c|c|c|} v(a) & v(b) & v(c) & v(f(a, b, c)) & v(g(a, b, c)) \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \hline \end{array}$$

And I need to decide which of these functions are complete. I made some googling but I didn't get the way how to solve such type of tasks. Books say that $L(\vee,\wedge,\neg)$, $L(\wedge,\neg)$, ... are complete and $L(\wedge)$, $L(\vee)$... are not. But how to apply this on the functions given by table?

I gues I need to make propositional formula from $f$ and $g$. Am I right? If so what's next?

• $v(g(a,b,c))$ is the minority conncetive : $v(g(a,b,c))$ always disagrees with the majority of $v(a), v(b), v(c)$. See Enderton, Exercises 4, page 52 : is not complete. – Mauro ALLEGRANZA Nov 4 '14 at 12:35

We can try exploiting the fact that we know that : $\lnot, \land$ is complete.

The ternary connective $g(a,b,c)$ is the minority connective : $v(g(a,b,c))$ always disagrees with the majority of $v(a),v(b),v(c)$.

We can formally set :

$v(g(a,b,c))=1$ iff $v(a)+v(b)+v(c) \le 1$.

We can define $\lnot$, because $v(g(a,a,a))=1$ iff $v(a)=0$.

But we cannot define $a \land b$, because $v(a \land b)=1$ iff $v(a)+v(b) = 2$.

Thus, it is not complete.

It seems to me that $f(a,b,c)$ is complete.

We can formally set :

$v(f(a,b,c))=[1-v(a)v(c)][1-v(b)v(c)]$.

In this way, we can define $\lnot$, because $v(f(a,a,a))=1$ iff $v(a)=0$.

We can check also that $f(a,b,c)$ is equivalent to : $\lnot c \lor (\lnot a \land \lnot b)$.

Obviously : $\lnot a \land \lnot a \equiv \lnot a$; thus $f(a,a,c)$ is $\lnot a \lor \lnot c$ i.e. $\lnot (a \land c)$ that is NAND, or Sheffer stroke and we know that it is complete.

• Oh that's not obvious at all. Thank you, you helped me a lot – Levitan Nov 4 '14 at 14:34