13
$\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.

$\endgroup$

4 Answers 4

8
$\begingroup$

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

$\endgroup$
1
  • $\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
    Commented Sep 4, 2012 at 22:55
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you very much for your answer. $\endgroup$
    – Pampero
    Commented Sep 4, 2012 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
    Commented Sep 4, 2012 at 23:20
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer. $\endgroup$
    – Pampero
    Commented Sep 4, 2012 at 22:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .