# Prove that a set of connectives is inadequate

It is relatively easy to prove that a given set of connectives is adequate. It suffices to show that the standard connectives can be built from the given set. It is proven that the set $\{\lor, \land, \neg\}$ is adequate, and from that set it can be inferred (applying De Morgan laws and such) that $\{\lor, \neg\}$, $\{\land, \neg\}$ and $\{\to, \neg\}$ are also adequate.

Nevertheless, I'm stuck trying to understand how to prove that a given set of connectives is inadequate. I know I have to prove that a standard connective can't be build using only the connectives of the given set, but I can't figure out how to do it.

FYI, I'm trying to prove that $\{\lor, \land\}$ and $\{\leftrightarrow, \neg\}$ are inadequate sets of connectives.

For $\{{\leftrightarrow},{\neg}\}$, notice that if we identify "true" and "false" with $1$ and $0$ modulo $2$, then $a\leftrightarrow b \equiv a+b+1 \pmod2$ and $\neg a \equiv a+1\pmod2$. So everything we can build from them will be represented by linear polynomials modulo 2.

We can convert that idea back to a direct proof that does not speak about modular arithmetic:

Lemma. Assume $f(x_1,\ldots,x_n)$ is a Boolean function built from $\leftrightarrow$ and $\neg$. Then for $1\le i\le n$ it holds either that $f$ does not depend on $x_i$ at all, or that inverting the value of $x_i$ will always invert the value of $f(x_1,\ldots,x_n)$.

Proof. By structural induction on $f$.

Since $a\land b$ does not have the property specified by the lemma, it cannot be built from $\leftrightarrow$ and $\neg$.

Notice that the structure of proofs that a set of connectives is not adequate is more varied than the structure of proofs that it is. (The latter is just a matter of showing that each member of a known adequate set can be expressed, which can then be verified by truth tables).

• Thank you very much for your answer. It's a bit complex for me due to my lack of math and logic background, but I can see your point. Thanks. Commented Sep 4, 2012 at 22:55

There is a result in Robert Reckhow's thesis that characterizes the adequate sets of connectives. The result says that for a set of connectives to be complete one needs the following:

• F and T (or formulas with these values),
• an odd connective (a connective is called odd if some fixing of its input variables with T and F except two input variables has odd number of Ts in its truth table),
• a non-monotone connective (a connective that turning an F to a T will make its value change from T to F).

These are necessary and sufficient conditions for a set of connectives to be adequate. If a set of connectives is not adequate then it lacks one of these. If you have an odd connective, you can fix the inputs with T and F to get either $$\vee$$ or $$\wedge$$. If you have a non-monotone connective, you can fix the inputs with T and F to get $$\lnot$$. Any boolean function can then be constructed from these as a CNF.

Note that even connectives are closed under composition as well as monotone connectives. So to prove that a set of connectives is inadequate, you typically need to show that either

• all of the connectives are monotone, or
• all of the connectives are even.

For your examples, the first one is a set of monotone connectives, the second one is a set of even connective. So they cannot be adequate.

For the first problem let $$\Phi$$ be the set of propositions built up from $$a,\lor$$, and $$\land$$. It can be described as follows:

1. $$a\in\Phi$$.
2. If $$\varphi,\psi\in\Phi$$, then $$\varphi\lor\psi,\varphi\land\psi\in\Phi$$.
3. $$\Phi$$ is the smallest set of propositions satisfying (1) and (2).

Now suppose that $$\varphi\in\Phi$$, and consider the truth table for $$\varphi$$:

$$\begin{array}{c|c} a&\varphi\\ \hline T&?_1\\ F&?_2 \end{array}$$

I claim that the truth value $$?_1$$ is $$T$$ for all $$\varphi\in\Phi$$, and therefore $$\lnot a\notin\Phi$$.

This is clearly the case for the proposition $$a$$. Suppose that it’s true for propositions $$\varphi,\psi\in\Phi$$. Then we have the following partial truth table;

$$\begin{array}{c|c} a&\varphi&\psi&\varphi\lor\psi&\varphi\land\psi\\ \hline T&T&T&T&T \end{array}$$

Thus, it’s true of $$\varphi\lor\psi$$ and $$\varphi\land\psi$$ as well, and by induction it’s true for every $$\varphi\in\Phi$$.

Try to find a similar idea for the second problem: some property that $$\leftrightarrow$$ and $$\lnot$$ preserve that $$\land,\lor$$, or $$\to$$ does not.

• Thank you very much for your answer. Commented Sep 4, 2012 at 22:59
• This rather interesting related question asks for a calculation of the number of expressively-adequate truth functions. There were no good answers. I still wonder if there is any reasonable algorithm for determining whether a given set of operators is expressively adequate.
– MJD
Commented Sep 4, 2012 at 23:20

Hint: For the first problem, prove, in principle by induction, that any propositional function $f(A)$ built from $\land$ and $\lor$ will always have the value $1$ if $A$ has value $1$.

We need a similar "invariance" property for the functions built from the set $\{\leftrightarrow, \neg\}$. I would suggest thinking of the truth table for a function $f(A,B)$ built up from these connectives. This truth table has $4$ entries, corresponding to the $4$ possible combinations of truth values of $A$ and $B$. Prove by induction that for any $f$ built up from our two connectives, an even number ($0$, $2$, or $4$) of the entries gets assigned the value True. For the connective $\leftrightarrow$, there is a bit of detail to showing that if $g(A,B)$ is true for $2$ entries, and $h(A,B)$ is true for $2$ entries, then $f(A,B)\leftrightarrow h(A,B)$ is true for an even number of entries.

• Thank you very much for your answer. Commented Sep 4, 2012 at 22:58