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.


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

  • $\begingroup$ Thank you very much for your answer. $\endgroup$ – Pampero Sep 4 '12 at 22:59
  • 1
    $\begingroup$ 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. $\endgroup$ – MJD Sep 4 '12 at 23:20

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

  • $\begingroup$ 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. $\endgroup$ – Pampero Sep 4 '12 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 with arity larger than 1 is called odd if it 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. 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

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


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.

  • $\begingroup$ Thank you very much for your answer. $\endgroup$ – Pampero Sep 4 '12 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.