Show that $ \{\lnot,\leftrightarrow\} $ is not functionally complete

Question

I have to prove that this set of logical operators is not functionally complete - $$ \{\lnot,\leftrightarrow\} $$

i've tried to implement this set with $ \{\rightarrow,\lor\} $ which is also not functionally complete, but didn't succeed.. thanks !

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.

Answer 2

Both of these functions are linear. If you make compositions of linear functions, the result is also linear. So any non-linear function is not constructible using these two.

Also, any problem of this sort can be solved in a similar way. For instance, the other set that you mention $\{\to, \lor\}$ is not complete because both connectives are truth-preserving, and composing truth-preserving functions again leads to truth-preserving functions. See here.

Answer 3

Represent Boolean functions as functions $\def\F{\Bbb F_2}\F^n\to\F$ (with $\F=\Bbb Z/2\Bbb Z$) by identifying false with$~0$ and true with$~1$. Such a function is called affine if it is of the form $(x_1,\ldots,x_n)\mapsto c_0+c_1x_1+\cdots+c_nx_n$ for some constants $c_0,c_1,\ldots,c_n\in\F$. Composing affine functions (for varying $n$) results in affine functions: in the expression for $f(g_1(x_1,\ldots,x_n),\ldots,g_k(x_1,\ldots,x_n))$ just work everything out by the distributive law.

Now $\lnot: x\mapsto 1+x$ and ${\leftrightarrow}:(x,y)\mapsto 1+x+y$ are affine functions, but among all $2^4=16$ functions $\F^2\to\F$, only $8$ are affine (there are three constants $c_0,c_1,c_2$ to choose), so there are certainly functions that are not affine, and therefore cannot be obtained by composition of $\lnot$ and $\leftrightarrow$. For instance $\land$ is such a function. (In fact the affine ones are $0$, $(x,y)\mapsto x$, $(x,y)\mapsto y$, $\leftrightarrow$, and their negations; all of these can be obtained as compositions of $\lnot$ and $\leftrightarrow$.)

Answer 4

Hint: If you have a formula made up of these and consider it as a function, in which ways can this function change when you negate one of the input variables?