Prove that $\{Tri, \lnot \}$ is not functional complete

Question

Let the function $Tri(p,q,r)$ which returns $t$ if and only if at least 2 out of 3 input variables are $t$. Prove that $\{Tri, \lnot\}$ is not functional complete.

I'd be glad for help, because frankly, I don't have a lead here.

Basically, the general idea is to invent some function with some property and claim that this function cannot be built by this set.

Thanks

Answer 1

I had trouble implementing the approach suggested by @Wojowu, so here is a different one.

Let us look at $F$, the set of two-variable functions that can be created from $T=\{Tri,\neg\}$. We will show that (for example) $OR \notin F$. Hence, $T$ is not functional complete.

Denote $\phi(x,y) \in F$. We will consider a few different cases by the complexity of $\phi$ (informally - how many times is any operator from $T$ used in $\phi$).

1. For zero complexity, $\phi(x,y)=x,y$ (where comma here means only one of those). Hence, the constant functions are in $F$.

2. Next, we add in an operator from $T$ (complexity one):

   • Adding $\neg$, we have that $\phi(x,y)=(\neg x), (\neg y)$. Hence, the constant negative functions are in $F$.

   • Adding $Tri$, one of the following is true:

     • $\phi(x,y)=Tri(x,x,x)=x$
     • $\phi(x,y)=Tri(x,x,y)=x$
     • $\phi(x,y)=Tri(x,y,y)=y$
     • From symmetry in the arguments of $\phi$ and $Tri$, we get all other cases.

     So no new function is added to $F$, other than the ones we already know about.

3. For the last step, let us add another operator from $T$:

   • Adding $\neg$, we have that $\phi(x,y)=x,y,(\neg x),(\neg y)$.
   • Adding $Tri$, one of the following is true:
     • $\phi(x,y)=Tri(x,\neg x,\neg y)=\neg y$
     • $\phi(x,y)=Tri(x,\neg x, y)=y$
     • One of the cases we saw in (2) occurs.
     • Again, from symmetry we get all other cases.

   For all cases, no new function is added to $F$.

We conclude that $F=\{x,y,(\neg x),(\neg y)\}$. In particular, $OR \notin F$. Hence, $T$ is not functional complete.