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

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?

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$.)