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

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 !

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.

• @Y.X. The assumption is that P occurs in a larger statement $\phi$, and that $\phi$ has at least two variables. Also, the truth-table for a statement with $n$ variables has $2^n$ rows. So, with two or more variables (i.e. $n \ge 2$, the number of rows becomes a multiple of 4. Finally, in the truth-table for $\phi$, P is one of the reference columns on the left, and they always have exactly as many $T$'s as $F$'s. And just to be clear: an atomic statement is the same as a variable. Mar 6, 2017 at 13:02
• Nice proof, and self-contained, unlike other answers. A few devilish details, sorry it's years after you answered: (*) There's no need for the claim to require 2 or more variables: clearly an atomic formula has an even number of T rows in its truth table. With that change the Base case of the proof will be correct/appropriate; it isn't now. (**) The undefined variables $p_i$ should be $n_i$. (***) $m_2$ and $n_2$ are used but never actually defined [$m_2$ maybe implicitly, $n_2$ never]. Of course $m_2 = m - m_1$, and $n_2 = n - n_1$. Mar 8, 2022 at 20:26
• @BrianO Makes sense, thanks!! Mar 8, 2022 at 21:01
• @DuduBob The truth-table for any function that refers to $2$ or more variables (and that is what we are dealing with here) will have a number of rows that is a multiple of $4$. Working out the truth-conditions for an atomic statement in such a truth-table will have an even number of T's and an even number of F's. Jan 15 at 15:10
• @DuduBob An atomic formula $P$ occurring in $\phi$ receives a T or an F in each row of the truth table for $\phi$; we're not considering a separate, smaller truth table for $P$ alone, which yes would have only two rows. Here, the number of rows is a multiple of 4, and the claim is that $P$ the number of rows in which it's T equals the number of rows in which it's F. Jan 16 at 5:09

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.

• Reading the description of the link, neither of the two given operations is linear, since that property requires taking the value 'false' when all arguments are false. For $\leftrightarrow$ one could repair this by intrchanging the roles of 'true' and 'false', but for $\lnot$ this does not work. So one needs a different notion than 'linear'. Nov 8, 2013 at 9:16
• @MarcvanLeeuwen Note that $a_0\ldots a_n$ are fixed boolean values. Nov 8, 2013 at 9:19
• @Marc $b_1 \leftrightarrow b_2 = 1 \oplus b_1 \oplus b_2$. It fits the definition on wikipedia. Although I do agree that it would be better to stick to calling such functions affine. Nov 8, 2013 at 9:25
• I missed the $a_0$ in the initial description of the WP article. But then the WP article contradicts itself, as it later clearly states that all arguments false should result in a false value. I think calling "linear" functions that need $a_0=1$ is very confusing since inconsistent with the use in linear algebra (which field may have usurpated the term "linear" that originally meant "straight", true, but that is now history). Nov 8, 2013 at 9:39

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

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?