11
$\begingroup$

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.

4 Answers 4

4

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.

  • 1
    [This rather interesting related question](http://math.stackexchange.com/questions/126043/finding-expressively-adequate-truth-functions) 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.2012-09-04
6

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

  • 0
    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.2012-09-04
6

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.

5

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.

  • 0
    Thank you very much for your answer.2012-09-04