# Q: Is the set of all binary connectives having an even number of Truth in their truth table is functionally incomplete?

Is the set $TC$ of all binary connectives having an even number of Truth values assigned to the entries of their truth table (i.e. 0, 2 or 4) is functionally incomplete?

It's easy to see that the total number of such connectives is 8, but I don't quite think its of any help.

I'm having a hunch that the set $TC$ is indeed functionally incomplete, and I was trying to show by induction on the number of connectives the following lemma, but I got stuck:

Every $\alpha$ that is expressed only by connectives from $TC$ has an even number of Truth values in it's truth table.

If this lemma is indeed true, than $TC$ is not complete, because we cannot express for example $p \wedge q$, due to it having an odd number of Truth entries.

Any ideas?

Assume $\alpha$ is a formula containing $n+1$ connectives from $TC$ and only connectives from $TC$. Write $\alpha$ as $\beta \Delta\gamma$, where $\Delta$ is a connective in $TC$, $\beta$ and $\gamma$ are formulas which contain only connectives from $TC$, and contain at most $n$ of them. By induction assumption $\beta$ and $\gamma$ are both true on an even number of rows in the truth table.
Now how are these paired together? More specifically: how many rows do we have that $\beta$ is $true$ and $\gamma$ is true, or $\beta$ is true and $\gamma$ is false? Since we know that $\gamma$ is true on an even number of rows, we see that if $(\beta,\gamma)$ is $(True,True)$ on an even number of rows, we also have to have $(\beta,\gamma)$ is $(True,False)$ on an even number of rows and by symmetry $(\beta,\gamma)$ is $(False,True)$ on an even number of rows and thus $(\beta,\gamma)$ is $(False,False)$ on an even number of rows. While if $(\beta,\gamma)$ is $(True,True)$ on an odd number of rows, we also have to have $(\beta,\gamma)$ as $(True,False)$ on an odd number of rows and by symmetry $(\beta,\gamma)$ is $(False,True)$ on an odd number of rows and thus $(\beta,\gamma)$ is $(False,False)$ on an even number of rows.
Now when we know this what can we say about $\beta\Delta\gamma$? If $\Delta$ makes nothing or everything true, then the lemma trivially hold and we are done. Thus assume it makes two rows true and two rows false in its basic truth table. Now if $(\beta,\gamma)$ is $(True,True)$ on an even number of rows, it follows that the two truth assignments of $(\beta,\gamma)$ which $\Delta$ map to true, correspond to two even number of rows, thus $\beta\Delta\gamma$ is true on an even number of rows. On the other hand if $(\beta,\gamma)$ is $(True,True)$ on an odd number of rows, it follows that the two truth assignments of $(\beta,\gamma)$ which $\Delta$ map to true, correspond to two odd number of rows say $2p+1$ and $2q+1$, thus $\beta\Delta\gamma$ is true on $2p+1+2q+1= 2(p+q+1)$ number of rows i.e. an even number of rows.