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.

Thanks in advance.

Solution 1:

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.

Solution 2:

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

Solution 3:

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.