Prove a set is not a complete set of connectives

Question

Prove that the set of {not, xor, iff} is not complete.

My question is in when defining a predicate how can you do it so that each of the above connectives are satisfied. The only truth assignments i know of is 0, 1 however i don't think it would work for this set of connectives. My best guess would be some truth assignment that affects one of two variables for xor and iff, but is still valid for not, which only take one.

Answer 1

Claim: Any truth-function $\phi$ defined over two or more variables and using $\neg$ and $\leftrightarrow$ only will have an even number of $T$'s and (therefore) an even number of $F$'s in the truth-table.

Proof: Take any such truth-function $\phi$. Since it involves two or more variables, the number of rows in the truth-table is a multiple of 4. By Induction over structure of $\phi$ we'll show that any subformula of $\phi$ will have an even number of $T$'s and $F$'s in the truth-table of $\phi$

Base: Take atomic statement $P$. In the truth-table of $\phi$, exactly half of the times $P$ will be $T$, and the other half it is $F$. So given that the number of rows in the truth-table is a multiple of 4, there are an even number of $T$'s and an even number of $F$'s

Step: Let $\psi$ be a subformula of $\phi$. We need to consider two cases:

Case 1: $\psi = \neg \psi_1$

By inductive hypothesis, $\psi_1$ has an even number of $T$'s and $F$'s in the truth-table. Since all $T$'s become $F$'s and vice versa when negating, that means that $\psi$ has an even number of $T$'s and $F$'s in the truth-table.

Case 2: $\psi = \psi_1 \leftrightarrow \psi_2$

By inductive hypothesis, $\psi_1$ and $\psi_2$ both have an even number of $T$'s and $F$'s in the truth-table.

Now consider what happens when we evaluate $\psi = \psi_1 \leftrightarrow \psi_2$. Let us first consider the $m$ rows where $\psi_1$ is $T$. Of those rows, assume that $\psi_2$ is $T$ in $m_1$ of those and hence $F$ in $m-m_1$ of those. This gives us $m_1$ $T$'s and $m-m_1$ $F$'s for $\psi$. Now consider the $n$ rows where $\psi_1$ is $F$. Of those rows, assume that $\psi_2$ is $T$ in $n_1$ of those and hence $F$ in $n-n_1$ of those. This gives us $n_1$ $F$'s and $n-n_1$ $T$'s for $\psi$. So, in total we get $m_1 + p_2$ $T$'s and $m_2 + p_1$ $F$'s for $\psi$.

But, since by inductive hypothesis $\psi_1$ has an even number of $T$'s, we know $m = m_1 + m_2$ and $n = n_1 + n_2$ are both even and thus $m_1$ and $m_2$ have the same parity, and same for $n_1$ and $n_2$. Also, since by inductive hypothesis $\psi_2$ has an even number of $T$'s and $F$'s in the truth-table, we have that $m_1 + n_1$ and $m_2 + n_2$ are both even, meaning that $m_1$ and $n_1$ have the same parity, and same for $m_2$ and $n_2$. Combining this, that means that $m_1$ and $n_2$ have the same parity, and same for $m_2$ and $n_1$. Hence, $m_1 + p_2$ and $m_2 + p_1$ are both even, meaning that $\psi$ has an even number of $T$'s and $F$'s in the truth-table.

Now that we have proven the claim, we know that you cannot capture truth-functions that have an odd number of $T$'s and an odd number of $F$'s in the truth-table. Hence, $\{ \neg, \leftrightarrow \}$ is not expressively complete.

Finally, let's point out that $P \oplus W \Leftrightarrow \neg P \leftrightarrow Q$. This means that if $\{ \neg, \leftrightarrow, \oplus \}$ is expressively complete, then $\{ \neg, \leftrightarrow \}$ is expressively complete as well. But since we just proved that $\{ \neg, \leftrightarrow \}$ is not expressively complete, it follows that $\{ \neg, \leftrightarrow, \oplus \}$ is not expressively complete either.

Answer 2

First, we have $$a \iff b = a \underline{\vee} \neg b $$ and $$\neg b = True \underline{\vee} b$$ ($\iff$ and $\neg$ can be defined in terms of $\underline{\vee}$), so we only have to prove $\{\underline{\vee} \}$ is not a complete set of connectives. And that is indeed true (see Proof that {xor,not} is not functionally complete)